这次周赛题目拉了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 } 暂时只补了这么多题目。太难了暂时还补不了，望谅解。