2019年华东师大高可信软件工程夏令营机试

A. 构造序列B. 整数划分C. 一只小蜜蜂D. 逃离大魔王E. 派对F. 小啵的抽奖 只是自己的想法，因为没地方测评所以不能保证正确，有不恰当的地方和错误欢迎指正；也期待有更好的做法@我。

A. 构造序列

【题目】 【思路】

这道题目要我们将序列调整为不下降序列，那肯定要对相邻元素进行考虑，使任意一对相邻元素，后者都不小于前者，即观察两两元素之差。

利用贪心的思想来做，对于给定的序列，观察每一对相邻的元素后者是否大于前者：

如果大于等于，满足不下降就不需要调整；如果小于，那么需要将前者减少，或者将后者增大，操作次数为两元素之差。

那到底是调整前者还是调整后者？我认为如果对序列从左向右调整，那么应该尽可能让前者减少，这样可以让右边的序列部分有更多调整空间；反之对序列从右向左调整，应该先考虑让后者增大，这样可以给左边的序列让出更大的调整空间。

---

例如：对于序列：$2,6,2,5,2$，假设从右向左调整，首先对于最后一对相邻元素 $5,2$ 计算出后者减前者的差为-3，那么需要进行调整，此时当然应该调整后者2，将其操作三次加到5，而不应该对前者5进行调整，虽然也是调整三次，但是变成2了会导致前面的序列调整空间变小。那么调整完后序列变为 $2,6,2,5,5$ 。

上面说的是尽可能先调整什么，那么什么时候可以按照我们的想法调整，什么时候不得不调整另一个元素，也就是对于上面的例子最后一对相邻元素 $5，2$ 来说，一定可以将后者2增大为5吗？会不会出现只能调整前者5的情况？

对于调整后的序列 $2,6,2,5,5$ ，此时考虑倒数第二对相邻元素 $2,5$，后者比前者大，无需调整；

考虑倒数第三对相邻元素 $6,2$，后者大于前者，按照想法，期望将后者2调整为6，但是如果这样调整了，序列将变为 $2,6,6,5,5$，破坏了已经调整好的右子序列。

这时就找到了调整的规律，不能只考虑当前对相邻元素的差，还需要考虑后一对元素的差，那么对于序列 $6,2,5$ 来说，令left表示前一对元素差，right表示后一对元素差，那么 $left=-4,right=3$; 因为$|left|>right$，所以此时必须调整前者，否则会破坏调整好的右子序列。

【代码描述】

有了上述的过程，从右向左调整的过程就可以写出代码了（其中temp2存放序列，right初值设为很大的数INF，因为最右边的肯定可以无限增大，所有最后一对相邻元素一定可以调整后者)：

int right_solve(){ // 从右向左计算 int ans = 0; int right = INF, left; for(int i=n-2; i>=0; i--){ left = temp2[i+1] - temp2[i]; if(left >= 0){ // 满足升序关系，更新right right = left; } else{ if(left+right >= 0){ // 尽量让右边的变大，给左边留下空间 temp2[i+1] -= left; } else{ // 只能让左边的减小 temp2[i] += left; } // 调整好后，这一对相邻元素的差为0 right = 0; // 累加操作次数 ans -= left; } } return ans; }

做到这里我发现对于序列 $7,7,7,7,6,5$，按照上述从右向左的调整过程，会变为 $6,6,6,6,6,6$，调整次数为5，但是如果从左向右调整，会变为 $7,7,7,7,7,7$，调整次数为3，显然应该取两者更小值。

【完整代码】

#include<iostream> using namespace std; const int maxn = 5010; const int INF = 0x3fffffff; int num[maxn], temp1[maxn], temp2[maxn]; int n; void print(int* A){ // 打印出num数组内容 for(int i=0; i<n; i++){ printf("%d", A[i]); if(i != n-1) printf(" "); else printf("\n"); } } int left_solve(){ // 从左向右计算 int ans = 0; // 操作次数 int left = INF, right; for(int i=0; i<n-1; i++){ right = temp1[i+1] - temp1[i]; if(right >= 0){ // 满足升序关系，更新left left = right; } else{ if(left+right >= 0){ // 尽量让左边的减小，给右边留下空间 temp1[i] += right; left = 0; } else{ // 只能更新右边的 temp1[i+1] -= right; } left = 0; ans -= right; // 操作次数应加上right的绝对值 } } return ans; } int right_solve(){ // 从右向左计算 int ans = 0; int right = INF, left; for(int i=n-2; i>=0; i--){ left = temp2[i+1] - temp2[i]; if(left >= 0){ // 满足升序关系，更新right right = left; } else{ if(left+right >= 0){ // 尽量让右边的变大，给左边留下空间 temp2[i+1] -= left; } else{ // 只能让左边的减小 temp2[i] += left; } right = 0; ans -= left; } } return ans; } int main(){ scanf("%d", &n); for(int i=0; i<n; i++){ scanf("%d", &num[i]); temp1[i] = num[i]; temp2[i] = num[i]; } // print(num); int lnum = left_solve(); // printf("lnum: %d\n", lnum); // print(temp1); int rnum = right_solve(); // printf("rnum: %d\n", rnum); // print(temp2); if(lnum < rnum) printf("%d", lnum); else printf("%d", rnum); return 0; }

B. 整数划分

【题目】 【思路】 我这里用到的是动态规划的思想，假设$dp[x][n]$数组的含义为数n可以用1,2,3…x组成的和的形式的个数。 比如$dp[2][5]$就表示5可以拆成1,2组成的和的形式个数，那么有：

$1+1+1+1+1$$1+1+1+2$$1+2+2$

那么很容易想到$dp[2][5]$会和$dp[1][5]$有关，因为：

5拆成用1,2表示的形式数= (5拆成用1表示的形式数) + (5拆成有2的和表示的形式数)

因此：$dp[2][5]=dp[1][5]$ + 一定有2的和的组合；

那后者怎么计算呢？ 我们可以想到5中一定要有2，那不就是3的组合数每个加2：

$1+1+1$ --> $1+1+1+2$$1+2$ --> $1+2+2$

即dp[2][3]，于是找到了转移方程$dp[2][5]=dp[1][5]+dp[2][3]$， 写成一般项为： $dp[x][n]=dp[x-1][n]+dp[x][n-x]$

但是上式是有条件的，因为比如dp[3][2]，应该是数2由1构成的和的组合数，加上2由包含3的和的组合数，但是因为2比3小，所以没有由3构成的组合数，那么对于n < x的情况，后一项是0，变为了： $dp[x][n]=dp[x-1][n]$

【初始值的确定】

容易想到对于一张dp[x][n]的二维表来说，我们可以初始化dp[1][n] = 1，因为任何数x拆成只有1的组合都是x个1相加，也可以初始化dp[0][n] = 0，任何书都没法拆成只有0的和。

-01234500000001应该为11111123

初始化后可以看到按照公式，dp[1][0]应该填1（才能得出dp[1][1] = dp[0][1] + dp[1][0]），此时就可以按照推出的公式来了：

// 求dp[x][n] if(n >= x){ dp[x][n] = dp[x-1][n] + dp[x][n-x]; } else{ dp[x][n] = dp[x-1][n]; }

那么这个表应该为：

-0123450000000111111121122333112345

可以发现dp[x][0]都应该为1，可以自行理解一下。那么dp[3][n]就是所求答案了。 观察表中的规律，方块等于两圆圈和。

【源代码】

#include<iostream> #include<cstring> using namespace std; const int maxn = 40000; // dp[x][n]表示数n可以拆成用1,2...x的和组成形式的个数 long long dp[4][maxn]; long long solve(int x){ // 初始化 for(int i=1; i<=x; i++){ dp[0][i] = 0; } for(int i=1; i<=3; i++){ dp[i][0] = 1; } for(int i=1; i<=3; i++){ for(int j=1; j<=x; j++){ // 数j拆成的组合等于数j-1拆成的组合数（每一种组合后加1就是j了） dp[i][j] = dp[i-1][j]; if(j >= i){ // 新添加包含i的组合，那么等于数j-i拆成的组合数 （每一种组合后加i就是j了） dp[i][j] += dp[i][j-i]; } } } return dp[3][x]; } int main(){ int n; while(scanf("%d", &n) != EOF){ long long ans = solve(n); printf("%lld\n", ans); } return 0; }

C. 一只小蜜蜂

【题目】 【解题思路】

这里有两个问题需要考虑，分别是：

如何计算路线条数？如何按要求打印出路线？

首先第一个问题：路线条数的计算。

观察蜂窝图可以发现：对于每个数x来说，下一步只能是x+1或者x+2。那能够想到的是，路线条数和起点终点无关，而只和二者之间的差值有关，即 |终点 - 起点| 的值。

上面说到的话反过来看，就是对于终点x，能够到达这里的路线只有两种可能，一种是从x-1过来的，一种是从x-2过来的。那么不就是斐波那契数列嘛，$f[n]=f[n-1]+f[n-2]$，初始值为$f[1]=1,f[2]=2$

因为，当二者差值为1时，路线条数只有一条；当二者差值为2时，有两条路线。比如起点为2，终点为3，那么只有一条路线（2，3）；起点为2，终点为4，那么有两条路线（2，3，4）和（2，4）；

---

第二个问题，如何按照要求打印出路线？

这显然是一个递归的过程，我定义了一个打印函数：

void print(int cur);

cur表示当前加入的数，显然递归边界是cur为终点；将cur加入路线后，可以考虑将cur+1和cur+2加入路线，然后递归调用print(cur+1)或者print(cur+2); 该函数可以写为：

void print(int cur){ if(cur > b) return; // 当前处理的数 if(cur == b){ for(int i=0; i<route.size(); i++){ cout << route[i] << " "; } cout << endl; return ; } for(int i=cur+1; i<=cur+2; i++){ route.push_back(i); print(i); route.pop_back(); } }

这样就按照字典序打印出了所有路线： 但是题目只要求输出不同的部分，并且只输出n条路线，因此需要多加一些约束条件，可以发现公共前缀的最后一个元素的特点是：下一个元素和该元素的差不是1了，也就是只要增量是2，就说明到了不一样的地方，该输出了。

【源代码】

#include<iostream> #include<vector> using namespace std; // 路线 vector<int> route; // 起点，终点和需要输出的路径条数 int a, b, n; // 路线条数和起点、终点无关，只和二者之差有关 int solve(int len){ int pre = 1, p = 2; len -= 2; for(int i=1; i<=len; i++){ int temp = p; p = pre+p; pre = temp; } return p; } // 打印字典序前n的路线 int num = 0; void print(int cur){ if(cur > b) return; // 当前处理的数 if(cur == b){ num++; if(num <= n){ bool flag = false; // 不需要输出 if(num == 1) flag = true; // 第一次所有都要输出 for(int i=0; i<route.size(); i++){ if(flag){ cout << route[i] << " "; } else{ if(i!=route.size()-1 && route[i+1] != route[i]+1){ // 后一个数发生了跳越，就要开始输出了 flag = true; cout << "< " << route[i] << " > "; } } } cout << endl; } return ; } for(int i=cur+1; i<=cur+2; i++){ route.push_back(i); print(i); route.pop_back(); } } int main(){ cin>>a>>b>>n; int ans = solve(b-a); cout<<ans<<endl; route.push_back(a); print(a); return 0; }

D. 逃离大魔王

【解题思路】

这是一道搜索题目，用BFS非常合适，因为对每个结点来说，它相对于起点(1, 1, 1)的层数就是Yuki到这个点所需要的时间。

那么就方便了，用一个三维数组matrix存放每个点的情况，全部初始化为0，-1表示墙，matrix[x][y][z] = t表示该结点在t时刻，以及后面的t时间内都不能走。也就是访问到这个结点时，用该结点相对起点的层数和matrix值比较即可。

因此对于每个结点，有四个元素需要保存：

struct node{ int x, y, z; // 坐标 int level; //层数 };

【算法描述】 用队列queue来实现BFS，将队首元素出队，判断其是否已经到了门口并且层数小于T（大魔王回来的时间），是则返回该结点的层数即为最少要花的时间；否则判断其上下左右前后的六个结点是否需要访问，是的话更新其层数为当前结点层数加1，否则无操作。

判断某结点是否需要访问（注意越界、入过队列、墙、技能时间范围内）：

bool judge(int x, int y, int z, int time){ // 判断坐标(x,y,z)是否可以走 // 越界 if(x<1 || x>l || y<1 || y>w || z<1 || z>h) return false; // 已经入过列 if(inq[x][y][z]) return false; // 如果是墙不能走 if(matrix[x][y][z] == -1) return false; // 如果有天火和磁暴不能走 if(time >= matrix[x][y][z] && time <= 2*matrix[x][y][z] ) return false; return true; }

注意在BFS中每个结点仅入队列一次，所以创建一个三维bool数组inq指示某坐标点是否已经入队过。

【源代码】

#include<iostream> #include<queue> using namespace std; const int maxn = 80; int l, w, h, T; // 城堡的长宽高以及卡尔回来所需的时间 struct node{ int x, y, z; // 坐标 int level; //层数 }start, temp; //int time = 0; // 当前时刻，完全可以用层数表示 int matrix[maxn][maxn][maxn]; // -1表示墙，其他表示当前时刻t和后t时刻都不能通过 bool inq[maxn][maxn][maxn]; // 是否入过队列 int X[6] = {-1, 1, 0, 0, 0, 0}; // 增量矩阵 int Y[6] = {0, 0, -1, 1, 0, 0}; int Z[6] = {0, 0, 0, 0, -1, 1}; bool judge(int x, int y, int z, int time){ // 判断坐标(x,y,z)是否可以走 // 越界 if(x<1 || x>l || y<1 || y>w || z<1 || z>h) return false; // 已经入过列 if(inq[x][y][z]) return false; // 如果是墙不能走 if(matrix[x][y][z] == -1) return false; // 如果有天火和磁暴不能走 if(time >= matrix[x][y][z] && time <= 2*matrix[x][y][z] ) return false; return true; } int BFS(int x, int y, int z){ // 起点默认为(1, 1, 1) // 终点为(l, w, h) start.x = x, start.y = y, start.z = z; start.level = 0; queue<node> Q; Q.push(start); inq[x][y][z] = true; while(!Q.empty()){ node top = Q.front(); Q.pop(); if(top.x==l && top.y==w && top.z == h){ // 遇到了终点返回其层数 return top.level; } if(top.level > T){ // 时间到了，大魔王回来了 return -1; } for(int i=0; i<6; i++){ int newX = top.x + X[i]; int newY = top.y + Y[i]; int newZ = top.z + Z[i]; int level = top.level+1; // 到这个结点的时间为层数 if(judge(newX, newY, newZ, level)){ temp.x = newX, temp.y = newY, temp.z = newZ; temp.level = level; Q.push(temp); inq[newX][newY][newZ] = true; } } } } int main(){ scanf("%d%d%d%d", &l, &w, &h, &T); int k, a, b, c, t; scanf("%d", &k); // 城堡初始化 for(int i=1; i<=l; i++){ for(int j=1; j<=w; j++){ for(int k=1; k<=h; k++){ matrix[i][j][k] = 0; } } } for(int i=0; i<k; i++){ scanf("%d%d%d", &a, &b, &c); matrix[a][b][c] = -1; // 墙 } scanf("%d", &k); for(int i=0; i<k; i++){ scanf("%d%d%d", &t, &a, &b); // 天火 for(int j=1; j<=h; j++){ // 注意城堡从(1, 1, 1)开始，不是(0, 0, 0) matrix[a][b][j] = t; // 在t时刻和后t时间内，上下不能走 } } scanf("%d", &k); for(int i=0; i<k; i++){ scanf("%d%d%d%d", &t, &a, &b, &c); // 磁暴 for(int j=0; j<4; j++){ matrix[a+X[j]][b+Y[j]][c] = t; // 在t时刻和后t时间内，前后左右不能走 } } int ans = BFS(1, 1, 1); printf("%d\n", ans); return 0; } /* input: 3 3 2 10 3 1 3 1 2 3 2 1 1 2 2 1 1 1 3 3 1 1 2 3 1 1 output: 5 input:（仅时间减少） 3 3 2 4 3 1 3 1 2 3 2 1 1 2 2 1 1 1 3 3 1 1 2 3 1 1 output: -1 */

E. 派对

【解题思路】

看着这是一道拓扑排序的题呀，但是第一个样例中发现有相同的(u, v)组合，处理的时候要注意，我是用bool型邻接矩阵存的。

拓扑排序就是不断的把入度为0的结点加入拓扑序列，这里还要注意满足题目中说的编号越小的人越应该靠前进场，这里我不是很明白，如果是要求输出最小的字典序列的话，那么第二个样例应该输出：2 4 1 3，但样例给的输出是：4 1 2 3；二者都是满足约束的拓扑排序，我的代码是输出最小字典序的拓扑排序，不知道加粗的话如何理解。可能有其他理解方式像之前的蓝桥杯似的，就不纠结了，当复习一下拓扑排序好了。

【源代码】

#include<iostream> #include<queue> #include<vector> using namespace std; const int maxn = 30010; bool G[maxn][maxn]; int inDegree[maxn]; // 每个顶点的入度 int n, m; vector<int> res; // 答案 void topoSort(){ queue<int> q; for(int i=1; i<=n; i++){ if(inDegree[i] == 0){ q.push(i); res.push_back(i); } } while(q.size() != 0){ int top = q.front(); q.pop(); for(int v=1; v<=n; v++){ if(G[top][v]){ inDegree[v]--; if(inDegree[v] == 0){ q.push(v); res.push_back(v); } } } } } int main(){ fill(inDegree, inDegree+maxn, 0); fill(G[0], G[0]+maxn*maxn, false); scanf("%d%d", &n, &m); int u, v; // 这里u,v可能会重复 for(int i=0; i<m; i++){ scanf("%d%d", &u, &v); // 之前连过就不管了 if(!G[u][v]){ G[u][v] = true; inDegree[v]++; // v点入度加1 } } topoSort(); // 题目说了数据保证有解 for(int i=0; i<res.size(); i++){ printf("%d", res[i]); if(i != n-1) printf(" "); } return 0; } /* input: 5 10 3 5 1 4 2 5 1 2 3 4 1 4 2 3 1 5 3 5 1 2 output: 1 2 3 4 5 */

F. 小啵的抽奖

【题目】 【解题思路】

这道题考察错位重排，百度写的很好理解。

设n个球全放错的情况有 s(n)种，那么可以有如下思路： 不妨设1号球选择2号盒，接下来会有两种情况：

2号球选择1号盒，剩下 （n-2）个球去错排，有 s（n-2） 种情况；2号球不选择1号盒，则题目可转化为把编号为2→n的小球分别放入编号为 1、3、4……→n的盒子错位重排（即2号球不在1号盒、3号球不在3号盒…n号球不在n号盒），相当于n-1个球错位重排，有s(n-1) 种；

因为1号球可以放到[2,n]中任意一个盒子里，共 （n-1）种选择，于是有递推公式：$$s(n)=(n-1)\ast [s(n-1)+s(n-2)]$$

上面讲解来自百度百科，可以继续化简得到只依赖于n的表达式。

【源代码】

#include<iostream> using namespace std; const int maxn = 22; long long s[maxn]; //n位错位重排的数目 void solve(){ s[1] = 0; s[2] = 1; // 2 1 for(int i=3; i<=20; i++){ s[i] = (i-1)*(s[i-1]+s[i-2]); } for(int i=1; i<=20; i++){ printf("%lld\n", s[i]); } } int main(){ solve(); int n, m; scanf("%d", &n); for(int i=0; i<n; i++){ scanf("%d", &m); printf("%lld\n", s[m]); } return 0; }