Codeforces 916 div3 A-F

A

题意分析：
看思考每个题的时间是否大于即是办理该题须要的时间，假如是，则能办理该题，否则不能，直接摆列计数即可
C++代码：

2. #include<iostream>
3. using namespace std;
4. int main(){
5.         int t,n;
6.         cin>>t;
7.         while(t--){
8.                 cin>>n;
9.                 string s;
10.                 cin>>s;
11.                 int cnt[26]={0};
12.                 for(int i=0;i<s.size();i++){
13.                         cnt[s[i]-'A']++;//思考A题的时间加一
14.                 }
15.                 int res=0;
16.                 for(int i=0;i<26;i++){
17.                         if(cnt[i]>=i+1)res++;//思考时间大于等于需要的时间
18.                 }
19.                 cout<<res<<endl;
20.         }
21.         return 0;
22. }

复制代码

B

题意分析：
一开始先让数组按照n~1的序次分列，然后将前k+1个数从小到大排序即可
C++代码：

2. #include<iostream>
3. #include<algorithm>
4. using namespace std;
5. const int N=55;
6. int a[N];
7. bool cmp(int a,int b){
8.         return a>b;
9. }
10. int main(){
11.         int t;
12.         cin>>t;
13.         while(t--){
14.                 int n,k;
15.                 cin>>n>>k;
16.                 for(int i=1,j=n;i<=n;i++,j--)a[i]=j;//先将所有数倒序
17.                 sort(a+1,a+k+2);//把前k+1排成正序，就有了k次兴奋次数啦
18.                 for(int i=1;i<=n;i++)cout<<a[i]<<" ";
19.                 cout<<endl;
20.         }
21.         return 0;
22. }

复制代码

C

题意分析：
 要求完成不高出k个任务可得到的最大的履历值
由于b数组中的元素都大于1，以是我们肯定会取到k个任务
假设i表现我们完成的任务停止到第i个，即i反面的任务都没做
此时可得到的最大履历值为a[1]+a[2]+...+a+(k-i)*(b[1~i]中的最大值)
以是要先预处理惩罚a的前缀和和b的前缀最大值
然后我们只需摆列每个任务作为分界点即可
C++代码：

2. #include<iostream>
3. using namespace std;
4. const int N=200010;
5. int a[N],b[N],maxx[N];
6. int n,k;
7. void solve(){
8.         cin>>n>>k;
9.         for(int i=1;i<=n;i++)maxx[i]=0;
10.         for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];//a变成其前缀和
11.     //maxx[i]含义：b[1~i]中最大的一个数
12.         for(int i=1;i<=n;i++)cin>>b[i],maxx[i]=max(maxx[i-1],b[i]);
13.         int ans=0;
14.     //从前往后枚举解决的问题截止到第几个
15.         for(int i=1;i<=min(n,k);i++){
16.                 int sum=a[i]+(k-i)*maxx[i];//一共解决到第i个，剩下的k-i个直接用b[1~i]中最大的一个
17.                 ans=max(ans,sum);//更新ans
18.         }
19.         cout<<ans<<endl;
20. }
21. int main(){
22.     ios::sync_with_stdio(false);
23.     cin.tie(0);
24.     cout.tie(0);
25.         int t;
26.         cin>>t;
27.         while(t--){
28.                 solve();
29.         }
30.         return 0;
31. }

复制代码

D 

题意分析：
先找出每种活动人数最多的三天，即找出每一行中最大的三个数
显然，最优解肯定是从这些数中每一行取一个，条件是这三个数不能在同一列，以是在存储最大的三个数时还要存一下坐标
C++代码：

2. #include<iostream>
3. #include<cstring>
4. #define x first
5. #define y second
6. using namespace std;
7. const int N=100010;
8. typedef pair<int,int> PII;
9. int a[4][N];
10. int g[4][4];//存储每一行中最大的三个数
11. PII s[4][4];//存储每一行中最大的三个数的坐标
12. int n;
13. void solve(){
14.         cin>>n;
15.         memset(g,0,sizeof g);
16.         for(int i=1;i<=3;i++){
17.                 int &d1=g[i][1],&d2=g[i][2],&d3=g[i][3];//存储每一行的最大值、次大值、第三大值
18.                 PII &s1=s[i][1],&s2=s[i][2],&s3=s[i][3];//三个数的坐标
19.                 for(int j=1;j<=n;j++){
20.                         cin>>a[i][j];
21.                         if(a[i][j]>=d1){
22.                                 d3=d2,d2=d1,d1=a[i][j];
23.                                 s3=s2,s2=s1,s1={i,j};
24.                         }else if(a[i][j]>=d2){
25.                                 d3=d2,d2=a[i][j];
26.                                 s3=s2,s2={i,j};
27.                         }else if(a[i][j]>d3){
28.                                 d3=a[i][j];
29.                                 s3={i,j};
30.                         }
31.                 }
32.         }
33.         //每一行的最大的三个及其下标已经找出来了
34.         int ans=0;
35.         for(int i=1;i<=3;i++)//第一行
36.                 for(int j=1;j<=3;j++)//第二行
37.                         for(int k=1;k<=3;k++){//第三行
38.                                 PII s1=s[1][i],s2=s[2][j],s3=s[3][k];
39.                                 if(s1.y!=s2.y&&s1.y!=s3.y&&s2.y!=s3.y)//它们不在同一列
40.                                         ans=max(ans,g[1][i]+g[2][j]+g[3][k]);
41.                         }
42.         cout<<ans<<endl;
43. }
44. int main(){
45.         ios::sync_with_stdio(false);
46.         cin.tie(0);
47.         cout.tie(0);
48.         int t;
49.         cin>>t;
50.         while(t--){
51.                 solve();
52.         }
53.         return 0;
54. }

复制代码

E1 和 E2

题意分析：
假如一共有n种颜色，则利用n次肯定会竣事游戏，由于每次利用肯定会有至少一方该颜色的弹珠数变为0
Alice想赢(分数差值尽大概大)
Bob想赢(分数差值尽大概小)
对于颜色为i的弹珠
1、Alice举行利用，则对答案的贡献为a-1
2、Bob举行利用，则对答案的贡献为-(b-1)
二者的差值为(a-1)+(b-1)
以是：
Alice选i,答案差值增长了a-1+b-1
Bob选i,答案差值淘汰了a-1+b-1
以是每次不管谁利用时，挑a-1+b-1的最大值即可
C++代码：

2. #include<iostream>
3. #include<queue>
4. using namespace std;
5. typedef pair<int,int> PII;
6. typedef long long LL;
7. const int N=200010;
8. int a[N],b[N];
9. int n;
10. void solve(){
11.         cin>>n;
12.         for(int i=1;i<=n;i++)cin>>a[i];
13.         for(int i=1;i<=n;i++)cin>>b[i];
14.         priority_queue<PII> q;//大根堆
15.         for(int i=1;i<=n;i++)q.push({(a[i]-1)+(b[i]-1),i});
16.         LL ans=0;
17.         for(int i=1;i<=n;i++){
18.                 PII t=q.top();
19.                 q.pop();
20.                 int id=t.second;
21.                 if(i&1)ans+=a[id]-1;//Alice操作，答案加上a[id]-1
22.                 else ans-=b[id]-1;//Bob操作，答案加上b[id]-1
23.         }
24.         cout<<ans<<endl;
25. }
26. int main(){
27.         ios::sync_with_stdio(false);
28.         cin.tie(0);
29.         cout.tie(0);
30.         int t;
31.         cin>>t;
32.         while(t--){
33.                 solve();
34.         }
35.         return 0;
36. }

复制代码

F 

题意分析：
对于某一棵子树，只要两个点不在一根链上，就可以组队
假设当前子树的根节点为u
maxn记载最大子树中的节点数量
sum记载全部子树的节点数量和
match记载最大子树中的最大匹配数（两人一匹配）
有两种情况：
1、maxn-match*2<=sum-maxn，则最大匹配数为sum/2
2、maxn-match*2>sum-maxn，则最大匹配数为match+sum-maxn
以是直接dfs搜以每个节点为根的子树的情况即可
C++代码：

2. #include<iostream>
3. #include<vector>
4. using namespace std;
5. typedef long long LL;
6. const int N=200010;
7. int h[N],e[N],ne[N],idx;
8. int size1[N],dp[N];//子树大小，最大子树能组成的队伍数
9. int n;
10. void add(int a,int b){
11.         e[idx]=b,ne[idx]=h[a],h[a]=idx++;
12. }
13. void dfs(int u){
14.         size1[u]=1;//以u为根的子树中的节点数一开始只有自己
15.         dp[u]=0;//最开始能配对的数量为0
16.         int maxn=0,match=0,sum=0,cnt=0;
17.         //sum表示所有子树节点之和,maxn表示最大子树中节点数量,match表示最大子树中已经匹配的队伍数
18.         //cnt用于记录节点u有几个子节点
19.         for(int i=h[u];i!=-1;i=ne[i]){
20.                 int j=e[i];
21.                 cnt++;
22.                 dfs(j);//这里不用判断j是否被搜过是因为这是一个有向图无环树，所以不可能往回搜
23.                 size1[u]+=size1[j];
24.                 dp[u]=max(dp[u],dp[j]);
25.                 if(maxn<size1[j]){
26.                         maxn=size1[j];
27.                         match=dp[j];
28.                 }
29.                 sum+=size1[j];
30.         }
31.         if(cnt==1)return;//只有一棵子树
32.         if(sum-maxn>=maxn-match*2)dp[u]=sum/2;
33.         else dp[u]=sum-maxn+match;
34. }
35. void solve(){
36.     cin>>n;
37.     for(int i=1;i<=n;i++)h[i]=-1;//初始化h数组
38.     idx=0;
39.     for(int i=2;i<=n;i++){
40.             int x;
41.             cin>>x;
42.             add(x,i);
43.         }
44.     dfs(1);
45.     cout<<dp[1]<<endl;
46. }
47. int main(){
48.     int T;
49.     cin>>T;
50.     while(T--){
51.         solve();
52.     }
53.     return 0;
54. }

复制代码