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

数列

取得整型数据的位数

#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;
}
1
2
3
4
5
6
7
8

整型数据各数位求和

int SoD(int x){//Sum of the Digits
	int y = 0;
	while(x > 0) { y += x % 10; x /= 10; }
	return y;
}
1
2
3
4
5

反转数（Reversed number）

#define LL long long

LL Reverse(LL x){
	LL ans=0;
	while(x) 
	{ans=ans*10+x%10;x/=10;}
    return ans;
}
1
2
3
4
5
6
7
8

前缀和

设sum[i]为数列中前i项的前缀和，s[i]为数列中第i项的值，如果sum[a]与sum[b]对M同余(a $$(\sum _{k=a+1}^b{s}_k)\%M==0$$

👉HDOJ-1003 Max Sum

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

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

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

👉最长连续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
#include
#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

👉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
#include
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

👉HDOJ-4561 连续最大积

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

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

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

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

排列

全排列

👉三生三世

【题目】
空间限制： 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
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

组合

组合数

【题目】
●题目描述
给一个长为 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)=\sum _{i=1}^{C(n,k)}{x}_i/C(n,k)，所以E(X)\ast C(n,k)=\sum _{i=1}^{C(n,k)}{x}_i为整数。$$
由于是随机选出组合，因此变换序列中各数的排列顺序并不会改变最终结果，却可以给计算带来很大好处。
对序列中的数从小到大排序，那么对于任何一种选法，其最小值必为前n-k+1个数中的一个。至此，题目简化为依次列举前n-k+1个数。定义循环变量为i(i<=1<= n-k+1)，则最小值为i的选法共有C(n-i,k-1)种，最终结果=$$\sum _{i=1}^{n-k+1}{a}_{i}C(n-i,k-1)$$
实际操作时，需预先生成包含C(n,k)所有取值的表，这里用到了计算组合数的常用公式$$C\genfrac{}{}{0ex}{}{k}{n}=C\genfrac{}{}{0ex}{}{k}{n-1}+C\genfrac{}{}{0ex}{}{k-1}{n-1}$$

#include
#include
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

不相邻组合

👉HDOJ-1205 吃糖果

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

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

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21