“Shopee杯” E 起来编程暨武汉大学 2020 年大学生程序设计大赛（网络预选赛）解题报告
比赛地址：“Shopee杯” e起来编程暨武汉大学2020年大学生程序设计大赛（网络预选赛）
题意
找出$0 \sim n$之间所有满足$(n+1)|(n^2+1)$的自然数
解题思路
根据平方差公式：$n^2-1=(n+1)(n-1)$ 可知 $(n+1)|(n^2+1)$。
1 2 3 4 5 6 7 8 9 10 11 12 #include <bits/stdc++.h> using namespace std; int main() { int T; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); printf("%d\n", n ? (n - 1) : n); } return 0; }
题意
给定一个数组，求有多少个数对 $a_i$ , $a_j$ , $i \neq j$ 满足 $a_i + a_j == 0$。
解题思路
记录下数组中每个权值的出现次数，记数组中权值 $i$ 的出现次数为 $cnt_i$ 。那么答案就是：
$\sum\limits_{i=1}^{max(a)} cnt_i \times cnt_{-i} + cnt_0 \times (cnt_0 - 1)/2$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include<bits/stdc++.h> using namespace std; int read(){ int c=0,nx,sign=1; while(!isdigit(nx = getchar())) if(nx=='-') sign=-1; while(isdigit(nx)) c=c*10+nx-'0',nx=getchar(); return sign*c; } const int N = 5e5 + 20; long long cnt[100]; int main(){ int n = read(); for(int i=1;i<=n;i++) cnt[read() + 20]++; long long ans = cnt[20] * (cnt[20] - 1) / 2; for(int i=1;i<=20;i++) if(cnt[i + 20] and cnt[20 - i]) ans += cnt[i + 20] * cnt[20 - i]; printf("%lld",ans); }
题意
给你若干字符串，求按照首尾字母相同的方式接龙能接上多少个，且必须按照题目输入的顺序接, 也就是先出现的字符串必须接在前面。
解题思路
使用 DP 实现，记 $dp[i][j]$ 表示以 $i$ 开头，$j$ 结尾的接龙的最长长度。
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 #include<bits/stdc++.h> #define inf 1<<29 #define maxn 1000010 typedef long long ll; using namespace std; int n,mp[210][210],ans; char str[110]; int main(){ cin>>n; for(int i=1;i<=n;++i){ scanf("%s",str); int len=strlen(str); char s=str[0],t=str[len-1]; for(int j='a';j<='z';++j){ if(mp[j][s]){ mp[j][t]=max(mp[j][t],mp[j][s]+len); } } mp[s][t]=max(mp[s][t],len); } for(int i='a';i<='z';++i) ans=max(ans,mp[i][i]); cout<<ans<<endl; return 0; }
题意
给你一个由大写字母构成的二维矩阵，你需要找到一个最大的正方形，使得这个正方形内只包含一种字母。
解题思路
本题实际上有多种通过方法，下面介绍两种参考方法：
（暴力哈希）将原矩阵内每一种字母都替换成一个素数，然后计算这个矩阵的二维前缀积（对大素数取模）。那么在给定二分长度 k 的前提下，我们每次可以枚举一个矩形的左上角 $(i,j)$ ，利用逆元计算出这么个矩形的积，再和这种字母的纯 $k ∗ k$ 正方形对应的哈希值比对。如果担心碰撞，只需改成双哈希就好。总复杂度为常数有点大的 $O(nmlog(n))$ 。
我们如果在原矩阵 F 的基础上预处理出一个新矩阵 $G$, 第 $i$ 行第 $j$ 列的值的意义为：这个值在这一行前面有多少个连续的数和它相同（包括自己）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include<bits/stdc++.h> #define inf 1<<29 #define maxn 1000010 typedef long long ll; using namespace std; int n,mp[210][210],ans; char str[110]; int main(){ cin>>n; for(int i=1;i<=n;++i){ scanf("%s",str); int len=strlen(str); char s=str[0],t=str[len-1]; for(int j='a';j<='z';++j){ if(mp[j][s]){ mp[j][t]=max(mp[j][t],mp[j][s]+len); } } mp[s][t]=max(mp[s][t],len); } for(int i='a';i<='z';++i) ans=max(ans,mp[i][i]); cout<<ans<<endl; return 0; }
题意
有一个排列，已知我们对于这个排列执行单调栈算法过程中，遍历到每一个位置之后单调栈的大小，有些位置缺失可以任意。求一个满足这种情况的字典序最小的排列。
解题思路
首先我们应该做的事，是补全这个单调栈数组 $b$。单调栈数组由于单调栈算法的特点，必然满足这么几个特点：
$b[1] = 1$
若 $b[i] > b[i − 1]$ ，则 $b[i] = b[i − 1] + 1$ ，且 $a[i] > a[i − 1]$ 。
对于 $b[i] <= b[i − 1]$ ，一定有 $a[i] < a[i − 1]$ 。
我们从左到右依次补全每一个为 $−1$ 的格子，那么策略应该是：
若 $i = 1$ ，$b[i] = 1$ 。
否则，如果我们填一个比 $b[i − 1]$ 小的数的话，就意味着之后补全的时候 $a[i − 1] > a[i]$ ，在字典序上不会是个好主意。所以应该填 $b[i − 1] + 1$ 。
补全数组之后，规律如下：
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 34 35 36 37 38 39 40 41 42 #include <bits/stdc++.h> using namespace std; int T, n; int p[200005]; int lst[200005], tail; int pre[200005]; int nxt[200005]; int s[200005]; int main() { scanf("%d", &T); for(int k = 0; k < T; ++k) { scanf("%d", &n); for(int i = 0; i <= n; ++i) nxt[i] = pre[i] = 0; tail = 0; for(int i = 1; i <= n; ++i) scanf("%d", &p[i]); p[1] = 1; for(int i = 2; i <= n; ++i) if(p[i] == -1) { if(p[i + 1] - p[i - 1] == 2) p[i] = p[i - 1] + 1; else p[i] = p[i - 1] + 1; } for(int i = 1; i <= n; ++i) { if(p[i] > p[i - 1]) { nxt[tail] = i; pre[i] = tail; tail = i; } else { int x = lst[p[i]]; nxt[pre[x]] = i; pre[i] = pre[x]; nxt[i] = x; pre[x] = i; } lst[p[i]] = i; } for(int i = 1, j = nxt[0]; i <= n; ++i, j = nxt[j]) s[j] = i; for(int i = 1; i <= n; ++i) printf("%d ", s[i]); printf("\n"); } return 0; }
