ACM团队周赛题解（1）

这次周赛题目拉了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 }

暂时只补了这么多题目。太难了暂时还补不了，望谅解。