简述
突然记起来 CSP 前特别喜欢的 POI 题还有一堆没写，所以就有了这个坑。
「POI2015」TRZ
写起来还挺麻烦。
我们考虑先把条件写出来：
\[ \begin{cases} s_r^1 – s_{l – 1}^1 \neq s_r^2 – s_{l – 1}^2 \neq s_r^2 – s_{l – 1}^2 \neq s_r^1 – s_{l – 1}^1 \end{cases} \]
进行移项之后发现可以做成自身的特征：
\[ \begin{cases} s_r^1 – s_r^2 \neq s_{l – 1}^1 – s_{l – 1}^2 \\ s_r^1 – s_r^3 \neq s_{l – 1}^1 – s_{l – 1}^3 \\ s_r^2 – s_r^3 \neq s_{l – 1}^2 – s_{l – 1}^3 \end{cases} \]
我们需要找到最长的区间使得这个条件成立，那么其实这就是一个偏序问题。每一个三维的点每一维直接做成其特征即可。而这个偏序需要知道除自己以外的所有信息，所以不能像正常的偏序来搞。所以，我们来进行拼凑。考虑按 \(x\) 排序，然后把 \(y\) 插入权值线段树，最后每个节点维护两个不同的 \(z\) 的极点位置即可。有点难写。
// P3590.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200, INF = 0x3f3f3f3f;
int n, ans, ptot = 1;
char str[MAX_N];
struct node
{
int lson, rson, max_val[2] = {-1, -1}, min_val[2] = {INF, INF};
} nodes[MAX_N * 3];
struct package
{
int id, x, y, z;
bool operator<(const package &rhs) const { return x < rhs.x; }
} pre[MAX_N], ai[MAX_N], bi[MAX_N];
int update(int qx, int l, int r, int p, package val)
{
if (p == 0)
p = ++ptot;
if (nodes[p].min_val[0] > val.id)
{
if (nodes[p].min_val[0] != INF && bi[nodes[p].min_val[0]].id != val.z)
nodes[p].min_val[1] = nodes[p].min_val[0];
nodes[p].min_val[0] = val.id;
}
else if (nodes[p].min_val[1] > val.id && bi[nodes[p].min_val[0]].z != val.z)
nodes[p].min_val[1] = val.id;
if (nodes[p].max_val[0] < val.id)
{
if (nodes[p].max_val[0] != -1 && bi[nodes[p].max_val[0]].z != val.z)
nodes[p].max_val[1] = nodes[p].max_val[0];
nodes[p].max_val[0] = val.id;
}
else if (nodes[p].max_val[1] < val.id && bi[nodes[p].max_val[0]].z != val.z)
nodes[p].max_val[1] = val.id;
if (l == r)
return p;
int mid = (l + r) >> 1;
if (qx <= mid)
nodes[p].lson = update(qx, l, mid, nodes[p].lson, val);
else
nodes[p].rson = update(qx, mid + 1, r, nodes[p].rson, val);
return p;
}
int query(int ql, int qr, int l, int r, int p, package val)
{
if (p == 0)
return 0;
if (ql <= l && r <= qr)
{
int min_val, max_val;
if (nodes[p].min_val[0] == INF)
return 0;
min_val = (val.z == bi[nodes[p].min_val[0]].z) ? nodes[p].min_val[1] : nodes[p].min_val[0];
max_val = (val.z == bi[nodes[p].max_val[0]].z) ? nodes[p].max_val[1] : nodes[p].max_val[0];
if (min_val == INF || max_val == -1)
return 0;
return max(abs(val.id - min_val), abs(val.id - max_val));
}
int mid = (l + r) >> 1, ret = 0;
if (ql <= mid)
ret = max(ret, query(ql, qr, l, mid, nodes[p].lson, val));
if (mid < qr)
ret = max(ret, query(ql, qr, mid + 1, r, nodes[p].rson, val));
return ret;
}
int main()
{
scanf("%d%s", &n, str);
for (int i = 0, ptr = 0; i < n; i++)
{
if (str[i] != str[ptr])
ptr = i;
ans = max(ans, i - ptr + 1);
}
for (int i = 1; i <= n; i++)
{
pre[i] = pre[i - 1];
if (str[i - 1] == 'C')
pre[i].x++;
if (str[i - 1] == 'B')
pre[i].y++;
if (str[i - 1] == 'S')
pre[i].z++;
}
int lower = 0;
for (int i = 1; i <= n; i++)
{
ai[i].x = pre[i].x - pre[i].y;
ai[i].y = pre[i].x - pre[i].z;
ai[i].z = pre[i].y - pre[i].z;
lower = min(lower, min(ai[i].x, min(ai[i].y, ai[i].z)));
ai[i].id = i;
}
n++;
for (int i = 1; i <= n; i++)
ai[i].x -= lower - 1, ai[i].y -= lower - 1, ai[i].z -= lower - 1;
for (int i = 1; i <= n; i++)
bi[i] = ai[i];
bi[0] = bi[n], sort(ai + 1, ai + 1 + n);
int domain = n - lower + 1;
for (int i = 1, ptr = 1; i <= n; i++)
{
if (ai[i].x != ai[ptr].x)
ptr = i;
if (ai[i].x != ai[i + 1].x)
{
for (int j = ptr; j <= i; j++)
ans = max(ans, max(query(1, ai[j].y - 1, 1, domain, 1, ai[j]), query(ai[j].y + 1, domain, 1, domain, 1, ai[j])));
for (int j = ptr; j <= i; j++)
update(ai[j].y, 1, domain, 1, ai[j]);
}
}
printf("%d\n", ans);
return 0;
}
「POI2009」LYZ
之前没学过 Hall 定理，后面发现结论还算是比较显然的：对于任意的左部点集 \(U\)，与之相连的极大右部点集 \(S\) 要满足 \(|U| \leq |S|\)。本题在数据范围小的时候显然可以直接二分图匹配做，但是现在的数据并不允许，并要求维护完美匹配性。首先发现最糟情况时存在一个区间 \([l, r]\) 满足：
\[ \sum_{i = l}^r X_i > (r – l + 1 + d) k \]
移项得到：
\[ \sum_{i = l}^r (X_i – k) > d \times k \]
线段树找一段这样的即可。
// P3488.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e5 + 200;
typedef long long ll;
int n, m, k, d;
struct node
{
ll lft, rig, sum, seg;
} nodes[MAX_N << 2];
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)
void pushup(int p)
{
nodes[p].sum = nodes[lson].sum + nodes[rson].sum;
nodes[p].lft = max(nodes[lson].lft, nodes[lson].sum + nodes[rson].lft);
nodes[p].rig = max(nodes[rson].rig, nodes[rson].sum + nodes[lson].rig);
nodes[p].seg = max(nodes[lson].rig + nodes[rson].lft, max(nodes[lson].seg, nodes[rson].seg));
}
void build(int l, int r, int p)
{
if (l == r)
{
nodes[p] = node{0, 0, -k, -k};
return;
}
build(l, mid, lson), build(mid + 1, r, rson);
pushup(p);
}
void update(int qx, int l, int r, int p, int val)
{
if (l == r)
{
nodes[p].sum += val, nodes[p].seg += val;
nodes[p].lft = nodes[p].rig = max(0LL, nodes[p].sum);
return;
}
if (qx <= mid)
update(qx, l, mid, lson, val);
else
update(qx, mid + 1, r, rson, val);
pushup(p);
}
#undef mid
#undef rson
#undef lson
int main()
{
scanf("%d%d%d%d", &n, &m, &k, &d), build(1, n, 1);
for (int i = 1; i <= m; i++)
{
int xpos, val;
scanf("%d%d", &xpos, &val), update(xpos, 1, n, 1, val);
puts(nodes[1].seg <= 1LL * d * k ? "TAK" : "NIE");
}
return 0;
}
「POI2014」KAR
想起在纪中做过的一道 A 组 SB 题，跟这个比较一致。发现区间之间可以直接维护，那么就上个线段树就好了。
// P3569.cpp
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 4e5 + 200;
int n, ai[MAX_N][2], q;
bool nodes[MAX_N << 2][2][2];
inline char nc()
{
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
int read()
{
int x = 0, f = 1;
char ch = nc();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = nc();
}
while (isdigit(ch))
x = (x << 3) + (x << 1) + ch - '0', ch = nc();
return x * f;
}
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)
inline void pushup(int p, int l, int r)
{
nodes[p][0][0] = nodes[p][1][0] = nodes[p][0][1] = nodes[p][1][1] = false;
for (register int a = 0; a < 2; a++)
for (register int b = 0; b < 2; b++)
for (register int c = 0; c < 2; c++)
for (register int d = 0; d < 2; d++)
nodes[p][a][d] |= nodes[lson][a][c] && nodes[rson][b][d] && ai[mid][c] <= ai[mid + 1][b];
}
inline void update(int qx, int l, int r, int p)
{
if (l == r)
return;
if (qx <= mid)
update(qx, l, mid, lson);
else
update(qx, mid + 1, r, rson);
pushup(p, l, r);
}
inline void build(int l, int r, int p)
{
if (l == r)
{
nodes[p][0][0] = nodes[p][1][1] = true;
return;
}
build(l, mid, lson), build(mid + 1, r, rson);
pushup(p, l, r);
}
#undef mid
#undef rson
#undef lson
int main()
{
n = read();
for (register int i = 1; i <= n; i++)
ai[i][0] = read(), ai[i][1] = read();
q = read(), build(1, n, 1);
while (q--)
{
int x = read(), y = read();
swap(ai[x][0], ai[y][0]), swap(ai[x][1], ai[y][1]);
update(x, 1, n, 1), update(y, 1, n, 1);
puts(nodes[1][0][0] || nodes[1][0][1] || nodes[1][1][0] || nodes[1][1][1] ? "TAK" : "NIE");
}
return 0;
}
「POI2014」KLO
我们考虑相间而放，用一个堆以大小为关键字来维护可选项。注意的是，我们尽量把和末尾颜色相同的 block 放前。每次选出最大的块、或者是次大的块放置，然后再 check 即可。
// P3569.cpp
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 4e5 + 200;
int n, ai[MAX_N][2], q;
bool nodes[MAX_N << 2][2][2];
inline char nc()
{
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
int read()
{
int x = 0, f = 1;
char ch = nc();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = nc();
}
while (isdigit(ch))
x = (x << 3) + (x << 1) + ch - '0', ch = nc();
return x * f;
}
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)
inline void pushup(int p, int l, int r)
{
nodes[p][0][0] = nodes[p][1][0] = nodes[p][0][1] = nodes[p][1][1] = false;
for (register int a = 0; a < 2; a++)
for (register int b = 0; b < 2; b++)
for (register int c = 0; c < 2; c++)
for (register int d = 0; d < 2; d++)
nodes[p][a][d] |= nodes[lson][a][c] && nodes[rson][b][d] && ai[mid][c] <= ai[mid + 1][b];
}
inline void update(int qx, int l, int r, int p)
{
if (l == r)
return;
if (qx <= mid)
update(qx, l, mid, lson);
else
update(qx, mid + 1, r, rson);
pushup(p, l, r);
}
inline void build(int l, int r, int p)
{
if (l == r)
{
nodes[p][0][0] = nodes[p][1][1] = true;
return;
}
build(l, mid, lson), build(mid + 1, r, rson);
pushup(p, l, r);
}
#undef mid
#undef rson
#undef lson
int main()
{
n = read();
for (register int i = 1; i <= n; i++)
ai[i][0] = read(), ai[i][1] = read();
q = read(), build(1, n, 1);
while (q--)
{
int x = read(), y = read();
swap(ai[x][0], ai[y][0]), swap(ai[x][1], ai[y][1]);
update(x, 1, n, 1), update(y, 1, n, 1);
puts(nodes[1][0][0] || nodes[1][0][1] || nodes[1][1][0] || nodes[1][1][1] ? "TAK" : "NIE");
}
return 0;
}
「POI2010」Monotonicity
首先我们可以把符号序列给倍长出来，然后再考虑用子序列匹配那一套进行 DP。而这里只需要单维，也就是说我们并不记录子序列的长度，因为可以注意到最长的答案中间切掉，也是满足最优子结构的（证明），所以可以不用记录，搞个树状数组就完事了。
// BZ2090.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200, MAX_M = 5e6 + 200;
int n, m, ai[MAX_N], nodes[3][MAX_M], dp[MAX_N];
char str[MAX_N];
inline int lowbit(int x) { return x & (-x); }
void update(int idx, int x, int d)
{
for (; x < MAX_M; x += lowbit(x))
nodes[idx][x] = max(nodes[idx][x], d);
}
int query(int idx, int x, int ret = 0)
{
for (; x; x -= lowbit(x))
ret = max(ret, nodes[idx][x]);
return ret;
}
int main()
{
char tmp[2];
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &ai[i]);
for (int i = 1; i <= m; i++)
scanf("%s", tmp), str[i] = tmp[0];
for (int i = m + 1; i <= n; i++)
str[i] = str[(i - 1) % m + 1];
int ans = 0;
for (int i = 1; i <= n; i++)
{
dp[i] = max(nodes[2][ai[i]], max(query(0, ai[i] - 1), query(1, MAX_M - ai[i]))) + 1;
ans = max(ans, dp[i]);
if (str[dp[i]] == '=')
nodes[2][ai[i]] = max(nodes[2][ai[i]], dp[i]);
else if (str[dp[i]] == '<')
update(0, ai[i], dp[i]);
else
update(1, MAX_M - ai[i] + 1, dp[i]);
}
printf("%d\n", ans);
return 0;
}
「POI2005」DWA-Two Parties
这道题就很骚了。
首先有个结论，就是一定能找出一个划分方案，使得某个集合中所有的点都连上了偶数条边，且是最优解。知道这个，我们可以尝试给每个点表一个状态 \(x_i\)，代表其集合 ID（0/1）。这样我们可以搞成一个异或方程组，然后高斯消元得到一个方案即可。
// P3429.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 220;
int n, deg[MAX_N], mat[MAX_N][MAX_N];
int main()
{
scanf("%d", &n);
for (int i = 1, tot, v; i <= n; i++)
{
scanf("%d", &tot);
while (tot--)
scanf("%d", &v), mat[i][v] = 1, deg[i]++;
if (deg[i] & 1)
mat[i][i] = mat[i][n + 1] = 1;
}
for (int i = 1; i <= n; i++)
{
int key = i;
for (int j = i + 1; j <= n; j++)
if (mat[j][i] != 0)
{
key = j;
break;
}
if (key != i)
for (int j = i; j <= n + 1; j++)
swap(mat[i][j], mat[key][j]);
for (int j = i + 1; j <= n; j++)
if (mat[j][i] == 1)
for (int k = i; k <= n + 1; k++)
mat[j][k] ^= mat[i][k];
}
mat[n][n] = 1;
// reverse;
for (int i = n - 1; i >= 1; i--)
{
for (int j = i + 1; j <= n; j++)
if (mat[i][j] != 0)
for (int k = j; k <= n + 1; k++)
mat[i][k] ^= mat[j][k];
mat[i][i] = 1;
}
int tot = 0;
for (int i = 1; i <= n; i++)
tot += mat[i][n + 1];
printf("%d\n", tot);
for (int i = 1; i <= n; i++)
if (mat[i][n + 1])
printf("%d ", i);
puts("");
return 0;
}
「POI2012」STU-Well
大概思路：首先二分那个差值，然后我们再来算每个位置归零的代价，再找最小的位置即可。
那么我们如何快速计算每个位置归零的代价呢？首先我们可以计算让全局合法的最小代价，方式是正反各扫一遍，保证 \(|a_i – a_{i + 1}| \leq mid\)。枚举 \(k\) 时，我们可以分左右来算贡献。以左侧为例，找到一个位置 \(a_{L} > (k – L)mid\)，那么 \([L, i – 1]\) 这一部分的和减去等差数列之和就是部分贡献了。我想了一会为什么这样是对的，发现：如果 \(a_{L} > (k – L)mid\)，且即使这段区间不是等差的，那么这段区间和减去等差数列之和，「多扣」的部分会从 \(a_L\) 上扣除。右侧原理一致。
// P3534.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + 200;
int n;
ll m, xi[MAX_N], ai[MAX_N], pre[MAX_N], prefix[MAX_N], suffix[MAX_N];
int check(int mid)
{
ai[1] = xi[1];
for (int i = 2; i <= n; i++)
ai[i] = min(ai[i - 1] + mid, xi[i]);
for (int i = n - 1; i >= 1; i--)
ai[i] = min(ai[i + 1] + mid, ai[i]);
ll acc = 0;
for (int i = 1; i <= n; i++)
acc += xi[i] - ai[i], pre[i] = pre[i - 1] + ai[i];
if (acc > m)
return 0;
for (int i = 1, ptr = 1; i <= n; i++)
{
while (ptr < i && ai[ptr] <= 1LL * (i - ptr) * mid)
ptr++;
prefix[i] = pre[i - 1] - pre[ptr - 1] - 1LL * (i - ptr) * (i - ptr + 1) / 2 * mid;
}
for (int i = n, ptr = n; i >= 1; i--)
{
while (ptr > i && ai[ptr] <= 1LL * (ptr - i) * mid)
ptr--;
suffix[i] = pre[ptr] - pre[i] - 1LL * (ptr - i) * (ptr - i + 1) / 2 * mid;
}
for (int i = 1; i <= n; i++)
if (prefix[i] + suffix[i] + acc + ai[i] <= m)
return i;
return 0;
}
int main()
{
scanf("%d%lld", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%lld", &xi[i]);
int l = 0, r = 1e9, res = 0;
while (l <= r)
{
int mid = (l + r) >> 1;
if (check(mid))
r = mid - 1, res = mid;
else
l = mid + 1;
}
printf("%d %d\n", check(res), res);
return 0;
}
「POI2014」PAN-Solar Panels
题目大概就是要求你在二维平面上，找到一个最大的 \(d\) 使得刚好 \(x = kd, y = kd\) 在这个矩形内有交点。发现有交点的条件是：
\[ \lfloor \frac{smax}{d} \rfloor – \lfloor \frac{smin – 1}{d} \rfloor > 0 \\ \lfloor \frac{wmax}{d} \rfloor – \lfloor \frac{wmin – 1}{d} \rfloor > 0 \]
那可以直接搞搞整除分块，每次取右端点做答案即可。
// P3579.cpp
#include <bits/stdc++.h>
using namespace std;
int T, smin, smax, wmin, wmax;
inline char nc()
{
static char buf[1000000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
int read()
{
int x = 0, f = 1;
char ch = nc();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = nc();
}
while (isdigit(ch))
x = (x << 3) + (x << 1) + ch - '0', ch = nc();
return x * f;
}
int main()
{
scanf("%d", &T);
while (T--)
{
smin = read(), smax = read(), wmin = read(), wmax = read();
smin--, wmin--;
int ans = 0;
for (int d = 1, gx; d <= min(smax, wmax); d = gx + 1)
{
gx = min({smax / (smax / d), wmax / (wmax / d)});
if (int(smin / d) != 0)
gx = min(gx, smin / (smin / d));
if (int(wmin / d) != 0)
gx = min(gx, wmin / (wmin / d));
if ((smax / d) - (smin / d) > 0 && (wmax / d) - (wmin / d) > 0)
ans = gx;
}
printf("%d\n", ans);
}
return 0;
}
「POI2015」PUS
经典的线段树优化建图，暴力拆成 \(k + 1\) 个区间之后跑 DAG DP 即可。
// P3588.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 6e5 + 200, MAX_E = 8e6 + 200;
int n, s, m, dp[MAX_N], head[MAX_N], current, sidx[MAX_N], ptot, deg[MAX_N], topoidx[MAX_N], topotot;
bool isFixed[MAX_N];
struct edge
{
int to, nxt, weight;
} edges[MAX_E];
void addpath(int src, int dst, int weight)
{
edges[current].to = dst, edges[current].nxt = head[src];
edges[current].weight = weight, head[src] = current++, deg[dst]++;
}
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)
void build(int l, int r, int p)
{
ptot = max(ptot, p);
if (l == r)
return (void)(sidx[l] = p);
addpath(p, lson, 0), addpath(p, rson, 0);
build(l, mid, lson), build(mid + 1, r, rson);
}
void update(int ql, int qr, int l, int r, int p, int src)
{
if (ql > qr)
return;
if (ql <= l && r <= qr)
return (void)(addpath(src, p, 0));
if (ql <= mid)
update(ql, qr, l, mid, lson, src);
if (mid < qr)
update(ql, qr, mid + 1, r, rson, src);
}
#undef mid
#undef rson
#undef lson
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d%d", &n, &s, &m), build(1, n, 1);
for (int i = 1; i <= n; i++)
dp[sidx[i]] = 1;
for (int i = 1, p, d; i <= s; i++)
scanf("%d%d", &p, &d), dp[sidx[p]] = d, isFixed[sidx[p]] = true;
while (m--)
{
int l, r, k, cpt, last = l - 1;
scanf("%d%d%d", &l, &r, &k), cpt = ++ptot, last = l - 1;
for (int i = 1, pt; i <= k; i++)
scanf("%d", &pt), addpath(sidx[pt], cpt, 1), update(last + 1, pt - 1, 1, n, 1, cpt), last = pt;
update(last + 1, r, 1, n, 1, cpt);
}
queue<int> q;
for (int i = 1; i <= ptot; i++)
if (deg[i] == 0)
q.push(i);
while (!q.empty())
{
int u = q.front();
q.pop(), topoidx[++topotot] = u;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (--deg[edges[i].to] == 0)
q.push(edges[i].to);
}
for (int i = 1; i <= ptot; i++)
if (deg[i] != 0)
puts("NIE"), exit(0);
for (int id = ptot; id >= 1; id--)
{
int u = topoidx[id], max_val = 1;
for (int i = head[u]; i != -1; i = edges[i].nxt)
max_val = max(max_val, dp[edges[i].to] + edges[i].weight);
if (isFixed[u] && max_val > dp[u])
puts("NIE"), exit(0);
else if (!isFixed[u])
dp[u] = max_val;
}
for (int i = 1; i <= n; i++)
if (dp[sidx[i]] > 1e9 || dp[sidx[i]] < 1)
puts("NIE"), exit(0);
puts("TAK");
for (int i = 1; i <= n; i++)
printf("%d%c", dp[sidx[i]], " \n"[i == n]);
return 0;
}