专栏文章

题解：P13028 [GCJ 2021 #1A] Hacked Exam

ggcx12012
P13028题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioznulc
此快照首次捕获于
2025/12/03 03:46
3 个月前
此快照最后确认于
2025/12/03 03:46
3 个月前
查看原文

前言

小清新组合计数题，但是代码写的太史了有点难受。

Solution

首先 N≤2N\le 2 的情形是简单的，请读者自行思考。
这里直接考虑 N=3N=3。由于 TT 比较大，显然我们需要一个单次 O(Q3)O(Q^3) 的做法。
一列大概有 88 个状态，然后 FFT 和 TTF 是本质相同的，于是一列只有 44 个不同状态，除去三个字符都相同的情况，只有 FFT，FTF，TFF 三种本质不同的状态，表示是否取出现次数较少的那个字符，设它们各有 c1,c2,c3c_1,c_2,c_3 个，三个字符相同的有 c4c_4 个，我们直接枚举 i≤c1,j≤c2,k≤c3i\le c_1,j\le c_2,k\le c_3 即可，然后在 a1−i=a2−j=a3−ka_1-i=a_2-j=a_3-k 的前提下把合法方案数 (c1i)(c2j)(c3k)(c4a1−i)\binom{c_1}{i}\binom{c_2}{j}\binom{c_3}{k}\binom{c_4}{a_1-i} 加进 sumsum 中。算每一位 T 和 F 的出现次数也是简单的，在总方案的基础上改动一下即可，然后取较大值加进 ansans 里，最后的答案就是 anssum\frac{ans}{sum}。
时间复杂度应该是 O(TQ3)O(TQ^3) 的，实际上只跑了 71ms。
还是晒一下代码把，不喜勿喷。
CPP
#include<bits/stdc++.h>
#include<cmath>
#define ll long long
#define ld long double
#define ull unsigned long long
#define lll __int128
#define N 500010
#define For(i,a,b) for(ll i=a;i<=b;++i)
#define Rof(i,a,b) for(ll i=a;i>=b;--i)
#define ls x<<1
#define rs x<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define mk make_pair
#define pb push_back
#define pii pair<ll,ll>
#define pque priority_queue
#define fi first
#define se second

using namespace std;
lll C[130][130];
char s[3][210];
int T,n,m,a[3];

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void sc(lll x){
	if(x>=10) sc(x/10);
	int p=x%10;
	cout<<p;
}
lll gcd(lll x,lll y){
	if(!y) return x;
	return gcd(y,x%y);
}
void fenshu(lll x,lll y){
	lll d=gcd(x,y);
	x/=d,y/=d;
	cout<<' ';
	sc(x);
	cout<<"/";
	sc(y);
	cout<<endl;
}
lll C1(int u,int v){
	if(u<0 || v<0 || u<v) return 0;
	return C[u][v];
}
lll g[4][2];
char ans1[210];
void sol(int id){
	memset(g,0,sizeof(g));
	n=read(),m=read();
	For(i,0,n-1){
		cin>>(s[i]+1);
		a[i]=read();
	}
	printf("Case #%d: ",id);
	if(n==1){
		For(i,1,m){
			if(a[0]*2>=m){
				if(s[0][i]=='T') printf("T");
				else printf("F");
			}else{
				if(s[0][i]=='F') printf("T");
				else printf("F");
			}
		}
		fenshu(max(a[0],m-a[0]),1);
		return;
	}
	lll sum=0,ans=0;
	if(n==2){
		int c1=0,c2=0;
		For(i,1,m){
			if(s[0][i]==s[1][i]) c2++;
			else c1++;
		}
		For(i,0,c1){
			int f1=i,f2=c1-i;
			if(a[0]-f1==a[1]-f2 && a[0]-f1<=c2 && a[0]-f1>=0){
				sum+=C1(c1,i)*C1(c2,a[0]-f1);
				g[0][0]+=C1(c1-1,i-1)*C1(c2,a[0]-f1);
				g[0][1]+=C1(c1-1,i)*C1(c2,a[0]-f1);
				g[1][0]+=C1(c1,i)*C1(c2-1,a[0]-f1-1);
				g[1][1]+=C1(c1,i)*C1(c2-1,a[0]-f1);
			}
		}
		For(i,1,m){
			if(s[0][i]==s[1][i]) ans+=max(g[1][0],g[1][1]);
			else ans+=max(g[0][0],g[0][1]);
		}
		For(i,1,m){
			if(s[0][i]==s[1][i]){
				if(g[1][0]>=g[1][1]){
					if(s[0][i]=='T') printf("T");
					else printf("F");
				}else{
					if(s[0][i]=='F') printf("T");
					else printf("F");
				}
			}else{
				if(g[0][0]>=g[0][1]){
					if(s[0][i]=='T') printf("T");
					else printf("F");
				}else{
					if(s[0][i]=='F') printf("T");
					else printf("F");
				}
			}
		}
		fenshu(ans,sum);
		return;
	}
	int c1=0,c2=0,c3=0,c4=0;
	For(i,1,m){
		if(s[0][i]!=s[1][i] && s[0][i]!=s[2][i]) c1++;
		else if(s[1][i]!=s[0][i] && s[1][i]!=s[2][i]) c2++;
		else if(s[2][i]!=s[1][i] && s[0][i]!=s[2][i]) c3++;
		else c4++;
	}
	For(i,0,c1){
		For(j,0,c2){
			For(k,0,c3){
				int f1=i+c2-j+c3-k,f2=j+c1-i+c3-k,f3=k+c1-i+c2-j;
				if(a[0]-f1==a[1]-f2 && a[1]-f2==a[2]-f3 && a[0]-f1<=c4){
					sum+=C1(c1,i)*C1(c2,j)*C1(c3,k)*C1(c4,a[0]-f1);
					g[0][0]+=C1(c1-1,i-1)*C1(c2,j)*C1(c3,k)*C1(c4,a[0]-f1);
					g[0][1]+=C1(c1-1,i)*C1(c2,j)*C1(c3,k)*C1(c4,a[0]-f1);
					g[1][0]+=C1(c1,i)*C1(c2-1,j-1)*C1(c3,k)*C1(c4,a[0]-f1);
					g[1][1]+=C1(c1,i)*C1(c2-1,j)*C1(c3,k)*C1(c4,a[0]-f1);
					g[2][0]+=C1(c1,i)*C1(c2,j)*C1(c3-1,k-1)*C1(c4,a[0]-f1);
					g[2][1]+=C1(c1,i)*C1(c2,j)*C1(c3-1,k)*C1(c4,a[0]-f1);
					g[3][0]+=C1(c1,i)*C1(c2,j)*C1(c3,k)*C1(c4-1,a[0]-f1-1);
					g[3][1]+=C1(c1,i)*C1(c2,j)*C1(c3,k)*C1(c4-1,a[0]-f1);
				}
			}
		}
	}
	For(i,1,m){
		if(s[0][i]!=s[1][i] && s[0][i]!=s[2][i]){
			ans+=max(g[0][0],g[0][1]);
			if(g[0][0]>=g[0][1]){
				if(s[0][i]=='T') printf("T");
				else printf("F");
			}else{
				if(s[0][i]=='F') printf("T");
				else printf("F");
			}
		}else if(s[1][i]!=s[0][i] && s[1][i]!=s[2][i]){
			ans+=max(g[1][0],g[1][1]);
			if(g[1][0]>=g[1][1]){
				if(s[1][i]=='T') printf("T");
				else printf("F");
			}else{
				if(s[1][i]=='F') printf("T");
				else printf("F");
			}
		}else if(s[2][i]!=s[1][i] && s[0][i]!=s[2][i]){
			ans+=max(g[2][0],g[2][1]);
			if(g[2][0]>=g[2][1]){
				if(s[2][i]=='T') printf("T");
				else printf("F");
			}else{
				if(s[2][i]=='F') printf("T");
				else printf("F");
			}
		}else{
			ans+=max(g[3][0],g[3][1]);
			if(g[3][0]>=g[3][1]){
				if(s[0][i]=='T') printf("T");
				else printf("F");
			}else{
				if(s[0][i]=='F') printf("T");
				else printf("F");
			}
		}
	}
	fenshu(ans,sum);
}

int main()
{
    //freopen("mex.in","r",stdin);
    //freopen("mex.out","w",stdout);
    For(i,0,129){
    	C[i][0]=1;
    	For(j,1,i) C[i][j]=C[i-1][j-1]+C[i-1][j];
    }
    T=read();
    For(i,1,T) sol(i);
   	return 0;
}
/*

*/

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...