在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
",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))
高斯消元即可。
/*
{
######################
# 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;
/*}
*/
const int MAXN=1e5+20;
int sg[MAXN];
vector<int> g[MAXN];
int n,m;
bool vis[MAXN];
void dfs(int now){
vis[now]=1;
for(auto it:g[now]) if(!vis[it]) dfs(it);
vector<int> sgg;
for(auto it:g[now]) sgg.PB(sg[it]);
sort(ALL(sgg));
sgg.erase(unique(ALL(sgg)),sgg.end());
sg[now]=-1;
rep(i,sgg.size()){
if(sgg[i]!=i){
sg[now]=i;
break;
}
}
if(sg[now]==-1) sg[now]=sgg.size();
}
const int MAQ=511;
const int MOD=998244353 ;
int mat[MAQ+1][MAQ+10];
LL quick(LL A,LL B){
if(B==0) return 1;
LL tmp=quick(A,B>>1);
tmp*=tmp;
tmp%=MOD;
if(B&1)
tmp*=A,tmp%=MOD;
return tmp;
}
LL pro;
void gauss(){
rb(i,0,MAQ){
int is=-1;
rb(j,i,MAQ){
if(mat[j][i]){
is=j;
break;
}
}
if(is==-1) continue;
swap(mat[i],mat[is]);
int inv=quick(mat[i][i],MOD-2);
rb(j,0,MAQ+1) mat[i][j]=1ll*mat[i][j]*inv%MOD;
rb(j,0,MAQ){
if(j!=i)
if(mat[j][i]){
rb(k,0,MAQ+1){
if(k!=i)
mat[j][k]-=1ll*mat[j][i]*mat[i][k]%MOD,mat[j][k]+=MOD,mat[j][k]%=MOD;
}
mat[j][i]=0;
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
rb(i,1,m){
int u,v;
scanf("%d%d",&u,&v);
g[u].PB(v);
}
pro=quick(n+1,MOD-2);
rb(i,1,n) if(!vis[i]) dfs(i);
rb(i,0,MAQ){
mat[i][i]=1;
rb(j,1,n){
mat[i][i^sg[j]]+=(MOD-pro);
mat[i][i^sg[j]]%=MOD;
}
mat[i][MAQ+1]=pro*(i==0);
}
gauss();
int res=1-mat[0][MAQ+1]+MOD;
res%=MOD;
printf("%d
",res);
return 0;
}