Codeforces Round #258 (Div. 2)

A. Game With Sticks http://codeforces.com/contest/451/problem/A

n横m竖 A先拿B后拿每次拿一横一竖，nm都100，o（n）暴力。

 1 #include<cstdio>
 2 int main(){
 3     int n,m;
 4     while(~scanf("%d%d",&n,&m)){
 5         bool flag=true;
 6         while(n>0&&m>0){
 7             n--;
 8             m--;
 9             flag=!flag;
10         }
11         if(flag) puts("Malvika");
12         else puts("Akshat");
13     }
14     return 0;
15 }

View Code

B. Sort the Array http://codeforces.com/contest/451/problem/B

10^5个数，都独立，只能将其中一段连续反序，问反序后是否能构成递增序列，o（nlogn）sort，和原串比较，找翻转的坐标，o（n）翻转，翻转后o（n）比较。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int M=100010;
 5 int a[M],b[M];
 6 int main(){
 7     int n;
 8     while(~scanf("%d",&n)){
 9         for(int i=0;i<n;i++){
10             scanf("%d",&a[i]);
11             b[i]=a[i];
12         }
13         sort(a,a+n);
14         int L=0,R=0;
15         for(int i=0;i<n;i++){
16             if(a[i]!=b[i]){
17                 L=i;
18                 break;
19             }
20         }
21         for(int i=n-1;i>=0;i--){
22             if(a[i]!=b[i]){
23                 R=i;
24                 break;
25             }
26         }
27         for(int i=L,j=R;i<j;i++,j--){
28             swap(b[i],b[j]);
29         }
30         bool flag=true;
31         for(int i=0;i<n;i++){
32             if(a[i]!=b[i]){
33                 flag=false;
34                 break;
35             }
36         }
37         if(flag){
38             puts("yes");
39             printf("%d %d
",L+1,R+1);
40         }
41         else{
42             puts("no");
43         }
44     }
45     return 0;
46 }

View Code

C. Predict Outcome of the Game http://codeforces.com/contest/451/problem/C

输入10^12用__int64，设xyz为三队赢的场数，x+-d1=y,y+-d2=z,枚举符号，共四种，对每一种判断剩下n-k场能否将xyz补齐。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 typedef __int64 LL;
 5 int t;
 6 LL n,k,d1,d2,tmp,x,y,z,big,cha;
 7 bool solve() {
 8     if(x<0||y<0||z<0) return false;
 9     big=0;
10     big=max(big,x);
11     big=max(big,y);
12     big=max(big,z);
13     cha=0;
14     cha+=big-x;
15     cha+=big-y;
16     cha+=big-z;
17     if(n-k>=cha&&(n-k-cha)%3==0){
18         return true;
19     }
20     return false;
21 }
22 int main() {
23     while(~scanf("%d",&t)) {
24         while(t--) {
25             scanf("%I64d%I64d%I64d%I64d",&n,&k,&d1,&d2);
26             tmp=k-2*d1-d2;
27             if(tmp>=0&&tmp%3==0) {
28                 x=tmp/3;
29                 y=x+d1;
30                 z=y+d2;
31                 if(solve()) {
32                     puts("yes");
33                     continue;
34                 }
35             }
36             tmp=k-2*d1+d2;
37             if(tmp>=0&&tmp%3==0) {
38                 x=tmp/3;
39                 y=x+d1;
40                 z=y-d2;
41                 if(solve()) {
42                     puts("yes");
43                     continue;
44                 }
45             }
46             tmp=k+2*d1-d2;
47             if(tmp>=0&&tmp%3==0) {
48                 x=tmp/3;
49                 y=x-d1;
50                 z=y+d2;
51                 if(solve()) {
52                     puts("yes");
53                     continue;
54                 }
55             }
56             tmp=k+2*d1+d2;
57             if(tmp>=0&&tmp%3==0) {
58                 x=tmp/3;
59                 y=x-d1;
60                 z=y-d2;
61                 if(solve()) {
62                     puts("yes");
63                     continue;
64                 }
65             }
66             puts("no");
67         }
68     }
69     return 0;
70 }

View Code