比赛链接：传送门
A. Golden Plate（简单思维题+暴力）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + 5;
int main()
{
ll ans = 0;
ll w, h, k;
cin >> w >> h >> k;
while (k--) {
ans += 2*w+2*h-4;
w -= 4;
h -= 4;
}
cout << ans << endl;
return 0;
}
B. Curiosity Has No Limits（暴力dfs）
题目大意：
给你两个长度为n的数组a，b，然后让你构造一个数组t使得ti|ti+1 = ai，ti&ti+1 = bi。
（0 ≤ ai, bi, ti ≤ 3， 2 ≤ n ≤ 105）
思路：
对当前位置的ai，bi，和前置的ti，ti+1的选择是很少的。
所以可以把这个ti+1全都预处理出来放在vector里面，用到的时候直接遍历vector即可。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 5;
struct Node{
int t1, t2;
Node(int _x = 0, int _y = 0) : t1(_x), t2(_y) {}
};
int N;
int a[MAX_N], b[MAX_N];
vector <Node> V[4][4];
vector <int> ans;
void init()
{
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
int a = i|j;
int b = i&j;
V[a][b].push_back(Node(i, j));
}
}
// for (int i = 0; i < 4; i++) {
// for (int j = 0; j < 4; j++) {
// for (int k = 0; k < V[i][j].size(); k++) {
// cout << i << ' ' << j << ' ' << V[i][j][k].t1 << ' ' << V[i][j][k].t2 << endl;
// }
// cout << endl;
// }
// }
}
bool dfs(int dep, int pret)
{
int cura = a[dep];
int curb = b[dep];
if (!V[cura][curb].size()) {
cout << "NO" << endl;
exit(0);
}
for (unsigned int k = 0; k < V[cura][curb].size(); k++) {
Node cur = V[cura][curb][k];
if (dep == N-1) {
if (cur.t1 == pret) {
cout << "YES" << endl;
ans.push_back(cur.t2);
return true;
}
else
continue;
}
if (cur.t1 == pret) {
if (dfs(dep+1, cur.t2)) {
ans.push_back(cur.t2);
return true;
}
}
}
return false;
}
int main()
{
init();
cin >> N;
for (int i = 1; i <= N-1; i++)
scanf("%d", a+i);
for (int i = 1; i <= N-1; i++)
scanf("%d", b+i);
for (unsigned int k = 0; k < V[a[1]][b[1]].size(); k++) {
Node cur = V[a[1]][b[1]][k];
if (dfs(1, cur.t1)) {
ans.push_back(cur.t1);
break;
}
}
if (!ans.size()) {
cout << "NO" << endl;
return 0;
}
for (int i = N-1; i > 0; i--) {
cout << ans[i] << ' ';
}
cout << ans[0] << endl;
return 0;
}
C. Cram Time（贪心+暴力）
题目大意：
第一天的时间为a，第二天的时间为b，然后有无限本书，阅读时间对应从1开始的正整数，且每个正整数只能用一次。
问：使得读的书最多的情况下，怎么安排这两天的读书顺序。
（1 ≤ a，b ≤ 109）
思路：
肯定是优先把时间短的书读掉。所以从时间为1的书开始累加，直到时间和sum将要大于a+b。标记之前所有加过的时间。
然后原来的总时间a+b要减去比sum多出来的部分。为了方便地防止减掉之后小于零，直接取a、b中较大者减掉这个差值。
现在a+b就等于sum了，然后分配之前累加的书。分配出的和到达a之后剩余的自然就是b，然后贪心地从剩余最大的开始分就可以了。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 5;
bool vis[MAX_N];
int main()
{
int a, b;
cin >> a >> b;
int sum = a+b;
int tot = 0;
for (int i = 1; sum >= i; i++) {
sum -= i;
vis[++tot] = true;
}
if (sum) {
if (a > b)
a -= sum;
else
b -= sum;
}
int cnta = 0;
for (int i = tot; i >= 1; i--) {
if (i <= a) {
a -= i;
vis[i] = false;
cnta++;
}
}
cout << cnta << endl;
bool firstprint = true;
for (int i = 1; i <= tot; i++) {
if (!vis[i]) {
if (firstprint)
firstprint = false;
else
printf(" ");
printf("%d", i);
}
}
cout << endl;
cout << tot-cnta << endl;
firstprint = true;
for (int i = 1; i <= tot; i++) {
if (vis[i]) {
if (firstprint)
firstprint = false;
else
printf(" ");
printf("%d", i);
}
}
cout << endl;
return 0;
}
D. Minimum path（bfs）
题目大意：
给定一个N*N的小写字母矩阵，从左上角开始走到右下角，每次可以向下走或者向右走。
路径上的字符可以构成一个长度为2*N-1的字符串。你可以对这个字符串修改k次。
求修改k次后的字符串中，字典序最小的一个。
懵逼：
比赛的时候想到用dp，同时维护字符串和剩余的修改次数。
但是字符串会占O(n)的内存，不过可以用滚动数组优化掉。
然后字符串的比较又会耗时O(n)，Becky_w说用哈希什么的，我硬是没想出来。
补题的时候想到可以直接维护答案，结果敲完发现和wyb一起迷之MLE。。
最后就是数据结构大佬Dilthey天秀，用数组模拟队列，然后跑bfs就AC了。
思路：
从左上角开始往右下角跑bfs，保证每层和左上角的曼哈顿距离都是一样的，每层都用一个队列保存。
每层跑出当前层的最优解，直接存入答案，对于跑出的非最优解直接舍弃掉(ind = -1)。
维护剩余更改次数k：
k不为0的时候才维护，如果当前位置的字符为'a'，那么k不变，否则k--。
维护答案：
当前剩余的k如果不为0的话那么这个位置的答案就为'a'，否则为当前这一层的最小的字符。
滚动数组模拟队列：
flag 标识当前队列使用的维度，!flag 标识下一层队列的维度。
tot[flag]，tot[!flag]表示队列的长度。
时间复杂度：
bfs遍历了原矩阵，所以时间复杂度是O(n2)。
宣传一波大佬博客：Dilthey的博客
#include <bits/stdc++.h> using namespace std; const int MAX_N = 2000 + 5; const int dx[2] = {1, 0}; const int dy[2] = {0, 1}; #define nx cur.x+dx[k] #define ny cur.y+dy[k] struct Node { char c; int x, y, resk; Node(char _c = '{', int _x = 0, int _y = 0, int k = 0) : c(_c), x(_x), y(_y), resk(k) {} bool operator < (const Node& a) const { if (resk == a.resk) return c < a.c; return resk > a.resk; } }; int N, K; char mat[MAX_N][MAX_N]; string ans; int tot[2], ind[MAX_N][MAX_N]; Node f[2][MAX_N << 1]; inline bool check(int x, int y) { if (x < 1 || x > N || y < 1 || y > N) return false; return true; } void bfs() { int flag = 0; // 滚动数组的下标，f的第一维 tot[0] = tot[1] = 0; if (mat[1][1] == 'a') f[flag][tot[flag]++] = Node('a', 1, 1, K); else f[flag][tot[flag]++] = Node(K?'a':mat[1][1], 1, 1, K?K-1:0); ans += K?'a':mat[1][1]; ind[1][1] = 0; while (tot[flag]) { char tar = 'z'+1; for (int i = 0; i < tot[flag]; i++) { Node cur = f[flag][i]; if (ind[cur.x][cur.y] < 0) continue; for (int k = 0; k < 2; k++) if (check(nx, ny)) { int nk = cur.resk; char nc = mat[nx][ny]; if (nk > 0 && nc != 'a') { nk--; nc = 'a'; } Node nxt(nc, nx, ny, nk); tar = min(tar, nc); if (ind[nx][ny] < 0) { f[!flag][tot[!flag]] = nxt; ind[nx][ny] = tot[!flag];//保存坐标用于下次删去 tot[!flag]++; } else { f[!flag][ind[nx][ny]] = min(f[!flag][ind[nx][ny]], nxt); } } } if (tar == 'z'+1) break; for (int i = 0; i < tot[!flag]; i++) { Node cur = f[!flag][i]; if (cur.c > tar) ind[cur.x][cur.y] = -1;//删去非最优的 } ans += tar; tot[flag] = 0; flag = !flag; } } int main() { cin >> N >> K; for (int i = 1; i <= N; i++) scanf("%s", mat[i]+1); memset(ind, -1, sizeof ind); ans = ""; bfs(); cout << ans << endl; return 0; } /* 3 0 irk thm aba */