這次周賽題目拉了CF315和CF349兩套題。
因為我代碼模闆較長，便隻放出關鍵代碼部分
#define ll long long
#define MMT(s,a) memset(s, a, sizeof s)
#define GO(i,a,b) for(int i = (a); i < (b); ++i)
#define GOE(i,a,b) for(int i = (a); i <= (b); ++i)
#define OG(i,a,b) for(int i = (a); i > (b); --i)
#define OGE(i,a,b) for(int i = (a); i >= (b); --i)
這是代碼中的幾個宏定義，需要拿代碼修改這個幾個就行了，若是用到代碼其他定義部分，會在代碼中額外添加。
這裡也隻是部分題解。
A - Cinema Line （CF-349A）
題意很簡單，就是說你是售票員，門票價格25元，有n個人來買票，錢隻有25，50，100三種，最開始你沒有錢，問你是否可以完成售票過程，即每個人都有足夠的零錢找他，按順序購票。
題目思路模拟即可。
1 int main(){
2 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
3 int n,a,flag = 1,tot1 = 0,tot2 = 0,tot3 = 0;
4 cin>>n;
5 GO(i,0,n){
6 cin>>a;
7 if(a == 25){
8 tot1++;
9 }
10 else if(a == 50){
11 if(tot1 > 0){
12 tot1--;
13 tot2++;
14 }
15 else
16 flag = 0;
17 }
18 else if(a == 100){
19 if(tot2 > 0 && tot1 > 0){
20 tot2--,tot1--;
21 tot3++;
22 }
23 else if(tot1 > 2){
24 tot1-=3;
25 tot3++;
26 }
27 else
28 flag = 0;
29 }
30 }
31 if(flag)
32 cout << "YES" << endl;
33 else
34 cout << "NO" << endl;
35 return 0;
36 } B - Color the Fence （CF-349B）
題目意思就是最開始有n，然後選取第i個數就需要花費a[i]，問最大能夠成的數。
題目思路：首先需要保證位數最大，是以先找到最小值min，n/min即為最大位數，然後對于每一位，從9-1往回找輸出。值得注意的是，可能你選取某個數會使得位數減少，是以選取數還得判斷是否會影響位數。雙重循環貪心。
1 int n,a[10] = {0};
2 int flag = 0,ii;
3
4 int main(){
5 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
6 cin>>n;
7 int minn = INT_MAX;
8 GOE(i,1,9){
9 cin>>a[i];
10 if(a[i] < minn)
11 minn = a[i];
12 }
13 if(minn > n){
14 cout << -1 << endl;
15 return 0;
16 }
17 int cnt = n / minn;
18 OGE(i,cnt,1){
19 OGE(j,9,1){
20 if(n >= a[j] && (n-a[j]) / minn >= i-1){
21 cout << j;
22 n -= a[j];
23 break;
24 }
25 }
26 }
27 cout << endl;
28 return 0;
29 } C - Mafia（CF-349C）
題目意思就是n個人進行Mafia的遊戲，遊戲規則就是選取一個人當裁判（類似狼人殺），其他n-1個人進行遊戲，如果某人某局為裁判，則不計入他的遊戲對局數。問要保證每個人i都玩了a[i]局遊戲。
題目思路：首先要保證最大值max = max(a[i])玩完，是以遊戲至少要玩max輪，在這max輪對局中，當某個人玩成了他的a[i]局，那麼剩下的max-a[i]局他就可以當裁判為其他人服務。
是以令sum = Σ(max - a[i])。
當sum >= max時，說明有足夠的輪數可以讓非最大值的人當裁判去完成最大值的max輪，這種情況隻需要玩max局即可。
當sum < max時，則需要額外的輪數讓其他人為最大值的人當裁判，而每一輪有n-1個人可以當裁判。這種情況就玩（max - sum）/（n-1）+max即可。
同理這道題也可以二分，因為每局都有n-1個人可以當裁判為剩下的一個人服務。那麼則從max —— Σ(a[i])二分選取cnt*（n-1） >= sum即可。
1 int a[100005];
2
3 int main(){
4 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
5 int n,maxx = INT_MIN;
6 ll sum = 0;
7 cin>>n;
8 GO(i,0,n){
9 cin>>a[i];
10 maxx = max(a[i],maxx);
11 }
12 GO(i,0,n)
13 sum += maxx - a[i];
14 if(sum >= maxx)
15 cout << maxx << endl;
16 else{
17 int cnt = 0;
18 while(sum < maxx){
19 cnt++;
20 sum += n-1;
21 }
22 cout << maxx+cnt << endl;
23 }
24
25 return 0;
26 } D - Apple Tree（CF-349D）
題意就是有一顆蘋果樹，根節點為1，然後保證非葉子節點的值都是0（就是樹枝上不會有蘋果，很好了解），葉子節點的值是a[i]，然後現在要使這顆樹變得平衡，平衡的定義為，每個非葉子節點的所有子節點值相同（就是說某個樹杈的所有樹枝包含的蘋果相同）。
題目思路：對于每一個結點u，要知道它的總分支數r[u]及現在所擁有的權值和val[u]，因為不同子樹總分支數不一定相同，故結點u每次減少的值需要是其所有子樹分支的最小公倍數，而且對于u的子樹也需要保證平衡，故u點每次需減去的值 = lcm * 兒子個數，值得注意的是lcm可能會爆long long，這種情況我們可以認為這個樹平衡當且僅當所有的蘋果都被拿走，即全部去掉。
那麼對于任意一個節點，先計算這個節點可拿走的蘋果數，再計算蘋果數目的上界，貪心選取最大重量更新節點情況。
代碼還有額外的宏定義
#define PB push_back
const ll INFF = 0x3f3f3f3f3f3f3f3f;
template<typename T>
inline T gcd(T a, T b){ return b==0 ? a : gcd(b,a%b); }
template<typename T>
inline T lcm(T a, T b){ if(a*b > INFF) return 0; return a / gcd(a,b) * b; }
1 const int maxn = 100005<<1;
2
3 ll v[maxn],dp[maxn],dis[maxn];
4 ll sum = 0;
5 vector<int> Edge[maxn];
6 bool flag;
7
8 void Add(int l,int r){
9 Edge[l].PB(r);
10 Edge[r].PB(l);
11 }
12
13 void dfs(int st,int fa){
14 dp[st] = v[st],dis[st] = 1;
15 int cnt = 0;
16 for(auto it : Edge[st]){
17 if(it == fa)
18 continue;
19 cnt++;
20 dfs(it,st);
21 int temp = lcm(dis[st],dis[it]);
22 if(temp)
23 dis[st] = temp;
24 else
25 dis[st] = 1, flag = 0;
26 dp[st] += dp[it];
27 }
28 for(auto it : Edge[st]){
29 if(it == fa)
30 continue;
31 dp[st] = min(dp[st],dp[it] - dp[it]%dis[st]);
32 }
33 (cnt == 0) && cnt++;
34 dp[st] *= cnt, dis[st] *= cnt;
35 }
36
37 int main(){
38 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
39 int n,l,r;
40 cin>>n;
41 GOE(i,1,n){
42 cin>>v[i];
43 sum += v[i];
44 }
45 GO(i,1,n){
46 cin>>l>>r;
47 Add(l,r);
48 }
49 flag = 1;
50 dfs(1,0);
51 if(!flag)
52 cout << sum << endl;
53 else
54 cout << sum - dp[1] << endl;
55
56 return 0;
57 } F - Sereja and Bottles（CF-315A）
題意就是n個瓶子，a[i]瓶可以打開其他的第b[i]瓶，問最後剩下多少瓶子沒有打開。
題目思路：标記模拟即可
1 int main(){
2 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
3 int n,cnt(0);
4 int a[105],b[105],vis[105] = {0};
5 cin>>n;
6 GOE(i,1,n)
7 cin>>a[i]>>b[i];
8 GOE(i,1,n){
9 GOE(j,1,n){
10 if(i != j && a[j] == b[i])
11 vis[j] = 1;
12 }
13 }
14 GOE(i,1,n){
15 if(vis[i])
16 cnt++;
17 }
18 cout << n - cnt << endl;
19
20 return 0;
21 } G - Sereja and Array（CF-315B）
題意就是三種操作.
1 就是把第x個元素變成v；
2 就是把所有元素加上v；
3 即使輸出第x個元素的值；
題目思路：1，3操作容易實作，主要是2操作，總不能周遊把每個值加上v，因為題目說了是所有值加上v，是以隻需要用一個數記錄v的和，輸出是加上這個就行，同時需要因為有1操作，是以還需要開額外一個數組記錄當某個值改變時，存取目前的v總和，輸出再減去這個值即可。
1 int n,m,temp = 0;
2 int a[100005],dis[100005];
3 int x,y,z;
4
5 int main(){
6 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
7 cin>>n>>m;
8 GOE(i,1,n)
9 cin>>a[i];
10 GO(i,0,m){
11 cin>>x;
12 if(x == 1){
13 cin>>y>>z;
14 dis[y] = temp;
15 a[y] = z;
16 }
17 else if(x == 2){
18 cin>>y;
19 temp += y;
20 }
21 else if(x == 3){
22 cin>>y;
23 cout << a[y] + temp - dis[y] << endl;
24 }
25 }
26
27 return 0;
28 } H - Sereja and Contest（CF-315C）
題意就是有n個數字，當f(a[i])小于k時删除這個數，輸出其位置，再從新計算。
f(i) = Σ(a[j]*(j-1) - (n-i)*a[i]);
題目思路：第一輪删除了a[i]，那麼下一輪删除的數的位置，一定時大于i的。
這個公式可以變成(j-1)* Σ(a[j]) - (j-1)*(n-i)*a[i]，可以發現前半部分就是一個字首和，是以過程中維護n的大小動态修改。
1 int n,k;
2 ll a[200005];
3
4 int main(){
5 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
6 cin>>n>>k;
7 GOE(i,1,n)
8 cin>>a[i];
9 ll now(0),tot(0),temp(n);
10 GOE(i,2,n){
11 now += a[i-1]*tot;
12 if(now - (temp-i+(n-temp))*a[i]*(i-1-(n-temp)) < k){
13 temp--;
14 now -= a[i]*tot;
15 cout << i << endl;
16 }
17 else
18 tot++;
19 }
20 return 0;
21 } I - Sereja and Periods（CF-315D）
題目意思就是兩個串分别是[a,b],[c,d]，運算規則就是b個a相連接配接，例如[abc,2] = abcabc;
然後問你[a,b]這個串中出現了幾次[c,d]。
題目思路：KMP找循環節。用cnt[i]記錄目前開始以c串的i位置找，經過一個a串後，會經過幾個c串，nxt記錄目前開始以c串的i位置開始找，經過一個a串後，比對的位置會到什麼地方。每次對于a串都是從0~lena找，因為走完一個a串後，下一條又從0開始了。
1e7，單層循環，沒問題。
1 int b,d,cnt[105] = {0},nxt[105];
2 string a,c;
3
4 int main(){
5 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
6 cin>>b>>d>>a>>c;
7 int lenc = c.size(),lena = a.size();
8 GO(i,0,lenc){
9 int temp = i;
10 GO(j,0,lena){
11 if(a[j] == c[temp]){
12 temp++;
13 if(temp == lenc)
14 cnt[i]++, temp = 0;
15 }
16 }
17 nxt[i] = temp;
18 }
19 int j = 0;
20 ll sum = 0;
21 GOE(i,1,b){
22 sum += cnt[j];
23 j = nxt[j];
24 }
25 cout << sum/d << endl;
26
27 return 0;
28 } 暫時隻補了這麼多題目。太難了暫時還補不了，望諒解。