这场题意和做法应该都比较明确，比较偏考验代码功底，算法的细节其实不多，所以讲解比较少，基本在代码中，代码中有比较详细的注释。如果还不能明白，可以私信问我或者回复。
Problem A：
给7张麻将牌（长度为2的字符串），问除花牌部分能不能组成"七星不靠"（这个可以自行百度）。
做法：应该挺显然的，处理下万饼条分别属于147,258,369的哪一类，再检查下类间是否互斥即可，具体看代码吧。
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main() {
int T; scanf("%d", &T); while(T--) {
vector<int> v[3];//存放万饼条的数字
//输入
for(int i = 0; i < 7; i++) {
char p[5]; scanf("%s", p);
if(p[1] == 'T')v[0].push_back(p[0] - '0');
if(p[1] == 'B')v[1].push_back(p[0] - '0');
if(p[1] == 'W')v[2].push_back(p[0] - '0');
}
int fl = 1;
//特判缺门的情况
for(int i = 0; i < 3; i++)if(v[i].empty()) {
puts("NO");
fl = 0;
break;
}
if(!fl)continue;
//排序
for(int i = 0; i < 3; i++)sort(v[i].begin(), v[i].end());
//判断万饼条内部是否满足隔3或者隔6的条件
for(int i = 0; i < 3; i++)for(int j = 1; i < v[i].size(); j++) {
if(v[i][j] - v[i][j - 1] == 3 || v[i][j] - v[i][j - 1] == 6);
else fl = 0;
}
//判断万饼条间元素对3取模是否互相独立
int cc[3] = {0};
for(int i = 0; i < 3; i++)cc[v[i][0] % 3]++;
for(int i = 0; i < 3; i++)if(!cc[i])fl = 0;
puts(fl ? "YES" : "NO");
}
return 0;
} Problem B：
给个n*n矩阵，每次消除一行一列，要求消除的行列和尽可能大，如果有多个方案可选，选择行号尽量小的，同行就选列号尽量小的。
消除后矩阵会变为(n-1)*(n-1)矩阵，继续消除操作。
问n次操作选择的行列方案分别是多少？
n范围500。
做法：预处理每行每列的和，每次消除枚举行列，计算方案的和，选出最佳的。
消除后将矩阵暴力的合并起来，并更新行列和的数组。
总体复杂度控制在立方级别就可以。
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int ph[N], pl[N]; //ph表示每列的和，pl表示每行的和
int a[N][N]; //存放矩阵元素
int main() {
int n; scanf("%d", &n);
for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){
//输入矩阵元素
scanf("%d", &a[i][j]);
//顺带处理每行每列的和
pl[i] += a[i][j], ph[j] += a[i][j];
}
for(int _ = 0; _ < n; _++) {
//计算每个坐标丢十字斩的的得分，求出题目要求的坐标
int x = 1, y = 1;
for(int i = 1; i <= n - _; i++)for(int j = 1; j <= n - _; j++) {
int pre = pl[x] + ph[y] - a[x][y];
int now = pl[i] + ph[j] - a[i][j];
if(now > pre)x = i, y = j;
}
printf("%d %d", x, y);
//处理当前每行每列的和
for(int i = 1; i <= n - _; i++)ph[i] -= a[x][i];
for(int i = 1; i <= n - _; i++)pl[i] -= a[i][y];
//将矩阵移位，处理的两个数组也移位
for(int i = 1; i < n - _; i++)for(int j = 1; j < y; j++)a[i][j] = a[i + 1][j];
for(int i = 1; i < x; i++)for(int j = y; j < n - _; j++)a[i][j] = a[i][j + 1];
for(int i = x; i < n - _; i++)for(int j = y; j < n - _; j++)a[i][j] = a[i + 1][j + 1];
for(int i = x; i < n - _; i++)pl[i] = pl[i + 1];
for(int i = y; i < n - _; i++)ph[i] = ph[i + 1];
}
} Problem C：
有若干个任务，每个任务可能有子任务，给出每个任务的开始与结束时间，保证某个任务的子任务一定在那个任务期间完成，且每个任务期间不会有其他非子任务的任务插入。
问哪个任务的纯用时（任务时间减去所有子任务时间）最大。
做法：可以看出任务在这样的限制下，可以用一个栈来处理，并计算总时长，那么只需要再处理所有任务的子任务时长，就可以得出答案了。
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main() {
int T; scanf("%d", &T);
while(T--) {
map<int, int> M; //存放子任务的时长和
stack<pair<int, int> > S; //存放当前父任务序列
int n; scanf("%d", &n);
int id = -1, maxtime = 0;
for(int i = 0; i < n; i++) {
int t, e, s; scanf("%d%d%d", &t, &e, &s);
if(s == 0) S.push(make_pair(t, e));//如果任务是开始，丢入栈中
else {
//任务结束，栈顶必定是这个任务的开始状态
//计算任务时长
int nowtime = t - S.top().first;
//判断当前任务的自身用时是否大于当前最大值
if(nowtime - M[e] > maxtime || nowtime - M[e] == maxtime && id > e)maxtime = nowtime - M[e], id = e;
S.pop();
//更新父任务的子任务时长和
if(!S.empty())M[S.top().second] += nowtime;
}
}
//输出答案
printf("%d", id);
}
return 0;
} Problem D：
给定一个地图，规模最大50*50，有10个以内的宝箱，在地图0-9的位置上，主人公位置在*号处。
主人公每一步的行动逻辑如下：
找出离他曼哈顿距离最近的宝箱。
枚举方向，优先级上下左右，如果枚举到的方向可以让离那个宝箱的最短路缩短，那么就走那个方向，其他方向不再枚举。
如果这样的行动逻辑可以拿走所有的宝箱，输出步长，否则输出-1。
做法：直接看代码吧，注释里写的很详细了。
-1的情况有两种，一种是死循环了，这个可以通过加tag判断。
一种是宝箱不可达，这个在处理最短路的过程中是可以发现的。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 55;
const int pos[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1}; //预处理上下左右
char Map[N][N]; //存放地图
int Box[N][2]; //存放宝箱坐标
int dis[N][N][N]; //存放每个宝箱到地图其他点的最短路
int pick[N]; //标记宝箱是否已经被拿过
int fl[N][N]; //标记地图中某个点是否被走过
int sx, sy; //人物当前的坐标
void init() {
memset(Map, 0, sizeof Map);
memset(pick, 0, sizeof pick);
memset(fl, 0, sizeof fl);
}
int main() {
int T; scanf("%d", &T); while(T--) {
//初始化全局数组
init();
//读入地图
int n, m; scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)scanf("%s", Map[i] + 1);
//搜索地图，查看宝箱坐标和起始点坐标
int cnt = 0;
for(int i = 1; i <= n; i++)for(int j = 1; i <= m; i++) {
if(Map[i][j] == '*')sx = i, sy = j, Map[i][j] = '.';
else if(isdigit(Map[i][j]))Box[Map[i][j] - '0'][0] = i, Box[Map[i][j] - '0'][1] = j, cnt++, Map[i][j] = '.';
}
//bfs处理出每个宝箱的点到地图中所有格子的最短路
for(int i = 0; i < cnt; i++) {
memset(dis[i], -1, sizeof dis[i]);
int x = Box[i][0], y = Box[i][1];
dis[i][x][y] = 0;
queue<pair<int, int> > Q; Q.push(make_pair(x, y));
while(!Q.empty()) {
int nowx = Q.front().first, nowy = Q.front().second;
for(int p = 0; p < 4; p++) {
int nextx = nowx + pos[p][0];
int nexty = nowy + pos[p][1];
if(Map[nextx][nexty] == '.' && dis[i][nextx][nexty] == -1) {
dis[i][nextx][nexty] = dis[i][nowx][nowy] + 1;
Q.push(make_pair(nextx, nexty));
}
}
Q.pop();
}
}
int ccnt = 0, len = 0; //分别表示当前拿走的宝箱数和步长
//开始行动
while(ccnt < cnt) {
int x = -1, mindis = 1e9;
//计算目标宝箱
for(int i = 0; i < cnt; i++) {
if(pick[i])continue;
int mdis = abs(Box[i][0] - sx) + abs(Box[i][1] - sy);
if(mdis < mindis)x = i, mindis = mdis;
}
//判断目标宝箱是否可达，或者当前这个格子曾经走过
if(dis[x][sx][sy] == -1 || fl[sx][sy]) {
puts("-1");
break;
}
fl[sx][sy] = 1;//标记当前格子已被走过
//枚举上下左右方向，找出下一步坐标
for(int p = 0; p < 4; p++) {
int nx = sx + pos[p][0];
int ny = sy + pos[p][1];
if(Map[nx][ny] != '.')continue;
if(dis[x][nx][ny] < dis[x][sx][sy]) {
len++, sx = nx, sy = ny;
break;
}
}
//判断是否已经到达宝箱
if(sx == Box[x][0] && sy == Box[x][1]) {
ccnt++, pick[x] = 1;
//将标记清空
memset(fl, 0, sizeof fl);
}
}
//输出答案
if(ccnt == cnt)printf("%d\n", len);
}
return 0;
} 
全部评论
(3) 回帖