Codeforces Round #274 (Div. 2)

A. Expression

CF万年不变的水题，a,b,c的顺序不能变，还是自己作死读，错题当成是顺序可变，然后被Hack了。。(￣_￣|||)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<set>
 7 #include<map>
 8 #include<stack>
 9 #include<vector>
10 #include<queue>
11 #include<string>
12 #include<sstream>
13 #define eps 0.000001
14 #define ALL(x) x.begin(),x.end()
15 #define INS(x) inserter(x,x.begin())
16 using namespace std;
17 typedef long long LL;
18 int i,j,k,n,m,x,y,T,ans,big,cas;
19 bool flag;
20 int main()
21 {
22     int a,b,c,ans=0,s[100];
23     scanf("%d%d%d",&a,&b,&c);
24     s[0]=(a+b)*c;
25     s[1]=a*(b+c);
26     //s[2]=(a+c)*b;
27     s[2]=a*b+c;
28     s[3]=a+b*c;
29     //s[5]=a*c+b;
30     s[4]=a*b*c;
31     s[5]=a+b+c;
32     for (i=0;i<=5;i++) ans=max(ans,s[i]);
33     cout<<ans<<endl;
34     return 0;
35 }

View Code

B. Towers

这道题是给出n个高为ai（ai个正方体堆成）的塔，要求使通过k次移动正方体（每次移动一个），使得这些塔稳定，即最高的高度减去最小的高度，让这个数最小

显然就是每次把最高的塔拿出一个正方体然后放到最低的上边可以了。。。

一开始我还在想怎么样才能很快地得到最小值和最大值，最后发现，没有必要用什么高级的数据结构，每次操作完后在快排一下就可以了，时间复杂度完全可以胜任

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<set>
 7 #include<map>
 8 #include<stack>
 9 #include<vector>
10 #include<queue>
11 #include<string>
12 #include<sstream>
13 #define eps 0.000001
14 #define ALL(x) x.begin(),x.end()
15 #define INS(x) inserter(x,x.begin())
16 using namespace std;
17 typedef long long LL;
18 struct node
19 {
20     int w,i;
21     bool operator <(const node &b) const
22     {
23         return w<b.w;
24     }
25 };
26 int i,j,k,n,m,x,y,T,big,cas,ans[1005][2],step;
27 node a[1005];
28 bool flag;
29 int main()
30 {
31     scanf("%d%d",&n,&k);
32     for (i=0;i<n;i++) 
33     {
34         cin>>a[i].w;
35         a[i].i=i+1;
36     }
37     sort(a,a+n);
38     while (1)
39     {
40         if (a[n-1].w-a[0].w<=1) break;
41         a[n-1].w--;
42         a[0].w++;
43         
44         step++;
45         ans[step][0]=a[n-1].i;
46         ans[step][1]=a[0].i;
47         sort(a,a+n);
48         if (step==k) break;
49     }
50     cout<<a[n-1].w-a[0].w<<" "<<step<<endl;
51     for (i=1;i<=step;i++) cout<<ans[i][0]<<" "<<ans[i][1]<<endl; 
52         
53     return 0;
54 }

View Code

C. Exams

Valera要参加n场考试，每场考试i，考试规定的时间是ai，但Valera通过老师可以提前到bi（bi<ai），即他既可以ai时参加，也可以bi时参加，Valera想仍按照ai从小到大的顺序参加考试，问最后一场考试时间最早是多少

显然先对ai为第一关键字，bi为第二关键字从小到大排序，然后从小到大扫描，

如果第i场考试，b[i-1]>b[i]那么显然，第i-1场考试不可以提前参加，如果a[i-1]<=b[i]，那么可以前i-1场均不提前参加，而第i场提前

= =因为漏考虑状态，所以被Hack了。。。pretest也够水的

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<set>
 7 #include<map>
 8 #include<stack>
 9 #include<vector>
10 #include<queue>
11 #include<string>
12 #include<sstream>
13 #define eps 0.000001
14 #define ALL(x) x.begin(),x.end()
15 #define INS(x) inserter(x,x.begin())
16 using namespace std;
17 typedef long long LL;
18 struct node
19 {
20     LL x,y;
21 }a[5005];
22 int i,j,k,n,m,x,y,T,ans,big,cas;
23 bool flag;
24 bool cmp(node a,node b)
25 {
26     if (a.x==b.x)return a.y<b.y;
27     return a.x<b.x;
28 }
29 int main()
30 {
31     scanf("%d",&n);
32     for (i=0;i<n;i++)
33     {
34         cin>>a[i].x>>a[i].y;
35     }
36     sort(a,a+n,cmp);
37     flag=true;
38     for (i=1;i<n;i++)
39     {
40         if (a[i-1].y>a[i].y)
41         {
42             flag=false;
43         }
44         if (a[i-1].x<=a[i].y)
45         {
46             flag=true;
47         }
48     }
49     if (flag) cout<<a[n-1].y<<endl;
50     else cout<<a[n-1].x<<endl;
51     return 0;
52 }

View Code

D. Long Jumps

一个长为l的尺子，上边有n个刻度，分别为a1,a2,,,an，其中a1=0，an=l，现要测x和y(x<y)，求需要加那几个刻度？

显然要加的刻度不会超过两个，先直接判断x是否已经可测，y是否已经可测，

如果都不可测，我们判断是否加一个刻度就可以完成任务，一共三种条件可以满足，详见代码

总值这次D题也很水

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<set>
 7 #include<map>
 8 #include<stack>
 9 #include<vector>
10 #include<queue>
11 #include<string>
12 #include<sstream>
13 #define eps 0.000001
14 #define ALL(x) x.begin(),x.end()
15 #define INS(x) inserter(x,x.begin())
16 using namespace std;
17 typedef long long LL;
18 int i,j,k,n,m,x,y,T,ans,big,cas,fx,fy,fz,u,v,num,l,a[100005],num1,num2,f1,f2,r,s;
19 bool flag;
20 set <int > p;
21 int main()
22 {
23     cin>>n>>l>>x>>y;
24     for (i=1;i<=n;i++) 
25     {
26         cin>>a[i];
27         p.insert(a[i]);
28     }
29     fx=0;fy=0;
30     for (set<int>::iterator t=p.begin();t!=p.end();t++)
31     {
32         u=*t;
33         v=u+x;
34         if (p.count(v)!=0) fx=1;
35         v=u+y;
36         if (p.count(v)!=0) fy=1;
37         v=u+x+y;
38         if (p.count(v)!=0) {fz=1;num=u+x;}
39         r=u+y;
40         s=u+y-x;
41         if (r>0&&s>0&&p.count(s)!=0&&u+y<=l)
42         {
43             f1=1;num1=u+y;
44         }
45         
46         r=u-x;
47         s=u-x+y;
48         if (r>0&&s>0&&p.count(s)!=0&&u-x>0)
49         {
50             f2=1;num2=u-x;
51         }
52         
53     }
54     if (fx&&fy) 
55     {
56         printf("0
");
57         return 0;
58     }
59     
60     if (!fx&&fy)
61     {
62         printf("1
%d
",x);
63         return 0;
64     }
65     if (fx&&!fy)
66     {
67         printf("1
%d
",y);
68         return 0;
69     }
70     if (!fx&&!fy)
71     {
72         if (fz)
73         {
74             printf("1
%d
",num);
75             return 0;
76         }
77         else
78         if (f1)
79         {
80             printf("1
%d
",num1);
81             return 0;
82         }else
83         if (f2)
84         {
85             printf("1
%d
",num2);
86             return 0;
87         }else
88         {
89             printf("2
%d %d
",x,y);
90             return 0;
91         }
92     }
93 
94     return 0;
95 }

View Code

E. Riding in a Lift

乘电梯，开始在a层，b层是不可以去的，假设我们在x层，要去y层，y必须满足|x - y| < |x - b|，现在因为无聊要乘k次电梯，问有多少种旅行方式，结果mod1000000007

很简单的dp，设dp[i][j]为第i次乘电梯，停在j层，如果a<b那么，dp[i][j]=dp[i-1][1]+dp[i-1][2]+...+dp[i-1][(b-j-1)/2+j]（由其他层转移而来）-dp[i-1][j]（不能自己转移到自己），因为要求和，所以可以用sum数组扫描一下，即sum[j]表示dp[i-1][1]至dp[i-1][j]的和。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<set>
 7 #include<map>
 8 #include<stack>
 9 #include<vector>
10 #include<queue>
11 #include<string>
12 #include<sstream>
13 #define eps 0.000001
14 #define MOD 1000000007
15 #define ALL(x) x.begin(),x.end()
16 #define INS(x) inserter(x,x.begin())
17 using namespace std;
18 typedef long long LL;
19 int i,j,k,n,m,x,y,T,ans,big,cas,a,b;
20 LL c[5005][5005],sum[5005];
21 bool flag;
22 int main()
23 {
24     scanf("%d%d%d%d",&n,&a,&b,&k);
25     if (a<b)
26     {
27         c[0][a]=1;
28         for (j=1;j<b;j++) sum[j]=sum[j-1]+c[0][j];
29         for (i=1;i<=k;i++)
30         {
31             for (j=1;j<b;j++)
32             {
33                 c[i][j]=(sum[(b-j-1)/2+j]-c[i-1][j]+MOD)%MOD;
34             }
35             sum[0]=0;
36             for (j=1;j<b;j++)
37                 sum[j]=(sum[j-1]+c[i][j])%MOD;
38         }
39         cout<<sum[b-1]<<endl;
40     }else
41     {
42         c[0][a]=1;
43         for (j=n;j>=b+1;j--) sum[j]=sum[j+1]+c[0][j];
44         for (i=1;i<=k;i++)
45         {
46             for (j=b+1;j<=n;j++)
47             {
48                 c[i][j]=(sum[j-(j-b-1)/2]-c[i-1][j]+MOD)%MOD;
49             }
50             sum[0]=0;
51             for (j=n;j>=b+1;j--)
52                 sum[j]=(sum[j+1]+c[i][j])%MOD;
53         }
54         cout<<sum[b+1]<<endl;
55     }
56     return 0;
57 }

View Code

总之这次这次比赛，题目比较水，本来是有AK的希望的Σ(っ °Д °;)っ，不多说什么了