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