题解 Codeforces Global Round 4

集训期间摸空打一场，打得身心俱疲..(* ￣︿￣)

standing:3122/7230 rate: -35 1500 → 1465

A. Prime Minister

出师不利..不知道为什么当时就是看不懂题面。一直不理解什么是"a strict majority"，以为是什么众数之类的..其实就是“绝对多数的”意思..还有一直以为要在议会里开派对..

然后，又因为“严格大于”而wa了一次，时间拖了很久，然后又被砍掉了50分..(#｀-_ゝ-)

#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX=105;
int n,tot,add;
int a[MAX],rec[MAX];

int main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in","r",stdin);
	#endif

	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i],tot+=a[i];

	rec[++rec[0]]=1; add+=a[1];
	for(int i=2;i<=n;++i) if(a[1]>=2*a[i]) rec[++rec[0]]=i,add+=a[i];

	if(add*2>tot){
		printf("%d\n",rec[0]);
		for(int i=1;i<=rec[0];++i) cout<<rec[i]<<" ";
	}
	else cout<<0<<endl;

	return 0;
}

B. WOW Factor

这道题倒是没什么难点，但是，翻译又出锅了..≡(▔﹏▔)≡
没有注意到"v"必须连续才算一个"w"..

#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int MAX=1e6+5;
char s[MAX];
int len;
ll tot,cnt,ans;
ll lx[MAX];

int main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in","r",stdin);
	#endif

	scanf("%s",s+1);
	len=strlen(s+1);
	lx[0]=1;
	for(int i=1;i<=len;++i){
		if(s[i]==‘o‘) lx[0]++;
		else lx[lx[0]]++;
	}
	for(int i=1;i<=lx[0];++i) if(lx[i]) lx[i]--;
	for(int i=1;i<=lx[0];++i) tot+=lx[i];
	for(int i=1;i<lx[0];++i) cnt+=lx[i],tot-=lx[i],ans+=cnt*tot;
	cout<<ans<<endl;

	return 0;
}

C. Tiles

这题倒是比较顺利地推导出来了\(ans=s^{h+w}\)，然后？看着int范围的模数硬是没有注意到要用long long

#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int MOD=998244353;
int h,w;

int qsm(int a,int b,int mod);

int main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in","r",stdin);
	#endif

	cin>>h>>w;
	cout<<qsm(2,h+w,MOD);

	return 0;
}

int qsm(int a,int b,int m){
	ll ans=1,c=a,mod=m;
	while(b){
		if(b&1) ans*=c,ans%=mod;
		c*=c,c%=mod;
		b>>=1;
	}
	return (int)ans;
}

D. Prime Graph

这道题..考场的时候有点怀疑人生，这世上难道还有这种巧妙的算法？看题解，哦，原来又是codeforce式的的构造题..

考试的时候尝试按照质数枚举遍，然后加上一点剪枝优化的爆搜取判节点度数的可行性。看起来可行，但有一个难以解决的问题是：知道了每个节点的度数之后怎么反过来构造出图..怀疑是这里的算法出了点问题..

而正解是：构造，而且有一个特别奇怪的规律。构造方法是，首先给每一个点连上两条边，构成一个环。酱紫的话每一个节点的度数是2，满足条件。但是边则不然。发现紧接着2的下一个质数就是3，所以我们可以为每两个节点再连一条边，同时保证度数是质数。然后！题解指出：对于\(n\in [3,1000]\)满足再\([n,\lfloor\frac{3\times n}{2}\rfloor]\)分布着至少一个质数.即这么做可以保证取到合适的边，满足边条数是质数的限制。这..看不出来就认了吧（〃｀ 3′〃）

#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
 
const int MAX=1e6+5,TOP=1e6;
 
bool vis[MAX]; int prime[MAX];
int n,ans;
 
void oula();
int lower_bound(int);
 
int main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in","r",stdin);
	#endif
 
	oula();
 
	cin>>n;
 
	ans=lower_bound(n);
	cout<<ans<<endl;
	for(int i=1;i<n;++i){
		cout<<i<<" "<<i+1<<endl;
	}
	cout<<n<<" "<<1<<endl;
 
	for(int i=1;i<=ans-n;++i){
		cout<<i<<" "<<i+(n>>1)<<endl;
	}
 
	return 0;
}
 
void oula(){
	for(int i=2;i<=TOP;++i){
		if(!vis[i]) prime[++prime[0]]=i;
		for(int j=1;j<=prime[0]&&prime[j]*i<=TOP;++j){
			vis[prime[j]*i]=true;
			if(i%prime[j]==0) break;
		}
	}
}
 
int lower_bound(int n){
	int l=1,r=prime[0];
	while(l<=r){
		int mid=(l+r)>>1;
		if(prime[mid]>=n) r=mid-1;
		else l=mid+1;
	}
	return prime[l];
}

剩下的..

集训期间需要学的实在是太多了，有点顾不上..

今天是7.21，才刚刚开始，我！，一定要！别被虐死了

Codeforces Global Round 4

原文：https://www.cnblogs.com/ticmis/p/13210858.html