Codeforces Round #598(div3)

题目链接

Codeforces Round #598(div3)

A

思路

就是问x个n和b个1能否组成S，贪心，先用n，不够的再用1即可。

实现代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int main()
{
	int q;
	scanf("%d",&q);
	while(q--)
	{
		int a,b,n,s;
		cin>>a>>b>>n>>s;
		if(1ll*a*n>s)s=s%n;
		else s=s-(a*n);
		if(b>=s)printf("YES\n");
		else printf("NO\n");
	}
 }

B

思路

让小的数尽可能的在前面，就从1枚举到n，查看他们的位置，他们能够到达的位置就是上一个最小的数被交换的位置，细节可能比较多注意一下即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 110;
int a[N];
int local[N];
bool vis[N];
bool vist[N];
int b[N];
int main()
{
	int q;
	scanf("%d",&q);
	while(q--)
	{
		queue<int>v;
		int n;
		scanf("%d",&n);
		for(int i=0;i<n;i++)scanf("%d",&a[i]),local[a[i]]=i;
		int now = 0;
		for(int i=1;i<=n;i++)
		{
			if(local[i]>now)
			{
				for(int j=local[i];j>now;j--)
				{
					local[a[j-1]]++;
					swap(a[j],a[j-1]);
				}
				now = local[i];
			}
			else now=max(now,local[i]+1);
		}
		for(int i=0;i<n;i++)printf("%d ",a[i]);
		printf("\n");
	}
}

C

思路

这题是比较难的了，不过思路很简单，起始中间有连续的不影响，因为d>=1所以连续的我们先不考虑，然后现在就转化成把桥分成k块的问题，很简单，每次跳到最远的地方即可。所以每次跳到d处。然后我们回来看输出，我们可以在木板中插入0，但是插入0的过程中保证i%d==0的地方要有桥即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 1e3+10;
int a[N];
vector<int>v;
int main()
{
	int n,m,d;
	scanf("%d %d %d",&n,&m,&d);
	int tn = n;
	int sum = 0;
	for(int i=0;i<m;i++)
	{
		scanf("%d",&a[i]);
		for(int j=0;j<a[i];j++)v.push_back(i+1);
		if(a[i]!=1)tn-=a[i]-1;
		sum+=a[i];
	}
	int No = n - sum;
	if(tn/d>m||(d==1&&sum!=n))return 0*printf("NO\n");
	else
	{
		int now = 0;
		int cnt = 0;
		while(No)
		{
			int needin = min(d-1,No);
			No-=needin;
			v.insert(v.begin()+now,needin,0);
			now+=d+a[cnt++]-1;
		}
	}
	printf("YES\n");
	for(int i=0;i<n;i++)
	{
		printf("%d ",v[i]);
	}
	cout<<endl;
	
}

D

思路

把0移到前面，记录每个0的位置，记录第一个1的位置，每次访问看当前的0能够前进到当前的1之后的哪一个位置，然后交换两个位置的数即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
vector<int>v;
int main()
{
	int q;
	scanf("%d",&q);
	while(q--)
	{
		v.clear();
		ll n,k;
		scanf("%I64d %I64d",&n,&k);
		string s;
		cin>>s;
		int now = -1;
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='0')v.push_back(i);
			if(now==-1&&s[i]=='1')now=i;
		}
		if(now==-1)
		{
			cout<<s<<endl;
			continue;
		}
		int cnt = 0;
		while(k)
		{
			
			while(cnt<v.size()&&v[cnt]<=now)cnt++;
			if(cnt==v.size())break;
			if(v[cnt]-now<=k)
			{
				k-=v[cnt]-now;
				s[now]='0';
				s[v[cnt]]='1';
				cnt++;
				now++;
			}
			else
			{
				s[max(v[cnt]-k,1ll*now)]='0';
				s[v[cnt]]='1';
				break;
			}
		}
		cout<<s<<endl;
	}
 }

E

思路

显然，队伍中的人数最多5个人，如果有六个人，我们就能把它分成两组，所得到的贡献是一样的。
那么我们就枚举第i个人，是跟第三个人，第四个人，或者第五个人在一起。
dp[i] 代表前i个人分组的最小值，那么第i个人和前面的几个人在一个组就可以表示为
>
dp[i+3]=min(dp[i],a[i+2]-a[i]);
dp[i+4]=min(dp[i],a[i+3]-a[i]);
dp[i+5]=min(dp[i],a[i+4]-a[i]);

根据这三个状态转移方程就能写出来了

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 2e5+10;
#define inf  0x3f3f3f3f3f3f
struct node
{
	int x;
	int index;
	bool operator < (const node a) const
	{
		return x<a.x;
	}
}a[N];
int l[N];
ll dp[N];
int t[N];
int main()
{
   int n;
   scanf("%d",&n);
   for(int i=0;i<n;i++)
   {
   	scanf("%d",&a[i].x);
   	a[i].index=i;
   	dp[i]=inf;
   }
   dp[n]=inf;
   dp[0]=0;
   sort(a,a+n);
   for(int i=0;i<n;i++)
   for(int j=3;j<=5&&i+j<=n;j++)
   {
   	   ll p = a[i+j-1].x-a[i].x;
   	   if(dp[i+j]>dp[i]+p)
   	   {
   	   	 l[i+j]=i;
   	   	 dp[i+j]=p+dp[i];
		}
   }
   int NumOfStudent = n;
   int NumOfTeam = 0;
   while(NumOfStudent!=0)
   {
   	for(int i=NumOfStudent-1;i>=l[NumOfStudent];i--)
   	t[a[i].index]=NumOfTeam;
   	NumOfTeam++;
   	NumOfStudent =  l[NumOfStudent];
   }
   printf("%I64d %d\n",dp[n],NumOfTeam);
   for(int i=0;i<n;i++)
   {
   	if(i)printf(" ");
   	printf("%d",t[i]+1);
   }
 }