Codeforces Round #452 (Div. 2)

已过ABC题，待更。

A题题意：给N个组，每个组有1个或两个人，问能组成多少个三人组。

A题题解：贪心的思想，统计出两个人和一个人的组数X和Y，肯定先选一个两人组和一个一个组组合。那么三人组个数就是X+(X-Y)/3。

AC代码：

 1 #include<iostream>
 2 using namespace std;
 3 int n,sum1,sum2;
 4 int main()
 5 {
 6     cin>>n;
 7     for(int i=1;i<=n;i++)
 8     {
 9         int x;
10         cin>>x;
11         if(x==1)sum1++;
12         else sum2++;
13     }
14     if(sum2>sum1)cout<<sum1<<endl;
15     else cout<<sum2+(sum1-sum2)/3<<endl;
16 }

B题题意：给定最多24个月的天数，问是否符合实际。

B题题解：因为不一定从第一个月开始，所以最多24个月就可以从36个循环里找是否存在一个子循环符合要求。

因为三年里最多一个29天，所以需要更改三次二月份的天数。

AC代码：

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 int a[37],b[25],n;
 5 int pe()
 6 {
 7     int ok = 0;
 8     for(int i=1;i<=36-n;i++)
 9     {
10         if(b[1]==a[i])
11         {
12             int k = 1;
13             while(k<n)
14             {
15                 if(a[i+k]!=b[k+1])break;
16                 k++;
17             }
18             if(k==n)ok=1;
19         }
20     }
21     return ok;
22 }
23 int main()
24 {
25     for(int i=1;i<=7;i++)
26     {
27         if(i&1)a[i]=31;
28         else a[i]=30;
29     }
30     for(int i=8;i<=12;i++)
31     {
32         if(i&1)a[i]=30;
33         else a[i]=31;
34     }
35     for(int i=13;i<=36;i++)a[i]=a[i-12];
36     cin>>n;
37     for(int i=1;i<=n;i++)
38     {
39         cin>>b[i];
40     }
41     int ok = 0;
42     a[2]=a[14]=a[26]=28;
43     ok = max(ok,pe());
44     a[2]=29;
45     ok = max(ok,pe());
46     a[2]=28;
47     a[14]=29;
48     ok = max(ok,pe());
49     a[14]=28;
50     a[26]=29;
51     ok = max(ok,pe());
52     if(ok)cout<<"Yes"<<endl;
53     else cout<<"No"<<endl;
54 }

C题题意：给从1-N的N个数，分成两组使得两组和的差最小，输出其中一组的个数和组里的每个数。

C题题解：一开始跑了一下，发现差是11001100的顺序，然后分4种情况wa了，发现N大了的时候组里的每个数规律是不定的。然后就贪心的思想了，从N往下找，找到就减去，记录找到的每个数即可。

AC代码：

 1 #include <iostream>
 2 using namespace std;
 3 const int maxn = 60007;
 4 int n,vis[maxn],now;
 5 int main(int argc, char const *argv[])
 6 {
 7     cin>>n;
 8     now = 0;
 9     int sum;
10     if(n&1)sum = (n+1)/2*n;
11     else sum = n/2*(n+1);
12     sum/=2;
13     for(int i=n;i>=1;i--)
14     {
15         if(sum>=i)
16         {
17             sum-=i;
18             vis[now++]=i;
19         }
20     }
21     if(n%4==0||n%4==3)cout<<sum<<endl;
22     else cout<<sum+1<<endl;
23     cout<<now<<" ";
24     for(int i=0;i<now;i++)
25     {
26         cout<<vis[i]<<" ";
27     }
28     cout<<endl;
29     return 0;
30 }