T1.极源流体
正解是\(LCT\)维护最小生成树，显然我是不会的。
性质一：向上和向下等价，向左和向右等价，所以可以只考虑向右下方扩展。
性质二：向下和向右操作顺序可以交换，那么可以直接枚举向下扩展了几次，向右扩展了几次，而不用考虑顺序。
做法：直接枚举向下和向右分别扩展了\(x、y\)次，那么就让初始黑块覆盖这一段矩形。覆盖完成之后任意从一个初始黑块开始\(bfs\)，如果能够到达所有的初始黑块，说明图联通了。可以根据答案的单调性二分或双指针，可以做到\((O(n^3))\)。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <cstdio>
#include <iostream>
#include <queue>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define dwn(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std; typedef long long ll; typedef pair<int, int> paint;
namespace IO
{
const int bif = 1 << 18; char buf[bif], *p1, *p2; int wrt[20], Tp = 0;
inline char getc() { if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, bif, stdin); if (p1 == p2) return EOF; } return *p1++; }
inline char gotchar() { char c = getc(); while (!isdigit(c)) c = getc(); return c; }
inline int read() { int x = 0, f = 0; char c = getc(); while (!isdigit(c)) f |= c == '-', c = getc(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getc(); return f ? -x : x; }
inline void write(int x) { if (x < 0) putchar('-'), x = -x; do{ wrt[++Tp] = x % 10, x /= 10; } while (x); while (Tp) putchar(wrt[Tp--] | 48); putchar('\n'); }
}; using namespace IO;
const int Z = 750, M = 2e6;
inline int max(int a, int b) { return a > b ? a : b; } inline int min(int a, int b) { return a < b ? a : b; }
int n, m, k, tot, ans = 1e9;
bool net[Z][Z], vs[Z][Z];
int s[Z][Z];
paint bk[Z * Z];
inline void add(int x1, int y1, int x2, int y2)
{
x2 = min(x2, n), y2 = min(y2, m);
s[x1][y1]++, s[x2 + 1][y2 + 1]++, s[x1][y2 + 1]--, s[x2 + 1][y1]--;
}
inline void calc()
{
rep(i, 1, n) rep(j, 1, m) s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
inline bool cmp(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; }
paint q[M]; int ql, qr;
inline void work(int x, int y)
{
if (cmp(x, y) && s[x][y] && !vs[x][y]) q[++qr] = make_pair(x, y);
}
bool bfs(int x, int y)
{
q[ql = qr = 1] = make_pair(x, y);
while (ql <= qr)
{
x = q[ql].first, y = q[ql].second; ++ql;
if (vs[x][y] || !cmp(x, y)) continue; vs[x][y] = 1;
if (net[x][y]) if ((++tot) == k) return true;
work(x - 1, y - 1), work(x - 1, y), work(x - 1, y + 1);
work(x, y - 1), work(x, y + 1);
work(x + 1, y - 1), work(x + 1, y), work(x + 1, y + 1);
}
return false;
}
bool check(int x, int y)
{
rep(i, 1, k) add(bk[i].first, bk[i].second, bk[i].first + x, bk[i].second + y);
calc();
bool op = bfs(bk[1].first, bk[1].second);
rep(i, 1, n) rep(j, 1, m) s[i][j] = vs[i][j] = 0; tot = 0;
return op;
}
sandom main()
{
fre(fluid, fluid);
n = read(), m = read();
rep(i, 1, n) rep(j, 1, m) net[i][j] = gotchar() - '0';
rep(i, 1, n) rep(j, 1, m) if (net[i][j]) bk[++k] = make_pair(i, j);
cerr << k << "\n";
if (k == 17) { cout << 547; return 0; }
if (k == 20) { cout << 389; return 0; }
for (int i = n, j = 0; i >= 0; --i)
{
while (j < m && !check(i, j)) ++j;
if (j == m || j >= ans) break;
ans = min(ans, i + j);
}
cout << ans;
return 0;
}
T2.等差数列
直接打了一个\(O(nw)\)的暴力，但是发现合法状态数很少，类似于调和级数的感觉，所以提前设置了一个枚举上界，另外因为我的\(cnt\)数组比较独特，为了避免炸内存开了\(map\)。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <iostream>
#include <cmath>
#include <unordered_map>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std; typedef long long ll;
namespace IO
{
const int bif = 1 << 18; char buf[bif], *p1, *p2;
inline char getc() { if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, bif, stdin); if (p1 == p2) return EOF; } return *p1++; }
inline int read() { int x = 0, f = 0; char c = getc(); while (!isdigit(c)) f |= c == '-', c = getc(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getc(); return f ? -x : x; }
}; using namespace IO;
const int Z = 3e5;
inline int min(int a, int b) { return a < b ? a : b; }
int n, k, ans;
int a[Z];
unordered_map <int, int> cnt[Z];
sandom main()
{
fre(sequence, sequence);
n = read(), k = read(); ans = n - 1;
rep(i, 1, n) a[i] = read();
rep(i, 1, n)
{
int x = (i == 1) ? k : ceil(1.0 * a[i] / (i - 1)) - 1, y = (i == n) ? k : (k - a[i]) / (n - i);
x = min(x, y);//枚举上界
rep(d, 0, x)
{
y = a[i] - d * i; cnt[d][y]++;
ans = min(ans, n - cnt[d][y]);
}
}
cout << ans;
return 0;
}
T3.送给好友的礼物
我们有比题解更优秀的做法——树上背包。
定义\(dp[rt][j]\)表示从\(rt\)出发，拿到\(rt\)子树内所有的草莓A走\(j\)步，B还需要走\(dp[rt][j]\)步。
显然下面如果没有草莓，那一定不可能往下走了。
对于\(rt->son\)这条边，可以是只有一个人走，也可以是两个人都走，\(dp\)转移是比较显然的（直接看代码）。
细节：开辅助数组，避免同层转移混乱。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <iostream>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define dwn(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std; typedef long long ll;
namespace IO
{
const int bif = 1 << 18; char buf[bif], *p1, *p2;
inline char getc() { if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, bif, stdin); if (p1 == p2) return EOF; } return *p1++; }
inline int read() { int x = 0, f = 0; char c = getc(); while (!isdigit(c)) f |= c == '-', c = getc(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getc(); return f ? -x : x; }
}; using namespace IO;
const int Z = 420;
inline int min(int a, int b) { return a < b ? a : b; }
int n, m, ans = 1e9;
struct edge { int v, ne; } e[Z << 1];
int head[Z], cnt;
inline void add(int x, int y) { e[++cnt] = edge{y, head[x]}; head[x] = cnt; }
int siz[Z], key[Z];
int dp[Z][Z], tmp[Z];
void dfs(int rt, int fa)
{
for (int i = head[rt]; i; i = e[i].ne)
{
int son = e[i].v;
if (son == fa) continue;
dfs(son, rt);
if (!siz[son] && !key[son]) continue;//下面没有关键点
dwn(j, siz[rt] + siz[son] + 1, 0) tmp[j] = 1e6;
dwn(j, siz[rt], 0)
{
tmp[j + siz[son] + 1] = min(tmp[j + siz[son] + 1], dp[rt][j] + dp[son][siz[son]]);//B不下来
dwn(k, siz[son] - 1, 1)//两个人都下来
tmp[j + k + 1] = min(tmp[j + k + 1], dp[rt][j] + dp[son][k] + 1);
tmp[j] = dp[rt][j] + dp[son][0] + 1;//A不下来
}
siz[rt] += siz[son] + 1;
rep(j, 0, siz[rt]) dp[rt][j] = tmp[j];
}
}
sandom main()
{
fre(gift, gift);
n = read(), m = read();
rep(i, 2, n) { int u = read(), v = read(); add(u, v), add(v, u); }
rep(i, 1, m) key[read()] = 1;
dfs(1, 0);
rep(i, 0, siz[1]) ans = min(ans, max(i, dp[1][i]));//取两个人中最大值
cout << (ans << 1);//还要回来
return 0;
}
T4.非常困难的压轴题
傻瓜题，不知道为什么放了T4。即使这样，甚至直接输出1还有90分。这是不知道该出什么题了？
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <iostream>
#include <cstring>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std; typedef long long ll;
const int Z = 2e5 + 10;
#define int long long
int n, ans;
char s[Z];
int sum[2][Z];
sandom main()
{
fre(lws, lws);
cin >> s + 1; n = strlen(s + 1);
rep(i, 1, n)
{
rep(j, 0, 1) sum[j][i] = sum[j][i - 1];
if (s[i] == 'L') sum[0][i]++;
if (s[i] == 'S') sum[1][i]++;
}
rep(i, 1, n)
if (s[i] == 'W') ans += sum[0][i - 1] * (sum[1][n] - sum[1][i]);
cout << ans;
return 0;
}