【补题日记】2018 CCPC桂林站

Pro

2018 China Collegiate Programming Contest - Guilin Site

Sol

A. Array Merge

贪心,如果没有顺序的限制,数字大的越靠前越优,而现在有顺序,所以把前i个元素综合考虑。

设前i个元素的平均值为a,则当新的值A[i+1]放进来的时候,判断A[i+1]最远能合并到哪,就把A[i+1]与放到该集合。

为什么扯到合并和集合了呢?因为这个题目本质上与不考虑位置时差不多,就是先分组然后A,B两个分完之后的集合分别看先放哪个最优。

写的时候遇到了一个问题,对2 1 5 2分组的时候,可能会把1和5分到一组,但其实把2 1 5放到一起会更好,因为会让平均值更大,注意这个地方就可以了。

D. Bits Reverse

可以发现,交换三位数字其实就是交换奇数位置或者偶数位置上的数字。

所以,如果x和y的奇数位或者偶数位的数字个数不同,答案为-1。其他情况为查询x中奇(偶)出现的位置与y中奇(偶)出现的位置。

二者位置差值除以二的求和就是答案。

G. Greatest Common Divisor

类似于更相减损,排序去重后,然后判断a[1]+k,与a[2]-a[1],a[3]-a[2],a[4]-a[3]等的gcd是否大于1

因为k是要求的值,所以分以下几种情况:

1.后面几个数字(除a[1]+k之外的数字,下同)的gcd=1,总的gcd一定等于1

2.gcd!=1,则可以通过枚举gcd的因子求得最小的k(具体看代码最后部分)

J. Stone Game

贪心,容易想到判断尽可能拿走的数目的奇偶性。

尽可能拿走的数目就是排序之后分几种情况累加的结果。从小到大排序后,依次修改每一个点。

对于i点,如果两边都比它的值大,那么这个点可以被完全拿走。

如果两边都比它的值小,那么这个点就可以被拿成左右两端最大值加1。

如果两边一个大一个小,那么这个点就可以被拿成左右两端最小值加1。

(特意用了排比句ovo)

Code

A. Array Merge

//By cls1277
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<sstream>
#include<set>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
#define PI acos(-1)
#define INF 2147483647
#define eps 1e-7
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define lowbit(_) _&(-_)
#define mk(_,__) make_pair(_,__)
#define pii pair<LL,LL>
#include <fstream>
#define ls x<<1
#define rs x<<1|1
#define endl '\n'
inline LL read() {
	LL x = 0, f = 1;char c = getchar();
	while (!isdigit(c)) { if (c == '-')f = -f;c = getchar(); }
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48ll), c = getchar();
	return x * f;
}

const LL maxn = 1e5+5;
LL n,m,a[maxn],b[maxn],p1,p2,l1,l2,tt,res,f1,f2;
vector<LL>ans;
struct Node {
	LL sum,cnt;
	Node(){};
	Node(LL ss , LL cc) {
		sum=ss , cnt=cc;
	}
	bool operator < (const Node &tmp) {
		return sum*tmp.cnt<cnt*tmp.sum;
	}
	Node operator + (const Node &tmp) {
		return Node(sum+tmp.sum,cnt+tmp.cnt);
	}
};
Node va[maxn],vb[maxn];

int main() {
	ios::sync_with_stdio(false);
	#ifdef DEBUG
	freopen("data.txt","r",stdin);
	#endif
	LL T; cin>>T;
	while(T--) {
		cout<<"Case "<<(++tt)<<": ";
		ans.clear();
		p1=p2=0; res=0;
		cin>>n>>m;
		Fo(i,1,n) cin>>a[i];
		Fo(i,1,m) cin>>b[i];
		Fo(i,1,n) {
			va[++p1] = Node(a[i],1);
			while(p1>1&&va[p1-1]<va[p1]) {
				va[p1-1] = va[p1-1]+va[p1];
				p1--;
			}
		}
		Fo(i,1,m) {
			vb[++p2] = Node(b[i],1);
			while(p2>1&&vb[p2-1]<vb[p2]) {
				vb[p2-1] = vb[p2-1]+vb[p2];
				p2--;
			}
		}
		va[++p1]=vb[++p2]=Node(-INF,1);
		//Fo(i,1,p1) cout<<va[i].sum<<" "<<va[i].cnt<<endl;
		//Fo(i,1,p2) cout<<vb[i].sum<<" "<<vb[i].cnt<<endl;
		l1=l2=1; f1=f2=1;
		while(f1<p1 || f2<p2) {
			if(va[f1]<vb[f2]) {
				for(LL i=l1; i<=l1+vb[f2].cnt-1; i++)
					ans.push_back(b[i]);
				l1+=vb[f2].cnt;
				f2++;
			} else {
				for(LL i=l2; i<=l2+va[f1].cnt-1; i++)
					ans.push_back(a[i]);
				l2+=va[f1].cnt;
				f1++;
			}
		}
		Fo(i,1,n+m)
			res+=i*ans[i-1];
		cout<<res<<endl;
	}
	return 0;
}

D. Bits Reverse

//By cls1277
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<sstream>
#include<set>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
#define PI acos(-1)
#define INF 2147483647
#define eps 1e-7
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define lowbit(_) _&(-_)
#define mk(_,__) make_pair(_,__)
#define pii pair<int,int>
#define ls x<<1
#define rs x<<1|1
#define endl '\n'
inline LL read() {
	LL x = 0, f = 1;char c = getchar();
	while (!isdigit(c)) { if (c == '-')f = -f;c = getchar(); }
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48ll), c = getchar();
	return x * f;
}

const LL maxn = 60;
LL a[maxn],b[maxn],p,f1,f2,c[maxn],d[maxn],ans,x,y,tt;

int main() {
	ios::sync_with_stdio(false);
	#ifdef DEBUG
	freopen("data.txt","r",stdin);
	#endif
	int T; cin>>T;
	while(T--) {
		cout<<"Case "<<(++tt)<<": ";
		ans=0;
		Ms(a,0); Ms(b,0);
		cin>>x>>y;
		p=0;
		while(x) {
			a[p++] = x%2;
			x/=2;
		}
		p=0;
		while(y) {
			b[p++] = y%2;
			y/=2;
		}
		f1=f2=0;
		for(int i=59; i>=0; i-=2) {
			if(a[i]) c[f1++]=i;
			if(b[i]) d[f2++]=i;
		}
		if(f1!=f2) {
			cout<<"-1"<<endl;
			continue;
		}
		for(int i=0; i<f1; i++)
			ans+=abs(d[i]-c[i])/2;
		f1=f2=0;
		for(int i=58; i>=0; i-=2) {
			if(a[i]) c[f1++]=i;
			if(b[i]) d[f2++]=i;
		}
		if(f1!=f2) {
			cout<<"-1"<<endl;
			continue;
		}
		for(int i=0; i<f1; i++)
			ans+=abs(d[i]-c[i])/2;
		cout<<ans<<endl;
	}
	return 0;
}

G. Greatest Common Divisor

//By cls1277
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<sstream>
#include<set>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
#define PI acos(-1)
#define INF 2147483647
#define eps 1e-7
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define lowbit(_) _&(-_)
#define mk(_,__) make_pair(_,__)
#define pii pair<int,int>
#define ls x<<1
#define rs x<<1|1
#define endl '\n'
inline LL read() {
	LL x = 0, f = 1;char c = getchar();
	while (!isdigit(c)) { if (c == '-')f = -f;c = getchar(); }
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48ll), c = getchar();
	return x * f;
}

const LL maxn = 1e5+5;
int T , tt , n , a[maxn] , _n;

int gcd(int x , int y) {
	return y?gcd(y,x%y):x;
}

int main() {
	ios::sync_with_stdio(false);
	#ifdef DEBUG
	freopen("data.txt","r",stdin);
	#endif
	cin>>T;
	while(T--) {
		int cnt1=0 , cnt2=0;
		cin>>n;
		if(n==1) {
			int m; cin>>m;
			if(m>1) {
				cout<<"Case "<<(++tt)<<": 0"<<endl;
			} else {
				cout<<"Case "<<(++tt)<<": 1"<<endl;
			}
		} else {
			int dd = 0;
			Fo(i,1,n) {
				int m; cin>>m;
				if(!dd) dd = m;
				else dd = gcd(dd , m);
				a[i] = m;
				if(m%2) cnt1++;
				else cnt2++;
			}
			if(dd>1||!cnt1) {
				cout<<"Case "<<(++tt)<<": 0"<<endl;
			} else if(!cnt2) {
				cout<<"Case "<<(++tt)<<": 1"<<endl;
			} else {
				sort(a+1 , a+n+1);
				_n = unique(a+1 , a+n+1)-a-1;
				if(_n==1) {
					cout<<"Case "<<(++tt)<<": 0"<<endl;
					continue;
				}
				int gg = a[2]-a[1];
				Fo(i,3,n) {
					gg = gcd(gg,a[i]-a[i-1]);
				}
				if(gg==1) cout<<"Case "<<(++tt)<<": -1"<<endl;
				else {
					int res = INF;
					Fo(j,1,sqrt(gg)) {
						if(gg%j==0) {
							if(j!=1) res = min(res , (int)(ceil(a[1]*1.0/j)*j-a[1]));
							res = min(res , (int)(ceil(a[1]*1.0/(gg/j))*(gg/j)-a[1]));
						}
					}
					cout<<"Case "<<(++tt)<<": "<<res<<endl;
				}
			}
		}
	}
	return 0;
}

J. Stone Game

//By cls1277
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<sstream>
#include<set>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
#define PI acos(-1)
#define INF 2147483647
#define eps 1e-7
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define lowbit(_) _&(-_)
#define mk(_,__) make_pair(_,__)
#define pii pair<int,int>
#define ls x<<1
#define rs x<<1|1
#define endl '\n'
inline LL read() {
	LL x = 0, f = 1;char c = getchar();
	while (!isdigit(c)) { if (c == '-')f = -f;c = getchar(); }
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48ll), c = getchar();
	return x * f;
}

const LL maxn = 1e5+5;
struct Node {
	int num , 	ops;
	Node(){};
	Node(int nn , int pp) {
		num=nn , ops=pp;
	}
};
int T,n,a[maxn],tt;
Node b[maxn];

bool operator < (const Node &b , const Node &c) {
	return b.num<c.num;
}

int main() {
	ios::sync_with_stdio(false);
	#ifdef DEBUG
	freopen("data.txt","r",stdin);
	#endif
	int T;
	cin>>T;
	while(T--) {
		cout<<"Case "<<(++tt)<<": ";
		cin>>n;
		int ans=0;
		Fo(i,1,n) {
			cin>>a[i];
			b[i]=Node(a[i],i);
		}
		if(n==1) {
			ans = a[1];
			if(ans%2) cout<<"Alice"<<endl;
			else cout<<"Bob"<<endl;
			continue;
		}
		sort(b+1,b+n+1);
		Fo(i,1,n) {
			Node u=b[i];
			if(u.ops==1) {
				if(a[u.ops+1]<=a[u.ops]) {
					ans+=a[u.ops]-a[u.ops+1]-1;
					a[u.ops] = a[u.ops+1]+1;
				} else {
					ans+=a[u.ops];
					a[u.ops] = 0;
				}
			} else if(u.ops==n) {
				if(a[u.ops-1]<=a[u.ops]) {
					ans+=a[u.ops]-a[u.ops-1]-1;
					a[u.ops] = a[u.ops-1]+1;
				} else {
					ans+=a[u.ops];
					a[u.ops] = 0;
				}				
			} else {
				if(a[u.ops]<a[u.ops-1]&&a[u.ops]<a[u.ops+1]) {
					ans+=a[u.ops];
					a[u.ops] = 0;
				} else if(a[u.ops]>=a[u.ops-1]&&a[u.ops]>=a[u.ops+1]) {
					ans+=a[u.ops]-max(a[u.ops-1],a[u.ops+1])-1;
					a[u.ops] = max(a[u.ops-1],a[u.ops+1])+1;
				} else {
					if(a[u.ops]<a[u.ops-1]) {
						ans+=a[u.ops]-a[u.ops+1]-1;
						a[u.ops] = a[u.ops+1]+1;
					} else {
						ans+=a[u.ops]-a[u.ops-1]-1;
						a[u.ops] = a[u.ops-1]+1;
					}
				}
			}
		}
		//cout<<ans<<endl;
		if(ans%2) cout<<"Alice"<<endl;
		else cout<<"Bob"<<endl;
	}
	return 0;
}

上一篇:cookie对象的使用


下一篇:Python一键转Jar包 Java调用Python