ABC round 427
- T3
注意到 \(n\) 非常小，那么枚举染色方式然后判断二分图即可。
#include <bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define rep_(i, a, b) for(int i = a; i >= b; --i)
using namespace std;
constexpr int N = 12;
vector<int> e[N];
int ans, sum, n, m, c[N], u[N * N], v[N * N];
void dfs(int s) {if(s == n + 1) {sum = 0;rep(i, 1, m) {if(c[u[i]] == c[v[i]]) {++sum;}}ans = min(ans, sum);return;}c[s] = 1;dfs(s + 1);c[s] = 0;dfs(s + 1);
}
signed main() {ans = 1145;cin >> n >> m;rep(i, 1, m) {cin >> u[i] >> v[i];}dfs(1);cout << ans;return 0;
}
- T4
用一些博弈论的简单知识，枚举 \(k\) 轮，每一轮用出度的状态更新自己的状态。
注意数组开二倍空间！
#include <bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define rep_(i, a, b) for(int i = a; i >= b; --i)
using namespace std;
constexpr int N = 2e5 + 5, K = 12;
int u, v, t, n, m, k;
bool state[N][K * 2]; // Attention!
char a[N];
vector<int> e[N];
void solve() {cin >> n >> m >> k;rep(i, 1, n) {rep(j, 0, k * 2 - 1) {state[i][j] = 0;}e[i].clear();}rep(i, 1, n) {cin >> a[i];state[i][k * 2] = a[i] == 'A';}rep(i, 1, m) {cin >> u >> v;e[u].push_back(v);}rep_(i, k * 2 - 1, 0) {rep(j, 1, n) {for(const register int to : e[j]) {state[j][i] |= !state[to][i + 1];}}}cout << (state[1][0] == 1 ? "Alice" : "Bob") << '\n';
}
signed main() {cin >> t;while(t--) {solve();}return 0;
}- T5
这题很恶心。
我不知道为什么官方题解写了个最短路的 tag，实际上就是一个 bfs。
首先我们要找一个表示法，能表示目前的状态，这样才能进行转移。
考虑要记录什么。首先肯定是我们从最初转移到现在，移动的方式。记录一个 \(dx\) 和 \(dy\)。
初始状态 state1
..# .#.
.#. - > #.. dx = 0， dy = -1
... ...
那就结束了吗？其实没有。
就比如上面这个例子里的初始状态。只是这么记录的话，那如果我让垃圾向上走一次再向下走一次，\(dx\) 就清零了，也就是和初始状态完全一样。
问题是出了边界的垃圾就不会再回来了。状态应该如下。
初始状态 state2 state3
..# 向上移动一次 .#. 向下移动一次 ...
.#. --------------- > ... --------------- > .#. //这才是最终状态
... ... ...
所以，我们要记录能覆盖全部垃圾的最小矩形。这样才知道什么垃圾已经被清除了。注意，这个矩形是指在初始状态中的边界。可以想象成这个最小的能覆盖所有垃圾的矩形在移动，然后每次出了边界就要缩小。但是缩小的操作，是在原数组完成的。
那么表示法其实就出来了，记录最小覆盖矩形的左上角坐标，右下角坐标，以及移动的方式。这六个数我用六元组表示，分别对应 $ bx, by, ex, ey, dx, dy$。
不理解的话看这个例子罢（
//状态六元组简称为
state1
#.#
.#. //s = {1, 1, 3, 3, 0, 0} (1,1)是最小覆盖矩形左上角，(3, 3)是右下角, (0, 0)目前移动方式
#.#
//向下平移一个
state2
...
#.# //s = {2, 1, 3, 3, 1, 0} (2,1)是最小覆盖矩形左上角，(3, 3)是右下角, (1, 0)目前移动方式
.#.
//向上平移一个
state3
#.#
.#. //s = {1, 1, 2, 3, 0, 0} (1,1)是最小覆盖矩形左上角，(2, 3)是右下角, (0, 0)目前移动方式
...
这样就做到了 state1 和 state3 不同！是不是懂了？
这个最小覆盖矩形每次都要重新算一遍。因为删掉一个垃圾可能不止影响 x， 也会影响 y。
还有就是一些常规的 bfs 事项了，像什么判重之类的。
至于代码的那个 \(dis\) 是不是不用讲干嘛用的（?
这题还有老多细节在代码里，我都注释了。
#include <bits/stdc++.h>
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
typedef long long ll;
constexpr int N = 15;
int ans, check, n, m, nx, ny, mx[5] = {1, 0, -1, 0}, my[5] = {0, 1, 0, -1};
char a[N][N];
struct state {int bx, ex, by, ey, dx, dy, dis;
}start, now, nxt;
map<tuple<int, int, int, int, int, int>, bool> vis;
void bfs() {queue<state> q;q.push(start);while(!q.empty()) {now = q.front();q.pop();if(vis[make_tuple(now.bx, now.ex, now.by, now.ey, now.dx, now.dy)]) continue;vis[make_tuple(now.bx, now.ex, now.by, now.ey, now.dx, now.dy)] = true;if(now.bx > now.ex || now.by > now.ey) {cout << now.dis << '\n';exit(0);} rep(i, 0, 3) {nxt = now;bool flag = false;nxt.dx += mx[i];nxt.dy += my[i];rep(j, nxt.bx, nxt.ex) {//这里因为now.bx = nxt.bx, now.by = nxt.by， 所以写啥都行，而下文就不行了。rep(k, nxt.by, nxt.ey) {nx = j + nxt.dx, ny = k + nxt.dy;if(a[j][k] == '#' && a[nx][ny] == 'T' && nx >= 1 && nx <= n && ny >= 1 && ny <= m) {flag = true; //会碰到高桥就不放队列break;}}if(flag) break;}if(!flag) { nxt.ex = nxt.ey = 0;nxt.bx = n + 1, nxt.by = m + 1;rep(i, now.bx, now.ex) {//这里不能写nxt噢rep(j, now.by, now.ey) {nx = i + nxt.dx, ny = j + nxt.dy;if(a[i][j] == '#' && nx >= 1 && nx <= n && ny >= 1 && ny <= m) {nxt.bx = min(nxt.bx, i); //这里i和j不要写成nx和ny！因为最小覆盖矩形始终是在原图上。nxt.ex = max(nxt.ex, i);nxt.by = min(nxt.by, j);nxt.ey = max(nxt.ey, j);}}} nxt.dis = now.dis + 1;q.push(nxt);}}}
}
int main() {//freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);cin >> n >> m;start.ex = start.ey = start.dis = 0;start.bx = n + 1;start.by = m + 1;//初始化（rep(i, 1, n) {rep(j, 1, m) {cin >> a[i][j];if(a[i][j] == '#') {++check;start.bx = min(start.bx, i);start.ex = max(start.ex, i);start.by = min(start.by, j);//计算最小覆盖矩形start.ey = max(start.ey, j);}}}if(!check) {cout << 0;//没啥用的特判return 0;}bfs();cout << -1 << '\n';return 0;
}
跑了 7ms。
- T6
比赛的时候蠢飞了，复杂度比别人凭空多一个 \(n\)。
折半搜索解决即可。注意分类讨论一下选不选择 \(n / 2\) 的位置，选不选择的两种情况分别开两个映射就行。
没啥好说的吧，自己看代码。
#include <bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define rep_(i, a, b) for(int i = a; i >= b; --i)
using namespace std;
constexpr int N = 65;
int n, m, ans, sum, gel, a[N];
unordered_map <int, int> b[2];
void dfs1(int now, int s, bool lst) {if(now == n / 2 + 1) {if(lst) {++b[1][s % m]; }else {++b[0][s % m];}return;}if(!lst) {dfs1(now + 1, s + a[now], true);dfs1(now + 1, s, false);}else {dfs1(now + 1, s, false);} }
void dfs2(int now, int s, bool lst, int typ) {if(now == n + 1) {ans += b[typ][((m - s) % m + m) % m];return;}if(!lst) {dfs2(now + 1, s + a[now], true, typ);dfs2(now + 1, s, false, typ);}else {dfs2(now + 1, s, false, typ); }
}
signed main() {cin >> n >> m;rep(i, 1, n) {cin >> a[i];gel += a[i];}dfs1(1, 0, false);dfs2(n / 2 + 1, 0, false, 0);dfs2(n / 2 + 1, 0, true, 1);cout << ans;return 0;
}