Codeforces Round #773 (Div. 2)

2023-10-04 17:55:28

A

Codeforces Round #773 (Div. 2)

只有这种情况答案不为 \(0\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline 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;
}
void write(int n)
{
	if(n<0){putchar('-');n=-n;}
	if(n>9)write(n/10);
	putchar(n%10^48);
}
int x[3],y[3];
void sol()
{
	for(int i=0;i<3;i++)x[i]=read(),y[i]=read();
	for(int i=0;i<3;i++)
	{
		for(int j=i+1;j<3;j++)
		{
			if(y[i]==y[j])
			{
				if(y[3-i-j]>y[i])return puts("0"),void();
				else return printf("%d\n",abs(x[i]-x[j])),void();
			}
		}
	}
	puts("0");
}
int main()
{
	int T=read();
	while(T--)sol();
}
//zzt qwq

B

见代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline 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;
}
void write(int n)
{
	if(n<0){putchar('-');n=-n;}
	if(n>9)write(n/10);
	putchar(n%10^48);
}
const int N=3e5+10;
map<int,bool> vis;
int a[N];
void sol()
{
	vis.clear();
	int n=read(),c=0;
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		if(!vis[a[i]])c++;
		vis[a[i]]=1;
	}
	for(int i=1;i<=c;i++)printf("%d ",c);
	for(int i=c+1;i<=n;i++)printf("%d ",i);
	puts("");
}
int main()
{
	int n=read();
	while(n--)sol();
}
//zzt qwq

C

直接大力贪。

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline 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;
}
void write(int n)
{
	if(n<0){putchar('-');n=-n;}
	if(n>9)write(n/10);
	putchar(n%10^48);
}
const int N=2e5+10;
int a[N];
map<int,int> cnt;
void sol()
{
	cnt.clear();
	int n=read(),x=read();
	for(int i=1;i<=n;i++)a[i]=read(),cnt[a[i]]++;
	sort(a+1,a+n+1);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(!cnt[a[i]])continue;
		if(cnt[a[i]*x])cnt[a[i]]--,cnt[a[i]*x]--;
		else cnt[a[i]]--,ans++;
	}
	printf("%lld\n",ans);
}
signed main()
{
	int T=read();
	while(T--)sol();
}
//zzt qwq

D

首先如果有数值出现计数词显然不合法。

否则的话维护一个 vector，对于当前的第一位，找到后面第一个匹配到他的位置 \(k\)，然后在 \(k\) 后面暴力加使得 \([1,k)\) 和 \([k,2k)\) 这段区间的数是对应相等的，然后消掉这段区间，再继续做。

可以证明复杂度是正确的，但我不会证。感性理解一下大概就是 \(\mathcal O(n^3)\) 左右的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline 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;
}
void write(int n)
{
	if(n<0){putchar('-');n=-n;}
	if(n>9)write(n/10);
	putchar(n%10^48);
}
const int N=1e6+10;
int vis[N];
int a[N];
map<int,int> cnt;
void sol(int T)
{
	cnt.clear();
	vector<int> v;
	int n=read();
	for(int i=1;i<=n;i++)a[i]=read(),cnt[a[i]]++,v.pb(a[i]);
	for(auto it:cnt)if(it.se&1)return puts("-1"),void();
	vector<pii> Ans;
	vector<int> len;
//	puts("TEST1");
	for(int i=0;i<v.size();i++)
	{
//		printf("i=%d\n",i);
		if(vis[i]==T)continue;
		int k=0;
		for(int j=i+1;j<v.size();j++)
		{
			if(v[j]==v[i])
			{
				k=j;
				break;
			}
		}
//		printf("k=%d\n",k);
		for(int j=i;j<k;j++)
		{
//			printf("j=%d\n",j);
			if(k+(j-i)<v.size()&&v[k+(j-i)]==v[j])vis[k+(j-i)]=T;
			else
			{
				Ans.pb(mp(k+(j-i),v[j]));
				if(k+(j-i)==v.size())
				{
//					puts("!!");
					v.pb(v[j]);
					v.pb(v[j]);
//					printf("v.size()=%d\n",(int)v.size());
				}
				else
				{
//					printf("v.size=%d\n",(int)v.size());
//					puts("??");
//					printf("k+(j-i)=%d\n",k+(j-i));
					v.insert(v.begin()+(k+(j-i)),v[j]);
					v.insert(v.begin()+(k+(j-i)),v[j]);
				}
				vis[k+(j-i)]=T;
			}
			vis[j]=T;
		}
		len.pb((k-i)*2);
	}
	printf("%d\n",(int)Ans.size());
	for(auto it:Ans)printf("%d %d\n",it.fi,it.se);
	printf("%d\n",(int)len.size());
	for(auto it:len)printf("%d ",it);
	puts("");
}
int main()
{
	int T=read();
	for(int i=1;i<=T;i++)sol(i);
}
//zzt qwq

E

可以发现一个人 \(p\) 能被确认是有病当且仅当存在一个 \(0\;l\;r\;1\) 操作使得 \(p\in[l,r]\) 且区间内其他人都被确认没病，能被确认没病就是被一个 \(1\;l\;r\;0\) 覆盖过。

考虑把操作离线下来，将所有的 \(1\;l\;r\;0\) 操作先做一遍，然后再对所有的 \(1\;l\;r\;1\) 看是否区间有且仅有一个数没被钦定为 \(0\)，记录下这个数被确认为 \(1\) 的最小时间，查询操作即考虑最小时间和当前操作时间的大小关系。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline 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;
}
void write(int n)
{
	if(n<0){putchar('-');n=-n;}
	if(n>9)write(n/10);
	putchar(n%10^48);
}
const int N=2e5+10;
struct sgt{
	struct seg{
		int l,r,min,tag;
		seg(){l=r=0,min=tag=1e9;}
	}t[N<<2];
	void build(int p,int l,int r)
	{
		t[p].l=l,t[p].r=r;
		t[p].min=t[p].tag=1e9;
		if(l==r)return;
		int mid=(l+r)>>1;
		build(p*2,l,mid);
		build(p*2+1,mid+1,r);
	}
	void pd(int p)
	{
		if(t[p].tag!=1e9)
		{
			t[p*2].tag=min(t[p*2].tag,t[p].tag);
			t[p*2+1].tag=min(t[p*2+1].tag,t[p].tag);
			t[p*2].min=min(t[p*2].min,t[p].tag);
			t[p*2+1].min=min(t[p*2+1].min,t[p].tag);
			t[p].tag=1e9;
		}
	}
	void modify(int p,int l,int r,int d)
	{
		if(l<=t[p].l&&t[p].r<=r)
		{
			t[p].min=min(t[p].min,d);
			t[p].tag=min(t[p].tag,d);
			return;
		}
		pd(p);int mid=(t[p].l+t[p].r)>>1;
		if(l<=mid)modify(p*2,l,r,d);
		if(r>mid)modify(p*2+1,l,r,d);
		t[p].min=min(t[p*2].min,t[p*2+1].min);
	}
	int query(int p,int l,int r)
	{
//		printf("query[%d, %d], now[%d, %d]\n",l,r,t[p].l,t[p].r);
		if(l<=t[p].l&&t[p].r<=r)return t[p].min;
		pd(p);int mid=(t[p].l+t[p].r)>>1,ans=1e9;
		if(l<=mid)ans=min(ans,query(p*2,l,r));
		if(r>mid)ans=min(ans,query(p*2+1,l,r));
		return ans;
	}
}T;
struct Query{
	int t;
	int l,r,x;
}q[N];
int f[N],sum[N];
int st[N][30],Log[N];
int query(int l,int r)
{
	int x=Log[r-l+1];
	return max(st[l][x],st[r-(1<<x)+1][x]);
}
int g[N];
int main()
{
	int n=read(),m=read();
	T.build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		q[i].t=read();
		if(q[i].t==0)q[i].l=read(),q[i].r=read(),q[i].x=read();
		else q[i].x=read();
	}
	for(int i=1;i<=m;i++)if(q[i].t==0&&q[i].x==0)T.modify(1,q[i].l,q[i].r,i);
	for(int i=1;i<=n;i++)f[i]=T.query(1,i,i);
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(f[i]!=1e9);
	for(int i=2;i<=n;i++)Log[i]=Log[i>>1]+1;
	for(int i=1;i<=n;i++)if(f[i]!=1e9)st[i][0]=f[i];
	for(int j=1;j<=Log[n];j++)for(int i=1;i+(1<<j)-1<=n;i++)st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
//	for(int i=1;i<=n;i++)printf("%d ",f[i]);puts("!!??!!!?");
//	for(int i=1;i<=n;i++)printf("%d ",sum[i]-sum[i-1]);
//	puts("!!");
	memset(g,0x7f,sizeof(g));
	for(int i=1;i<=m;i++)
	{
		if(q[i].t==0&&q[i].x==1)
		{
			int l=q[i].l,r=q[i].r;
			if(sum[r]-sum[l-1]==r-l){
//				puts("FUCK!");
				int tm=max(query(l,r),i);
				int L=l,R=r,pos=0;
				while(L<=R)
				{
					int mid=(L+R)>>1;
					if(sum[mid]-sum[l-1]<mid-l+1)R=mid-1,pos=mid;
					else L=mid+1;
				}
//				printf("pos=%d??????, tm=%d\n",pos,tm);
				g[pos]=min(g[pos],tm);
			}
		}
	}
	T.build(1,1,n);
	for(int i=1;i<=m;i++)
	{
//		printf("%d, %d, %d, %d\n",q[i].t,q[i].l,q[i].r,q[i].x);
		if(q[i].t==0&&q[i].x==0)T.modify(1,q[i].l,q[i].r,0);
		else if(q[i].t==1)
		{
			if(g[q[i].x]<=i)
				puts("YES");
			else if(T.query(1,q[i].x,q[i].x)==0)
				puts("NO");
			else 
				puts("N/A");
		}
//		for(int j=1;j<=n;j++)printf("%d ",T.query(1,j,j));
//		puts("!!!");
	}
}
//zzt qwq

F

还不会。

上一篇：实例10 continue,让循环不做工作自己走


下一篇：CentOS 7 安装PostgrelSQL9.6