T1
NFLSOJ P2023050961 捉迷藏
首先只需要考虑所有叶子，只要每个叶子都连向了另一个距离超过 \(2\) 的叶子，则符合要求。距离超过 \(2\) 等价于在不同的父亲下。则问题变为一堆点，每个点有颜色，同色点间没有边，异色点间两两有边，求最大匹配。
结论：设点最多的颜色 \(c\) 有 \(x\) 个点，若 \(x \ge \lceil \frac{n}{2} \rceil\)，则答案为 \(n - x\)，否则为 \(\lfloor \frac{n}{2} \rfloor\)。前者显然，后者考虑构造。先把这 \(x\) 个点排成一个环，维护一个指针指向环内任意一个点。遍历其他所有点，将这个点插入当前指针所指的点的下一位，然后将指针顺时针移到下一个颜色为 \(c\) 的点。容易发现这样得到的环任意两个相邻点不同色，两两匹配即可。
代码
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int head[200005], nxt[400005], to[400005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int f[200005], dfn[200005];
int lf[200005], lcnt;
int deg[200005];
int ncnt;
void dfs1(int x, int fa) {
f[x] = fa;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v != fa)
dfs1(v, x);
}
}
int main() {
freopen("hide.in", "r", stdin);
freopen("hide.out", "w", stdout);
int tc;
cin >> tc;
while (tc--) {
for (int i = 1; i <= n; i++) deg[i] = head[i] = 0;
ecnt = 0;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
++deg[u], ++deg[v];
}
if (n == 2) {
cout << "-1\n";
continue;
}
ncnt = lcnt = 0;
int rt = 1;
for (int i = 1; i <= n; i++) (deg[i] == 1) ? (lf[++lcnt] = i) : (rt = i);
dfs1(rt, 0);
sort(lf + 1, lf + lcnt + 1, [](int a, int b) { return f[a] < f[b]; });
if (f[lf[1]] == f[lf[lcnt]]) {
cout << -1 << "\n";
continue;
}
int ans = 0;
for (int i = 1, j = 1; i <= lcnt; i = j) {
while (j <= lcnt && f[lf[j]] == f[lf[i]]) ++j;
if (j - i >= (lcnt + 1) / 2) {
ans = j - i;
break;
}
}
if (!ans)
ans = (lcnt + 1) / 2;
cout << ans << "\n";
}
return 0;
}
T2
NFLSOJ P2023050962 涂奶酪
首先注意到所有点会形成一棵基环树，而我们只关心 \(s\) 所在的弱连通分量。先假设 \(s\) 原本是白色，而我们需要花 \(p_s\) 的代价把它凭空染成黄色，最后再减去这个代价。会发现一个点会被多次染色，颜色就在两者间交替。首先考虑 \(s\) 不在环内的情况，考虑 \(dp[i][j]\) 表示 \(i\) 的子树内，\(i\) 被染了 \(j\) 次色的最大收益。容易发现 \(i\) 被染色 \(j\) 次时其所有儿子染色次数都 \(\le j\)，所以是好转移的。当 \(s\) 不在环内时，\(j\) 只能为 \(0 / 1 / 2\)。
然后考虑 \(s\) 所在环大小为 \(2\) 的情况。对 \(s\) 和 \(a_s\) 分别跑一次上一段的树形 dp，然后由于环长只有 \(2\)，\(a_s\) 至多被染色一次。所以情况数很少，直接分讨即可。
对于剩下的，会发现可能会有一个黄色的线段在环上一直转悠。如果在环上每个点写下这个点的染色次数，会发现任何时刻所有数极差不超过 \(2\)，而且任何符合要求的染色次数都可以构造。所以我们先对环上每个点跑那个树形 dp，然后把第二维开到 \(n\)，最后枚举一下 \(s\) 的染色次数，在环上稍微 dp 一下即可。
代码
#include <iostream>
#define int long long
using namespace std;
const int inf = 0x7ffffffffffffff;
int n, s;
int a[5005];
int dp[5005][5005];
int c[5005], ccnt;
int head[5005], nxt[5005], to[5005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
bool vis[5005];
int w[5005], p[5005];
void dfs(int x) {
for (int i = 1; i <= n; i++) dp[x][i] = ((i & 1) ? w[x] : 0) - p[x] * i;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (!vis[v]) {
dfs(v);
int mx = 0;
for (int j = 1; j <= n; j++) {
mx = max(mx, dp[v][j]);
dp[x][j] = max(dp[x][j], dp[x][j] + mx);
}
}
}
}
signed main() {
freopen("cheese.in", "r", stdin);
freopen("cheese.out", "w", stdout);
cin >> n >> s;
for (int i = 1; i <= n; i++) cin >> w[i];
for (int i = 1; i <= n; i++) cin >> p[i];
for (int i = 1; i <= n; i++) cin >> a[i], add(a[i], i);
for (int i = s; !vis[i]; i = a[i]) {
vis[i] = 1;
c[++ccnt] = i;
}
if (a[c[ccnt]] != s) {
dfs(s);
cout << max(dp[s][1], dp[s][2]) + p[s] << "\n";
return 0;
}
if (ccnt == 2) {
dfs(s);
dfs(a[s]);
cout << max(dp[s][1], max(dp[s][1] + dp[a[s]][1], dp[s][2])) + p[s] << "\n";
return 0;
}
for (int i = 1; i <= ccnt; i++) dfs(c[i]);
int ans = -inf;
for (int i = 1; i <= n; i++) {
int s0, s1, s2;
s0 = s1 = s2 = dp[s][i];
for (int j = ccnt; j > 1; j--) {
(i ^ 1) ? (s2 += dp[c[j]][i - 2]) : 0;
s1 += dp[c[j]][i - 1];
s0 += dp[c[j]][i];
s1 = max(s1, s0);
s2 = max(s2, s1);
}
ans = max(ans, (i ^ 1) ? s2 : s1);
}
cout << ans + p[s] << "\n";
return 0;
}
T3
NFLSOJ P2023050963 玩游戏
先假设 \(0\) 比 \(1\) 少，否则翻转序列并反转 \(0 / 1\)。通过模拟可以发现长度大于 \(1\) 的 \(1\) 连续段会向右移，而 \(0\) 连续段会向左移，当两个相撞的时候每次两个的长度都会减少 \(1\) 直到其中一个长度为 \(1\) 为止。我们先找到一个位置使得将 \(0\) 视为 \(-1\) 之后所有前缀和非负，并且序列末尾没有 \(1\)。可以发现一定可以找到这样的位置。然后按照连续段模拟，每找到一个 \(1\) 连续段就扔到栈里，找到一个 \(0\) 连续段就跟栈里的东西撞一撞，抵消掉。最后可以知道剩余的 \(1\) 连续段的位置和长度。对于剩下的位置 \(01\) 交替即可。然后就是一个 KMP 求循环节。把最后一次相撞的结束时间和循环节加起来即为所求。
代码
#include <iostream>
#include <algorithm>
#include <cassert>
#define int long long
using namespace std;
const int P = 1000000007;
string str;
int n;
struct node {
int s, l;
} stk[10000005];
int sz;
int nxt[10000005];
int ss[10000005];
signed main() {
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
int tc;
cin >> tc;
while (tc--) {
cin >> str;
n = str.size();
int c0 = 0, c1 = 0;
for (int i = 0; i < n; i++) c0 += (str[i] == '0'), c1 += (str[i] == '1');
if (c0 > c1) {
for (int i = 0; i < n; i++) str[i] = '0' + ((str[i] - '0') ^ 1);
reverse(str.begin(), str.end());
}
int s = 0, p = 0, cs = 1;
for (int i = 0; i < n; i++) {
s += (str[i] == '0' ? -1 : 1);
s < cs ? (p = i + 1, cs = s) : 0;
}
if (s == n) {
cout << 1 << "\n";
continue;
}
if (p && p != n) {
string tstr = str;
str = "";
for (int i = p; ; i = (i + 1) % n) {
str += tstr[i];
if (i == p - 1)
break;
}
}
int pos = n - 1;
while (str[pos] == '1') str.pop_back(), --pos;
string asdf;
while (pos + 1 < n) asdf += '1', ++pos;
str = asdf + str;
sz = 0;
int ans = 0;
for (int i = 0, j = 0; i < n; i = j) {
while (j < n && str[j] == str[i]) ++j;
if (j == i + 1)
continue;
if (str[i] == '1')
stk[++sz] = (node) { i, j - i - 1 };
else {
int cl = j - i - 1;
while (cl) {
int val = min(cl, stk[sz].l);
ans = max(ans, (j - stk[sz].s + min(cl - stk[sz].l, stk[sz].l - cl)) / 2 - 1);
stk[sz].l -= val, cl -= val;
(stk[sz].l == 0) ? (--sz) : 0;
}
}
}
for (int i = 1; i <= n; i++) ss[i] = 0;
int cur = 1;
stk[++sz] = (node) { n, -1 };
for (int i = 1; i <= sz; i++) {
stk[i].s += ans;
while (cur < stk[i].s + 1) ss[(cur - 1) % n + 1] = ((cur & 1) != (stk[i].s & 1)), ++cur;
for (int j = 0; j <= stk[i].l; j++)
ss[(stk[i].s + j) % n + 1] = 1;
cur = stk[i].s + stk[i].l + 1 + 1;
}
nxt[0] = -1, nxt[1] = 0;
for (int i = 2, j = 1; i <= n; i++, j++) {
while (j && ss[i] != ss[j]) j = nxt[j - 1] + 1;
nxt[i] = j;
}
ans += (n % (n - nxt[n]) == 0 ? n - nxt[n] : n);
cout << ans % P << "\n";
}
return 0;
}
经典结论。
观察性质。
按照题意模拟，观察性质。
标签：5005,int,ecnt,++,20240503,str,dp From： https://www.cnblogs.com/forgotmyhandle/p/18172100