526互联

Educational Codeforces Round 109 (Rated for Div. 2)

发布时间 2023-08-24 10:11:05作者: gan_coder

B题没想到被坑了两次，极端情况明明也很好想，硬是WA了两发。
C题很想之前做过的经典蚂蚁题，但是又不太一样，
但分析之后，发现之后奇偶性相同才可能碰撞，那么分开处理，
假如已经有相向而行，肯定是最快碰撞的，用一个栈维护即可，最后就是剩下的肯定是
L L L ... R R R将它们配对即可。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef long long ll;
const ll mo=1e9+7;
const int N=3e5+5;
struct node{
	int x,d,id;
};
node a[N],b[N],c[N],s[N],t[N];
int n,ans[N],m,tot,top,cnt,x,y;
char ch;
bool cmp(node a,node b){
	return a.x<b.x;
}
void work(){
	top=0;
	cnt=0;
	sort(b+1,b+tot+1,cmp);
	fo(i,1,tot){
		if (b[i].d) {
			s[++top]=b[i];
		}
		else{
			if (top){
				ans[s[top].id]=ans[b[i].id]=(b[i].x - s[top].x)/2;
				top--;
			}
			else {
				t[++cnt]=b[i];
			}
		}
	}
	fo(i,1,cnt/2) {
		x=2*i-1; y=2*i;
		ans[t[x].id]=ans[t[y].id]=(t[x].x+t[y].x)/2;
	}
	
	fo(i,1,top/2) swap(s[i],s[top-i+1]);
	fo(i,1,top/2) {
		x=2*i-1; y=2*i;
		ans[s[x].id]=ans[s[y].id]=(m-s[x].x + m-s[y].x)/2;
	}
	
	if (cnt%2==1 && top%2==1) {
		ans[t[cnt].id]=ans[s[top].id]=(m+t[cnt].x+m-s[top].x)/2;
	}
}
int main() {

//    freopen("data.in","r",stdin);
	
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d %d",&n,&m);
		fo(i,1,n) ans[i]=0;
		
		fo(i,1,n) {
			scanf("%d",&a[i].x);
			a[i].id=i;
		}
		
		fo(i,1,n) {
			scanf("%c",&ch);
			scanf("%c",&ch);
			a[i].d=(ch=='R');
		}	
		
		tot=0;
		fo(i,1,n) {
			if (a[i].x&1) b[++tot]=a[i];
		}
		work();
		
		tot=0;
		fo(i,1,n) {
			if (a[i].x%2==0) b[++tot]=a[i];
		}
		work();
		
		fo(i,1,n) {
			if (ans[i]) printf("%d ",ans[i]);
			else printf("%d ",-1);
		}
		printf("\n");
	}
	
	return 0;
}

D题很明显是N^2dp，首先我们注意到，1的相对顺序不可能改变，否则肯定不是最优的。

\(f[i][j]\)表示第i个1放在j位置的最小值，转移即可。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef long long ll;
const ll mo=1e9+7;
const ll inf=1e9;
const int N=5005;
int f[N][N],g[N];
int a[N],p[N],tot,n,ans;
void cmin(int &x,int y){
	x=min(x,y);
}
int main() {

//    freopen("data.in","r",stdin);
	
	scanf("%d",&n);
	tot=0;
		
	fo(i,1,n) {
		scanf("%d",&a[i]);
		if (a[i]==1) p[++tot]=i;
	}
	
	if (!tot) {
		printf("%d",0);
		return 0;
	}
		
	fo(i,0,n) fo(j,0,n) f[i][j]=inf;
	
	fo(i,0,n) g[i]=0;
	
	fo(i,1,tot) {
		fo(j,1,n) {
			if (!a[j]) cmin(f[i][j], g[j-1]+abs(p[i]-j));
		}
		g[0]=inf;
		fo(j,1,n) g[j]=min(g[j-1], f[i][j]);
	}
	
	ans=inf;
	fo(i,1,n) ans=min(ans, f[tot][i]);
	printf("%d\n",ans);
	
	return 0;
}