Codeforces Round 916 (Div. 3)（A~E题解）

今天也是小小的vp了一下这场比赛，我对这场比赛的感觉就是比我之前做的都要简单，最简单的一次div3（个人感觉）

话不多说来看这次比赛

A. Problemsolving Log

题解：这题就是说，对于每个问题，其解决时间是按照26个英文字母顺序来规定的解题时间，A题1分钟做完，Z题26分钟做完，然后给你一个字符串说明每分钟都在做哪道题，只要做这道题的时间大于等于解题时间，就说明把这道题做出来了

然后我们就可以遍历一遍字符串统计每道题的做题时间，然后去和题目中解题时间比较，只要大于等于就说明解出来一道题

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n;
char s[505];
int vis[30];
signed main()
{
	cin>>t;
	while(t--)
	{
		memset(vis,0,sizeof(vis));
		cin>>n;
		cin>>s;
		for(int i=0;i<n;i++)
		{
			vis[s[i]-'A'+1]++;
		}
		int ans=0;
		for(int i=1;i<=26;i++)
		{
			if(vis[i]>=i)
			ans++;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

 B. Preparing for the Contest

题解：很水的一道构造题，真的巨水，他想让我们求出有n个数，有k次兴奋的序列，什么时候有兴奋呢？当a[ i+1 ]> a[ i ]的时候会产生一次兴奋，那么我们就可以说，保证前k个数不变，然后将后面所有数进行倒序排列就直接解决了

//明显的构造题 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
int a[55];
 
signed main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		for(int i=1;i<=n;i++)
		a[i]=i;
		int l=k+1,r=n;
		while(l<=r)
		{
			int t=a[l];
			a[l]=a[r];
			a[r]=t;
			l++,r--;
		}
		for(int i=1;i<=n;i++)
		printf("%lld ",a[i]);
		cout<<"\n";
	}
	return 0;
}

C. Quests 

 

题解：一开始刚看题我还以为是动态规划里面和那个五倍经验日很像的问题，等看完题我才发现，啥呀，就是一个简单的前缀和，然后暴力枚举每一种情况即可，唯一需要注意到的细节就是n和k的大小，因为k>n是一定可以将所有任务遍历一遍的

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,k;
int a[200005];
int b[200005];
int sum[200005];//前缀和数组，要统计做到第i个任务时，所能获得的总的经验
signed main()
{
	cin>>t;
	while(t--)
	{
		memset(sum,0,sizeof(sum));
		cin>>n>>k;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			sum[i]=sum[i-1]+a[i]; 
		}
		int maxn=0;//统计对于前i个任务，最大的重复做后面几次的最大经验值
		for(int i=1;i<=n;i++)
		{
			cin>>b[i];
		}
		int ans=0;//统计最大经验值 
		for(int i=1;i<=min(n,k);i++)
		{
			if(b[i]>maxn)
			maxn=b[i]; 
			int flag=sum[i]+(k-i)*maxn;
			ans=max(ans,flag);
		}
		cout<<ans<<"\n";
	}
	return 0;
}

 D. Three Activities

 题解：这题怎么说呢，说难也难，说简单也简单，反正我错了三次，现在想来还是当时太蠢了，竟然想要枚举出来，一直靠if去判断条件

这题的正解是将三个活动都用一个结构体存起来，结构体里面放的一个是人数，还有一个是天数，然后对结构体数组进行排序，找到人数最多的后面三天，然后搞一个三重循环，遍历每个活动人最多的三天就可以，如果三天各自没有挤在一天就可以更新记录人数最多的ans的值

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n;
struct node1
{
	int flag;//下标位置
	int ans;//人数 
}a[100005];
 
struct node2
{
	int flag;//下标位置
	int ans;//人数 
}b[100005];
 
struct node3
{
	int flag;//下标位置
	int ans;//人数 
}c[100005];
 
 
bool cmp1(node1 a,node1 b)
{
	return a.ans>b.ans;
}
 
bool cmp2(node2 a,node2 b)
{
	return a.ans>b.ans;
}
 
bool cmp3(node3 a,node3 b)
{
	return a.ans>b.ans;
}
 
signed main()
{
	cin>>t;
	while(t--)
	{
		
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].ans;
			a[i].flag=i;
		}
		for(int i=1;i<=n;i++)
		{
			cin>>b[i].ans;
			b[i].flag=i;
		}
		for(int i=1;i<=n;i++)
		{
			cin>>c[i].ans;
			c[i].flag=i;
		}
		
		sort(a+1,a+1+n,cmp1);
		sort(b+1,b+1+n,cmp2);
		sort(c+1,c+1+n,cmp3);
		
		int ans=0;
		for(int i=1;i<=3;i++)
		{
			for(int j=1;j<=3;j++)
			{
				for(int k=1;k<=3;k++)
				{
					if(a[i].flag!=b[j].flag&&a[i].flag!=c[k].flag&&b[j].flag!=c[k].flag)
					{
						ans=max(ans,a[i].ans+b[j].ans+c[k].ans);
					}
				}
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}

E2. Game with Marbles (Hard Version)

 

 

 题解：简单版本和这个版本一个代码，最主要是要去学到其中的数学思维，会了那个思维就都可以解决了

首先我们可以知道，如果谁都无法做出选择，那么最后的得分一定是每一项a[i]-b[i]的和

首先我们考虑爱丽丝的影响，如果爱丽丝不选i那么原本对于这一项的值为a[i]-b[i]，但是爱丽丝选择后变成了a[i]-1-0;

因此爱丽丝选择i的影响为b[i]-1;（让得分变大）

我们考虑鲍勃的影响，如果鲍勃不选i那么原本对于这一项的值为a[i]-b[i]，但是鲍勃选择后变成了

0-b[i]+1;

因此鲍勃选择i的影响为1-a[i];（让得分变小）

因此每个人选的总影响就应该为a[i]+b[i]-2，因此我们应该对a[i]+b[i]的值进行排序，然后从最大的一端开始选，然后输出结果即可

#include<bits/stdc++.h>
#define int long long
#define N 220000
using namespace std;
int a[N];
int b[N];
int sum[N];
int n,t;
bool cmp(int x,int y)
{
    return a[x]+b[x]<a[y]+b[y];
}
signed main()
{
    cin>>t;
    while(t--)
	{
        cin>>n;
        for(int i=1;i<=n;i++)
		{
            cin>>a[i];
        }
        for(int i=1;i<=n;i++)
		{
            cin>>b[i];
        }
        int ans=0;
        for(int i=1;i<=n;i++)
		{
            ans+=a[i]-b[i];
            sum[i]=i;
        }
        sort(sum+1,sum+1+n,cmp);
        for(int i=n;i>=1;i-=2)
		{
            ans+=b[sum[i]]-1;
        }
        for(int i=n-1;i>=1;i-=2)
		{
            ans-=a[sum[i]]-1;
        }
        cout<<ans<<"\n";
    }
    return 0;
}