Educational Codeforces Round 109 A B C D 题解

A. Potion-making

题意

给出w，要求配出含量为w%的溶液，每次只能加一份水或者溶质，最少要几次才可以实现

思路

• 配比即为w:100-w，化简即可

时间复杂度

O(T)

参考代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
const int maxn=1e5+10;
int t,n,m,num[maxn];
 
int main() {
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		if(n==0 || n==100) {
			printf("1\n");
			continue;
		}
		m=100-n;
		int gcd=__gcd(n,m);
		printf("%d\n",n/gcd+m/gcd);
	}
}

---

 

B. Permutation Sort

题意

给出数组A，保证A是1到n的全排列，每次可以选择一个长度小于n的连续子串随意重排，最少操作几次才可以恢复成全排列

思路

• 每次排列尽可能多的元素
• 开始显然要尽可能把1和n排列正确
• 即：遇到n在开头且1在结尾，要排三次：把1挪走，把1归位同时挪走n，把n归位
• 遇到1不在开头且n不在结尾，要排两次：把1归位，把n归位
• 剩下情况移动一次即可

时间复杂度

O(Tn)

参考代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
const int maxn=1e5+10;
int t,n,m,num[maxn],f[maxn];
 
int main() {
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",num+i);
		}
		int ans=0,f=1;
		for(int i=1;f && i<=n;i++) if(num[i]!=i) f=0;
		if(f) {
			printf("0\n");
			continue;
		}
		
		if(num[1]!=1) ans++;
		if(num[n]!=n) ans++;
		if(num[1]==n && num[n]==1) ans++;
		
		printf("%d\n",max(ans,1));
	}
}

---

 

C. Robot Collisions

题意

数轴上有一堆机器人，向左或右走，每分钟走一格，到头会回头，在整数点相遇就会爆炸，请问每个机器人啥时候爆炸

思路

• 首先区分奇偶性与方向，按照每种奇偶性与方向暴力分类讨论即可

时间复杂度

O(Tn)

参考代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
const int maxn=3e5+10;
struct robot{
	int pos,id,dir;
}a[maxn];
bool cmp(robot a,robot b){ return a.pos<b.pos;}
int ans[maxn],n,m,t;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i].pos);
			a[i].id=i;
		}
		for(int i=1;i<=n;i++){
			string st;
			cin>>st;
			a[i].dir=(st[0]=='R');
		} 
		sort(a+1,a+1+n,cmp);
		vector<pair<int,int> > l0,l1,r0,r1;
		for(int i=1;i<=n;i++){
			if(a[i].pos&1){
				if(a[i].dir)
					r1.push_back(make_pair(a[i].pos,a[i].id));
				else
					if(r1.size()){
						ans[a[i].id]=ans[r1[r1.size()-1].second]=(a[i].pos-r1[r1.size()-1].first)/2;
						r1.pop_back();
					} else 
						l1.push_back(make_pair(a[i].pos,a[i].id));
			}else{
				if(a[i].dir)
					r0.push_back(make_pair(a[i].pos,a[i].id));
				else
					if(r0.size()){
						ans[a[i].id]=ans[r0[r0.size()-1].second]=(a[i].pos-r0[r0.size()-1].first)/2;
						r0.pop_back();
					} else 
						l0.push_back(make_pair(a[i].pos,a[i].id));
			}
		}
		for(int i=r1.size()&1;i<r1.size();i+=2)
        	ans[r1[i].second]=ans[r1[i+1].second]=(2*m-r1[i].first-r1[i+1].first)/2;
        
        for(int i=r0.size()&1;i<r0.size();i+=2)
           	ans[r0[i].second]=ans[r0[i+1].second]=(2*m-r0[i].first-r0[i+1].first)/2;
        
        for(int i=0;i<l1.size();i+=2){
        	if(i==l1.size()-1)break;
        	ans[l1[i].second]=ans[l1[i+1].second]=(l1[i].first+l1[i+1].first)/2;
        }
        	
        for(int i=0;i<l0.size();i+=2){
        	if(i==l0.size()-1)break;
        	ans[l0[i].second]=ans[l0[i+1].second]=(l0[i].first+l0[i+1].first)/2;
        }
        	
        if(r1.size()&1)
            if(l1.size()&1)
                ans[r1[0].second]=ans[l1[l1.size()-1].second]=(m+m-r1[0].first+l1[l1.size()-1].first)/2;
            else
            	ans[r1[0].second]=-1;
        else
            if(l1.size()&1)
                ans[l1[l1.size()-1].second]=-1;
            	
        if(r0.size()&1)
        	if(l0.size()&1)
        	    ans[r0[0].second]=ans[l0[l0.size()-1].second]=(m+m-r0[0].first+l0[l0.size()-1].first)/2;
        	else
        	    ans[r0[0].second]=-1;
        else
        	if(l0.size()&1)
        	    ans[l0[l0.size()-1].second]=-1;
        for(int i=1;i<=n;i++) printf("%d ",ans[i]);
        printf("\n");
	}
}

---

 

D. Armchairs

题意

一些位置上有人，每分钟可以走一格，不可以同时走，要把所有人移到不同位置上，保证有解，请问最少要多少时间？

思路

• 看到5000的数据范围，想到暴力dp
• 每个位置，如果本身有人，一定直接结束，不能接受
• 如果本身每人，可以考虑接受所有人，暴力枚举即可

时间复杂度

参考代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int maxn=5000+10;
int n,a[maxn],last,f[maxn][maxn];//f[i][j]表示在i这个位置的人安排到j位置时最小代价 
int main(){
	scanf("%d",&n);
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++) scanf("%d",a+i);
	for(int i=0;i<=n;i++) f[0][i]=0;
	for(int i=1;i<=n;i++) if(a[i]) {
		for(int j=1;j<=n;j++){
			f[i][j]=f[i][j-1];
			if(!a[j])
				f[i][j]=min(f[i][j],f[last][j-1]+abs(j-i));
		}
		last=i;
	}
	printf("%d\n",f[last][n]); 
}