[C++知识库]【蓝桥杯预备营集结三】软件类 C/C++ 预备试题分析及解答

🎉为备战蓝桥杯，从今天开始更几期蓝桥杯的内容，总结相关试题，分析解题思路，铺好康庄大道，直到巅峰🎉

🎉🎉目前持续总结更新🎉🎉

💗 大家好🤗🤗🤗，我是左手の明天！💗

📆 最近更新：2022 年 4 月 8 日，左手の明天的第 221 篇原创博客

目录

🚩平方和

🚩年号字串

🚩数列求值?

🚩最大降雨量

🚩迷宫

🚩RSA解密

🚩完全二叉树的权值

🚩倒杨辉三角形

🚩回文串

🚩外卖店优先级

🚩修改数组

🚩糖果

🚩垒骰子

🚩组合数问题

---

👍👍👍👍👍👍

🌟🌟?预祝各位能够得到好的名次?🌟🌟

🚩平方和

??题目

小明对数位中含有2、0、1、9 的数字很感兴趣，在1 到40 中这样的数包括1、2、9、10 至32、39 和40，共28 个，他们的和是574，平方和是14362。

注意，平方和是指将每个数分别平方后求和。

请问，在1 到2019 中，所有这样的数的平方和是多少？

??思路

只需要用一个循环遍历，并检测变量是否符合题目要求即可。

??代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long cnt=0;
    for(int i=1;i<=2019;i++){
   	 int t=i,x=0;
      while(t){
   		int p=t%10;
   		if(p==0||p==1||p==2||p==9) x++;
   		t/=10;
	}
	if(x) cnt+=i*i;
   }
   cout<<cnt<<endl;
   return 0;
}

??结果

🎉答案：2658417853

🚩年号字串

??题目

小明用字母 A 对应数字 1，B 对应 2，以此类推，用 Z 对应 26。对于 27以上的数字，小明用两位或更长位的字符串来对应，例如 AA 对应 27，AB 对应 28，AZ 对应 52，LQ 对应 329。

请问 2019 对应的字符串是什么？

??思路

这题就是用 A~Z 来表示 1 ~ 26 这几个数，然后要将 2019 用 A~Z 这 26 个字母表示出来，其实就类似于进制转换。

??代码

#include <iostream>
using namespace std;

void solve(int n) {
	if (!n) {
		return ;
	}
	solve(n / 26);
	cout << (char)(n % 26 + 64);
}

int main() {
	solve(2019);
	return 0;
}

??结果

🎉答案：BYQ

🚩数列求值?

??题目

给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求第 20190324 项的最后 4 位数字。

??思路

类似于斐波那契数列的第 n 项，只不过递推式变了，不能用递归，否则爆栈，还有一个问题是直接算到第 20190324 项肯定是会溢出的，在计算过程中要进行取余操作。

??代码

#include <iostream>
using namespace std;

int solve(int n) {
	if (n <= 3) {
		return 1;
	}
	int a = 1, b = 1, c = 1, res;
	for (int i = 4; i <= n; i++) {
		res = (a + b + c) % 10000; // 取余
		a = b;
		b = c;
		c = res;
	}
	return res;
}

int main() {
	cout << solve(20190324) << endl;
	return 0;
}

??结果

🎉答案：4659

🚩最大降雨量

??题目

由于沙之国长年干旱，法师小明准备施展自己的一个神秘法术来求雨。这个法术需要用到他手中的49 张法术符，上面分别写着1 至49 这49 个数字。法术一共持续7 周，每天小明都要使用一张法术符，法术符不能重复使用。每周，小明施展法术产生的能量为这周7 张法术符上数字的中位数。
法术施展完7 周后，求雨将获得成功，降雨量为7 周能量的中位数。由于干旱太久，小明希望这次求雨的降雨量尽可能大，请大最大值是多少？

??思路

🍊错误思路：

这个题一开始看到它必是贪心，中位数就是从小到大排列的数组中，其中有一半比中位数大，有一半比中位数小，感觉它是田忌赛马，然后我就写了一下，发现确实是田忌赛马，如果每周的中位数是递增的，那么最后的答案必然是第四周的降雨量，这样它和每一周的差从7缩小到了4，不可能再缩小了。

🍊正确思路：

注意读题，求的不是七周中位数的和，而是七周中位数的中位数的最大值

a,b,c,x,e,f,g分别是每周的中位数。而x是a,b,c,x,e,f,g是这七周的每一周的中位数的中位数

题目的要求是让我们最大化这个x;

我们可以假定x已经是我们要求的值，那么为了让x符合题目信息，我们必须让第4周的后3天，第5，6，7周的后4天都大于这个值。

那么很显然有15个数比x大，那么x就等于49 - 15 = 34。

???结果

🎉答案：34

🚩迷宫

??题目
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。

010000
000100
001001
110000

迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上、下、左、右四个方向之一。

对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。

对于下面这个更复杂的迷宫（30 行 50 列） ，请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。请注意在字典序中D<L<R<U。（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。

01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

??思路

如何把地图数据放入代码中是一个问题，一般用文本替换。就是一道经典的寻路问题，使用 BFS，因为 BFS 得到的解总是最优解，即步数最少的解，那么我们在遍历的时候按照字典序从小到大的顺序进行四个方向遍历进行了。

??代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<set>
using namespace std;
 
#define N 30
#define M 50
 
char map[N][M];
int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}};//D<L<R<U
char ch[4]={'D','L','R','U'};
int vis[N][M]={0};
 
struct point
{
	int x,y;
	string road;
	point(int a,int b)
	{
		x=a;
		y=b;
	}
};
 
void bfs()
{
	queue<point> q;
	point p(0,0);
	p.road="";
	q.push(p);
	vis[0][0]=1;
	while(!q.empty())
	{
		point t=q.front();
		q.pop();
		if(t.x==N-1&&t.y==M-1)
		{
			cout<<t.road<<endl;
			break;
		}
		for(int i=0;i<4;i++)
		{
			int dx=t.x+dir[i][0];
			int dy=t.y+dir[i][1];
			if(dx>=0&&dx<N&&dy>=0&&dy<M)
			{
				if(map[dx][dy]=='0'&&!vis[dx][dy])
				{
					point tt(dx,dy);
					tt.road=t.road+ch[i];//记录路径
					q.push(tt);
					vis[dx][dy]=1;
				}
			}
		}
	}
}
 
int main()
{
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<M;j++)
			scanf("%c",&map[i][j]);
		getchar();//读掉回车 
	}
	bfs();
	return 0;
}

??结果

🎉答案：

DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR

🚩RSA解密

??题目

RSA是一种经典的加密算法。它的基本加密过程如下。

首先生成两个大质数p,q，令n = p*q，设d与(p-1)*(q-1)互质，则可以找到e，使得d*e除以(p-1)*(q-1)的余数为1。

n,d,e组成了私钥，n,d构成了公钥。

当使用公钥加密一个整数X时(X<=n-1)，计算C = X^d mod n，则C是加密后的密文。

当收到密文C时，可以使用私钥解开，计算公式为：X = C^e mod n。

例如：当p = 5, q = 11, n = 55, e = 27。

若加密数字24，得24^3 % 55 = 19。

解密数字19，得19^27 % 55 = 24。

现在你知道公钥中n = 1001733993063167141，d = 212353，同时，你截获了别人发送的密文C = 20190324，请问，原文是多少？

??思路

给一个n，分解质因数成p*q， 然后计算d关于(p-1)*(q-1)的逆元，结果为e，求C^e % n的结果。
??n = 1001733993063167141
??d = 212353
??c = 20190324

??代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;

//筛素数
const int maxn = 1e8+10;
const LL n = 1001733993063167141ll;
const LL p = 891234941ll;
const LL q = 1123984201ll;
const LL d = 212353;
const LL c = 20190324;
int a[maxn];
int sushu[maxn/10];
bool notPrime[maxn]; ///筛素数分解不出来，目测是9位数*10位数 
int cnt;
void getPrime(int n)
{
	for(int i=2;i<=n;++i)
	{
		if(!notPrime[i]) sushu[cnt++] = i;
		for(int j=0;j<cnt&&1ll*i*sushu[j]<=n;++j)
		{
			notPrime[i*sushu[j]] = true;
			if(i%sushu[j]==0) break; 
		} 
	}
	for(int i=0;i<20;++i) cout<<sushu[i]<<" ";cout<<endl;
}

// 分解质因数
void fenjie(LL x)
{
	cout<<x<<" = 1";
	for(int i=0;i<cnt&&sushu[i]<=x/sushu[i];++i)
	{
		while(x%sushu[i]==0)
		{
			cout<<" * "<<sushu[i];
			x /= sushu[i];
		}
	}
	if(x>1) cout<<" * "<<x;
	cout<<endl;
}

//  暴力破解法
void BF(LL x)
{
	cout<<x<<" = "; 
	for(LL i=1e8+1;i<x;i+=2)
	{
		if(x%i==0)
			cout<<i<<" * ",x/=i;
	}
	cout<<x<<endl;
}

// 拓展欧几里得算法
void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
	if(b==0)
	{
		d = a; x = 1; y = 0; return;
	}
	exgcd(b,a%b,d,y,x);
	y -= (a/b)*x;
}
LL rev(LL t,LL m)
{
	LL d,x,y;
	exgcd(t,m,d,x,y);
	return (x%m+m)%m;
}

// 快速乘
LL fast_product(LL a,LL b,LL mod)
{
	LL ans = 0;
	while(b)
	{
		if(b&1) ans = (ans+a)%mod;
		a = (a+a)%mod;
		b>>=1;
	}
	return ans;
}

// 快速幂 
LL fast_pow(LL a,LL b,LL mod)
{
	LL ans = 1;
	while(b)
	{
		if(b&1) ans = fast_product(ans,a,mod);
		a = fast_product(a,a,mod);
		b>>=1;		
	} 
	return ans;
}
int main()
{
	//getPrime(maxn-5);
	//fenjie(n);
	BF(n);
	LL y = (p-1)*(q-1);
	LL e = rev(d,y);
	LL answer = fast_pow(c,e,n);
	cout<<answer<<endl;

	return 0;
}

??结果

🎉答案：579706994112328949

🚩完全二叉树的权值

??题目

给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A 1 , A 2 , ··· A N ，如下图所示：

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。

注：根的深度是 1。

【输入格式】

第一行包含一个整数 N。
第二行包含 N 个整数 A 1 , A 2 , ··· A N 。

【输出格式】

输出一个整数代表答案。

【样例输入】

7
1 6 5 4 3 2 1

【样例输出】

2

??思路

完全二叉树的第 i 层的最大节点数为 2^(i-1) 个，那么对于某个下标的元素，我们只需要知道他属于哪一层就行了，因为给的数据范围为 100000 个节点以内，这么多节点组成的完全二叉树有多少层呢？

我们知道完全二叉树的节点总数和深度的关系为深度为 n 的完全二叉树最多拥有 2^n - 1 个节点，也就是当完全二叉树为满二叉树的时候节点数最多。而一颗层数为 17 层的完全二叉树最大节点数为 2^17 - 1 = 131071，已经大于给定的 n 的范围，那么我们计算出每一个节点所属的深度层，再统计就很简单了，因为题目中给的根的深度为 1, 那么我们计算的深度需要往后移一位，即最大深度为 18。

基本思路：用数组存储，获取这颗树的深度，然后定义一个深度长的数组，用来存储每行的和，然后进行冒泡排序输出。

??代码

#include <iostream>
using namespace std;
//2的i次方
int f1(int i){
    int sum=1;
    for(int j=0;j<i;j++){
        sum*=2;
    }
    return sum;
}
//获取深度
int f(int n){
    int i=1;
    while(1){
        //2的i-1次方，就是第i层的开头
        int head=f1(i-1);
        //2的i次方-1，就是第i层的结尾
        int rear=f1(i)-1;
        if(n>=head&&n<=rear){
            break;
        }
        i++;
    }
    return i;
}
int main(){
    int n;
    cin>>n;
    int a[n+1];
    a[0]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    //获取深度
    int p=f(n);
    //cout<<p<<endl;
    int k[p];//用来存储每层的和的数组
    //初始化k数组为0；
    for(int i=0;i<p;i++){
        k[i]=0;
    }
    for(int i=1;i<p;i++){
        for(int j=f1(i-1);j<=f1(i)-1;j++){
            k[i-1]+=a[j];
        }
    }
    //最后一层
    for(int j=f1(p-1);j<=n;j++){
        k[p-1]+=a[j];
    }
    //打印
//    for(int j=0;j<p;j++){
//        cout<<k[j]<<" ";
//    }
    int k1[p];//做一个备份
    for(int i=0;i<p;i++){
        k1[i]=k[i];
    }
    //排序,冒泡
    for(int i=0;i<p-1;i++){
        bool b=true;
        for(int j=0;j<p-1-i;j++){
            if(k[j]>k[j+1]){
                int temp=k[j];
                k[j]=k[j+1];
                k[j+1]=temp;
                b=false;
            }
        }
        if(b){
            break;
        }
    }
    int i;
    for(i=0;i<p;i++){
        if(k1[i]==k[p-1]){
            break;
        }
    }
    cout<<i+1<<endl;
    return 0;
}

??结果

🎉答案：387420489

🚩倒杨辉三角形

??题目

Fans喜欢图形，而且喜欢把图形倒过来欣赏。有一次，他看见杨辉三角形 了，觉得很新鲜，于是就把它们大大小小地摆布出来。输入一些整数n（1≤n≤10），读入其每个整数，以该整数为行数，其画出来的倒杨辉三角形就是fans所喜欢欣赏的。Fans是手工做的，你却可以用编程更快捷地做出来，多爽啊!

【输入格式】

多组数据，每组数据占一行

【输出格式】

每个倒杨辉三角参考样例输出，每输出一个后必跟一空行

【输入样例】

5
3

【输出样例】

  1     4     6     4     1
     1     3     3     1
        1     2     1
           1     1
              1

  1     2     1
     1     1
        1

??代码

#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
    int n;
    while(cin>>n){
        int **a=new int* [n];
        for(int i=0;i<n;i++){
            a[i]=new int[n];
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<=i;j++){
                if(j==0||i==j){
                    a[i][j]=1;
                }else{
                    a[i][j]=a[i-1][j]+a[i-1][j-1];
                }
            }
        }
        for(int i=n-1;i>=0;i--){
            int m=i;
            for(int k=0;k<n-m-1;m++){
                cout<<"   ";
            }
            for(int j=0;j<=i;j++){
                cout<<std::right<<setw(3)<<a[i][j]<<"   ";//这里一定要是右对齐3位，如果是左对齐，测试通不过
            }
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}

🚩回文串

abcba

Y

#include <iostream>
using namespace std;
bool is_huiwen(string s){
    bool b=true;
    int s_len=s.size();
    for(int i=0;i<=s_len/2;i++){
        if(s[i]!=s[s_len-i-1]){
            b=false;
            break;
        }
    }
    return b;
}
int main(){
    string s;
    while(cin>>s){
        bool b=is_huiwen(s);
        if(b){
            cout<<"Y"<<endl;
        }else{
            cout<<"N"<<endl;
        }
    }
    return 0;
}

🚩外卖店优先级

??题目

“饱了么”外卖系统中维护着 N 家外卖店，编号 1 ～ N。 每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。

每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0； 而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。

如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中； 如果 优先级小于等于 3，则会被清除出优先缓存。

给定 T 时刻以内的 M 条订单信息， 请你计算 T 时刻时有多少外卖店在优先缓存中。

【输入格式】

第一行包含 3 个整数 N、M 和 T。

以下 M 行每行包含两个整数 ts 和 id，表示 ts 时刻编号 id 的外卖店收到 一个订单。

【输出格式】

输出一个整数代表答案。

【样例输入】

2 6 6

1 1

5 2

3 1

6 2

2 1

6 2

【样例输出】
?

1

【样例解释】

6 时刻时， 1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6， 加入优先缓存。 所以是有 1 家店 (2 号) 在优先缓存中。

【评测用例规模与约定】

对于 80% 的评测用例，1≤ N,M,T ≤10000。 对于所有评测用例，1≤ N,M,T ≤100000，1≤ts≤T，1≤id ≤ N。

??思路

1、他需要求的是T时刻有多少优先缓存，那么我们只需要每次专门判断其中一家店是否优先缓存。如果符合就res++

2、那么如何判断是否优先缓存呢，在输入的时候，记录每次输入的时刻出现的次数，即单位时间外卖份数。

从时间1一直循环到T：

• 如果当前外卖份数为0，则优先级-1（注意不能小于0）；
• 如果当前外卖份数不为0，则优先级+=2*外卖数；
• 最后每一时刻都需要判断是否为优先缓存 【优先级>5 ??? 优先级<=3】

??代码

#include<bits/stdc++.h>
using namespace std;
const int n=100010;
int a[120*n];

//这个数组【120*i+j】代表i店j时刻的外卖数
int b[n];
//b存优先级
int main()
{
	int N,M,T;
 	cin>>N>>M>>T;
 
 	for(int i=1;i<=M;i++)
 	{
 		int x,y;
 		 cin>>x>>y;
  		 a[y*120+x]++;//第y家店第x时刻的外卖 
 	}

	//每家店都判断一次
	int res=0; //最后结果
 	bool youxian;//当前是否是优先缓存
 	for(int i=1;i<=N;i++)
 	{
 		youxian=false;
  		for(int j=1;j<=T;j++)
  		{
  			if(a[i*120+j])//不为0就加
  			b[i]+=2*a[i*120+j];
  			else//否则减
  			b[i]=max(0,b[i]-1);
			
			//优先判断
			if(b[i]<=3)youxian=false;
    			if(b[i]>5)youxian=true;
  		}
  		if(youxian)res++;
 	}
 	cout<<res<<endl;
 	return 0;
}

🚩修改数组

??题目

给定一个长度为 N 的数组?A = [A1, A2, · · · AN]，数组中有可能有重复出现的整数。现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2, A3, · · · , AN。当修改 Ai 时，小明会检查 Ai 是否在 A1 ～ Ai-1 中出现过。如果出现过，则小明会给 Ai 加上 1 ；如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直到 Ai 没有在 A1 ～ Ai-1 中出现过。当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。现在给定初始的 A 数组，请你计算出最终的 A 数组。

【输入格式】

第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, · · · , AN 。

【输出格式】

输出 N 个整数，依次是最终的 A1, A2, · · · , AN。

【样例输入】

5
2 1 1 3 4

【样例输出】

2 1 3 4 5

??思路

bool标记每次+1很容易就t了（如果有N个数，全都为N，那么这是O(n^2/2）的复杂度，当n=1e5时就已经超时了）。这题可以巧妙地利用并查集。 我们初始化i的父亲为i，然后依次遍历输入的数组，使a[i] = getf(a[i])，再令f(a[i]) = f(a[i]+1)即可。

假如我们连续输入1,2,1：第一次输入1，a[1] = getf(1) = 1，更新f[1] = getf(a[1]+1) = 2； 第二次输入2，a[2] = getf(2) = 2，更新f[2] = getf(a[2]+1) = 3；第三次 再输入1，a[3] = getf(1) = getf(2)?= 3， 这时候a[3]便等于3了，而这种?查?的时间复杂度仅为O( logn)。??

整体时间复杂度O(n*logn*logn)。?

??代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int a[maxn],f[maxn];
int getf(int x)
{
	return f[x] = f[x] == x ? x:getf(f[x]); 
}
int main()
{
	for(int i=1;i<=maxn-1;i++)
		f[i] = i;
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		int nf = getf(a[i]);
		a[i] = nf;
		f[a[i]] = getf(nf+1);
	}
	for(int i=1;i<=n;i++) {
		cout << a[i];
		if(i != n)
			cout << " ";
	}
	return 0;
}

🚩糖果

??题目

糖果店的老板一共有M 种口味的糖果出售。为了方便描述，我们将M种口味编号1~M。小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是K颗一包整包出售。幸好糖果包装上注明了其中K 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。给定N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。

【输入格式】

第一行包含三个整数N、M 和K。
接下来N 行每行K 这整数T1,T2,...,TK，代表一包糖果的口味。
1<=N<=100，1<=M<=20，1<=K<=20，1<=Ti<=M。

【输出格式】

一个整数表示答案。如果小明无法品尝所有口味，输出-1。

【样例输入】

6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2

【样例输出】

2

??思路

牵扯到选不选，而且选择达到的目标给的范围很小的时候，多半可以压缩状态。

而且这道题又问的是最少的包数，多半是压状dp。

算法：顺序枚举每一包糖果，然后枚举每一个状态，然后用糖果的状态去获得新状态，并且更新状态里的最少包数。

注意事项：枚举状态的时候，一定要去掉不合法的状态。

??代码一

🍊dfs+剪枝

预处理每一列的可选状态， 选择需要被覆盖的列中的最小的分支

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=105, M=21;
int log2[1<<M];
vector<int> col[M];
int n,m,k;

int lowbit(int x){
    return x&-x;
}

bool dfs(int depth ,int state){
    if(depth==0) return state==(1<<m)-1;
    
    int t=-1;
    for(int i=(1<<m)-1-state; i; i-=lowbit(i)){
        int c=log2[lowbit(i)];
        if(t==-1||col[c].size()<col[t].size())
            t=c;
    }
    
    for(auto row: col[t])
        if(dfs(depth-1, state|row)) return true;

    return false;
}

int main(){
    cin>>n>>m>>k;
    for(int i=0; i<m; i++) log2[1<<i]=i;
    
    for(int i=0; i<n; i++){
        int state=0;
        int x;
        for(int j=0; j<k; j++){
            cin>>x;
            state|=1<<x-1;
        }
         for(int j=0; j<m; j++){
             if(state>>j&1) col[j].push_back(state);
         }
    }
    
    int depth=0;
    while(depth<=m&&!dfs(depth, 0)) depth++;
    if(depth>m) depth=-1;
    cout<<depth;
    return 0;
}

🍊状压dp

先枚举路径，再枚举状态； 每个状态都尝试这条路径

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

const int M=21, N=105;
int dp[1<<M];
int candy[N][M];
int n,m,k;

int main(){
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=k; j++) 
           cin>>candy[i][j];
            
    memset(dp, -1, sizeof dp);
    
    int lim=1<<m;
    dp[0]=0;
    for(int i=1; i<=n; i++){
        int t=0;
        for(int j=1; j<=k ;j++) t|=1<<candy[i][j]-1;  //路径t
        int nt;
        for(int st=0; st<lim; st++){
            if(dp[st]==-1) continue;
            int nst=st|t;
            if(dp[nst]==-1||dp[nst]>dp[st]+1) dp[nst]=dp[st]+1; 
        }
    }
    
    cout<<dp[lim-1];
}

🚩垒骰子

??题目

赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。?
经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！ 我们先来规范一下

骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。?

假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。 ?atm想计算一下有多少种不同的可能的垒骰子方式。

两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。 由于方案数可能过多，请输出模 10^9 + 7 的结果。 ?不要小看了 atm 的骰子数量哦～ ?

「输入格式」?

第一行两个整数 n m n表示骰子数目?
接下来 m 行，每行两个整数 a b ，表示 a 和 b 数字不能紧贴在一起。 ?

「输出格式」?

一行一个数，表示答案模 10^9 + 7 的结果。 ?

「样例输入」

?2 1

?1 2 ?

「样例输出」

544 ?

「数据范围」?

对于 30% 的数据：n <= 5 对于 60% 的数据：n <= 100?
对于 100% 的数据：0 < n <= 10^9, m <= 36?

??思路

①当堆放方式(相邻的两个骰子哪两个面挨着)确定，每个骰子有四个侧面可以旋转，所以结果应该是4^n * 堆放方式。

②动态规划的思想， 每次加一个骰子到最顶端，考虑6个面，每一个面可以有多少种方式。 此时则需要考虑已经搭好的骰子顶端没种面朝上的可能方式数量。这样便出现了递推关系式：面[i]方式数=已经搭好, 面[i]可以接触的面,朝上的数量累加。

③测试用例所示：第二层放面1的时候就=1+1+1+1+1（这里没有加面2）；面[1]=5，面[2]=5，面[3]=6，面[4]=6，面[5]=6，面[6]=6；则由于对面关系，第二层搭建完毕后，向上面为面[i]的方式数：面[1]=6，面[2]=6，面[3]=6，面[4]=5， ?面[5]=5，面[6]=6；则第三层放面1的时候就=6+6+5+5+6（这里没有加面2）。

dp[i][j]?代表高度为i，顶面点数为j的方案数，于是?dp[i][j]?就等于i-1高度时所有与j对面无冲突方案数的累加。

当然，最下面一层所有面在上的方案数都为1，求得结果后还要乘以?4^i?，因为每一个骰子都可以保证顶端点数不变的情况下四面旋转。

不过对于这道题1e9的数据O(n)的算法感觉还是会超时

于是使用了矩阵的方式来计算，关于矩阵列向量的选择求和与斐波那契数列相似。

构造出这样一个冲突矩阵之后便可以用矩阵快速幂的方法很快解决了，最终再与初始第一层的方案数相乘，便是结果。

??代码一

🍊普通o(n)解法

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
#include<queue>
#include<stack>

#define mod 1000000007
typedef __int64 LL;

bool isc[7][7]; //存储冲突面

LL mult(LL a,LL n)  //数的快速幂 a^n
{
    LL ans=1;
    while(n)
    {
        if(n&1)ans=(ans*a)%mod;
        a=(a*a)%mod;
        n>>=1;
    }
    return ans;
}

int main()
{
    LL n,m;
    while(~scanf("%I64d%I64d",&n,&m))
    {
        memset(isc,false,sizeof(isc));
        for(int i=0; i<m; i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            isc[a][b]=isc[b][a]=true;
        }
        LL dp[2][7],e=0;    //利用滚动数组的原理，不浪费多余空间
        for(int i=1; i<7; i++)  //初始化第0层
            dp[0][i]=1;
        for(LL i=1; i<n; i++)   //剩余n-1层
        {
            e^=1;
            for(int j=1; j<7; j++)  //上面一层下面为j
            {
                dp[e][j]=0;
                for(int k=1; k<7; k++)  //下面一层顶端为k
                    if(!isc[j][k])      //不冲突
                        dp[e][j]+=dp[e^1][k];
                dp[e][j]%=mod;      //取模
            }
        }
        LL sum=0;
        for(int i=1; i<7; i++)  //求最后一层的所有情况和
            sum+=dp[e][i];
        printf("%I64d\n",(sum*mult(4,n))%mod);  //每个都可以四面旋转
    }
    return 0;
}

🍊矩阵解法

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
#include<queue>
#include<stack>

#define mod 1000000007
typedef __int64 LL;

struct marx     //定义矩阵
{
    int d[6][6];
    marx() {}
    marx(int x) //构造：对角线赋值为x
    {
        memset(d,0,sizeof(d));
        for(int i=0; i<6; i++)
            d[i][i]=x;
    }
};

marx mul(marx a,marx b) //矩阵乘法
{
    marx res=marx(0);   //零
    for(int i=0; i<6; i++)
        for(int j=0; j<6; j++)
            for(int s=0; s<6; s++)
                res.d[i][j]=((a.d[i][j]*b.d[j][s])%mod+res.d[i][j])%mod;
    return res;
}

LL sb;
marx mult(marx t,LL n)  //矩阵快速幂 t^n
{
    marx res=marx(1);   //单位矩阵
    LL ans=1,ss=4*4;    //顺便计算了一下 4^n
    while(n)
    {
        if(n&1)res=mul(res,t),ans=(ans*ss)%mod;
        t=mul(t,t);
        ss=(ss*ss)%mod;
        n>>=1;
    }
    sb=ans;
    return res;
}

int main()
{
    LL n,m;
    while(~scanf("%I64d%I64d",&n,&m))
    {
        marx isc,ans;
        for(int i=0; i<6; i++)
        {
            for(int j=0; j<6; j++)
                isc.d[i][j]=1;  //初始化矩阵
            ans.d[1][i]=1;  //第一层各面情况
        }
        int a,b;
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&a,&b);
            isc.d[a-1][b-1]=isc.d[b-1][a-1]=0;  //标记互斥面
        }
        LL sum=0;
        ans=mul(ans,mult(isc,n-1)); //计算矩阵幂以及与第一层结果的乘积
        for(int i=0; i<6; i++)
            sum=(sum+ans.d[1][i])%mod;  //最终求和
        printf("%I64d\n",(sb*sum)%mod); //每一层可以四面旋转
    }
    return 0;
}

🚩组合数问题

??题目

给n,m,k，求有多少对( i , j ) (i,j)(i,j)满足1 ≤ i ≤ n，0 ≤ j ≤ m i n (i,m) 1 ≤ i ≤ n，0 ≤ j ≤ min(i,m) 1 ≤ i ≤ n，0 ≤?j ≤ min(i,m)且C (i,j) ≡ 0 ( mod k ) ；C(i,j) ≡ 0(mod k)C(i,j)≡0(modk)，k 是质数。其中 C(i,j)?是组合数，表示从 i 个不同的数中选出j个组成 一个集合的方案数。

【输入格式】

第一行两个数 t, k，其中 t 代表该测试点包含 t 组询问，k 的意思与上文中 相同。

接下来 t 行每行两个整数 n, m，表示一组询问。

【输出格式】

输出 t 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答 案除以?1 0 9 + 7 10^9 + 7109+7的余数。

【样例输入】

1 2
3 3

【样例输出】

1

??思路

题目意思转化为小于n和m的p进制数中有多少对数（i,j）i > j 且i中至少一位小于j，然后就可以愉快的数位dp了。在这里我们可以求它的对立，求i>=j，且i每一位都大于j的对数。由于p很大，所以不能使用记忆化搜索。

转移方程：

定义三个函数

1. LL calc(LL x, LL y) //x取值[0, x], y取值[0,y] x >=y的数量
2. LL calc1(LL x, LL y) // x不变，y取值为[0,y] x >= y的数量
3. LL calc2(LL x, LL y) // y不变 x取值为[0,x] x >= y的数量

🍊dp[i][0]：第i位无限制

dp[i][0]=dp[i?1][0]?calc(p?1,p?1)+dp[i?1][1]?calc(a[i]?1,p?1)+dp[i?1][2]?calc(p?1,b[i]?1)+dp[i?1][3]?calc(a[i]?1,b[i]?1)

要使第i位无限制，可以从上一位的无限制转移过来，也可以从i到达上界的数组转移过来，但是不能取a[i]，因为取了的话就不能叫做无限制了，这一位有了一个限制不能超过a[i]，后面两项同理。

🍊dp[i][1]：n的前i位为上界，m未达上界?

dp[i][1]=dp[i?1][1]?clac1(a[i],p?1)+dp[i?1][3]?calc1(a[i],b[i]?1)

要使n始终为上界，那么可以从两个地方转移过来，前一个有限制的在这里还是取了a[i],所以还是有限制。都有限制的，使得a[i]到达限制b[i]不到达限制就可以转到这个状态。

🍊dp[i][2]：m的前i位都为上界，n未达上界

dp[i][2]=dp[i?1][2]?clac2(p?1,b[i])+dp[i?1][3]?clac2(a[i]?1,b[i])

🍊dp[i][3]：n，m都到达了上界

dp[i][3]&=a[i]>b[i]?

因为要使的n的每一位都大于m。

??代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace {
  template <typename T> inline void read(T &x) {
    x = 0; T f = 1;char s = getchar();
    for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;
    for(;  isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);
    x *= f;
  }
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i <  (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define _srep(n,m,i)for (register int i = (n); i >= (m); i--)
#define _sfor(n,m,i)for (register int i = (n); i >  (m); i--)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
const LL Mod = 1e9+7;
const LL inv_2 = 5e8+4;
LL dp[65][4];
/*
用卢卡斯定理后转化为n，m的k进制数中，n中至少有一位大于m则模k为0.
考虑对立事件，求出n中所有位都大于m的对数，在用总方案减去它 
dp[i][0] :第i位无限制 
dp[i][1] :n的前i位为上界，m未达上界 
dp[i][2] :m的前i位位上界，n未达上界 
dp[i][3] :n，m都到达了上界 
*/
LL calc(LL x, LL y) {//x取值[0, x], y取值[0,y] x >=y的数量 
  if(x < 0|| y < 0) return 0;
  if(x < y) {
    x %= Mod; y %= Mod;
    return (x+2) * (x + 1) % Mod * inv_2 % Mod;
  }
  x %= Mod; y %= Mod;
  return ((y + 2) * (y + 1) % Mod * inv_2 % Mod + (x-y) * (y+1) % Mod) % Mod; 
}
LL calc1(LL x, LL y) { // x不变，y取值为[0,y] x >= y的数量 
  return min(x, y) + 1;
}
LL calc2(LL x, LL y) { // y不变 x取值为[0,x] x >= y的数量 
  if(x < y) return 0;
  return x - y + 1;
}
LL a[100], b[100], P;
int main() {
  int t; read(t); read(P);
  while(t--) {
    LL n, m, ans;
    read(n); read(m);
    if(m > n) m = n;
    ans = calc(n, m);    
    int lenn = 0, lenm = 0;
    while(n) a[lenn++] = n % P, n /= P;
    while(m) b[lenm++] = m % P, m /= P;
    n = max(lenn, lenm);
    memset(dp, 0, sizeof dp);
    dp[n][3] = 1;
    for(int i = n-1; ~i; i--) {
      dp[i][0] = dp[i+1][0] * calc(P-1, P-1) + dp[i+1][1] * calc(a[i]-1, P-1)
       + dp[i+1][2] * calc(P-1, b[i]-1) + dp[i+1][3] * calc(a[i]-1, b[i]-1);
      dp[i][1] = dp[i+1][1] * calc1(a[i], P-1) + dp[i+1][3] * calc1(a[i], b[i]-1);
      dp[i][2] = dp[i+1][2] * calc2(P-1, b[i]) + dp[i+1][3] * calc2(a[i]-1, b[i]);
      dp[i][3] = dp[i+1][3] & (a[i] >= b[i]);
      dp[i][0] %= Mod; dp[i][1] %= Mod; dp[i][2] %= Mod;
      a[i] = b[i] = 0;
    }
    ans -= dp[0][0] + dp[0][1] + dp[0][2] + dp[0][3];
    ans %= Mod;
    if(ans < 0) ans += Mod;
    printf("%lld\n", ans);
  }
}
/*
1 2
509295295705797874 372612087921270267
265498746
*/

📢📢📢

未完待续。。。敬请期待

📢📢📢

🍊🍊🍊

总结不易，看到这那就来个三连吧，肝。。。🍺🍺🍺

🍊🍊🍊

署名：左手の明天

《新程序员》：云原生和全面数字化实践

50位技术专家共同创作，文字、视频、音频交互阅读