csp-s模拟测试10.1(b)X 国的军队,排列组合, 回文题解

题面：https://www.cnblogs.com/Juve/articles/11615883.html

X 国的军队：

好像有O(T*N)的直接贪心做法

其实多带一个log的二分也可以过

先对所有据点按b-a由大到小排序(按此方案排序后顺序扫是最优的)

然后二分答案

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define int long long

#define re register

using namespace std;

const int MAXN=1e5+5;

inline int read(){

	re int x=0;re char ch=getchar();

	while(ch<'0'||ch>'9') ch=getchar();

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0',ch=getchar();}

	return x;

}

int t,n,l,r;

struct node{

	int a,b;

	inline friend bool operator < (node p,node q){

		return p.b-p.a>q.b-q.a;

	}

}c[MAXN];

inline bool check(re int x){

	for(re int i=1;i<=n;++i){

		if(x<c[i].b) return 0;

		x-=c[i].a;

	}

	return 1;

}

signed main(){

	t=read();

	while(t--){

		n=read();

		l=0,r=0;

		for(re int i=1;i<=n;++i){

			c[i].a=read(),c[i].b=read();

			l+=c[i].a,r+=c[i].b;

		}

		sort(c+1,c+n+1);

		while(l<r){

			re int mid=(l+r)>>1;

			if(check(mid)) r=mid;

			else l=mid+1;

		}

		printf("%lld\n",l);

	}

	return 0;

}

排列组合：

把$C_{n}^{i}*C_{n}^{i}$变成$C_{n}^{i}*C_{n}^{n-i}$，

这样的话,就是对于每个 i,计算 n 个中选 i 个的方案数乘上 n 个中选(n-i)个的方案数,最后累加起来。

这样得到的答案,实际上相当于 2n 个物品,在前 n 个中选 i 个,在后 n 个中选(n-i)个,、

又由于 i 取遍 0~n 所有整数,那么累加后方案数就等于 $C_{2*n}^{n}$。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define int long long

#define re register

using namespace std;

const int MAXN=2e6+5;

const int mod=1e9+7;

int t,n,fac[MAXN],inv[MAXN];

inline int q_pow(re int a,re int b,re int p){

	re int res=1;

	while(b){

		if(b&1) res=res*a%p;

		a=a*a%p;

		b>>=1;

	}

	return res;

}

inline void get_c(re int N){

	fac[0]=fac[1]=inv[0]=1;

	for(re int i=2;i<=N;++i){

		fac[i]=fac[i-1]*i%mod;

	}

	inv[N]=q_pow(fac[N],mod-2,mod);

	for(re int i=N-1;i>=1;--i){

		inv[i]=inv[i+1]*(i+1)%mod;

	}

}

inline int C(re int n,re int m){

	if(m>n) return 0;

	if(m==n) return 1;

	return fac[n]%mod*inv[m]%mod*inv[n-m]%mod;

}

signed main(){

	get_c(2e6);

	scanf("%lld",&t);

	while(t--){

		scanf("%lld",&n);

		printf("%lld\n",C(2*n,n));

	}

	return 0;

}

回文：

定义g[i][j]表示i到j这一段是否回文，可以由g[i+1][j-1]转移：

for(int i=1;i<=len;++i){

	g[i][i]=1;

	f[i][i]=1;

	for(int j=1;j<=min(i-1,len-i);++j){

		if(s[i-j]==s[i+j]){

			g[i-j][i+j]=1;

		}else break;

	}

}

for(int i=1;i<=len-1;++i){

	if(s[i]==s[i+1]){

		g[i][i+1]=1;

		f[i][i+1]=3;

		for(int j=1;j<=min(i-1,len-i-1);++j){

			if(s[i-j]==s[i+1+j]){

				g[i-j][i+1+j]=1;

			}else break;

		}

	}

}

定义f[i][j]表示i到j这段的答案

有转移：$f[l][r]=f[l+1][r]+f[l][r-1]-f[l+1][r-1]+g[l][r]$

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define int long long

#define re register

using namespace std;

const int MAXN=5005;

char s[MAXN];

int t,len,f[MAXN][MAXN];

bool g[MAXN][MAXN];

signed main(){

	scanf("%s",s+1);

	len=strlen(s+1);

	for(int i=1;i<=len;++i){

		g[i][i]=1;

		f[i][i]=1;

		for(int j=1;j<=min(i-1,len-i);++j){

			if(s[i-j]==s[i+j]){

				g[i-j][i+j]=1;

			}else break;

		}

	}

	for(int i=1;i<=len-1;++i){

		if(s[i]==s[i+1]){

			g[i][i+1]=1;

			f[i][i+1]=3;

			for(int j=1;j<=min(i-1,len-i-1);++j){

				if(s[i-j]==s[i+1+j]){

					g[i-j][i+1+j]=1;

				}else break;

			}

		}

	}

	for(int i=2;i<=len;++i){

		for(int l=1;l<=len-i+1;++l){

			int r=l+i-1;

			f[l][r]=f[l+1][r]+f[l][r-1]-f[l+1][r-1]+g[l][r];

		}

	}

	scanf("%lld",&t);

	while(t--){

		re int l,r;

		scanf("%lld%lld",&l,&r);

		printf("%lld\n",f[l][r]);

	}

	return 0;

}

巴特西

csp-s模拟测试10.1(b)X 国的军队,排列组合, 回文题解

最新文章

热门文章