时间戳

首页 > 技术文章 > Codeforces Global Round 3

Codeforces Global Round 3

shanxieng 2019-06-25 18:57 原文

Codeforces Global Round 3

B - Born This Way

首先二分从B到C坐的是哪个航班，然后枚举从A到B坐的是哪个航班即可。

#include<bits/stdc++.h>
#define qmin(x,y) (x=min(x,y))
#define qmax(x,y) (x=max(x,y))
#define pir pair<int,int>
#define mp(x,y) make_pair(x,y)
#define fr first
#define sc second
#define rsort(x,y) sort(x,y),reverse(x,y)
#define vic vector<int>
#define vit vic::iterator
using namespace std;

char gc() {
//	static char buf[100000],*p1,*p2;
//	return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;
	return getchar();
}

template<class T>
int read(T &ans) {
	T f=1;ans=0;
	char ch=gc();
	while(!isdigit(ch)) {
		if(ch==EOF) return EOF;
		if(ch=='-') f=-1;
		ch=gc();
	}
	while(isdigit(ch))
		ans=ans*10+ch-'0',ch=gc();
	ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
	return read(a)==EOF?EOF:read(b);
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
	return read(a,b)==EOF?EOF:read(c);
}

typedef long long ll;
const int Maxn=1100000;
const int inf=0x3f3f3f3f;
const ll mod=998244353;

int n,m,k;
ll a[Maxn],b[Maxn],ta,tb;

bool check(int x) {
	int temp=1;
	if(n<=k||m<=k) return true;
	for(int i=1;i<=n;i++) {
		while(b[temp]<a[i]+ta&&temp<x) temp++;
		if(i-1+x-temp<=k) return true;
	}
	return false;
}

int main() {
//	freopen("test.in","r",stdin);
	read(n,m);
	read(ta,tb,k);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=m;i++) read(b[i]);
	b[m+1]=(ll)inf<<2ll;
	if(check(m+1)) {
		puts("-1");
	}
	else {
		int l=1,r=m,mid=l+r>>1,ans;
		while(l<=r) {
			if(check(mid)) {
				ans=mid;
				l=mid+1;
			}
			else r=mid-1;
			mid=l+r>>1;
		}
		printf("%I64d\n",b[ans]+tb);
	}
	return 0;
}

C - Crazy Diamond

首先考虑2到n-1中的每一个数，如果这个数应该放在左半边，那么可以考虑把这个数从当前位置移动到n，然后移动到应该放的位置。而移动到n的时候如果这个数是在左半边，就直接移动，否则先移动到1再移动到n。右半边同理。最后特判一下1和n即可。移动的次数为3n。

#include<bits/stdc++.h>
#define qmin(x,y) (x=min(x,y))
#define qmax(x,y) (x=max(x,y))
#define pir pair<int,int>
#define mp(x,y) make_pair(x,y)
#define fr first
#define sc second
#define rsort(x,y) sort(x,y),reverse(x,y)
#define vic vector<int>
#define vit vic::iterator
using namespace std;

char gc() {
//	static char buf[100000],*p1,*p2;
//	return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;
	return getchar();
}

template<class T>
int read(T &ans) {
	T f=1;ans=0;
	char ch=gc();
	while(!isdigit(ch)) {
		if(ch==EOF) return EOF;
		if(ch=='-') f=-1;
		ch=gc();
	}
	while(isdigit(ch))
		ans=ans*10+ch-'0',ch=gc();
	ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
	return read(a)==EOF?EOF:read(b);
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
	return read(a,b)==EOF?EOF:read(c);
}

typedef long long ll;
const int Maxn=1100000;
const int inf=0x3f3f3f3f;
const ll mod=998244353;

int n,p[Maxn],b[Maxn],tot;
pir ans[Maxn];

void work(int x,int y) {
	ans[++tot]=mp(x,y);
	b[p[x]]=y;
	b[p[y]]=x;
	swap(p[x],p[y]);
}

int main() {
//	freopen("test.in","r",stdin);
	read(n);
	for(int i=1;i<=n;i++) read(p[i]),b[p[i]]=i;
	for(int i=2;i<=n/2;i++) {
		if(p[i]==i) continue;
		if(b[i]<=n/2) {
			work(b[i],n);
			work(n,i);
		}
		else {
			work(b[i],1);
			work(1,n);
			work(n,i);
		}
	}
	for(int i=n/2+1;i<n;i++) {
		if(p[i]==i) continue;
		if(b[i]>n/2) {
			work(b[i],1);
			work(1,i);
		}
		else {
			work(b[i],n);
			work(1,n);
			work(1,i);
		}
	}
	if(p[1]!=1) work(1,n);
	printf("%d\n",tot);
	for(int i=1;i<=tot;i++)
		printf("%d %d\n",ans[i].fr,ans[i].sc);
	return 0;
}

D - Dirty Deeds Done Dirt Cheap

有两种类型的数列，第一种是第一个数比第二个数大，而第二种是第一个数比第二个数小。

那么如果\(a_i<b_i\)，这对数一定要放在第二种，否则放在第一种。

考虑第一种数列，要让数列形成波浪形，就要满足\(b_{i-1}<a_i\)，又因为\(b_{i-1}<a_{i-1}\)，所以只要按照a从小到大排序即可。对于第二种数列同理。

#include<bits/stdc++.h>
#define qmin(x,y) (x=min(x,y))
#define qmax(x,y) (x=max(x,y))
#define pir pair<int,int>
#define mp(x,y) make_pair(x,y)
#define fr first
#define sc second
#define rsort(x,y) sort(x,y),reverse(x,y)
#define vic vector<int>
#define vit vic::iterator
using namespace std;

char gc() {
//	static char buf[100000],*p1,*p2;
//	return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;
	return getchar();
}

template<class T>
int read(T &ans) {
	T f=1;ans=0;
	char ch=gc();
	while(!isdigit(ch)) {
		if(ch==EOF) return EOF;
		if(ch=='-') f=-1;
		ch=gc();
	}
	while(isdigit(ch))
		ans=ans*10+ch-'0',ch=gc();
	ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
	return read(a)==EOF?EOF:read(b);
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
	return read(a,b)==EOF?EOF:read(c);
}

typedef long long ll;
const int Maxn=1100000;
const int inf=0x3f3f3f3f;
const ll mod=998244353;

int n,a[Maxn],b[Maxn],tot,cnt;
pir c[Maxn],d[Maxn];

int main() {
//	freopen("test.in","r",stdin);
	read(n);
	for(int i=1;i<=n;i++) {
		read(a[i],b[i]);
		if(a[i]<=b[i]) c[++tot]=mp(a[i],i);
		else d[++cnt]=mp(a[i],i);
	}
	if(tot>cnt) {
		printf("%d\n",tot);
		rsort(c+1,c+tot+1);
		for(int i=1;i<=tot;i++) printf("%d ",c[i].sc);
	}
	else {
		printf("%d\n",cnt);
		sort(d+1,d+cnt+1);
		for(int i=1;i<=cnt;i++) printf("%d ",d[i].sc);
	}
	return 0;
}

E - Earth Wind and Fire

首先石子的相对顺序是不会改变的，因为如果一个石子在移动的过程中跨过了另一个石子，那么只需要把这个石子移动到那个石子上，然后移动那个石子即可。

这样，对于每一个石子，就确定下来最终要移动到哪个位置，记向右走为正，向左走为负，对偏移量做一个类似括号序列的东西即可。

#include<bits/stdc++.h>
#define qmin(x,y) (x=min(x,y))
#define qmax(x,y) (x=max(x,y))
#define pir pair<int,int>
#define mp(x,y) make_pair(x,y)
#define fr first
#define sc second
#define rsort(x,y) sort(x,y),reverse(x,y)
#define vic vector<int>
#define vit vic::iterator
using namespace std;

char gc() {
//	static char buf[100000],*p1,*p2;
//	return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;
	return getchar();
}

template<class T>
int read(T &ans) {
	T f=1;ans=0;
	char ch=gc();
	while(!isdigit(ch)) {
		if(ch==EOF) return EOF;
		if(ch=='-') f=-1;
		ch=gc();
	}
	while(isdigit(ch))
		ans=ans*10+ch-'0',ch=gc();
	ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
	return read(a)==EOF?EOF:read(b);
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
	return read(a,b)==EOF?EOF:read(c);
}

typedef long long ll;
const int Maxn=1100000;
const int inf=0x3f3f3f3f;
const ll mod=998244353;

int n,top,s[Maxn],tot;
ll a[Maxn],b[Maxn];
pair<ll,int> p[Maxn];
pair<pir,ll> ans[Maxn];

void add(int x,int y,int z) {
	ans[++tot]=mp(mp(x,y),z);
}

int main() {
//	freopen("test.in","r",stdin);
	read(n);
	for(int i=1;i<=n;i++) read(a[i]),p[i]=mp(a[i],i);
	for(int i=1;i<=n;i++) read(b[i]);
	sort(p+1,p+n+1);
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++) a[i]=b[i]-p[i].fr;
	ll temp=0;
	for(int i=1;i<=n;i++) temp+=a[i];
	if(temp) return 0*puts("NO");
	for(int i=1;i<=n;i++) {
		if(a[i]<0) {
			while(top) {
				int temp=min(-a[i],a[s[top]]);
				if(!temp) {
					top--;
					continue;
				}
				add(p[s[top]].sc,p[i].sc,min(-a[i],a[s[top]]));
				a[i]+=temp;
				a[s[top]]-=temp;
				if(a[i]==0) break;
			}
			if(a[i]<0) return 0*puts("NO");
		}
		else s[++top]=i;
	}
	puts("YES");
	printf("%d\n",tot);
	for(int i=1;i<=tot;i++) {
		printf("%d %d %I64d\n",ans[i].fr.fr,ans[i].fr.sc,ans[i].sc);
	}
	return 0;
}

F - Foo Fighters

从低位到高位考虑，枚举每个最高位等于这个位的数，计算出其当前的实际价值，然后求和，如果和的符号和整体的和的符号相同，那么就将这一位变号。每一个数只会被访问到一次，时间复杂度为\(O(n2^n)\)。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
#define qmin(x,y) (x=min(x,y))
#define qmax(x,y) (x=max(x,y))
#define vic vector<int>
#define vit vic::iterator
#define pir pair<int,int>
#define fr first
#define sc second
#define mp(x,y) make_pair(x,y)
#define rsort(x,y) sort(x,y),reverse(x,y)
using namespace std;

inline char gc() {
//	static char buf[100000],*p1,*p2;
//	return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
	return getchar();
}

template<class T>
int read(T &ans) {
	ans=0;char ch=gc();T f=1;
	while(!isdigit(ch)) {
		if(ch==EOF) return -1;
		if(ch=='-') f=-1;
		ch=gc();
	}
	while(isdigit(ch))
		ans=ans*10+ch-'0',ch=gc();
	ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
	return read(a)!=EOF&&read(b)!=EOF?2:EOF;
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
	return read(a,b)!=EOF&&read(c)!=EOF?3:EOF;
}

typedef long long ll;
const int Maxn=1100000;
const int inf=0x3f3f3f3f;

int n;
ll s,ans;
pair<ll,ll> a[Maxn];

ll work(ll x) {
	ll f=1;
	while(x) {
		if(x&1) f*=-1;
		x>>=1;
	}
	return f;
}

signed main() {
//	freopen("test.in","r",stdin);
	read(n);
	for(int i=1;i<=n;i++) read(a[i].fr,a[i].sc);
	for(int i=1;i<=n;i++) s+=a[i].fr;
	sort(a+1,a+n+1,[&](pair<ll,ll> a,pair<ll,ll> b) {
		return a.sc<b.sc;
	});
	a[n+1].sc=0x7fffffffffffffff;
	int temp=1;
	for(ll i=2;temp<=n;i<<=1) {
		int x=temp;
		while(a[x].sc<i) x++;
		ll sum=0;
		for(int j=temp;j<x;j++) sum+=work(a[j].sc&ans)*a[j].fr;
		if((sum<0)==(s<0)&&(sum>0)==(s>0)) ans|=(i>>1);
		temp=x;
	}
	printf("%lld\n",ans);
	return 0;
}

G - Gold Experience

首先贪心地求出来补图中的一个独立集，这个独立集中每对数其最大公约数大于一，这个可以用莫比乌斯函数在\(2^8\)的时间内求出。

如果独立集大小大于等于\(k\)，那么就得到了答案，否则的话补图中的联通块数一定小于\(k\)，因为\(k<2n\)那么点数不为1的联通块中的总点数也一定大于\(k\)。那么就把这些点找出来即可，可以用整体二分。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
#define qmin(x,y) (x=min(x,y))
#define qmax(x,y) (x=max(x,y))
#define vic vector<int>
#define vit vic::iterator
#define pir pair<int,int>
#define fr first
#define sc second
#define mp(x,y) make_pair(x,y)
#define rsort(x,y) sort(x,y),reverse(x,y)
using namespace std;

inline char gc() {
//	static char buf[100000],*p1,*p2;
//	return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
	return getchar();
}

template<class T>
int read(T &ans) {
	ans=0;char ch=gc();T f=1;
	while(!isdigit(ch)) {
		if(ch==EOF) return -1;
		if(ch=='-') f=-1;
		ch=gc();
	}
	while(isdigit(ch))
		ans=ans*10+ch-'0',ch=gc();
	ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
	return read(a)!=EOF&&read(b)!=EOF?2:EOF;
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
	return read(a,b)!=EOF&&read(c)!=EOF?3:EOF;
}

typedef long long ll;
const int Maxn=110000;
const int Maxm=11000000;
const int inf=0x3f3f3f3f;

int bj[Maxm],pi[Maxm],tot,f[Maxm],mu[Maxm];
int n,a[Maxn],k;
vic A,B,C[Maxn],d[Maxn];
pir p[Maxn];

void pre(int x) {
	mu[1]=1;
	for(int i=2;i<=x;i++) {
		if(!bj[i]) {
			pi[++tot]=i;
			f[i]=tot;
			mu[i]=-1;
		}
		int j=0,temp;
		while((temp=i*pi[++j])<=x) {
			bj[temp]=1;
			f[temp]=j;
			if(i%pi[j]==0) {
				mu[temp]=mu[i]*pi[j];
				break;
			}
			mu[temp]=mu[i]*mu[pi[j]];
		}
	}
}

int query(int x,int cnt,int y) {
	if(cnt==d[x].size()) return bj[y];
	return query(x,cnt+1,y)+query(x,cnt+1,y*d[x][cnt]);
}

void add(int x,int cnt,int y) {
	if(cnt==d[x].size()) {
		bj[y]+=mu[y];
		return ;
	}
	add(x,cnt+1,y),add(x,cnt+1,y*d[x][cnt]);
}

void del(int x,int cnt,int y) {
	if(cnt==d[x].size()) {
		bj[y]=0;
		return ;
	}
	del(x,cnt+1,y),del(x,cnt+1,y*d[x][cnt]);
}

void solve(int l,int r,vic v) {
	if(v.empty()) return ;
	if(l==r) {
		C[l]=v;
		return ;
	}
	vic ls,rs;
	int mid=l+r>>1;
	for(int i=l;i<=mid;i++) add(A[i],0,1);
	for(auto i:v)
		if(query(i,0,1)) ls.push_back(i);
		else rs.push_back(i);
	for(int i=l;i<=mid;i++) del(A[i],0,1);
	solve(l,mid,ls),solve(mid+1,r,rs);
}

signed main() {
//	freopen("test.in","r",stdin);
	read(n,k);
	for(int i=1;i<=n;i++) read(a[i]);
	pre(10000000); memset(bj,0,sizeof(bj));
	for(int i=1;i<=n;i++) {
		int x=a[i];
		while(x!=1) {
			int y=pi[f[x]];
			d[i].push_back(y);
			while(x%y==0) x/=y;
		}
		if(!query(i,0,1)) A.push_back(i),add(i,0,1);
		else B.push_back(i);
	}
	if(A.size()>=k) {
		for(int i=0;i<k;i++) printf("%d ",A[i]);
		return 0;
	}
	for(auto i:A) del(i,0,1);
	solve(0,A.size()-1,B);
	int sum=0;
	for(int i=0;i<A.size();i++) p[i]=mp(C[i].size(),i);
	rsort(p,p+A.size());
	for(int i=0;i<A.size();i++) {
		sum+=p[i].fr+1;
		if(sum>=k) {
			int ned=k-(i+1)*2;
			vic ans;
			for(int j=0;j<=i;j++) {
				int x=min(p[j].fr-1,ned);
				ned-=x;
				x++; ans.push_back(A[p[j].sc]);
				for(int k=0;k<x;k++) ans.push_back(C[p[j].sc][k]);
			}
			for(auto i:ans) printf("%d ",i);
			return 0;
		}
	}
	return 0;
}

推荐阅读