T1
洛谷 P3479 GAS-Fire Extinguishers
考虑贪心，从叶子往上，对于每个点能不放就不放，实在要放了再放。要知道一个点能不能不放，需要知道子树中最深的还没有被覆盖的点的距离。记 \(f[i][j]\) 为 \(i\) 子树中距离 \(i\) 为 \(j\) 的点有多少点没有被覆盖。一个点放了灭火器之后可以覆盖子树之外的点，所以还要记录 \(g[i][j]\) 表示 \(i\) 子树中距离 \(i\) 为 \(j\) 的点上的灭火器总共还能覆盖多少点。到每个点，先转移 \(f,g\)，然后如果 \(f[i][k] \ne 0\) 则在 \(i\) 放 \(\lceil \frac{f[i][k]}{s} \rceil\) 个灭火器。然后如果两个子树中分别有距离 \(i\) 为 \(j\) 和 \(k - j\) 或 \(k - j - 1\) 的未覆盖点和灭火器，那么用灭火器把这个未覆盖点消掉。最后在根尽量用灭火器把所有剩下的点都消掉，然后再看还有多少点需要覆盖。
代码
#include <iostream>
#define int long long
using namespace std;
int n, s, d;
int head[100005], nxt[200005], to[200005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int f[100005][21];
int g[100005][21];
int ans = 0;
void dfs(int x, int fa) {
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v != fa) {
dfs(v, x);
for (int i = 1; i <= d; i++) {
f[x][i] += f[v][i - 1];
g[x][i] += g[v][i - 1];
}
}
}
++g[x][0];
int tmp = (g[x][d] + s - 1) / s;
f[x][0] += tmp * s;
ans += tmp;
for (int i = 0; i <= d; i++) {
int j = d - i;
int t = min(f[x][i], g[x][j]);
f[x][i] -= t, g[x][j] -= t;
}
for (int i = 0; i < d; i++) {
int j = d - 1 - i;
int t = min(f[x][i], g[x][j]);
f[x][i] -= t, g[x][j] -= t;
}
}
signed main() {
cin >> n >> s >> d;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs(1, 0);
for (int i = 0; i <= d; i++) {
for (int j = d - i; ~j; j--) {
int tmp = min(f[1][i], g[1][j]);
f[1][i] -= tmp, g[1][j] -= tmp;
}
}
int asdf = 0;
for (int i = 0; i <= d; i++) asdf += g[1][i];
ans += (asdf + s - 1) / s;
cout << ans << "\n";
return 0;
}
T2
洛谷 P3480 KAM-Pebbles
差分，然后就变成阶梯博弈了。只不过是每次把左边的扔到右边。
代码
#include <iostream>
using namespace std;
int a[1005];
int main() {
int tc;
cin >> tc;
while (tc--) {
int n;
cin >> n;
int ans = 0;
for (int i = 1; i <= n; i++) cin >> a[i], ans ^= (((n - i + 1) & 1) * (a[i] - a[i - 1]));
cout << (ans ? "TAK\n" : "NIE\n");
}
return 0;
}
T4
洛谷 P3482 SLO-Elephants
首先肯定是若干个环。在环之内拆掉这个环的最优方案就是把代价最小的数每次和它所指向的点交换位置，这样解决一个环的代价就是 \(sum + mn \times (l - 2)\)，其中 \(sum\) 是环内代价和，\(mn\) 是最小代价，\(l\) 是环长。然后发现如果一个环内所有数都很大，我们可以把全局的最小值和环内最小值先换位，然后拿全局最小值把这个环搞掉，然后再换回来。所以对于每个环都求一下这两种代价然后取最小值加起来即可。
代码
#include <iostream>
#define int long long
using namespace std;
int n;
int val[1000005];
int f[1000005], s[1000005], v[1000005], sz[1000005], a[1000005], b[1000005];
int m = 2147483647;
int getf(int x) { return (f[x] == x ? x : (f[x] = getf(f[x]))); }
bool Merge(int x, int y) {
x = getf(x), y = getf(y);
if (x == y)
return 0;
if (sz[x] > sz[y])
swap(x, y);
f[x] = y;
s[y] += s[x];
sz[y] += sz[x];
v[y] = min(v[y], v[x]);
return 1;
}
int ans = 0;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> val[i], f[i] = i, sz[i] = 1, s[i] = v[i] = val[i], m = min(m, v[i]);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
cin >> b[i];
if (!Merge(a[i], b[i])) {
int x = getf(a[i]);
ans += (sz[x] != 1) * min(s[x] + v[x] * (sz[x] - 2), s[x] + v[x] + m * (sz[x] + 1));
}
}
cout << ans << "\n";
return 0;
}
T5
洛谷 P3485 BAJ-The Walk of the Bytie-boy
考虑 dp，朴素的就是 \(f[i][j]\) 表示 \(i \rightarrow j\) 是回文的最小步数，每次枚举两条相等的边转移。但是这样是 \(m^2\) 的，爆炸。考虑把 dp 状态拆掉。令 \(f[i][j]\) 还是不变，\(g[i][j][c]\) 表示 \(i \rightarrow k \rightarrow j\)，其中前一段是回文，后一段只有一条边权为 \(c\) 的边的最小步数。转移是简单的，使用 bfs 即可。注意要开两个 bfs 队列分别放两种 dp 值。
代码
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector<int> vec1[405][30];
vector<int> vec2[405][30];
struct node1 {
int x, y;
} pg[405][405][30];
struct node2 {
int x, y, c;
} pf[405][405];
queue<node1> q1;
queue<node2> q2;
int f[405][405], g[405][405][30];
void bfs() {
while (!q1.empty() || !q2.empty()) {
if (!q1.empty() && (q2.empty() || f[q1.front().x][q1.front().y] <= g[q2.front().x][q2.front().y][q2.front().c])) {
node1 tmp = q1.front();
q1.pop();
int x = tmp.x, y = tmp.y;
for (int i = 0; i < 26; i++) {
for (auto v : vec1[y][i]) {
if (g[x][v][i] > f[x][y] + 1) {
g[x][v][i] = f[x][y] + 1;
pg[x][v][i] = (node1) { x, y };
q2.push((node2) { x, v, i });
}
}
}
} else {
node2 tmp = q2.front();
q2.pop();
int x = tmp.x, y = tmp.y, z = tmp.c;
for (auto v : vec2[x][z]) {
if (f[v][y] > g[x][y][z] + 1) {
f[v][y] = g[x][y][z] + 1;
pf[v][y] = (node2) { x, y, z };
q1.push((node1) { v, y });
}
}
}
}
}
int ans[100005];
void print(int x, int y) {
int l = 0, r = f[x][y] + 1, t = f[x][y];
while (l + 1 < r) {
node2 tmp1 = pf[x][y];
ans[++l] = tmp1.c;
x = tmp1.x, y = tmp1.y;
if (l + 1 >= r)
break;
node1 tmp2 = pg[x][y][tmp1.c];
ans[--r] = tmp1.c;
x = tmp2.x, y = tmp2.y;
}
for (int i = 1; i <= t; i++) cout << (char)(ans[i] + 'a');
cout << "\n";
}
int main() {
memset(f, 63, sizeof f);
memset(g, 63, sizeof g);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
char c;
cin >> c;
vec1[u][c - 'a'].emplace_back(v);
vec2[v][c - 'a'].emplace_back(u);
f[u][v] = 1;
pf[u][v] = (node2) { 0, 0, c - 'a' };
q1.push((node1) { u, v });
}
for (int i = 1; i <= n; i++) f[i][i] = 0, q1.push((node1) { i, i });
bfs();
int d, x, y;
cin >> d;
cin >> x;
--d;
while (d--) {
cin >> y;
if (f[x][y] != 0x3f3f3f3f)
cout << f[x][y] << " ", print(x, y);
else
cout << -1 << "\n";
x = y;
}
return 0;
}
T6
洛谷 P3488 LYZ-Ice Skates
类似于二分图完美匹配的东西，考虑 Hall 定理：对于左部点的任意子集，其在右部点的邻集大小都大于等于该子集。我们考虑这个条件最有希望不满足的时候肯定是左边选一段尺码连续的人，这样邻集才能尽量小。所以只需要对每个区间看 \(\sum r_i\) 是否小于等于 \(k(r + d - l + 1)\) 即可。稍微移个项，发现是个最大子段和，直接线段树即可。
代码
#include <iostream>
#define int long long
using namespace std;
int n, m, k, d;
struct node {
int s, mx, lmx, rmx;
} T[1000005];
node operator+(node a, node b) {
node c;
c.s = a.s + b.s;
c.mx = max(a.rmx + b.lmx, max(a.mx, b.mx));
c.lmx = max(a.lmx, a.s + b.lmx);
c.rmx = max(b.rmx, b.s + a.rmx);
return c;
}
struct Segment_Tree {
void Build(int o, int l, int r) {
T[o].mx = T[o].lmx = T[o].rmx = -k;
T[o].s = -k * (r - l + 1);
if (l == r)
return;
int mid = (l + r) >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
}
void Add(int o, int l, int r, int x, int y) {
if (l == r) {
T[o].mx += y;
T[o].lmx += y;
T[o].rmx += y;
T[o].s += y;
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
Add(o << 1, l, mid, x, y);
else
Add(o << 1 | 1, mid + 1, r, x, y);
T[o] = T[o << 1] + T[o << 1 | 1];
}
node Query(int o, int l, int r, int L, int R) {
if (L <= l && r <= R)
return T[o];
int mid = (l + r) >> 1;
if (R <= mid)
return Query(o << 1, l, mid, L, R);
if (L > mid)
return Query(o << 1 | 1, mid + 1, r, L, R);
return Query(o << 1, l, mid, L, R) + Query(o << 1 | 1, mid + 1, r, L, R);
}
} seg;
signed main() {
cin >> n >> m >> k >> d;
seg.Build(1, 1, n);
while (m--) {
int x, y;
cin >> x >> y;
seg.Add(1, 1, n, x, y);
cout << (seg.Query(1, 1, n, 1, n).mx <= k * d ? "TAK\n" : "NIE\n");
}
return 0;
}
T7
洛谷 P3497 KOL-Railway
首先观察到如果存在 \(i < j < k\) 使得 \(a_k < a_j < a_i\)，那么 \(i\) 和 \(j\) 不能在同一个栈中。因为在 \(k\) 加入之前，\(i, j\) 都不会被弹出，而如果在同一个栈中的话，栈中就会出现顺序对，而这是不合法的。所以倒序枚举，维护后缀最小值 \(mn\)，每个点和尚未枚举到的、权值在 \((mn, a_i)\) 的点连边表示不在同一个栈中。暴力连边显然是 \(n^2\) 的，考虑线段树优化建图。由于是双向边，需要分别维护入树与出树。考虑如何只连没遍历到的点，我们可以把所有遍历到的点到根的路径上所有点都换一个新的，然后新的点就不向原来的叶子连边。这样以后连边都不会走到这个叶子。接下来 dfs 染色，原图中能够到达的两个叶子不能同色。但是对于线段树上的辅助节点，其颜色不能乱设。考虑第一次遍历到这个点时最后一个访问的叶子，很显然这个点能够到达的所有叶子都和最后一个访问的叶子异色。如果之后再来到这个点，但是最后一个访问的叶子颜色改变了，这样就会在叶子上产生矛盾。所以线段树上节点的颜色第一次访问到这个点时最后一个访问的叶子的颜色。这样所有点的染色方案都确定了。至于字典序最小，只需要顺序遍历每个点，如果没被染色就染 \(1\)，然后确定它能染的所有点。这样就能保证字典序最小。
代码
#include <iostream>
using namespace std;
int n;
int a[100005];
bool lf[6800005];
int head[6800005], nxt[13600005], to[13600005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
struct node {
int l, r, in, out;
} T[1000005];
int ncnt;
struct Segment_Tree {
void Build(int o, int l, int r) {
T[o].in = ++ncnt, T[o].out = ++ncnt;
if (l == r) {
T[o].in = T[o].out = l;
return;
}
int mid = (l + r) >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
add(T[o].in, T[o << 1].in), add(T[o].in, T[o << 1 | 1].in);
add(T[o << 1].out, T[o].out), add(T[o << 1 | 1].out, T[o].out);
}
void Add(int o, int l, int r, int L, int R, int x) {
if (L <= l && r <= R) {
if (l != r || !lf[l]) {
add(x, T[o].in);
add(T[o].out, x);
}
return;
}
int mid = (l + r) >> 1;
if (L <= mid)
Add(o << 1, l, mid, L, R, x);
if (R > mid)
Add(o << 1 | 1, mid + 1, r, L, R, x);
}
void Work(int o, int l, int r, int x) {
if (l == r)
return;
int mid = (l + r) >> 1;
if (x <= mid)
Work(o << 1, l, mid, x);
else
Work(o << 1 | 1, mid + 1, r, x);
T[o].in = ++ncnt, T[o].out = ++ncnt;
if (l != mid || !lf[l])
add(T[o].in, T[o << 1].in), add(T[o << 1].out, T[o].out);
if (mid + 1 != r || !lf[r])
add(T[o].in, T[o << 1 | 1].in), add(T[o << 1 | 1].out, T[o].out);
}
} seg;
bool vis[6800005];
int clr[6800005];
void dfs(int x, int lst) {
vis[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v <= n) {
if (!vis[v]) {
clr[v] = clr[x] ^ 1;
dfs(v, v);
} else if (v != lst && clr[v] == clr[x]) {
cout << "NIE\n";
exit(0);
}
} else {
if (!vis[v]) {
clr[v] = clr[x];
dfs(v, lst);
} else if (lf[v] && clr[v] != clr[x]) {
cout << "NIE\n";
exit(0);
}
}
lf[x] |= lf[v];
}
}
int main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
ncnt = n;
for (int i = 1; i <= n; i++) cin >> a[i];
seg.Build(1, 1, n);
for (int i = n, m = n + 1; i; i--) {
m = min(m, a[i]);
if (m < a[i] - 1)
seg.Add(1, 1, n, m + 1, a[i] - 1, a[i]);
lf[a[i]] = 1;
seg.Work(1, 1, n, a[i]);
}
for (int i = 1; i <= n; i++) {
if (!vis[a[i]])
dfs(a[i], a[i]);
}
cout << "TAK\n";
for (int i = 1; i <= n; i++) cout << clr[a[i]] + 1 << " ";
cout << "\n";
}
T8
洛谷 P3499 NAJ-Divine Divisor
首先拿 \(10^6\) 以内的所有素数把所有数除一遍，然后考虑得到的数，只有以下四种情况：
-
\(a[i] = 1\)
-
\(a[i] = p\)
-
\(a[i] = pq\)
-
\(a[i] = p^2\)
其中 \(p\) 和 \(q\) 都是质数。第一类不管，第二类使用 Miller-Rabin 判一下，第四类就看是不是完全平方数，第三类考虑与别的所有数求 \(\gcd\)，求出来要是不为 \(1\)，说明是拆开了，否则说明这个数里的质数没有在别的数里出现过，所以我们并不关心质数的具体数值，只需要统计下出现次数即可。
代码
#include <iostream>
#include <string.h>
#include <math.h>
#include <map>
#define int long long
#define i128 __int128
using namespace std;
int n;
map<int, int> mp;
map<int, int> bonus;
int p[1000005], pcnt;
bool mark[1000005];
void Sieve(int n) {
for (int i = 2; i <= n; i++) {
if (!mark[i])
p[++pcnt] = i;
for (int j = 1; p[j] * i <= n && j <= pcnt; j++) {
mark[p[j] * i] = 1;
if (i % p[j] == 0)
break;
}
}
}
int gcd(int a, int b) { return (b ? gcd(b, a % b) : a); }
int mr[12] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
inline int qpow(int x, int y, int P) {
int ret = 1;
while (y) {
if (y & 1)
ret = (i128)ret * x % P;
y >>= 1;
x = (i128)x * x % P;
}
return ret;
}
bool check(int a, int p) {
int d = p - 1;
if (qpow(a, d, p) != 1)
return 1;
int tmp;
while (!(d & 1)) {
tmp = qpow(a, d >>= 1, p);
if (tmp == p - 1)
return 0;
else if (tmp != 1)
return 1;
}
return 0;
}
bool isPrime(int x) {
for (int i = 0; i < 12; i++) {
if (x == mr[i])
return 1;
}
for (int i = 0; i < 12; i++) {
if (check(mr[i], x))
return 0;
}
return 1;
}
int cnt[1000005];
int a[1000005];
int cnt1;
char ans[1000005];
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
Sieve(1000000);
for (int i = 1; i <= pcnt; i++) {
for (int j = 1; j <= n; j++)
while (a[j] % p[i] == 0) ++cnt[i], a[j] /= p[i];
}
// 1, p, p ^ 2, p * q
for (int i = 1; i <= n; i++) {
if (a[i] == 1)
continue;
if (isPrime(a[i])) {
++mp[a[i]];
continue;
}
int r = sqrt(a[i]);
if (r * r == a[i]) {
mp[r] += 2;
continue;
}
bool rec = 0;
for (int j = 1; j <= n; j++) {
if (a[i] == a[j])
continue;
int tmp = gcd(a[i], a[j]);
if (tmp != 1) {
mp[tmp]++, mp[a[i] / tmp]++;
rec = 1;
break;
}
}
if (!rec)
bonus[a[i]]++;
}
int mxc = 0, mcnt = 0;
for (int i = 1; i <= pcnt; i++) {
if (cnt[i] > mxc) {
mxc = cnt[i];
mcnt = 0;
}
mcnt += (cnt[i] == mxc);
}
for (auto v : mp) {
if (v.second > mxc) {
mxc = v.second;
mcnt = 0;
}
mcnt += (v.second == mxc);
}
for (auto v : bonus) {
if (v.second > mxc) {
mxc = v.second;
mcnt = 0;
}
mcnt += (v.second == mxc) * 2;
}
cout << mxc << "\n";
sprintf(ans, "%.0Lf", powl(2.0L, mcnt));
ans[strlen(ans) - 1]--;
double x = 1;
while (mcnt--) x *= 2;
cout << ans << "\n";
return 0;
}
T9
洛谷 P3502 CHO-Hamsters
考虑 \(dp[i][j]\) 表示总共出现了 \(i\) 次，最后一个串是 \(j\) 的最小代价。考虑往串后面接一个 \(k\) 串，则肯定是把 \(k\) 中与 \(j\) 后缀重复的最长部分删掉，然后把剩下的接上去。这样两个串之间转移的代价就可以算了，直接 \(\min +\) 广义矩乘优化 dp 即可。
代码
#include <iostream>
#define int long long
using namespace std;
const int inf = 0x7fffffffffffff;
int n, m;
struct Matrix {
int a[200][200];
int* operator[](int x) { return a[x]; }
} I, E, T;
Matrix operator*(Matrix a, Matrix b) {
Matrix c;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
c[i][j] = inf;
for (int k = 0; k < n; k++)
c[i][j] = min(c[i][j], a[i][k] + b[k][j]);
}
}
return c;
}
Matrix qpow(Matrix x, int y) {
Matrix ret = E;
while (y) {
if (y & 1)
ret = ret * x;
y >>= 1;
x = x * x;
}
return ret;
}
string str[205];
int nxt[100005];
int calc(string s) {
nxt[0] = -1, nxt[1] = 0;
int n = s.size();
s = ' ' + s;
for (int i = 2, j = 0; i <= n; i++) {
while (j != -1 && s[j + 1] != s[i]) j = nxt[j];
nxt[i] = ++j;
}
return nxt[n];
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> str[i];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
E[i - 1][j - 1] = inf;
if (i == j)
T[i - 1][j - 1] = str[j].size() - calc(str[i]);
else
T[i - 1][j - 1] = str[j].size() - calc(str[j] + str[i]);
}
E[i - 1][i - 1] = 0;
}
for (int i = 1; i <= n; i++) I[0][i - 1] = str[i].size();
I = I * qpow(T, m - 1);
int ans = inf;
for (int i = 1; i <= n; i++) ans = min(ans, I[0][i - 1]);
cout << ans << "\n";
return 0;
}
T10
洛谷 P3505 TEL-Teleportation
把图分层，第一层是 \(1\)，第二层是与 \(1\) 直接相连的所有点，第三层是与第二层直接相连的所有点（不含 \(1\)）。第六层是 \(2\)，第五层是与 \(2\) 直接相连的所有点，第四层是与第五层直接相连的所有点（不含 \(2\)）。剩下的点先不管。这样的一张图，首先层之内可以任意连边，然后相邻的两层之间任两点都能互相连边。将所有边都连上，最后减去初始的边就能算出最多新建的边数。至于剩下的点，我们把这些点分配到第三层时的答案算一下和分配到第四层答案算出来取最大值即为最后的答案。证明考虑把两个代价分别列出来，设分配 \(x\) 个点到第三层的答案为 \(f(x)\)，然后能够发现是一个一次函数，所以最值就在两个端点处取到。
代码
#include <iostream>
#include <queue>
#define int long long
using namespace std;
int n, m;
int head[40005], nxt[2000005], to[2000005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int cnt[10];
int v[40005];
queue<int> q;
void bfs(int S) {
q.push(S);
if (S == 1)
v[S] = 1;
else
v[S] = 6;
while (!q.empty()) {
int x = q.front();
q.pop();
if (v[x] == 3 || v[x] == 4)
continue;
for (int i = head[x]; i; i = nxt[i]) {
int vv = to[i];
if (!v[vv]) {
v[vv] = v[x] + (S == 1 ? 1 : -1);
q.push(vv);
}
}
}
}
int f(int x) { return x * (x - 1) / 2; }
int calc() {
return cnt[1] * cnt[2] + cnt[2] * cnt[3] + cnt[3] * cnt[4] + cnt[4] * cnt[5] + cnt[5] * cnt[6] + f(cnt[1]) + f(cnt[2]) + f(cnt[3]) + f(cnt[4]) + f(cnt[5]) + f(cnt[6]);
}
signed main() {
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
add(u, v);
add(v, u);
}
bfs(1), bfs(2);
for (int i = 1; i <= n; i++) cnt[v[i]]++;
int ans = 0;
cnt[3] += cnt[0], ans = calc();
cnt[3] -= cnt[0], cnt[4] += cnt[0], ans = max(ans, calc());
cout << ans - m << "\n";
return 0;
}
T11
洛谷 P3506 MOT-Monotonicity
直接设 \(f_i\) 表示以 \(i\) 结尾的最大长度，然后根据长度确定接下来的大小关系，使用树状数组优化转移。这个 dp 虽然看起来不像对的，但是它确实具有最优子结构，它确实是对的。
代码
#include <iostream>
#define lowbit(x) ((x) &(-(x)))
using namespace std;
inline int read() {
int ret = 0;
char c = getchar();
while (c < '0' || c > '9') c = getchar();
while ('0' <= c && c <= '9') ret = ret * 10 + c - 48, c = getchar();
return ret;
}
int n, k;
string str, s;
int a[500005];
struct PBIT {
int bit[1000005], p[1000005];
void add(int x, int y, int pos) { for (; x <= 1000000; x += lowbit(x)) y >= bit[x] ? (p[x] = pos, bit[x] = y) : 0; }
pair<int, int> query(int x) {
int ret = 0, pos = 0;
for (; x; x -= lowbit(x)) bit[x] > ret ? (ret = bit[x], pos = p[x]) : 0;
return make_pair(ret, pos);
}
} pbit;
struct SBIT {
int bit[1000005], p[1000005];
void add(int x, int y, int pos) { for (; x; x -= lowbit(x)) y >= bit[x] ? (p[x] = pos, bit[x] = y) : 0; }
pair<int, int> query(int x) {
int ret = 0, pos = 0;
for (; x <= 1000000; x += lowbit(x)) bit[x] > ret ? (ret = bit[x], pos = p[x]) : 0;
return make_pair(ret, pos);
}
} sbit;
struct BIT {
int bit[1000005], p[1000005];
void add(int x, int y, int pos) { y > bit[x] ? (p[x] = pos, bit[x] = y) : 0; }
pair<int, int> query(int x) { return make_pair(bit[x], p[x]); }
} bit;
pair<int, int> dp[5000005];
int ans[500005], acnt;
int main() {
n = read(), k = read();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i <= k; i++) {
char c = getchar();
s += c;
getchar();
}
while (str.size() < n) str += s;
str = ' ' + str;
int ans = 0, mp = 0;
for (int i = 1; i <= n; i++) {
pair<int, int> mx1 = pbit.query(a[i] - 1);
pair<int, int> mx2 = sbit.query(a[i] + 1);
pair<int, int> mx3 = bit.query(a[i]);
pair<int, int> mx = max(mx1, max(mx2, mx3));
dp[i] = mx;
++dp[i].first;
if (dp[i].first > ans)
ans = dp[i].first, mp = i;
if (str[dp[i].first] == '=')
bit.add(a[i], dp[i].first, i);
if (str[dp[i].first] == '<')
pbit.add(a[i], dp[i].first, i);
if (str[dp[i].first] == '>')
sbit.add(a[i], dp[i].first, i);
}
cout << dp[mp].first << "\n";
return 0;
}
T12
洛谷 P3511 MOS-Bridges
首先考虑二分答案，然后有些边的某些方向就会被 ban 掉。对于剩下的图，我们要为每条方向未定的边确定一个方向，使得图中存在一个欧拉回路。关于欧拉回路，有一个结论：每个点的入度都等于出度等于度数的一半。有了这个结论，就可以通过网络流构造一个度数合法的方案，从而跑出对应的欧拉回路。
代码
#include <iostream>
#include <queue>
using namespace std;
const int inf = 2147483647;
int n, m;
struct Edge {
int u, v, x, y;
} E[2005];
namespace Dinic {
int S, T;
int head[3005], nxt[200005], to[200005], res[200005], ecnt = 1;
int cur[3005];
void add(int u, int v, int ww) {
to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, res[ecnt] = ww;
to[++ecnt] = u, nxt[ecnt] = head[v], head[v] = ecnt, res[ecnt] = 0;
}
queue<int> q;
int dep[3005];
bool bfs() {
for (int i = 1; i <= T; i++) dep[i] = -1;
dep[S] = 1;
q.push(S);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (dep[v] == -1 && res[i]) {
dep[v] = dep[x] + 1;
q.push(v);
}
}
}
return (dep[T] != -1);
}
int dinic(int x, int flow) {
if (x == T)
return flow;
int ret = 0;
for (int i = cur[x]; i && flow; i = nxt[i]) {
cur[x] = i;
int v = to[i];
if (dep[v] == dep[x] + 1 && res[i]) {
int tmp = dinic(v, min(res[i], flow));
res[i] -= tmp;
res[i ^ 1] += tmp;
flow -= tmp;
ret += tmp;
}
}
if (ret == 0)
dep[x] = -1;
return ret;
}
int dinic() {
int ret = 0;
while (bfs()) {
for (int i = 1; i <= T; i++) cur[i] = head[i];
ret += dinic(S, inf);
}
return ret;
}
void ini() {
ecnt = 1;
for (int i = 1; i <= T; i++) head[i] = 0;
}
}
int deg[1005];
bool chk(int k) {
Dinic::ini();
for (int i = 1; i <= m; i++) {
Dinic::add(Dinic::S, i, 1);
if (E[i].x <= k)
Dinic::add(i, E[i].v + m, 1);
if (E[i].y <= k)
Dinic::add(i, E[i].u + m, 1);
}
for (int i = 1; i <= n; i++) Dinic::add(i + m, Dinic::T, deg[i] / 2);
return Dinic::dinic() == m;
}
namespace Euler {
int head[1005], nxt[2005], to[2005], id[2005], ecnt;
void add(int u, int v, int x) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, id[ecnt] = x; }
bool ban[2005];
int stk[2005], sz;
void dfs(int x, int in) {
for (int i = head[x]; i; i = nxt[i]) {
head[x] = nxt[i];
if (ban[i])
continue;
ban[i] = 1;
int v = to[i];
dfs(v, i);
}
in ? (stk[++sz] = in) : 0;
}
void work() {
dfs(1, 0);
for (int i = sz; i; i--) cout << id[stk[i]] << " ";
cout << "\n";
}
}
signed main() {
cin >> n >> m;
Dinic::S = n + m + 1;
Dinic::T = n + m + 2;
for (int i = 1; i <= m; i++) {
cin >> E[i].u >> E[i].v >> E[i].x >> E[i].y;
deg[E[i].u]++;
deg[E[i].v]++;
}
int l = 1, r = 1000, mid, ans = -1;
while (l <= r) {
mid = (l + r) >> 1;
if (chk(mid))
ans = mid, r = mid - 1;
else
l = mid + 1;
}
if (ans == -1) {
cout << "NIE\n";
return 0;
}
cout << ans << "\n";
chk(ans);
for (int i = 1; i <= m; i++) {
for (int j = Dinic::head[i]; j; j = Dinic::nxt[j]) {
if (Dinic::to[j] > n + m)
continue;
if (Dinic::res[j] == 0) {
if (Dinic::to[j] - m == E[i].v)
Euler::add(E[i].u, E[i].v, i);
else
Euler::add(E[i].v, E[i].u, i);
}
}
}
Euler::work();
return 0;
}