Codeforces Round #556 Div. 1

2024-02-21 11:57:46

　　A：注意到2和两个1几乎没有差别，因为除2外的偶数都不是质数。于是最开始放一个2，然后放奇数个1，再把2放完，最后若有1再排在最后即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 200010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,m,a[N],cnt;
bool flag[N];
signed main()
{
	n=read();
	for (int i=1;i<=n;i++) if (read()==1) cnt++;
	if (cnt==n) {for (int i=1;i<=n;i++) printf("1 ");return 0;}
	cout<<2<<' ';n--;
	if (cnt&1)
	{
		for (int i=1;i<=cnt;i++) printf("1 ");
		for (int i=1;i<=n-cnt;i++) printf("2 ");
	}
	else
	{
		for (int i=1;i<=cnt-1;i++) printf("1 ");
		for (int i=1;i<=n-cnt;i++) printf("2 ");
		if (cnt) printf("1 ");
	}
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　B：考虑单组询问怎么做。设f[a][b][c]为最短的前缀长度满足能从中挑出第一种宗教的前a位、第二种宗教的前b位、第三种宗教的前c位。转移考虑最后一个被挑出的字符属于那种宗教。设nxt[i][j]表示i之后第一个j字符的出现位置即可O(1)转移。原题由于每次只有一位字符变化，转移是O(250²)的。才知道这个nxt数组原来就叫序列自动机（

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 100010
#define M 260
char getc(){char c=getchar();while (c!='+'&&c!='-'&&(c<'a'||c>'z')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,m,a,b,c,f[M][M][M],nxt[N][26];
char s[N],A[N],B[N],C[N];
signed main()
{
	n=read(),m=read();
	scanf("%s",s+1);
	for (int i=0;i<26;i++) nxt[n+1][i]=nxt[n+2][i]=n+1;
	for (int i=n;i>=0;i--)
	{
		for (int j=0;j<26;j++) nxt[i][j]=nxt[i+1][j];
		if (i) nxt[i][s[i]-'a']=i;
	}
	for (int i=1;i<=m;i++) 
	{
		char op=getc();
		if (op=='+')
		{
			int x=read();char ch=getc();
			if (x==1)
			{
				A[++a]=ch;
				for (int p=0;p<=b;p++)
					for (int q=0;q<=c;q++)
					{
						f[a][p][q]=nxt[f[a-1][p][q]+1][A[a]-'a'];
						if (p) f[a][p][q]=min(f[a][p][q],nxt[f[a][p-1][q]+1][B[p]-'a']);
						if (q) f[a][p][q]=min(f[a][p][q],nxt[f[a][p][q-1]+1][C[q]-'a']);
					}
			}
			if (x==2)
			{
				B[++b]=ch;
				for (int p=0;p<=a;p++)
					for (int q=0;q<=c;q++)
					{
						f[p][b][q]=nxt[f[p][b-1][q]+1][ch-'a'];
						if (p) f[p][b][q]=min(f[p][b][q],nxt[f[p-1][b][q]+1][A[p]-'a']);
						if (q) f[p][b][q]=min(f[p][b][q],nxt[f[p][b][q-1]+1][C[q]-'a']);
					}
			}
			if (x==3)
			{
				C[++c]=ch;
				for (int p=0;p<=a;p++)
					for (int q=0;q<=b;q++)
					{
						f[p][q][c]=nxt[f[p][q][c-1]+1][ch-'a'];
						if (p) f[p][q][c]=min(f[p][q][c],nxt[f[p-1][q][c]+1][A[p]-'a']);
						if (q) f[p][q][c]=min(f[p][q][c],nxt[f[p][q-1][c]+1][B[q]-'a']);
					}
			}
		}
		else
		{
			int x=read();
			if (x==1) a--;
			if (x==2) b--;
			if (x==3) c--;
		}
		if (f[a][b][c]<=n) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　C：左括号视为1，右括号视为-1，一个点在树中的深度就是其在括号序列中出现位置的前缀和，于是就要找x<=y<=z最大化s_x-2s_y+s_z。场上死活不会维护这玩意，水平低啊。类似于最大子段和地直接线段树维护即可，合并时讨论xyz各自在哪一半，当然维护的前缀和是只考虑节点所表示区间内部的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 200010
char getc(){char c=getchar();while (c!='('&&c!=')') c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,q,a[N],L[N<<2],R[N<<2],sum[N<<2],tree[N<<2][5];
char s[N];
void update(int k,int x)
{
	tree[k][0]=0;
	tree[k][1]=tree[k][2]=x;
	tree[k][3]=tree[k][4]=-x;
	sum[k]=x;
}
void up(int k)
{
	sum[k]=sum[k<<1]+sum[k<<1|1];
	tree[k][0]=max(tree[k<<1][0],tree[k<<1|1][0]);
	tree[k][0]=max(tree[k][0],max(tree[k<<1][3]+sum[k<<1]+tree[k<<1|1][1],tree[k<<1][1]-sum[k<<1]+tree[k<<1|1][4]));
	tree[k][1]=max(tree[k<<1][1],sum[k<<1]+tree[k<<1|1][1]);
	tree[k][2]=min(tree[k<<1][2],sum[k<<1]+tree[k<<1|1][2]);
	tree[k][3]=max(max(tree[k<<1][3],tree[k<<1|1][3]-sum[k<<1]),tree[k<<1][1]-2*(tree[k<<1|1][2]+sum[k<<1]));
	tree[k][4]=max(max(tree[k<<1][4],tree[k<<1|1][4]-sum[k<<1]),-2*tree[k<<1][2]+tree[k<<1|1][1]+sum[k<<1]);
}//0 �� 1 ���ǰ׺�� 2 ��Сǰ׺�� 3 ǰ������ 4 �������� 
void build(int k,int l,int r)
{
	L[k]=l,R[k]=r;
	if (l==r) {if (l) update(k,a[l]);return;}
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	up(k);
}
void modify(int k,int x,int p)
{
	if (L[k]==R[k]) {update(k,p);return;}
	int mid=L[k]+R[k]>>1;
	if (x<=mid) modify(k<<1,x,p);
	else modify(k<<1|1,x,p);
	up(k);
}
signed main()
{
	n=read()-1<<1,q=read();
	scanf("%s",s+1);
	for (int i=1;i<=n;i++) if (s[i]=='(') a[i]=1;else a[i]=-1;
	build(1,0,n);printf("%d\n",tree[1][0]);
	for (int i=1;i<=q;i++)
	{
		int x=read(),y=read();
		modify(1,x,a[y]),modify(1,y,a[x]);
		swap(a[x],a[y]);
		printf("%d\n",tree[1][0]);
	}
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　D：所有MST中同一种权值的边对连通性的贡献是相同的。于是先考虑添加a边后的连通性情况。此时在同一个连通块中的点的最短路径只能包含a边。然后考虑将当前的连通块缩点，并加入b边，那么若要路径能被MST包含，则不能通过b边重复到达同一连通块。这样可以设f[i][S]为到i号点所经过连通块集合为S时的最短路径，跑dij即可。然而n太大了。但同时n又不够大。于是考虑一些奇技淫巧。之前的dij中记录S是为了防止重复到达同一连通块，但当连通块只有一个点的时候，重复到达该点显然不会更优。进一步发现对连通块含两个点、三个点的情况同样成立。于是S集合中只需要记录所有大小>=4的连通块即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 80
#define M 210
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,m,a,b,fa[N],d[N][N],p[N],t,f[N][1<<18],size[N],id[N],belong[N],cnt;
bool flag[N][1<<18];
struct data
{
	int x,y,z;
	bool operator <(const data&a) const
	{
		return z>a.z;
	}
}e[M];
struct data2{int to,nxt,len;
}edge[M<<1];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}
priority_queue<data> q;
signed main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	n=read(),m=read(),a=read(),b=read();
	for (int i=1;i<=m;i++)
	{
		e[i].x=read(),e[i].y=read(),e[i].z=read();
		addedge(e[i].x,e[i].y,e[i].z);
		addedge(e[i].y,e[i].x,e[i].z);
	}
	memset(d,60,sizeof(d));
	for (int i=1;i<=n;i++) fa[i]=i,d[i][i]=0;
	for (int i=1;i<=m;i++)
	if (e[i].z==a) fa[find(e[i].x)]=find(e[i].y);
	for (int i=1;i<=n;i++) size[find(i)]++;
	for (int i=1;i<=n;i++) if (size[i]>=4) id[i]=cnt++;
	for (int i=1;i<=n;i++) belong[i]=size[find(i)]>=4?(1<<id[find(i)]):0;
	memset(f,60,sizeof(f));f[1][belong[1]]=0;q.push((data){1,belong[1],0});
	while (!q.empty())
	{
		data x=q.top();q.pop();
		if (flag[x.x][x.y]) continue;
		flag[x.x][x.y]=1;
		for (int j=p[x.x];j;j=edge[j].nxt)
		if ((edge[j].len!=b||!(x.y&belong[edge[j].to])&&find(x.x)!=find(edge[j].to))&&x.z+edge[j].len<f[edge[j].to][x.y|belong[edge[j].to]])
		{
			f[edge[j].to][x.y|belong[edge[j].to]]=x.z+edge[j].len;
			q.push((data){edge[j].to,x.y|belong[edge[j].to],f[edge[j].to][x.y|belong[edge[j].to]]});
		}
	}
	for (int i=1;i<=n;i++)
	{
		int ans=inf;
		for (int j=0;j<(1<<cnt);j++) ans=min(ans,f[i][j]);
		cout<<ans<<' '; 
	}
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　result：rank 99 rating +76 小号上IM啦qwq

码农公寓

相关文章