Codeforces Round #443 Div. 1

2022-11-27 19:46:33

　　A：考虑每一位的改变情况，分为强制变为1、强制变为0、不变、反转四种，得到这个之后and一发or一发xor一发就行了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 500010

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 a[20];

signed main()

{

	int n=read(),x=0;

	while (n--)

	{

		char c=getchar();

		while (c!='|'&&c!='^'&&c!='&') c=getchar();

		int u=read();

		for (int i=0;i<10;i++)

		if (u&(1<<i))

		{

			if (c=='|') a[i]=1;

			if (c=='^')

			{

				if (a[i]==0) a[i]=3;

				else if (a[i]==1) a[i]=2;

				else if (a[i]==2) a[i]=1;

				else if (a[i]==3) a[i]=0;

			}

		}

		else

		{

			if (c=='&') a[i]=2;

		}

	}

	cout<<3<<endl;

	for (int i=1;i<=3;i++)

	{

		int x=0;

		for (int j=0;j<10;j++)

		if (a[j]==i) x|=1<<j;

		if (i==2) cout<<'&'<<' '<<(1023^x)<<endl;

		else

		{

			if (i==1) cout<<'|';else cout<<'^';

			cout<<' '<<x<<endl;

		}

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　B：先按k=1的情况处理一下。然后若考虑首尾相接是否会超过m个，若会则删掉，若恰好有k个则继续删。最后如果只剩下一种数特殊讨论。坑点比较多。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

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,k,a[N],b[N],stk[N],top;

ll ans;

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read(),m=read(),k=read();

	for (int i=1;i<=n;i++) a[i]=read();

	int u=0;int cnt=0;

	for (int i=1;i<=n;i++)

	{

		if (!top) stk[++top]=a[i],cnt++;

		else

		{

			if (stk[top]==a[i]) cnt++;

			else cnt=1;

			stk[++top]=a[i];

		}

		if (cnt==m)

		{

			top-=m;ans+=1ll*k*m;cnt=0;

			for (int j=top;j>=0;j--) if (stk[j]!=stk[top]) {cnt=top-j;break;}

		}

	}

	u=top;memcpy(b,stk,sizeof(b));

	int nnn=n;

	n=u;memcpy(a,b,sizeof(a));

	bool flag=0;

	for (int i=2;i<=n;i++) if (a[i]!=a[1]) {flag=1;break;}

	if (!flag) {cout<<1ll*nnn*k%m;return 0;}

	int l=1,r=n;

	while (l<=r)

	{

		int x=l,y=r;

		if (a[l]!=a[r]) break;

		while (a[x+1]==a[l]) x++;

		while (a[y-1]==a[r]) y--;

		if (x>=y)

		{

			ans+=(1ll*k*(r-l+1)/m)*m;

			if (1ll*k*(r-l+1)%m==0) ans+=n-(r-l+1);

			break;

		}

		if (x-l+1+r-y+1>=m)

		{

			ans+=1ll*(k-1)*m;

			if (x-l+1+r-y+1>m) break;

			else if (m==(x-l+1+r-y+1)) l=x+1,r=y-1;

			else break;

		}

		else break;

	}

	ans=1ll*nnn*k-ans;

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　C：考虑建图，a向b连边表示a可以打败b。这样缩点后度数为0的点（显然只会存在一个）中的所有选手都可能取胜。考虑动态维护。每个SCC记录大小和各项的minmax。注意到所有SCC每一项都构成偏序关系(max_i<min_i+1)，于是用一个set，新加入一个点时找到前驱后继，看新点能否与其互相打败而合并成一个新的SCC即可。具体实现参考了这份代码https://codeforces.com/contest/878/submission/31775120，感觉过于优美。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<set>

using namespace std;

#define ll long long

#define N 50010

#define M 12

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;

struct data

{

	int size,min[M],max[M];

	bool operator <(const data&a) const

	{

		for (int i=1;i<=m;i++) if (max[i]>a.min[i]) return 0;

		return 1;

	}

	void merge(const data&a)

	{

		size+=a.size;

		for (int i=1;i<=m;i++)

		{

			if (a.min[i]<min[i]) min[i]=a.min[i];

			if (a.max[i]>max[i]) max[i]=a.max[i];

		}

	}

};

multiset<data> q;

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read(),m=read();

	for (int i=1;i<=n;i++)

	{

		data p;p.size=1;

		for (int j=1;j<=m;j++) p.min[j]=p.max[j]=read();

		multiset<data>::iterator first_beat_p=q.lower_bound(p),first_p_cannot_beat=q.upper_bound(p);

		while (first_beat_p!=first_p_cannot_beat)

		{

			p.merge(*first_beat_p);

			first_beat_p=q.erase(first_beat_p);

		}

		q.insert(p);multiset<data>::iterator tmp=q.end();tmp--;

		printf("%d\n",(*tmp).size);

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D：考虑所有数值都为01的情况。这样一共只有2^k种本质不同的特征，可以bitset记录每种特征最后的答案直接暴力过去。不为01的话容易想到二分答案之类，实际上使用完全相同的做法得到01时的答案，最后类似于二分答案的做即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<bitset>

using namespace std;

#define ll long long

#define N 100010

#define K 12

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,q,k,a[K][N],b[N][K],cnt,u;

bitset<(1<<K)> S[N];

bool cmp(const int &x,const int &y)

{

	return a[x][u]<a[y][u];

}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("d.in","r",stdin);

	freopen("d.out","w",stdout);

#endif

	n=read(),k=read(),q=read();

	for (int i=0;i<k;i++)

		for (int j=1;j<=n;j++)

		a[i][j]=read();

	for (int i=0;i<k;i++)

	{

		for (int j=0;j<(1<<k);j++)

		S[i][j]=(j&(1<<i))>0;

	}

	for (u=1;u<=n;u++)

	{

		for (int j=0;j<k;j++) b[u][j]=j;

		sort(b[u],b[u]+k,cmp);

	}

	cnt=k-1;

	for (int i=1;i<=q;i++)

	{

		int op=read(),x=read()-1,y=read();

		if (op==1) S[++cnt]=S[x]|S[y-1];

		if (op==2) S[++cnt]=S[x]&S[y-1];

		if (op==3)

		{

			u=0;

			for (int j=k-1;j>=0;j--)

			{

				u|=1<<b[y][j];

				if (S[x][u]) {printf("%d\n",a[b[y][j]][y]);break;}

			}

		}

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

码农公寓

相关文章