第十届蓝桥杯大赛软件类省赛

这些题官网还没有解答的，我主要参考了b站UP主大雪菜的解法（绝大部分题先自己做了一遍），当然也网上查了一些解答，但发现现在网上的一些解法并不正确，希望可以给大家一个参考。

具体题目官网可以下载，Java、C++ 大学 A 组的题一样（有两题顺序不一样），写到一起。

我的代码应该避免不了错误（填空题还是可以保证的 o_o …），如果有任何问题，欢迎大家评论指正。

Java 大学 B 组

试题 A: 组队

【问题描述】
作为篮球队教练，你需要从以下名单中选出 1 号位至 5 号位各一名球员，
组成球队的首发阵容。
每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1
号位至 5 号位的评分之和最大可能是多少？

编号 1 号位 2 号位 3 号位 4 号位 5 号位
1 97 90 0 0 0
2 92 85 96 0 0
3 0 0 0 0 93
4 0 0 0 80 86
5 89 83 97 0 0
6 82 86 0 0 0
7 0 0 0 87 90
8 0 97 96 0 0
9 0 0 89 0 0
10 95 99 0 0 0
11 0 0 96 97 0
12 0 0 0 93 98
13 94 91 0 0 0
14 0 83 87 0 0
15 0 0 98 97 98
16 0 0 0 93 86
17 98 83 99 98 81
18 93 87 92 96 98
19 0 0 0 89 92
20 0 99 96 95 81
（如果你把以上文字复制到文本文件中，请务必检查复制的内容是否与文
档中的一致。在试题目录下有一个文件 team.txt，内容与上面表格中的相同，
请注意第一列是编号）

思路
我首先想的就是暴力，（怪不得叫暴力杯），直接枚举所有情况。结果为490，不过也可以直接看出来。

#include<vector>
#include<iostream>

using namespace std;

vector<int> peo[21];

int main(){
    
    int a,x;
    for(int i=0;i<20;i++){
    
        cin >> a;
        for(int j=0;j<5;j++){
    
            cin >> x;
            peo[a-1].push_back(x);
        }
    }

    int res = 0;
    for(int i=0;i<20;i++)
        for(int j=0;j<20;j++){
    
            if(i == j) continue;
            for(int jj=0;jj<20;jj++){
    
                if(i == jj || j == jj) continue;
                for(int jjj=0;jjj<20;jjj++){
    
                    if(jjj == i || jjj == jj || jjj == i) continue;
                    for(int jjjj=0;jjjj<20;jjjj++){
    
                        if(jjjj == i || jjjj == j || jjjj == jj || jjjj == jjj) continue;
                        res = max(res,peo[i][0]+peo[j][1]+peo[jj][2]
                                  +peo[jjj][3]+peo[jjjj][4]);
                    }
                }
            }
        }
    cout << res;
    return 0;
}

试题 B: 不同子串

【问题描述】
一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成
的串。例如，字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab，一共 7 个。
注意在计算时，只算本质不同的串的个数。
请问，字符串0100110001010001 有多少个不同的非空子串？

思路
枚举起点和终点，答案是100。

#include<vector>
#include<iostream>
#include<unordered_set>
using namespace std;

unordered_set<string> st;

int main(){
    
    string str = "0100110001010001";
    for(int i=0;i<str.size();i++)
        for(int j=i+1;j<=str.size();j++)
            st.insert(str.substr(i,j-i));
    cout << st.size();
    return 0;
}

试题 C: 数列求值

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

思路
直接算就可以了，答案是4659。

#include<iostream>
using namespace std;

int dp[20190334];

int main(){
    
    dp[0] = dp[1] = dp[2] = 1;
    for(int i=3;i<20190334;i++){
    
        dp[i] = ((dp[i-1]+dp[i-2])%10000+dp[i-3])%10000;
    }
    cout << dp[20190324 - 1] << endl;
    return 0;
}

试题 D: 数的分解

【问题描述】
把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包
含数字 2 和 4，一共有多少种不同的分解方法？
注意交换 3 个整数的顺序被视为同一种方法，例如 1000+1001+18 和
1001+1000+18 被视为同一种。

思路
直接算就可以了，答案是40785。

#include<iostream>
using namespace std;

inline bool is_ok(int x){
    
    while(x){
    
        if(x % 10 == 2 || x % 10 == 4) return false;
        x /= 10;
    }
    return true;
}

int main(){
    
    int res = 0;
    for(int i=1;i<2019;i++){
    
        if(!is_ok(i)) continue;
        for(int j=1;j<2019;j++){
    
            if(!is_ok(j)) continue;
            if(2019-i-j <= 0 || !is_ok(2019-i-j)) continue;
            if(i < j && j < 2019-i-j) res++;
        }
    }
    cout << res << endl;
    return 0;
}

试题 E: 迷宫 – important

【问题描述】
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可
以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这
个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，
一共 10 步。其中 D、 U、 L、 R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，
其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中D<L<R<U。（如果你把以下文字复制到文本文件中，请务
必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 maze.txt，
内容与下面的文本相同）
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无法记录最短路径的具体路径，就写了一个DFS版本的，给的4*6迷宫正确跑出来了，但是30*50的迷宫跑不出来，时间复杂度太高了。（代码还没考虑字典序）

#include<iostream>
#include<queue>
using namespace std;

const int ROW = 30;
const int COL = 50;
int X[] = {
    0,0,-1,1};
int Y[] = {
    1,-1,0,0};
char C[] = {
    'R','L','U','D'};
char g[ROW][COL];
bool vis[ROW][COL];

inline bool is_ok(int x,int y){
    
    if(x < 0 || x >= ROW || y < 0 || y >= COL) return false;
    if(vis[x][y] || g[x][y] == '1') return false;
    return true;
}

string res = "";

void dfs(int x,int y,string temp){
    
    if(res != "" && temp.size() > res.size()) return;
    if(x == ROW-1 && y == COL-1){
    
        if(res == "" || res.size() > temp.size())
            res = temp;
        return;
    }

    for(int i=0;i<4;i++){
    
        int newx = x+X[i];
        int newy = y+Y[i];
        if(is_ok(newx,newy)){
    
            vis[newx][newy] = true;
            dfs(newx,newy,temp+C[i]);
            vis[newx][newy] = false;
        }
    }
}

int main(){
    
    for(int i=0;i<ROW;i++)
        for(int j=0;j<COL;j++)
            cin >> g[i][j];

    dfs(0,0,"");
    cout << res << endl;
    return 0;
}

然而实际上BFS还是可以通过一定手段得到具体路径的。
输出为：

DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
186

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

const int ROW = 30;
const int COL = 50;
int X[] = {
    1,0,0,-1};
int Y[] = {
    0,-1,1,0};
char C[] = {
    'D','L','R','U'};
char g[ROW][COL];
bool vis[ROW][COL];

inline bool is_ok(int x,int y){
    
    if(x < 0 || x >= ROW || y < 0 || y >= COL) return false;
    if(vis[x][y] || g[x][y] == '1') return false;
    return true;
}

struct node{
    
	int x,y;
	string str;
	node(int x,int y,string str):x(x),y(y),str(str){
    }
};

void bfs(){
    
    queue<node> q;
    q.push(node(0,0,""));
    vis[0][0] = true;
    while(q.size()){
    
		int len = q.size();
        while(len--){
    
            auto item = q.front();
            q.pop();
            
			if(item.x == ROW-1 && item.y == COL-1){
    
				cout << item.str << endl;
				cout << item.str.size() << endl;
				return;
			}
				
            for(int i=0;i<4;i++){
    
                int newx = item.x+X[i];
                int newy = item.y+Y[i];
                if(is_ok(newx,newy)){
    
                	q.push(node(newx,newy,item.str+C[i]));
                	vis[newx][newy] = true;
				} 
            }
        }
    }
}

int main(){
    
    for(int i=0;i<ROW;i++)
        for(int j=0;j<COL;j++)
            cin >> g[i][j];
    bfs();
    return 0;
}

试题 F: 特别数的和

【问题描述】
小明对数位中含有 2、 0、 1、 9 的数字很感兴趣（不包括前导 0），在 1 到
40 中这样的数包括 1、 2、 9、 10 至 32、 39 和 40，共 28 个，他们的和是 574。
请问，在 1 到 n 中，所有这样的数的和是多少？
【输入格式】
输入一行包含两个整数 n。
【输出格式】
输出一行，包含一个整数，表示满足条件的数的和。
【样例输入】
40
【样例输出】
574

思路
因为蓝桥杯貌似不支持C++11，所以非填空题，我就写非C++11代码了。
这道题明显送分呀！

#include<iostream>
using namespace std;

inline bool is_ok(int x){
    
	while(x){
    
		int d = x % 10;
		if(d == 2 || d == 0 || d == 1 || d == 9) return true;
		x /= 10;
	}
	return false;
}

int main(){
    
	int x;
   	cin >> x;
   	int res = 0;
   	for(int i=1;i<=x;i++)
   		if(is_ok(i))
   			res+=i;
   	cout << res;
    return 0;
}

试题 G: 外卖店优先级 – todo

【问题描述】
“饱了么”外卖系统中维护着 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

恶心的模拟题 (；′⌒`)

试题 H: 人物相关性分析

【问题描述】
小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob
有多少次同时出现。
更准确的说，小明定义 Alice 和 Bob“同时出现”的意思是：在小说文本
中 Alice 和 Bob 之间不超过 K 个字符。
例如以下文本：
This is a story about Alice and Bob. Alice wants to send a private message to Bob.
假设 K = 20，则 Alice 和 Bob 同时出现了 2 次，分别是”Alice and Bob”
和”Bob. Alice”。前者 Alice 和 Bob 之间有 5 个字符，后者有 2 个字符。
注意:

1. Alice 和 Bob 是大小写敏感的， alice 或 bob 等并不计算在内。
2. Alice 和 Bob 应为单独的单词，前后可以有标点符号和空格，但是不能
   有字母。例如 Bobbi 並不算出现了 Bob。
   【输入格式】
   第一行包含一个整数 K。
   第二行包含一行字符串，只包含大小写字母、标点符号和空格。长度不超
   过 1000000。
   【输出格式】
   输出一个整数，表示 Alice 和 Bob 同时出现的次数。
   【样例输入】
   20
   This is a story about Alice and Bob. Alice wants to send a private message to Bob.
   【样例输出】
   2

按照题意写应该就可以了。记住读入一行字符串的写法getline(cin,str);。

#include<iostream>
#include<vector>
#include<string>
using namespace std;

const string a = "Alice";
const string b = "Bob";

struct word{
    
	int b,e;
	string w;
	word(string w,int b,int e):w(w),b(b),e(e){
    }
};
vector<word> vec;

inline bool check(char c) {
    
    return c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z';
}

int main(){
    
	int n;
	cin >> n;
	getchar();
	string str;
	getline(cin,str);
	
	for(int i=0;i<str.size();i++){
    
		if(!check(str[i])) continue;
		int j = i;
		while(j<str.size() && check(str[j])) j++;
		vec.push_back(word(str.substr(i,j-i),i,j));
		i = j;
	}
	
	int res = 0;
	word last("",-1,-1);
	for(int i=0;i<vec.size();i++){
    
		if(vec[i].w == a){
    
			if(vec[i].b - last.e <= n && last.w == b) res++;
			last = vec[i];
		}
		else if(vec[i].w == b){
    
			if(vec[i].b - last.e <= n && last.w == a) res++;
			last = vec[i];
		}
	}
	cout << res << endl;  
    return 0;
}

试题 I: 后缀表达式 – todo

【问题描述】
给定 N 个加号、 M 个减号以及 N + M + 1 个整数 A1; A2; · · · ; AN+M+1，小
明想知道在所有由这 N 个加号、 M 个减号以及 N + M + 1 个整数凑出的合法的
后缀表达式中，结果最大的是哪一个？
请你输出这个最大的结果。
例如使用1 2 3 + -，则 “2 3 + 1 -” 这个后缀表达式结果是 4，是最大的。
【输入格式】
第一行包含两个整数 N 和 M。
第二行包含 N + M + 1 个整数 A1; A2; · · · ; AN+M+1。
【输出格式】
输出一个整数，代表答案。
【样例输入】
1 1
1 2 3
【样例输出】
4

本来以为直接排序后先加后减就可以了，结果后缀表达式一次可以运算多个数，需要按照负号的个数和负数的个数来分类讨论。

试题 J: 灵能传输 – todo

【题目背景】
在游戏《星际争霸 II》中，高阶圣堂武士作为星灵的重要 AOE 单位，在
游戏的中后期发挥着重要的作用，其技能”灵能风暴“可以消耗大量的灵能对
一片区域内的敌军造成毁灭性的伤害。经常用于对抗人类的生化部队和虫族的
刺蛇飞龙等低血量单位。
【问题描述】
你控制着 n 名高阶圣堂武士，方便起见标为 1; 2; · · · ; n。每名高阶圣堂武士
需要一定的灵能来战斗，每个人有一个灵能值 ai 表示其拥有的灵能的多少（ai
非负表示这名高阶圣堂武士比在最佳状态下多余了 ai 点灵能， ai 为负则表示这
名高阶圣堂武士还需要 −ai 点灵能才能到达最佳战斗状态）。现在系统赋予了
你的高阶圣堂武士一个能力，传递灵能，每次你可以选择一个 i 2 [2; n − 1]，若
ai ≥ 0 则其两旁的高阶圣堂武士，也就是 i − 1、 i + 1 这两名高阶圣堂武士会从
i 这名高阶圣堂武士这里各抽取 ai 点灵能；若 ai < 0 则其两旁的高阶圣堂武士，
也就是 i − 1; i + 1 这两名高阶圣堂武士会给 i 这名高阶圣堂武士 −ai 点灵能。形
式化来讲就是 ai−1+ = ai; ai+1+ = ai; ai− = 2ai。
灵能是非常高效的作战工具，同时也非常危险且不稳定，一位高阶圣堂
武士拥有的灵能过多或者过少都不好，定义一组高阶圣堂武士的不稳定度为
maxn
i=1jaij，请你通过不限次数的传递灵能操作使得你控制的这一组高阶圣堂武
士的不稳定度最小。
【输入格式】
本题包含多组询问。输入的第一行包含一个正整数 T 表示询问组数。
接下来依次输入每一组询问。
每组询问的第一行包含一个正整数 n，表示高阶圣堂武士的数量。
接下来一行包含 n 个数 a1; a2; · · · ; an。
【输出格式】
输出 T 行。每行一个整数依次表示每组询问的答案。
【样例输入】
3 3
5 -2 3
4
0 0 0 0
3
1 2 3
【样例输出】
3 0 3

好让人头晕的题目呀！！！

C++ 大学 B 组

试题 A: 组队 – completed

试题 B: 年号字串

【问题描述】
小明用字母 A 对应数字 1， B 对应 2，以此类推，用 Z 对应 26。对于 27
以上的数字，小明用两位或更长位的字符串来对应，例如 AA 对应 27， AB 对
应 28， AZ 对应 52， LQ 对应 329。
请问 2019 对应的字符串是什么？

思路
直接写26进制会在Z处出问题，但是对于这个填空题还是可以正确算出来是BYQ的，参考了别人的处理：
有26个字母，即当做26进制计算，但又不完全是26进制，因为当被26整除时并不需要进位，而是用Z表示；因此用递归算法时，单独处理被26整除的情况。

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

void re(int x){
    
	if(x == 0) return;
	if(x%26 == 0){
    	// 这里 
		re((x-1)/26);
		cout << "Z"; 
	}else{
    
		re(x/26);
		char s = 'A'+x%26-1;
		cout << s;
	}
}

int main(){
    
	for(int x=1;x<=2019;x++){
    
		re(x);
		cout << endl; // BYQ 
	}
    return 0;
}

试题 C: 数列求值 – completed

试题 D: 数的分解 – completed

试题 E: 迷宫 – completed

试题 F: 特别数的和 – completed

试题 G: 完全二叉树的权值

【问题描述】
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从
上到下、从左到右的顺序依次是 A1, A2, · · · AN，如下图所示：
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点
权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 1。
【输入格式】
第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, · · · AN 。
【输出格式】
输出一个整数代表答案。
【样例输入】
7
1 6 5 4 3 2 1
【样例输出】
2

思路
比较坑的是有可能int溢出，所以要用long long，还有就是有负数，所以初始化max_要用INT_MIN（之前我直接用0初始化了）。

#include<iostream>
using namespace std;

int a[100010];

int main(){
    
	int n;
	cin >> n;
	for(int i=0;i<n;i++) cin >> a[i];
	
	long long res = 0,max_ = INT_MIN;
	int depth = 0;
	int i = 0;
	while(i<n){
    
		int num = 1<<depth;
		long long temp = 0;
		while(num-- && i<n) temp+=a[i++];
		if(temp > max_){
    
			max_ = temp;
			res = depth;
		}
		depth++;
	}
	cout << res+1 << endl; 
    return 0;
}

试题H：等差数列

【问题描述】
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一
部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有
几项？
【输入格式】
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A1; A2; · · · ; AN。 (注意 A1 ∼ AN 并不一定是按等差数
列中的顺序给出)
【输出格式】
输出一个整数表示答案。
【样例输入】
5
2 6 4 10 20
【样例输出】
10

思路
关键应该是求出等差数列的d，而d为每相邻项的差的最大公约数。有一些坑，比如判断d是否为0，以及直接以为是最小相邻项的差为d。

#include<iostream>
#include<algorithm>
#include<set>

using namespace std;

int a[100010];

int gcd(int a,int b){
    
	if(b == 0) return a;
	return gcd(b,a%b);
}

int main(){
    
	// 若为1 3 6,那么q != 2 && q != 3, q == gcd(2,3)
	int n;
	cin >> n;
	for(int i=0;i<n;i++) cin >> a[i];
	sort(a,a+n);
	
	set<int> d;
	for(int i=0;i<n-1;i++) d.insert(a[i+1]-a[i]);
	
	int gcdv = -1;
	for(set<int>::iterator it=d.begin();it!=d.end();++it){
    
//		cout << *it << endl;
		if(gcdv == -1) gcdv = *it;
		else gcdv = gcd(gcdv,*it);
	}
	if(gcdv == 0) cout << n << endl; // 这里容易没考虑 
	else cout << (a[n-1]-a[0])/gcdv+1 << endl;
    return 0;
}

试题 I: 后缀表达式 – completed

试题 J: 灵能传输 – completed

Java/C++ 大学 A 组

试题 A: 平方和

【问题描述】
小明对数位中含有 2、 0、 1、 9 的数字很感兴趣，在 1 到 40 中这样的数包
括 1、 2、 9、 10 至 32、 39 和 40，共 28 个，他们的和是 574，平方和是 14362。
注意，平方和是指将每个数分别平方后求和。
请问，在 1 到 2019 中，所有这样的数的平方和是多少？

思路
送分题吧，注意使用long long，结果为：
2019
2658417853

#include<iostream>
using namespace std;

inline bool is_ok(int x){
    
	while(x){
    
		int d = x%10;
		if(d == 2 || d == 0 || d == 1 || d == 9) return true;
		x /= 10;
	}
	return false;
}

int main(){
    
	int n; cin >> n;
	long long res = 0;
	for(int i=1;i<=n;i++){
    
		if(is_ok(i)){
    
			res += i*i;
		}
	} 
	cout << res << endl;
    return 0;
}

试题 B: 数列求值 – completed

试题 C: 最大降雨量

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

思路
直接暴力算不完呀！完全没有思路，看了看其他大佬的思路，orz
探讨一下这道题的思路，就是每周用的符列在一起就是一个7*7的矩阵
###=###
###=###
###=###
###&###
###=###
###=###
###=###
其中=表示每周的中位数，&表示最后的中位数，所以，&后面和下面的数字一定要比&大，所以
###=###
###=###
###=###
###& 35 36 37
###38 39 40 41
###42 43 44 45
###46 47 48 49
所以最后的数字是34.

试题 D: 迷宫 – completed

试题 E: RSA 解密 – important

【问题描述】
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 时（小于 n），计算 C = Xd mod n，则 C 是加
密后的密文。
当收到密文 C 时，可使用私钥解开，计算公式为 X = Ce mod n。
例如，当 p = 5, q = 11, d = 3 时， n = 55, e = 27。
若加密数字 24，得 243 mod 55 = 19。
解密数字 19，得 1927 mod 55 = 24。
现在你知道公钥中 n = 1001733993063167141, d = 212353，同时你截获了
别人发送的密文 C = 20190324，请问，原文是多少？

思路
首先要知道扩展欧几里得算法：
已知整数a、b，在求得a,b最大公约数的同时，找到整数x，y (有一个可能为负数)，使之满足：ax+by = gcd(a , b);

推导参考文章：https://blog.csdn.net/destiny1507/article/details/81750874

扩展欧几里得算法可以在 O(logn)的时间复杂度内求出系数 x,y。

C++ 代码

int exgcd(int a, int b, int &x, int &y){
    
    if (b == 0){
    
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;
}

还需要会快速幂算法，这里就不介绍了。

// 快速计算 a^b%c
long long fast_pow(long long a,long long b,long long c){
    
	long long res = 1%c, temp = a;
	while(b){
    
		if(b & 1) res = (res*temp)%c;
		temp = (temp*temp)%c;
		b >>= 1;
	}
	return res;
}

自己写的C++，缺少高精度的乘法，在快速幂乘法时会溢出。所以计算 fast_pow(C,e,n)需要依靠python的快速幂算法解决。

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

// ax + by == gcd(a,b)
long long exgcd(long long a,long long b,long long& x,long long& y){
    
	if(b == 0){
    
		x = 1;y = 0;
		return a;
	}
	long long d = exgcd(b,a%b,y,x);
	y -= (a/b)*x;
	return d;
}

long long fast_pow(long long a,long long b,long long c){
    
	long long res = 1%c, temp = a;
	while(b){
    
		if(b & 1) res = (res*temp)%c;
		temp = (temp*temp)%c;
//		cout << res << " " << temp << endl;
		b >>= 1;
	}
	return res;
}

int main(){
    
	long long n = 1001733993063167141, d = 212353;
	long long C = 20190324;	
//	long long n = 55, d = 3;
//	long long C = 19;
	long long p,q;
	for(long long i=3;i<n;i+=2) // 找质数 
		if(n%i == 0){
    
			p = i;
			q = n/i;
			break;
		}
	cout << p << " " << q << endl; // 891234941 1123984201

	// d*e + fn*k == 1 且 gcd(d,fn) == 1 
	long long fn = (p-1)*(q-1);
	long long e,k;
	exgcd(d,fn,e,k);
	
	// e移动到正数 这里溢出了?  
	e = e%fn + fn;
	e = e%fn; 
	cout << e << " " << k << " " << fn << endl; // 823816093931522017 37716 1001733991047948000 
	// cout << (d*e % fn == 1) << endl; // 在python上验证成立 
	
	// X = pow(C,e) mod n C++的取模快速幂还是要溢出 python直接**运算，算不完也得快速幂 
	long long X = fast_pow(C,e,n); // 这里要用python，也可以C++大整数实现乘法，但是太麻烦 
	cout << X << endl; // 因为快速幂溢出，结果为-774706639346732542 
    return 0;
}

python测试代码，输出为
579706994112328949
20190324
答案即为579706994112328949。

def fast_pow(C, e, n):
    res = 1%n
    temp = C
    while(e > 0):
        if(e & 1):
            res = (res*temp)%n
        temp = (temp*temp)%n
        e >>= 1
    return res

C = 20190324
e = 823816093931522017
n = 1001733993063167141
print(fast_pow(C,e,n))
d = 212353
print(fast_pow(C,e,n)**d%n)

虽然破译RSA密码很爽，但是也太不容易了吧！（而且现实中的n很大，第一步找p、q就算不完）

试题 F: 完全二叉树的权值 – completed

试题 G: 外卖店优先级 – completed

试题 H: 修改数组 – important

【问题描述】
给定一个长度为 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
【评测用例规模与约定】
对于 80% 的评测用例， 1 ≤ N ≤ 10000。
对于所有评测用例， 1 ≤ N ≤ 100000， 1 ≤ Ai ≤ 1000000。

思路
最直接的想法肯定是直接模拟呗，然后我自己构造最坏情况下的数据，发现要跑7秒钟（不过大概80%的数据还是可以过的 o_o …）

#include<iostream>
#include<string>
#include<fstream>

using namespace std;

int a[2000010];
bool vis[2000010];

int main(){
    
	// 坏情况 7.772 seconds
//	ofstream outf("abc.txt");
//	outf << 100000 << endl;
//	for(int i=100000;i>=1;i--)
//		if(i > 50000) outf << i << " ";
//		else outf << 50000 << " ";
//    outf.close();
//    
//    ifstream inf("abc.txt");
//    int n;
//	inf >> n;
//	for(int i=0;i<n;i++){
    
//		inf >> a[i];
//		while(vis[a[i]]) a[i]++;
//		vis[a[i]] = true;
//	}
//	inf.close();
	
	int n;
	cin >> n;
	for(int i=0;i<n;i++){
    
		cin >> a[i];
		while(vis[a[i]]) a[i]++;
		vis[a[i]] = true;
	}
	for(int i=0;i<n;i++){
    
		string s = (i == n-1)?"":" ";
		cout << a[i] << s;
	}
	return 0;
}

正确解法应该是保存区间。可以用set<pair<int,int>>,但是用并查集更加巧妙

#include<iostream>
#include<string>
using namespace std;

int a[100010];
int father[2000010];

int findFather(int a){
    
	if(a != father[a]) father[a] = findFather(father[a]);
	return father[a];
} 

void Union(int a,int b){
    
	int fathera = findFather(a);
	int fatherb = findFather(b);
	if(a != b) father[fathera] = fatherb;
}

int main(){
    
	// 并查集  findFather保存区间右端点 
	for(int i=0;i<2000010;i++) father[i] = i;
	
	int n;
	cin >> n;
	for(int i=0;i<n;i++){
    
		cin >> a[i];
		a[i] = findFather(a[i]);
		Union(a[i],a[i]+1); // 让a[i]的father的father为a[i]+1;
	}
	for(int i=0;i<n;i++){
    
		string s = (i == n-1)?"":" ";
		cout << a[i] << s;
	}
	return 0;
}

试题 I: 糖果 – important

【问题描述】
糖果店的老板一共有 M 种口味的糖果出售。为了方便描述，我们将 M 种
口味编号 1 ∼ M。
小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而
是 K 颗一包整包出售。
幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知
道每包内的糖果口味。
给定 N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖
果。
【输入格式】
第一行包含三个整数 N、 M 和 K。
接下来 N 行每行 K 这整数 T1; T2; · · · ; TK，代表一包糖果的口味。
【输出格式】
一个整数表示答案。如果小明无法品尝所有口味，输出 −1。
【样例输入】
6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2
【样例输出】
2
【评测用例规模与约定】
对于 30% 的评测用例， 1 ≤ N ≤ 20 。
对于所有评测样例， 1 ≤ N ≤ 100， 1 ≤ M ≤ 20， 1 ≤ K ≤ 20， 1 ≤ Ti ≤ M。

思路
用的BFS，用结点保存当前选了哪些袋vis、当前这些袋选了哪些糖果。数据范围较小，应该是没有问题。（这道题还真不确定）

#include<iostream>
#include<string>
#include<cstring>
#include<queue>

using namespace std;

int a[105][25];

struct node{
    
	bool vis[105];
	int now; // 当前选了那些糖果
	node(){
    
		memset(vis,0,sizeof vis);
		now = 0;
	}
};

int main(){
    
	int n,m,k;
	int fed;
	cin >> n >> m >> k;
	fed = (1<<m)-1;
	
	for(int i=0;i<n;i++)
		for(int j=0;j<k;j++)
			cin >> a[i][j];
	
	queue<node> q;
	q.push({
    });
	int res = 0;
	while(q.size()){
    
		int len = q.size();
		while(len--){
    
			node it = q.front();
			q.pop();
			if(it.now == fed){
    
				// 测试查看选了哪些行 
				// for(int i=0;i<105;i++) if(it.vis[i]) cout << i << " ";
				cout << res << endl;
				return 0;
			}
			
			for(int i=0;i<n;i++){
    
				node newIt = it;	
				if(newIt.vis[i]) continue;
				newIt.vis[i] = true;
				for(int j=0;j<k;j++)
					newIt.now |= 1<<(a[i][j]-1); 
				q.push(newIt);
			}
		}
		res++;
	}
	cout << -1 << endl;
	return 0;
}

试题 J: 组合数问题 – important

【问题描述】
给 n; m; k，求有多少对 (i; j) 满足 1 ≤ i ≤ n; 0 ≤ j ≤ min(i; m) 且 Cij ≡
0(mod k)， k 是质数。其中 Cij 是组合数，表示从 i 个不同的数中选出 j 个组成
一个集合的方案数。
【输入格式】
第一行两个数 t; k，其中 t 代表该测试点包含 t 组询问， k 的意思与上文中
相同。
接下来 t 行每行两个整数 n; m，表示一组询问。
【输出格式】
输出 t 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答
案除以 109 + 7 的余数。
【样例输入】
1 2
3 3
【样例输出】
1
【样例说明】
在所有可能的情况中，只有 C21 = 2 是 2 的倍数。
【样例输入】
2 5
4 5
6 7
【样例输出】
0 7
【样例输入】
3 23
23333333 23333333
233333333 233333333
2333333333 2333333333
【样例输出】
851883128
959557926
680723120
【数据规模和约定】
对于所有评测用例， 1 ≤ k ≤ 10^8; 1 ≤ t ≤ 10^5; 1 ≤ n; m ≤ 10^18，且 k 是质数。
评测时将使用 10 个评测用例测试你的程序，每个评测用例的限制如下：

评测用例编号		t 		n; m 		k
1; 2 		≤ 1 		≤ 2000 		≤ 100
3; 4 		≤ 10^5 		≤ 2000 		≤ 100
5; 6; 7 		≤ 100 		≤ 10^18 		≤ 100
8; 9; 10 		≤ 10^5 		≤ 10^18 		≤ 10^8

思路
本来是准备放弃治疗 ○|￣|_，但是找到了该题的一个题解地址：
https://www.luogu.com.cn/problemnew/solution/P2822
大佬们太强了，我感觉我的数论还可以抢救一波！

首先了解一些定义：
设m是大于1的正整数，a、b是整数，如果m|(a-b)，则称a与b关于模m同余，记作a≡b(mod m)。显然有如下事实：

• 若a≡0(mod m)，则m|a;
• a≡b(mod m)等价于a与b分别用m去除，余数相同。

然后是组合数和杨辉三角的关系，具体查看上面的题解。

下面的解法可以在洛谷里面得95分，但是按照原题的数据范围，这种解法最多只能过4个样例

#include<iostream>
#include<queue>
#include<cstdio>

using namespace std;

const int N = 2001;
long long C[N][N]; 

void init(int k){
    
	// 想象杨辉三角 
	C[0][0] = 1;
	C[1][0] = 1,C[1][1] = 1;
	for(int i=2;i<N;i++) C[i][0] = 1;
	// C j上i下 
	for(int i=2;i<N;i++)
		for(int j=1;j<=i;j++)
			C[i][j] = (C[i-1][j-1] + C[i-1][j])%k;
}

int main(){
    
	int t,k;
	scanf("%d%d",&t,&k);
	
	init(k);

	while(t--){
    
		int n,m;
		int res = 0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
    
			int min_ = min(i,m);
			for(int j=0;j<=min_;j++)
				if(C[i][j] == 0) res++;
		}
		cout << res << endl;
	}
	return 0;
}

正确解法应该用Lucas定理，惹不起 (⊙ˍ⊙)：
1.当n,m都很小的时候可以利用杨辉三角直接求。
C(n,m)=C(n-1,m)+C(n-1,m-1)；
2、n和m较大，但是p为素数的时候
Lucas定理是用来求 c(n,m) mod p，p为素数的值。