第一场（2020/03/20）：
题目一：
有一叠扑克牌，每张牌介于1和10之间。有四种出牌方法：
- 单出一张
- 出两张相同的牌(对子)
- 出五张顺子(如12345)
- 出三连对子(如112233)
给10个数，表示1-10每种牌有几张，问最少要多少次能出完。每种牌最多有四张。
解题思路：
DFS 回溯法，先判断组成三连对和组成顺子需要的次数，递归深度 k 就是次数。对于对子和单张的可以直接通过枚举数需要打多少次。可以在组成三连对和顺子的时候增加剪枝操作加快运算：如果构不成三连对或者顺子，则不用进行回溯。
时间复杂度大概为 O(4^10)。
C++ 实现：
#include<bits/stdc++.h>
using namespace std;
int a[15],ans=123456789;
void dfs(int k) // k表示次数
{
//检查是否有三连对子
for(int i=1;i<=8;i++) {
bool flag = true;
for(int j=i;j<i+3;j++)
if(a[j] < 2) { // 不能构成三连对
flag = false; // 剪枝
break;
}
if(flag == true) { // 可以构成三连对
for(int j=i;j<i+3;j++)
a[j] -= 2;
dfs(k+1);
for(int j=i;j<i+3;j++) // 回溯一步
a[j] += 2;
}
}
//检查是否有顺子
for(int i=1;i<=6;i++) {
bool flag = true;
for(int j=i;j<i+5;j++)
if(a[j] < 1) { // 不能构成顺子
flag = false; // 剪枝
break;
}
if(flag == true) { // 可以构成顺子
for(int j=i;j<i+5;j++)
a[j] -= 1;
dfs(k+1);
for(int j=i;j<i+5;j++) // 回溯一步
a[j] += 1;
}
}
//没有三连对和顺子，直接统计答案
int cnt = 0;
for(int i=1;i<=10;i++) {
if(a[i]==4) cnt += 2; // 直接构成两个一对
else if(a[i]==3) cnt+=2; // 一对，一单张
else if(a[i]==2) cnt+=1; // 一对
else if(a[i]==1) cnt+=1; // 一单张
}
ans = min(ans, cnt+k); // 更新答案
}
int main()
{
for(int i=1;i<=10;i++) cin >> a[i];
dfs(0);
cout << ans;
return 0;
}
题目二：
小明在学旋律，每段旋律都可以用字符串来表示，并且旋律的每个字符的ASCALL码递增的。比如以下4段旋律 :
aaa
bcd
bcdef
zzz
现在就是要求，小明能够吧这些旋律拼接起来组成最长的旋律。
比如上述例子输出 11 最长的旋律为 aaabcdefzzz
解题思路：
实际上，这道题和之前做过的 Leetcode 【DP】139. Word Break 很类似。
排序 + 动态规划（DP）：
- 首先按照字符串最后一个字母，由小到大排序，如果最后一个相同，按第一个由小到大字母排序。
- 然后定义 dp 数组，对于每个字符串 str，dp[i] 表示从字母 'a' 到字母 str[str.size()-1] 为结尾的最长上升字符串的长度。
- 枚举输入的字符串 s，s 的最后一个字母 end = s[s.size()-1]。从字符串首字母 s[0] 到字母 'a' 倒着循环（假设循环遍历为 i），使用状态转移方程
dp[end] = max(dp[end], dp[i] + s.size())来更新 dp[end] 的最大值。 - 最后，dp['a'] ~ dp['z'] 中的最大值就是答案。
比如上述例子：
（0）按照排序规则排完后为 aaa、bcd、bcdef、zzz，建立一个 dp[515]，初始化全为 0。然后计算：
（1）dp['a'] = max(dp['a'], dp['a'] (首字母) + 3) = 3；
（2）dp['d'] = max(dp['d'], dp['b'] (首字母) + 3) = 3；dp['d'] = max(dp['d'], dp['a'] + 3) = 3 + 3 = 6；
（3）dp['f'] = max(dp['f'], dp['b'] (首字母) + 5) = 5；dp['f'] = max(dp['f'], dp['a'] + 5) = 3 + 5 = 8；
（4）dp['z'] = max(dp['z'], dp['z'] (首字母) + 3) = 3；dp['z'] = max(dp['z'], dp['y'] + 3) = 3；dp['z'] = max(dp['z'], dp['x'] + 3) = 3；...... ；dp['z'] = max(dp['z'], dp['f'] + 3) = 8 + 3 = 11；...... ；dp['z'] = max(dp['z'], dp['d'] + 3) = max(11, 6 + 3) = 11；...... ；dp['z'] = max(dp['z'], dp['a'] + 3) = max(11, 3 + 3) = 11.
（5）最后，找出 dp['a'] ~ dp['z'] 中的最大值就是答案。
简单地说，比如一个字符串是 defg，我们就看一下字母 d 之前的能不能连接到以 g 为结尾的字符串后面，因此要循环 d、c、b、a，来更新 dp[g] = max(dp[g], dp[d(或者c\b\a)]+4)。
现在来解释两个问题：
-
为什么排序规则是上面那样的？
首先，按照末尾字符串先从小到大排序这个毋庸置疑，因为比如 abc、fgh，要计算 dp[h]，需要用到 dp[f] 到 dp[a] 这些之前的结果；
然后，如果末尾字符串相同，为什么还要按照首字母排序呢？因为比如 ab、bb，要计算字符串 bb 的 dp[b]，需要用到 dp[b] 和 dp[a] 的结果，如果不按照首字母排序，那么可能 bb 会出现在 ab 前面。求解 bb 的时候 dp[a] 是 0，因此就会产生错误答案 2，而不是 4。 -
为什么在更新 dp[i] 时要从 s[0] 到 'a' 倒着循环？
这是因为比如 s = "bb"，如果倒着循环可以得到正确答案 2，但是正着循环，从 'a' 到 s[0] = 'b'，更新 dp['b'] 的时候，按照上面的状态转移方程，"bb" 会重复计算一次，得到 dp['b'] = 4 的错误答案。
空间复杂度为 O(26)，时间复杂度为 O(26*n)。
C++ 实现：
#include<bits/stdc++.h>
using namespace std;
struct node {
string s;
int len;
};
node xuan[1000005];
bool cmp(node a, node b) { // 排序规则
if(a.s[a.len-1] < b.s[b.len-1]) return true;
else if(a.s[a.len-1] > b.s[b.len-1]) return false;
else {
return a.s[0] < b.s[0];
}
}
int f[500]; // f[i]表示从字符'a'到字符串最后一个字符的最大长度
int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++) {
cin >> xuan[i].s;
xuan[i].len = xuan[i].s.size();
}
sort(xuan+1,xuan+n+1,cmp);
for(int i=1;i<=n;i++) {
int start = xuan[i].s[0];//第一位字符的ASCLL值
int end = xuan[i].s[xuan[i].len-1];//最后一位字符的ASCLL值
for(char c=start; c>='a';c--) //必须从start开始倒着循环到'a'
f[end] = max(f[end], f[c]+xuan[i].len);
}
int ans = 0;
for(char c='a';c<='z';c++)
if(f[c]>ans) ans = f[c];
cout << ans;
return 0;
}
第二场（2020/03/23）：
题目一：
N个人，任意选k个，再从k个里任选1个当队长，求总组合数。
解题思路：
总数 S = 0*C(N,0) + ... + i*C(N,i) + N*C(N,N)
倒着加：S + S = N*(C(N,0) + ... + C(N,N) = N*2^(N)
所以 S = N*2^(N-1)
接下来只需要考虑计算 2^(N-1) 的快速计算方法就好了（快速幂算法）
时间复杂度O(logN)，可以AC
C++ 实现：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
ll ksm(ll a, ll b) // 快速幂算法
{
ll ans=1, base=a;
while(b) {
if(b&1) ans=ans*base%mod;
base=base*base%mod;
b>>=1;
}
return ans%mod;
}
int main() {
ll n;
cin>>n;
ll ans=n*ksm(2,n-1)%mod;
cout<<ans<<endl;
return 0;
}
题目二：
一个地图 n*m，包含1个起点，1个终点，其他点包括可达点和不可达点。每一次可以：上下左右移动，或使用1点能量从（i,j) 移动到（n-1-i, m-1-j)，最多可以使用5点能量。求从起点到达终点的最短路径长度。
解题思路：
类似于广度优先搜索的（使用队列），只不过还要考虑到达某个坐标有能量时，也可以进行跳跃，因此也可以入队列。
因为队列入队时，肯定越到后面步数需要越多，所以其实第一次访问到终点坐标就可以跳出了，即就是最短路径。
空间复杂度 O(m*n), 时间复杂度 O(m*n)。
C++ 实现：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
struct node { // 某个节点信息
int x,y;
int stp; // 到达这个节点时所走的步数
int cnt; // 到达这个节点时还有多少能量
};
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int sx,sy; // 起点坐标
int n,m;
int ex,ey; // 终点坐标
bool check(int x,int y){
if(x>=1&&x<=n&&y>=1&&y<=m){
return true;
}
else{
return false;
}
}
char Map[505][505]; // 地图
int vis[505][505]; // 标记某个点是否走过
int BFS() {
queue<node>q;
node st;
st.x=sx;
st.y=sy;
st.stp=0;
st.cnt=5;
vis[sx][sy]=1;
q.push(st); // 起点入队列
while(!q.empty()){
node now =q.front();
if(now.x==ex&&now.y==ey)return now.stp; // 最短路径即是第一次到达的步数
q.pop();
node nxt;
for(int i=0;i<4;i++) { // 上下左右搜索
nxt.x=now.x+dir[i][0];
nxt.y=now.y+dir[i][1];
nxt.stp=now.stp+1;
nxt.cnt=now.cnt;
if(check(nxt.x,nxt.y)&&vis[nxt.x][nxt.y]==0&&(Map[nxt.x][nxt.y]=='.'||Map[nxt.x][nxt.y]=='E')){ // '.' 为可达
vis[nxt.x][nxt.y]=1;
q.push(nxt);
}
}
if(now.cnt>=1){ // 如果到达 now 这个节点还有能量
nxt.x=n+1-now.x;
nxt.y=m+1-now.y;
nxt.stp=now.stp+1;
nxt.cnt=now.cnt-1;
if(check(nxt.x,nxt.y)&&vis[nxt.x][nxt.y]==0&&(Map[nxt.x][nxt.y]=='.'||Map[nxt.x][nxt.y]=='E')){ // '.' 为可达
vis[nxt.x][nxt.y]=1;
q.push(nxt);
}
}
}
return -1; // 队列为空，不可达
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%s",Map[i]+1);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(Map[i][j]=='S'){ // 起点
sx=i;sy=j;
}
if(Map[i][j]=='E'){ // 终点
ex=i;ey=j;
}
}
}
cout<<BFS()<<endl;
return 0;
}
第三场（2020/03/25）：
题目一：
给定一个 3 行 n 列的矩阵 a (n<=10^5)，从每一列选择一个数 bi 组成一个数组，然后要求使这个数组前一项减后一项的绝对值之和最小。即求
∑ |b(i) - b(i+1)| (i=1,2,...,n-1)
输入示例：
5
5 9 5 4 4
4 7 4 10 3
2 10 9 2 3
这里可以选择 [5 7 5 4 4]，所以输出等于 |7-5|+|5-7|+|4-5|+|4-4|=5。所以输出就是5。
解题思路：
动态规划。这道题和 Leetcode 【DP】64. Minimum Path Sum 很类似，使用 f[i][j] 存储到达点 (i, j) 的最小绝对值之和，最后 min({f[1][n]，f[2][n], f[3][n]}) 就是最终的答案。状态转移方程如下：
f[i][j] = min(f[k][j-1] + abs(a[k][j-1] - a[i][j])), k = 1, 2, 3
边界情况：f[1][1] = f[2][1] = f[3][1] = 0 (初始绝对值累加和为0)
时间复杂度为 O(9*n)，空间复杂度为 O(3*n)。
C++ 实现：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
ll a[4][100005], f[4][100005];
int main()
{
int n;
cin>>n;
for(int i=1; i<=3; i++) {
for(int j=1; j<=n; j++) {
cin>>a[i][j];
}
}
memset(f, 0x7f, sizeof(f)); // 相当于 0x7f7f7f7f (int下)
f[1][1] = f[2][1] = f[3][1] = 0;
for(int j=2; j<=n; j++) { // 先要遍历列
for(int i=1; i<=3; i++) { // 再遍历行
for(int k=1; k<=3; k++) {
f[i][j] = min(f[i][j], f[k][j-1] + abs(a[i][j] - a[k][j-1]));
}
}
}
cout<<min(f[1][n], min(f[2][n], f[3][n]));
}
优化：
因为 f[i][j] = min(f[k][j-1] + abs(a[k][j-1] - a[i][j])), k = 1, 2, 3，则发现第 j 列只依赖于 j-1 列，因此没必要开辟一个 f[i][j] 大小的二维数组，只需要开辟两个一维数组：f[4] 和 pre[4]，其中 f[i] 记录当前列每一行绝对值累加和，pre[i] 记录上一列每一行绝对值累加和。 因此状态转移方程为：
f[i] = min(pre[k] + abs(a[k][j-1] - a[i][j])), k = 1, 2, 3
边界情况：pre[1] = pre[2][1] = pre[3][1] = 0 (初始绝对值累加和为0)
需要注意的是，每次求 f 数组的每一个 f[i] 时，都要先初始化为最大值，并且每次计算完 f 数组后，都要将 f 数组拷贝给 pre 数组。
时间复杂度为 O(12*n)，空间复杂度为 O(1) (只有两个大小为 4 的数组)。
空间优化的 C++ 代码实现：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
// f数组记录当前列每一行绝对值累加和，pre数组记录上一列每一行绝对值累加和
ll a[4][100005], f[4], pre[4];
int main()
{
int n;
cin>>n;
for(int i=1; i<=3; i++) {
for(int j=1; j<=n; j++) {
cin>>a[i][j];
}
}
pre[1] = pre[2] = pre[3] = 0;
for(int j=2; j<=n; j++) {
memset(f, 0x7f, sizeof(f)); // 因为是一维，所以每次都必须先初始化
for(int i=1; i<=3; i++) {
for(int k=1; k<=3; k++) {
f[i] = min(f[i], pre[k] + abs(a[i][j] - a[k][j-1]));
}
}
for(int t=1; t<=3; t++) { // f数组更新完后，将其拷贝给pre数组
pre[t]=f[t];
}
}
cout<<min(f[1], min(f[2], f[3]));
}
题目二：
给出一个 n*m 二维矩阵 (n<=500, m<=500)，矩阵的每一行和每一列都是一个独立的等差数列，其中一些数据缺失了，现在需要推理隐藏但是可以被唯一确定的数字，然后对输入的查询进行回答。
输入描述：
第一行，n,m,q 分别表示矩阵的行数，列数和查询的条数。
接下来的 n 行，每行 m 个数表示这个矩阵，0表示缺失数据。
接下来 q 行，每行两个数字 x, y 表示对矩阵中第 i 行第 j 列的数字进行查询。
输出描述：
如果可以确定该位置的数字，则输出该数字，如果不能确定则输出 字符串 "Unknown"。
输入示例：
2 3 6
1 0 3
0 0 0
1 1
1 2
1 3
2 1
2 2
2 3
输出示例：
1
2
3
Unknown
Unknown
Unknown
样例解释：
矩阵是一个 2*3 的矩阵：[[1,0,3], [0,0,0]]，总共询问 6 次。由第一行，可以确定公差为 1，因此前三次询问中，第一行的三个数都可以确定。但是，第二行是 3 个 0，不能推断出每一个数，因此后三次询问中，都输出 "Unknown"。
解题思路：
先将整个矩阵 a 推断出来，把能够确定的数字填入矩阵中，并用一个标记数组 vis 标记某个位置的数是否是确定的。然后再进行询问，对于确定的数直接输出结果，否则输出 "Unknown"。
关键点在于，如何推断出这个矩阵？如果我们知道每一行有两个确定的数字，我们就可以计算出该行的公差 d；同理，如果我们知道每一列有两个确定的数字，我们也可以计算出该列的公差 d。比如某一行：0 3 0 0 9 11 0 0，我们找到 3 和 9，就可以计算出公差 d = 2，并且可以推断出这行的其他数字，因此改行可以得到 1 3 5 7 9 11 13 15。
因此，算法步骤如下（假设是 work() 处理函数）：
- 对于每一行，去计算公差 d，如果可以计算出来，推断该行所有的数字，填充到矩阵 a 中，并用标记数组 vis 标记该行所有数字都可以推断。
- 对于每一列，去计算公差 d，如果可以计算出来，推断该列所有的数字，填充到矩阵 a 中，并用标记数组 vis 标记该列所有数字都可以推断。
举例：
a 矩阵 -> 推断行 -> 推断列
0 2 0 4 1 2 3 4 1 2 3 4
1 0 5 0 1 3 5 7 1 3 5 7
0 4 0 0 0 4 0 0 1 4 7 10
但是，这种做法有一个问题，比如：
a 矩阵 -> 推断行 -> 推断列
0 2 0 4 1 2 3 4 1 2 3 4
0 3 0 0 0 3 0 0 0 3 0 5
0 0 0 6 0 0 0 6 0 4 0 6
会发现只推断一次行于列，推断不完全！实际上，需要推断多次，才能将所有的数字全部推理出来。再比如下面的这个例子：
7*5的矩阵，需要行列各推理三次才能全部推理结束
黄色表示确定的数字，空白表示不确定的数字。因此，需要调用 3 次 work() 函数才能全部推理出来。
因此，可以在代码中写一个 while(work()) ; 不断调用 work() 处理函数，在 work() 函数中加一个标记变量 flag = false，假设新一轮扫描中没有产生新的未知量，如果发现标记数组 vis 不再变化为止，说明推断结束，返回 flag (false)，否则，将 flag 改为 true，继续进行下一轮的推断。
其实，还有一个更为隐蔽的 case，就是比如某一行为 -1 0 1，这个 0 是确定的数字，并不是未知量，因此需要在找两个非 0 数字过程中将条件 if(a[i][j] != 0) 改成 if(a[i][j] != 0 || vis[i][j] == true)，就可以考虑到这种情况。如：
a 矩阵 -> 推断行 -> 推断列
-1 0 0 -1 0 0 -1 -2 -3 (-2根据0推出)
0 -1 1 -3 -1 1 -3 -1 1
-5 0 5 -5 0 5 (这个0确定) -5 0 5 (这个0确定)
在推断第 3 行的时候，中间的 0 是确定的数字，不是未知量，因此 vis[3][2] = true，当推断第 2 列时，根据 if(a[3][2] != 0 || vis[3][2] == true) 这个条件，条件也成立，说明可以利用 a[3][2] 上的 0，来推断出 a[1][2] = -2。
时间复杂度为 O(k*n*m)（k 是 work() 函数调用的次数），空间复杂度也为 O(n*m)。
C++ 实现：
#include<iostream>
using namespace std;
int n,m,q,x,y;
int a[505][505], vis[505][505];
void work() // 填充矩阵a，并标记某个位置的数是否是确定的
{
int flag = false; // 新一轮扫描中，没有产生新的未知量
for(int i=1; i<=n; i++) { // 枚举每一行，检验该行上是否有两个确定的数字
int p = 0; // 对于第i行，找到第一个确定的数字出现的位置p和公差d
int d = 0x7fffffff;
for(int j=1; j<=m; j++) {
if(a[i][j]!=0 || vis[i][j]==true) { // 后一个条件是为了处理 -1 0 1 的情况，这个0是确定的数字0
if(p==0) {
p = j;
} else { // 第二次出现确定的数字，可以计算出公差d
d = (a[i][j]-a[i][p]) / (j-p);
break;
}
}
}
if(d!=0x7fffffff) { // d计算出来了，填充第i行中的每个数
for(int j=1; j<=m; j++) {
a[i][j] = a[i][p] + d * (j-p);
if(vis[i][j] == false) flag = true; // 新一轮扫描中，产生了新的未知量
vis[i][j] = true; // 标记第i行的每个数字都是确定的
}
}
}
for(int j=1; j<=m; j++) { // 枚举每一列，检验该列上是否有两个确定的数字
int p = 0;
int d = 0x7fffffff;
for(int i=1; i<=n; i++) {
if(a[i][j]!=0 || vis[i][j] == true) {
if(p==0) {
p = i;
} else {
d = (a[i][j]-a[p][j]) / (i-p);
break;
}
}
}
if(d!=0x7fffffff) {
for(int i=1; i<=n; i++) {
a[i][j] = a[p][j] + d * (i-p);
if(vis[i][j] == false) flag = true;
vis[i][j] = true;
}
}
}
return flag; // 如果返回true，说明还需要继续扫描一轮
}
int main()
{
// 输入
cin>>n>>m>>q;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>a[i][j];
}
}
// 处理
while(work()); // 扫描多次行域列，直到vis数组不变化为止，才说明推断结束
// 询问q次
for(int i=1; i<=q; i++) {
cin>>x>>y;
if(vis[x][y]) {
cout<<a[x][y]<<endl;
} else {
cout<<"Unknown"<<endl;
}
}
}
网友评论