在Master卡了半年终于上International Master 了!

A

做这题千万不能着急。我卡了二十分钟左右。
一开始以为存在一对\((x,y)\)和\((y,x)\)答案就会++。不过这样根本过不了样例。
我仔细分析了一下，一个\((x,y)\)可以直接移动到\((x,x)\)和\((y,y)\)。但是可能会和某一些棋子冲突。所以我们将一个棋子和可以一步达到的位置连接一条边就可以发现，如果存在一个环答案++。
在进一步，对于每一个棋子的位置\((x,y)\)，将\(x,y\)连接一条边。然后就是要数环的个数。
由于最终的图是由简单环和链构成的，所以直接上dsu就可以了。

/*
{
######################
#       Author       #
#        Gary        #
#        2020        #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
//    int x=0;
//    char ch=getchar();
//    while(ch<'0'||ch>'9'){
//        ch=getchar();
//    }
//    while(ch>='0'&&ch<='9'){
//        x=(x<<1)+(x<<3)+(ch^48);
//        ch=getchar();
//    }
//    return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
int fa[100000+20];
int root(int x){
	if(fa[x]==x) return x;
	return fa[x]=root(fa[x]);
}
void solve(){
	int n,m;
	scanf("%d%d",&n,&m);
	rb(i,1,n) fa[i]=i;
	int rest=m;
	rb(i,1,m){
		int x,y;
		scanf("%d%d",&x,&y);
		if(x==y){
			rest--;
			continue;
		}
		if(root(x)==root(y)) rest++;
		fa[root(x)]=root(y);
	}
	printf("%d\n",rest);
}
int main(){
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

B

可以发现对于每一个对，肯定是以下四个中的一个：
\((0,0),(0,1),(1,1),(1,0)\)。
可以发现如果0的个数固定了，也就固定了有多少个\((0,0)\)和\((1,1)\)。
也就是说\((1,0)\)和\((0,1)\)的数量之和是定值。
然后就可以贪心了，如果\(x>y\)，就将填补的某一段前缀填1，后缀填0。反之亦然。
时间复杂度\(O(N)\)。

/*
{
######################
#       Author       #
#        Gary        #
#        2020        #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
//    int x=0;
//    char ch=getchar();
//    while(ch<'0'||ch>'9'){
//        ch=getchar();
//    }
//    while(ch>='0'&&ch<='9'){
//        x=(x<<1)+(x<<3)+(ch^48);
//        ch=getchar();
//    }
//    return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
int sum[2][100000+20];
int main(){
	string s;
	cin>>s;
	int n=s.length();
	int x,y;
	cin>>x>>y;
	LL rest=0;
	vector<int> pos;
	rb(i,1,n){
		sum[0][i]=sum[0][i-1];
		sum[1][i]=sum[1][i-1];
		if(s[i-1]!='?'){
			if(s[i-1]=='0'){
				rest+=1ll*sum[1][i]*y;
			}
			else{
				rest+=1ll*sum[0][i]*x;
			}
			sum[s[i-1]-'0'][i]++;
		}
		else{
			pos.PB(i);
		}
	}
	LL tmp=0;
		for(auto it:pos){
			tmp+=1ll*(sum[1][n]-sum[1][it])*x+1ll*(sum[1][it])*y;
		} 
	if(x>y){
		//1放后
		LL tmptmp=tmp;
		rep(i,pos.size()){
			tmp-=1ll*(sum[1][pos[i]]+i)*y;
			tmp-=1ll*(sum[1][n]-sum[1][pos[i]])*x;
			tmp+=1ll*(sum[0][n]-sum[0][pos[i]]+pos.size()-i-1)*y;
			tmp+=1ll*(sum[0][pos[i]])*x;
			check_min(tmptmp,tmp);
		}
		rest+=tmptmp;
	}
	else{
		//1放钱
		LL tmptmp=tmp;
		if(pos.size())
			rl(i,pos.size()-1,0){
				tmp-=1ll*(sum[1][n]-sum[1][pos[i]]+pos.size()-i-1)*x;
				tmp-=1ll*(sum[1][pos[i]])*y;
				tmp+=1ll*(sum[0][n]-sum[0][pos[i]])*y;
				tmp+=1ll*(sum[0][pos[i]]+i)*x;
				check_min(tmptmp,tmp);
			}
		rest+=tmptmp;
	}
	cout<<rest<<endl;
	return 0;
}

C

肯定有一些位置是正代价，有一些是负代价。然后在纸上算一算正负的可能分布，然后就可以了。

/*
{
######################
#       Author       #
#        Gary        #
#        2020        #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
//    int x=0;
//    char ch=getchar();
//    while(ch<'0'||ch>'9'){
//        ch=getchar();
//    }
//    while(ch>='0'&&ch<='9'){
//        x=(x<<1)+(x<<3)+(ch^48);
//        ch=getchar();
//    }
//    return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
int have[100];
int need[100];
int main(){
	int n;
	LL t;
	cin>>n>>t;
	string s;
	cin>>s;
	t-=(1<<(s[n-1]-'a'));
	t+=(1<<(s[n-2]-'a'));
	LL sum=0;
	rb(i,0,n-3) sum=sum+(1<<(s[i]-'a'));
	t+=sum;
	if(t%2==1||t<0){
		puts("No");
		return 0;
	}
	t/=2;
	rb(i,0,n-3) have[s[i]-'a']++;
	rep(i,60) need[i]=(t>>i)&1;
	rep(i,60){
		if(need[i]&&!have[i]){
			puts("No");
			return 0;
		}
		if(need[i]) have[i]--;
		have[i+1]+=have[i]/2;
	}
	puts("Yes");
	return 0;
}

D

暂无

E

搞出每一个点的SG值。
然后设\(dp[i]\)表示当前的值为i，然后胜利的概率。
转移:
\(p(x) = \frac{(x = 0)}{N+1} + \sum_{i=1}^N \frac{1}{N+1} p(x \oplus g_i)\)

高斯消元即可。
代码暂无