组合数学(上)：数列、排列、组合

数列 取得整型数据的位数 #define LL long long int NoD(LL x){//Number of Digits int sum=0; if(x%10==0) sum++; while(x>0) {x/=10;sum++;} return sum; } 整型数据各数位求和 int SoD(int x){//Sum of the Digits int y = 0; while(x > 0) { y += x % 10; x /= 10; } return y; } 反转数（Reversed number） #define LL long long LL Reverse(LL x){ LL ans=0; while(x) {ans=ans*10+x%10;x/=10;} return ans; } 前缀和

设sum[i]为数列中前i项的前缀和，s[i]为数列中第i项的值，如果sum[a]与sum[b]对M同余(a<b)，则 ( ∑ k = a + 1 b s k ) % M = = 0 (\sum_{k=a+1}^{b}s_k) \% M == 0 (k=a+1∑b​sk​)%M==0

👉HDOJ-1003 Max Sum

题目：给出一个数列，找出其中各项之和最大的子数列，输出其起点位置、终点位置与各项之和。

思路：如果数列全是负项，最大和即为最大项的值。否则，最大和一定非负。在输入时进行检查，初始化首项为子数列起点。先更新最大值，再判断和符号，如果为负，从下一项开始新的子数列。证明：能够判断出总和为负，说明最新项为负，此前和已取到极大值，虽然之前的项包含之后的项有可能取到更大的和，但是之后的项不包含之前的项和一定更大，所以之前的项与之后的项应以最新项作为分界点分开。

#include<stdio.h> int main(){ int t; scanf("%d",&t); for(int j=1;j<=t;j++){ int n,i,ms,b,mb,s,temp,e; scanf("%d",&n); ms=-1001;//和的最小值为-1000 mb=b=1;s=0; for(i=0;i<n;i++){ scanf("%d",&temp); s+=temp; if(s>ms){ ms=s; mb=b; e=i+1; } if(s<0){ b=i+2; s=0; } } printf("Case %d:\n",j); printf("%d %d %d\n",ms,mb,e); if(j<t) printf("\n"); } return 0; } 👉最长连续01等串

【题目】 “等串”：含有相等数量0和1的01串。 输入一个01串(长度N满足1≤N≤100000)，输出最长等子串和等子序列的长度。

【思路】 设母串中含有t0个0和t1个1，则最长等子序列的长度=2*min(t0,t1) 下面求最长等子串的长度。 本题中合法的等子串必须满足含0和1的数量相等，’0’和’1’的作用相互抵消。不妨设0的作用值为-1，1的作用值为1，则合法条件可表述为总作用值为0。用sum[i]代表前i个字符作用值的前缀和，则当sum[l-1]==sum[r]时，子串[l,r]为等子串。 本题sum[i]的取值范围为[-100000, 100000]，对于每一个确定的sum[i]，当l与r的差值最大时，等子串最长。从前往后寻找满足sum[l]=x的最小的l，结果存储在mint[x]中；从后往前寻找满足sum[r]=x的最大的r，结果存储在maxt[x]中。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100000; const int maxn=N+5; char t[maxn];int sum[maxn],mint[2*maxn],maxt[2*maxn]; int main(){ int n,i,ans1,t0,t1,ans2; scanf("%d",&n);scanf("%s",t+1); t0 = t1 = 0; for(i = 1; i<=n; i++) if(t[i] == '0') {t0++;sum[i]=sum[i-1]-1;} else {t1++;sum[i]=sum[i-1]+1;} ans2 = min(t1, t0)*2; memset(mint,-1,sizeof(mint)); memset(maxt,-1,sizeof(maxt)); for(i=0;i<=n;i++){ int x=sum[i]; if(mint[N+x]==-1)//数组下标非负化：整体+N mint[N+x]=i;//记录最小的a } for(i=n;i>=0;i--){ int x=sum[i]; if(maxt[x+N]==-1) maxt[x+N]=i;//记录最大的b } ans1=0; for(i=0;i<=2*maxn;i++) if(mint[i]!=-1) ans1=max(ans1,maxt[i]-mint[i]); printf("%d %d\n",ans1,ans2); return 0; } 👉300倍数子串

【题目】 输入一个数串s（1≤∣s∣≤10^5），输出是300的倍数的子串数量。 注意：可以有前导和后置0，形式全等、位置不同的子串视为2个子串。

【思路】 注意到是300的倍数也就是既是3的倍数又是100的倍数。3的倍数即各位和为3的倍数，100的倍数即最后两位为0（也有可能就是单个0）。 记sum[i]为前i位的和对3取模的值，s[i]为数串中第i个数的值，那么对于长度大于等于2的子串[l,r]，合法条件为sum[l-1]==sum[r-2]且s[r]==s[r-1]==0。单个0也合法。 从小到大枚举子串右界r，并同时记录有多少个0≤x≤r-2分别满足sum[x]=0,1,2。

#include<stdio.h> #include<string.h> #define LL long long const int N=1e5+5; char s[N];int sum[N]; int main(){ int r,n,temp,flag; scanf("%s",s+1); n=strlen(s+1); LL cnt=0;int sl0=1,sl1=0,sl2=0; sum[0]=0; if(s[1]=='0') cnt++; if(s[2]=='0') cnt++; if(s[1]=='0'&&s[2]=='0') cnt++; for(r=3;r<=n;r++){ temp=(sum[r-3]+s[r-2])%3; if(s[r]=='0'&&s[r-1]=='0') flag=1; else flag=0; if(temp==0) {sl0++;if(flag) cnt+=sl0;} else if(temp==1) {sl1++;if(flag) cnt+=sl1;} else {sl2++;if(flag) cnt+=sl2;} if(s[r]=='0') cnt++; sum[r-2]=temp; } printf("%lld\n",cnt); return 0; } 👉HDOJ-4561 连续最大积

【题目】 给出一个数列{an},an∈{-2,0,2}，计算数列中某一段连续元素的积的最大值。 如果最终的答案小于等于0，直接输出0 若答案是2^x ，输出x。

【思路】 以0为分隔符，选出字串。统计字串的长度，对负数进行处理。 先输入全部数据，再处理。用变量sum统计，其绝对值代表长度，符号代表积的符号。按正序、倒序遍历，根据当前项符号对sum进行处理。

当前a[i]符号当前sum符号对sum的处理符号变化绝对值变化a[i]>0sum<0sum=sum-1不变号绝对值+1a[i]>1sum>=0sum=sum+1不变号绝对值+1a[i]<0sum<0sum=-sum+1变号绝对值+1a[i]<1sum>=0sum=-sum-1变号绝对值+1a[i]=0/sum=0//

为什么需要从正、反两个方向来遍历： 对于一个序列来说，其中包含的-2个数是确定的。虽然sum绝对值一直在增大，但只有其值为正时才可能对max有贡献。不同的遍历方向，遇到-2的位置不同。 以网友贡献的一组数据为例

数据-2222-2-22sum（正序）-1-2-3-45-6-7sum（逆序）-76543-21 #include<stdio.h> int a[10010],sum,max; void fun(int i){ if (a[i]>0) {if(sum<0) sum=sum-1; else sum=sum+1;} else if (a[i]<0) {if (sum<0) sum=-sum+1; else sum=-sum-1;} else sum=0; if (sum>max) max=sum; } int main(){ int T,n,i,k; scanf("%d",&T); for(k=1;k<=T;k++){ scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); max=0; sum=0; for (i=0;i<n;i++) fun(i); sum=0; for (i=n-1;i>=0;i--) fun(i); printf("Case #%d: %d\n",k,max); } return 0; } 排列 全排列 👉三生三世

【题目】 空间限制： 32768K  题目描述 给出2个玩家的ID，如果后一个ID是前一个ID的全排列的一种，且和前一个ID不一样， 便认为后一个是前一个的前世。现输入这2个玩家的ID，判断后一个是不是前一个的前世。  输入描述 输入的第一行包含一个整数n，代表字符串ID的长度。(n<=2e5) 接下来两行分别给出一个长度为n的字符串，可能包含所有大写字母及小写字母。  输出描述 输出yes代表是，no代表不是。  示例1 输入 4 QBDH BQDH 输出 yes  示例2 输入 5 jwjnb jwjnb 输出 no

【思路】全排列：两个排列所含字符及数量均相同。

#include<stdio.h> int main(){ char a[200005]={0},b[200005]={0}; int n,i;//n代表ID长度 int ac[125]={0},bc[125]={0};//ac代表a中包含的各字符数量 scanf("%d",&n); scanf("%s",&a); scanf("%s",&b);//? int same=0;//same代表两字符串中等位相同字符数量 for(i=0;i<n;i++){ ac[a[i]-'A']++;bc[b[i]-'A']++; if(a[i]==b[i]) same++; } int flag=1; if(same==n) flag=0;//全等 else{ for(i='A'-'A';i<='Z'-'A';i++) if(ac[i]!=bc[i]) {flag=0;break;} if(i=='Z') for(i='a'-'A';i<='z'-'A';i++) if(ac[i]!=bc[i]) {flag=0;break;} } if(flag==1) printf("yes\n"); else printf("no\n"); return 0; } 组合 组合数

【题目】 ●题目描述 给一个长为 n 的序列 a1,a2,…,an，从中等概率选出 k 个下标不同的数字，求最小值的期望值。 不难发现期望值乘以C(n,k)之后是一个整数，你只需要输出这个整数对 1000000007 取模后的结果。 这里C(n,k)表示从 n 个数中无序选出 k 个数的方案数，也就是组合数。 ●输入描述 第一行是一个正整数T(T≤20)，表示测试数据的组数， 对于每组测试数据， 第一行是两个正整数 n,k(n≤1000,k≤n)，分别表示序列长度以及选出的数字个数。 第二行包含n个整数ai(0≤ai≤1000)。 ●输出描述 对于每组测试数据，输出一行，包含一个整数，表示期望值乘以C(n,k)之后对 1000000007 取模的结果。 ●示例1 输入 1 5 2 1 2 3 4 5 输出 20

【思路】 期望值 E ( X ) = ∑ i = 1 C ( n , k ) x i / C ( n , k ) ，所以 E ( X ) ∗ C ( n , k ) =   ∑ i = 1 C ( n , k ) x i 为整数。 期望值E(X)=\sum_{i=1}^{C(n,k)}{x_i/}C(n,k)，所以E(X)* C(n,k)=\ \sum_{i=1}^{C(n,k)}x_i为整数。 期望值E(X)=i=1∑C(n,k)​xi​/C(n,k)，所以E(X)∗C(n,k)= i=1∑C(n,k)​xi​为整数。 由于是随机选出组合，因此变换序列中各数的排列顺序并不会改变最终结果，却可以给计算带来很大好处。 对序列中的数从小到大排序，那么对于任何一种选法，其最小值必为前n-k+1个数中的一个。至此，题目简化为依次列举前n-k+1个数。定义循环变量为i(i<=1<= n-k+1)，则最小值为i的选法共有C(n-i,k-1)种，最终结果= ∑ i = 1 n − k + 1 a i C ( n − i , k − 1 ) \sum_{i=1}^{n-k+1}a_iC(n-i,k-1) i=1∑n−k+1​ai​C(n−i,k−1) 实际操作时，需预先生成包含C(n,k)所有取值的表，这里用到了计算组合数的常用公式 C k n = C k n − 1 + C k − 1 n − 1 C{k\atop n}=C{k\atop n-1}+C{k-1\atop n-1} Cnk​=Cn−1k​+Cn−1k−1​

#include<stdio.h> #include<algorithm> #define MO 1000000007 using namespace std; int a[1005],c[1005][1005];//c[n][k]存储组合数C(n,k)取模后的值 int main(){ int t; scanf("%d",&t); for(int i=0;i<1005;i++) c[i][0]=1; for(int i=1;i<1005;i++) for(int j=1;j<=i;j++) c[i][j] =(c[i-1][j]+c[i-1][j-1])%MO; while(t--){ int n,k; scanf("%d%d",&n,&k);//n表示序列长度，k表示选出的数字个数 for(int i=1;i<=n;i++) scanf("%d",&a[i]);//a存储序列 sort(a+1,a+n+1);//处理为递增序列 long long int out = 0;//out存储最终结果 for(int i=1;i<=n-k+1;i++)//序列中各数 {out+=a[i]*c[n-i][k-1];out%=MO;} printf("%lld\n",out); } return 0; } 不相邻组合 👉HDOJ-1205 吃糖果

题目：有一个小朋友叫Gardon，他不喜欢将一样的糖果放在一起吃，喜欢先吃一种，下一次吃另一种。输入各种糖果的类型（最多1000000种）和数量（每种最多1000000个），判断是否存在一种吃糖果的顺序，使得Gardon能以他的方式，把所有糖果都吃完。

思路：排列中不相邻问题使用插空法，剩余糖果能够插满数量最多的糖果之间的所有空隙即可。

#include<stdio.h> int main(){ int T,N,m,p,t; __int64 s;//s位数可能超过int存储范围 scanf("%d",&T); while(T--){ scanf("%d",&N); scanf("%d",&m); s=0; while(--N){ scanf("%d",&p); if(p>m) {t=m;m=p;p=t;} s+=p; } if(s>=m-1) printf("Yes\n"); else printf("No\n"); } return 0; }