拿下 ABD, 顺利晋级， 预赛的时候C没有仔细想，推荐C题，一个非常不错的构造题目！
A Magic Trick 简单的题目来取得集合的交并
1: #include <iostream>
2: #include <algorithm>
3: #include <set>
4: #include <vector>
5: using namespace std;
6: int main()
7: { 8: freopen("A-small-attempt0.in","r",stdin); 9: freopen("A-small-attempt0.out","w",stdout);10: int T;
11: cin>>T;
12: for(int t=1; t<=T; t++)
13: {14: int x,y;
15: cin>>x;
16: int m[4][4];
17: set<int> X;
18: for(int i=0; i<4; i++)
19: {20: for(int j=0; j<4; j++)
21: {22: cin>>m[i][j];
23: if(i+1 == x) X.insert(m[i][j]);
24: }
25: }
26: cin>>y;
27: set<int> Y;
28: for(int i=0; i<4; i++)
29: {30: for(int j=0; j<4; j++)
31: {32: cin>>m[i][j];
33: if(i+1 == y) Y.insert(m[i][j]);
34: }
35: }
36: vector<int> ret(X.size() + Y.size());
37: auto itr = set_intersection(X.begin(),X.end(), Y.begin(),Y.end(), ret.begin());
38: ret.resize(itr - ret.begin());
39: cout<<"Case #"<<t<<": ";
40: if(ret.size() == 1)
41: cout<<ret[0]<<endl;
42: else if(ret.size() > 1)
43: {44: cout<<"Bad magician!"<<endl;
45: } else cout<<"Volunteer cheated!"<<endl;
46: }
47: }
B Cookie Clicker Alpha 核心观察可以通过简单的推导获得一个upper bound，然后枚举到这个upper bound就OK。
1: #include <iostream>
2: #include <cmath>
3: using namespace std;
4:
5: int main()
6: { 7: freopen("B-large.in","r",stdin); 8: freopen("B-large.out","w",stdout);9: int T;
10: cin>>T;
11: for(int t = 1; t<= T; t++)
12: {13: double C,F,X;
14: cin>>C>>F>>X;
15:
16: double ret = X/2.0;
17: int up = max( (F*X - 2*C)/(F*C), 0.0);
18: //cout<<up<<endl;
19: double Nec = 0.0f;
20: for(int k = 0; k< up; k++)
21: {22: Nec += C/(2+k*F);
23: ret = min(ret, Nec + X/(2+(k+1)*F));
24: }
25: printf("Case #%d: %.7f\n", t, ret);26: //cout<<"Case #"<<t<<": "<<ret<<endl;
27: }
28: }
C Minesweeper Master 这是一个构造的题目，非常非常的不错！核心观察在于扫雷的机制在边界的时候需要是2*n的这样一个结构才可能保证顺利完成边界情况。
1: #include <iostream>
2:
3: using namespace std;
4:
5: char Map[55][55];
6: int main()
7: { 8: freopen("C-large-practice.in","r",stdin); 9: freopen("C-large-practice.out","w",stdout);10: int T; cin>>T;
11:
12: for(int t= 1; t<=T; t++)
13: {14: bool possible = false;
15: int R,C,M;
16: cin>>R>>C>>M;
17: for(int i=0; i<R; i++)
18: {19: for(int j=0; j<C; j++)
20: {21: Map[i][j] = '*';
22: }
23: }
24: if(R == 1 || C == 1 || R*C == M+1)
25: {26: possible = true;
27: Map[0][0] = 'c';
28: int num = R*C - M-1;
29: for(int i=0; i<R; i++)
30: {31: for(int j=0; j<C; j++)
32: {33: if(i==0 && j==0) continue;
34: else if(num >0)
35: {36: Map[i][j] = '.';
37: num--;
38: }else Map[i][j] = '*';
39: }
40: }
41: }else
42: {43: for(int r = 2; r<=R; r++)
44: {45: for(int c = 2; c<=C; c++)
46: {47: int mineleft = M - (R*C - r*c);
48: if( mineleft <= (r-2)*(c-2) && mineleft >=0)
49: {50: possible = true;
51: for(int i=0; i<R; i++) for(int j=0; j<C; j++)Map[i][j] = '*';
52: Map[0][0]= 'c';
53: for(int i=0; i<2; i++) for(int j=0; j<c; j++)
54: {55: if(i ==0 && j==0) continue;
56: Map[i][j] = '.';
57: }
58: for(int i=2; i<r; i++) for(int j=0; j<2; j++) Map[i][j] = '.';
59: mineleft = (r-2)*(c-2) - mineleft;
60: for(int i= 2; i<r; i++) for(int j=2; j<c; j++)
61: {62: if(mineleft > 0)
63: {64: mineleft --;
65: Map[i][j] = '.';
66: } else Map[i][j] = '*';
67:
68: }
69: }
70:
71: }
72: }
73:
74: }
75: cout<<"Case #"<<t<<":"<<endl;
76: if(possible)
77: {78: for(int i=0; i<R; i++)
79: {80: for(int j=0; j<C; j++)
81: {82: cout<<Map[i][j];
83: }
84: cout<<endl;
85: }
86: }
87: else
88: {89: cout<<"Impossible"<<endl;
90: }
91: }
92: }
详细的分析参见：http://www.huangwenchao.com.cn/2014/04/gcj-2014-qual.html
D Deceitful War 类似于田忌赛马的问题，核心观察在于 每一个人的最优策略都是采用刚刚比你大的来进行比较。
1: #include <iostream>
2: #include <vector>
3: #include <algorithm>
4:
5: using namespace std;
6:
7: int main()
8: { 9: freopen("D-large.in","r",stdin); 10: freopen("D-large.out","w",stdout);11: int T; cin>>T;
12: for(int t=1; t<= T; t++)
13: {14: int N;
15: cin>>N;
16: vector<double> A(N);
17: vector<double> B(N);
18: for(int i=0; i<N; i++) cin>>A[i];
19: for(int i=0; i<N; i++) cin>>B[i];
20: sort(A.begin(), A.end());
21: sort(B.begin(), B.end());
22: int War = 0;
23: for(int i = A.size()-1, j= B.size()-1; i>=0 && j>= 0;)
24: {25: if(B[j]>A[i])
26: {27: War++;
28: i--;
29: j--;
30: } else if(B[j] <A[i])
31: {32: i--;
33: }
34: }
35: //cout<<N - War<<endl;
36: int NOWar = 0;
37: for(int i = B.size()-1, j= A.size()-1; i>=0 && j>= 0;)
38: {39: if(A[j]>B[i])
40: {41: NOWar++;
42: i--;
43: j--;
44: } else if(A[j] <B[i])
45: {46: i--;
47: }
48: }
49: //cout<<NOWar<<endl;
50: cout<<"Case #"<<t<<": "<<NOWar<<" "<<N-War<<endl;
51: }
52: return 0;
53: }