被打爆了。

A - Union of Grid Paths

題目大意：有一個(gè) \(H\times W\) 的網(wǎng)格圖，給出從左上角 \((1,1)\) 走到右下角 \((H,W)\) 的一個(gè)路徑串（包含 R、D、?），其中部分位置的字符未知，用 ? 表示。R 和 D 分別代表向右走和向下走?？梢詧?zhí)行任意次操作，每次操作可以將 ? 替換成 R 或 D，要求替換后這個(gè)串是一個(gè)合法的從左上走到右下的操作序列，之后按照這個(gè)操作序列在網(wǎng)格圖上走，并把所有經(jīng)過的格子涂黑。問最終可以涂黑多少個(gè)格子。\(H,W\le 2\times 10^5\)

把所有 ? 優(yōu)先替換成 R 做一次，再優(yōu)先替換成 D 做一次，可以得到每一行可能被涂黑的最左邊位置和最右邊位置，之后就能計(jì)算答案了。

#include<bits/stdc++.h>
using namespace std;
#define N 200020
int T,n,m,l[N],r[N];
char s[N<<1];
void init()
{
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)l[i]=m+1,r[i]=0;
	int R=m-1,D=n-1;
	for(int i=1;i<=n+m-2;i++)
		if(s[i]=='R')R--;
		else if(s[i]=='D')D--;
	int x=1,y=1,t=R;
	for(int i=1;i<=n+m-2;i++){
		l[x]=min(l[x],y);
		r[x]=max(r[x],y);
		if(s[i]=='R')y++;
		if(s[i]=='D')x++;
		if(s[i]=='?'){
			if(t)y++,t--;
			else x++;
		}
	}
	l[x]=min(l[x],y);
	r[x]=max(r[x],y);
	x=1,y=1,t=D;
	for(int i=1;i<=n+m-2;i++){
		l[x]=min(l[x],y);
		r[x]=max(r[x],y);
		if(s[i]=='R')y++;
		if(s[i]=='D')x++;
		if(s[i]=='?'){
			if(t)x++,t--;
			else y++;
		}
	}
	long long ans=0;
	for(int i=1;i<=n;i++)ans+=r[i]-l[i]+1;
	printf("%lld\n",ans);
}
int main()
{
	scanf("%d",&T);
	while(T--)init();
}

賽時(shí)一直在爆 D，這題沒來得及想，遺憾。

B - Greater Than Average

題目大意：給定數(shù)組，定義數(shù)組的權(quán)值為嚴(yán)格大于平均值的數(shù)字個(gè)數(shù)，求子序列中最大的權(quán)值。\(N\le 2\times 10^5\)

直接把賽時(shí)的思考路徑放上來吧。

考慮最優(yōu)子序列肯定是選一些能夠產(chǎn)生貢獻(xiàn)的數(shù)，然后再選一個(gè)權(quán)值的前綴把平均值拉下來

比如目前a[1],a[2],a[3]是不產(chǎn)生貢獻(xiàn)的，那么考慮選了x個(gè)和為sum的數(shù)，那么就需要保證min of x>(sum+s[3])/(x+3)

那么相當(dāng)于要選大于平均數(shù)的最小的x個(gè)數(shù)

于是考慮我們要讓區(qū)間[l,r]的這些數(shù)產(chǎn)生貢獻(xiàn)，就需要找到i滿足

a[l]>(s[r]-s[l-1]+s[i])/(i+r-l+1)

(i+r-l+1)a[l]>s[r]-s[l-1]+s[i]

顯然此時(shí)取i=l-1一定最優(yōu)，因?yàn)榭梢员M量拉低平均值

所以就是考慮取一段前綴，然后求平均值確定分界線，統(tǒng)計(jì)答案

做一下補(bǔ)充說明。因?yàn)榇_定了取 \(i=l-1\) 一定最優(yōu)，所以最優(yōu)解中一定是取 \([1,r]\) 作為子序列。于是只需要枚舉前綴，然后確定 \(l\) 的位置計(jì)算答案。

#include<bits/stdc++.h>
using namespace std;
#define N 200020
int T,n,a[N];
int main()
{
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		sort(a+1,a+n+1);
		long long sum=0;
		int ans=0;
		for(int i=1;i<=n;i++){
			sum+=a[i];
			ans=max(ans,i+1-(int)(upper_bound(a+1,a+i+1,sum/i)-a));
		}
		printf("%d\n",ans);
	}
}

這題開場(chǎng)交了 3 發(fā) CE，原因是沒搞明白 (upper_bound(a+1,a+i+1,sum/i)-a) 的值的類型。

印象里 CF 也有一道類似的平均數(shù)相關(guān)的題，當(dāng)年直接秒了，但是現(xiàn)在遇到這種題需要把思考過程寫出來才能想明白，果然變菜了...

C - Removal of Multiples

題目大意：初始有一個(gè)集合 \(S\) 包含全體正整數(shù)，會(huì)執(zhí)行 \(Q\) 次操作，每次操作給出數(shù)字 \(A,B\)，將 \(S\) 中所有 \(A\) 的倍數(shù)移除，并詢問第 \(B\) 小。\(Q\le 10^5,2\le A\le 10^9,B\le 10^5\)

注意到 \(B\) 和 \(Q\) 都是 \(10^5\) 級(jí)別的，所以考慮前 \(2\times 10^5\) 個(gè)質(zhì)數(shù)，每次操作至多只會(huì)刪除 \(1\) 個(gè)質(zhì)數(shù)，所以答案不會(huì)超過第 \(2\times 10^5\) 個(gè)質(zhì)數(shù)的大小。

所以把 \(M=3\times 10^6\) 以內(nèi)的質(zhì)數(shù)篩出來，并令 \(S=\{1,2,\dots,M\}\)，這樣足夠我們進(jìn)行操作。每次直接模擬對(duì)應(yīng)操作并用樹狀數(shù)組維護(hù)前 \(i\) 個(gè)數(shù)里還有多少個(gè)數(shù)在集合中，詢問時(shí)直接二分即可。雖然是雙 \(\log\) 但是跑得飛快。

#include<bits/stdc++.h>
using namespace std;
#define N 3000010
int Q,a,b,t[N],M=3000000;
int cnt,p[N],v[N],g[N];
int lowbit(int x){return x&(-x);}
void cg(int x,int c){while(x<N)t[x]+=c,x+=lowbit(x);}
int ask(int x){int r=0;while(x)r+=t[x],x-=lowbit(x);return r;}
int get(int x)
{
	int l=1,r=M,mid;
	while(l<r){
		mid=l+r>>1;
		if(ask(mid)<x)l=mid+1;
		else r=mid;
	}
	return l;
}
int main()
{
	for(int i=2;i<N;i++){
		if(!v[i])p[++cnt]=i;
		for(int j=1;j<=cnt && i*p[j]<N;j++){
			v[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	}
	for(int i=1;i<=M;i++)cg(i,1);
	scanf("%d",&Q);
	while(Q--){
		scanf("%d%d",&a,&b);
		if(a<=M && !g[a]){
			for(int i=a;i<=M;i+=a)
				if(!g[i])g[i]=1,cg(i,-1);
		}
		printf("%d\n",get(b));
	}
}

水題，沒啥好說的。

D - Ancestor Relation

題目大意：給定 \(N\times N\) 的 \(01\) 矩陣 \(A\)，問有多少大小為 \(N\) 的以 \(1\) 為根的樹滿足 \(A_{i,j}=1\) 當(dāng)且僅當(dāng) \(i,j\) 之間有祖先后代關(guān)系。\(N\le 400\)

考慮當(dāng) \(A_{i,j}=1\) 時(shí)誰是誰的祖先。設(shè) \(b_i\) 為矩陣的第 \(i\) 行，可以用 bitset 存。那么若 \(i\) 是 \(j\) 的祖先則一定有 \(b_j\subseteq b_i\)。如果此時(shí) \(b_i\neq b_j\) 則一定能判斷出祖先后代關(guān)系，否則會(huì)有 \(b_i=b_j\)。

經(jīng)過分析可以發(fā)現(xiàn)，若 \(i\) 是 \(j\) 的祖先且 \(b_i=b_j\)，這意味著從 \(i\) 走到 \(j\) 的路徑上一定是不存在分叉的，且路徑上的所有點(diǎn)對(duì)應(yīng)的 \(b\) 一定相同。而這些點(diǎn)相互之間可以任意調(diào)換位置，所以答案可以乘上 \(cnt!\)。

于是接下來只需要做合法性的判斷，需要判斷以下幾點(diǎn)：

• \(b\) 相同的那些點(diǎn)一定要在 \(A\) 中連成一個(gè)完全子圖
• \(A_{1,i}=A_{i,1}=1\) 必須成立
• 如果 \(b_i\) 和 \(b_j\) 沒有相互包含關(guān)系，那么 \(A_{i,j}=0\)，反之亦然

#include<bits/stdc++.h>
using namespace std;
#define N 410
#define MOD 998244353
int T,n,a[N][N],fa[N],fac[N];
bitset<N>b[N];
vector<int>d[N];
int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
void Union(int x,int y){if(Find(x)!=Find(y))fa[Find(x)]=Find(y);}
void init()
{
	long long ans=1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		fa[i]=i;
		d[i].clear();
		b[i].reset();
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++){
		scanf("%d",&a[i][j]);
		if(a[i][j])b[i][j]=1;
	}
	for(int i=2;i<=n;i++)
	for(int j=i+1;j<=n;j++)
		if(b[i]==b[j])Union(i,j);
	for(int i=2;i<=n;i++){
		if(!a[1][i])ans=0;
		d[Find(i)].push_back(i);
	}
	for(int i=2;i<=n;i++)if(!d[i].empty()){
		int sz=d[i].size();
		for(int j=0;j<sz;j++)
		for(int k=j+1;k<sz;k++){
			int x=d[i][j],y=d[i][k];
			if(!a[x][y])ans=0;
		}
		ans*=fac[sz];
		ans%=MOD;
	}
	for(int i=1;i<=n;i++)
	for(int j=i;j<=n;j++)
		if((b[i]&b[j])==b[j] || (b[i]&b[j])==b[i]){
			if(a[i][j]==0)ans=0;
		}
		else if(a[i][j])ans=0;
	printf("%lld\n",ans);
}
int main()
{
	fac[0]=1;
	for(int i=1;i<N;i++)fac[i]=1ll*fac[i-1]*i%MOD;
	scanf("%d",&T);
	while(T--)init();
}

賽時(shí)犯蠢沒有想到子集關(guān)系，一直在想 bitcount 的大小關(guān)系，于是就寄了，遺憾。

E - Four Square Tiles

題目大意：給定 \(N,H,W\)，問有多少種在 \(H\times W\) 的網(wǎng)格圖內(nèi)放置 \(4\) 個(gè) \(N\times N\) 方塊的方案數(shù)，使得每個(gè)方塊都在網(wǎng)格內(nèi)，且每個(gè)格子最多只被覆蓋一次。\(N,H,W\le 10^9;H,W\le 3N-1\)

由于 \(H,W\le 3N-1\)，所以一行里最多存在兩個(gè)不同的 \(N\times N\) 方塊，對(duì)列也是一樣。所以四個(gè)方塊大致構(gòu)成 左上、右上、左下、右下 的形狀。于是可以先判掉 \(\min(H,W)\lt 2N\) 的情況。

基于上述結(jié)論，考慮怎么刻畫 左上、右上、左下、右下 這四個(gè)塊?？梢园l(fā)現(xiàn) \((N,N),(N,2N),(2N,N),(2N,2N)\) 必須被四個(gè)不同的方塊覆蓋，于是以這四個(gè)格子作為四種塊的代表元。

設(shè)這四個(gè)方塊的左上角坐標(biāo)分別為 \((a_1,b_1),(a_2,b_2),(a_3,b_3),(a_4,b_4)\)，考慮這些變量之間的關(guān)系，可以列出：

• \(1\le a_1\)，\(a_1+N\le a_3\)，\(a_3+N-1\le H\)
• \(1\le a_2\)，\(a_2+N\le a_4\)，\(a_4+N-1\le H\)
• \(1\le b_1\)，\(b_1+N\le b_2\)，\(b_2+N-1\le W\)
• \(1\le b_3\)，\(b_3+N\le b_4\)，\(b_4+N-1\le W\)

發(fā)現(xiàn)這些不等式的正整數(shù)解組數(shù)非常好算（因?yàn)椴煌M之間相互獨(dú)立），但這些還不夠，因?yàn)槲覀冞€需要保證左上和右下不交，且右上和左下不交。

根據(jù)對(duì)稱性，這兩對(duì)方塊相交的方案數(shù)顯然相同。而且可以發(fā)現(xiàn)，這兩對(duì)方塊在上述四個(gè)不等式的約束下一定不會(huì)同時(shí)相交。所以我們只需要統(tǒng)計(jì)其中一種情況的方案數(shù)并減去他們就好，以左上右下相交為例，此時(shí)幾個(gè)變量需滿足條件（注意之前的四組條件也必須滿足，這里一起寫下來）：

• \(1\le a_2\)，\(a_2+N\le a_4\)，\(a_4\le a_1+N-1\)，\(a_1+N\le a_3\)，\(a_3+N-1\le H\)
• \(1\le b_3\)，\(b_3+N\le b_4\)，\(b_4\le b_1+N-1\)，\(b_1+N\le b_2\)，\(b_2+N-1\le W\)

最后答案就是第一部分四組不等式解的個(gè)數(shù)減去兩倍的第二部分兩組不等式解的個(gè)數(shù)。

其中每一組不等式解的數(shù)量都是容易計(jì)算的，這里直接開搞。

• \(1\le a_1\)，\(a_1+N\le a_3\)，\(a_3+N-1\le H\)，只需稍作變形就可化為 \(1\le a_1\lt a_3-N+1\le H-2N+2\)，方案數(shù)就是 \(\binom{H-2N+2}{2}\)。
• \(1\le a_2\)，\(a_2+N\le a_4\)，\(a_4+N-1\le H\)，同理可得方案數(shù)為 \(\binom{H-2N+2}{2}\)。
• \(1\le b_1\)，\(b_1+N\le b_2\)，\(b_2+N-1\le W\)，同理可得方案數(shù)為 \(\binom{W-2N+2}{2}\)。
• \(1\le b_3\)，\(b_3+N\le b_4\)，\(b_4+N-1\le W\)，同理可得方案數(shù)為 \(\binom{W-2N+2}{2}\)。
• \(1\le a_2\)，\(a_2+N\le a_4\)，\(a_4\le a_1+N-1\)，\(a_1+N\le a_3\)，\(a_3+N-1\le H\)，變形后化為 \(1\le a_2\lt a_4-N+1\lt a_1+1\lt a_3-N+2\le H-2N+3\)，方案數(shù)為 \(\binom{H-2N+3}{4}\)。
• \(1\le b_3\)，\(b_3+N\le b_4\)，\(b_4\le b_1+N-1\)，\(b_1+N\le b_2\)，\(b_2+N-1\le W\)，同理可得方案數(shù)為 \(\binom{W-2N+3}{4}\)。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define MOD 998244353
const LL inv2=499122177;
const LL inv24=291154603;
LL C(LL n,LL m)
{
	if(m==2)return n*(n-1)%MOD*inv2%MOD;
	return n*(n-1)%MOD*(n-2)%MOD*(n-3)%MOD*inv24%MOD;
}
int main()
{
	int T,n,h,w;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&h,&w);
		if(min(h,w)<2*n){
			printf("0\n");
			continue;
		}
		LL ans=C(h-2*n+2,2)*C(h-2*n+2,2)%MOD;
		ans*=(C(w-2*n+2,2)*C(w-2*n+2,2)%MOD),ans%=MOD;
		LL d=2ll*C(h-2*n+3,4)*C(w-2*n+3,4)%MOD;
		printf("%lld\n",(ans+MOD-d)%MOD);
	}
}

感覺是很好的基礎(chǔ)容斥計(jì)數(shù)題。