T1
洛谷 P3436 PRO-Professor Szu
首先缩点。然后从所有没有入度的强连通分量开始 dfs，进行 dp，数一下每个点到终点有多少路径。要注意的是当且仅当一个点能够到达终点时才能够用来更新其他点的 dp 值。
代码
#include <iostream>
#define int long long
using namespace std;
int n, m;
struct Graph {
int head[1000005], nxt[1000005], to[1000005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
} g1, g2;
int clr[1000005], scnt, ncnt;
int dfn[1000005], low[1000005], stk[1000005], sz;
bool vis[1000005];
int ssz[1000005];
void tarjan(int x) {
dfn[x] = low[x] = ++ncnt;
stk[++sz] = x;
vis[x] = 1;
for (int i = g1.head[x]; i; i = g1.nxt[i]) {
int v = g1.to[i];
if (!dfn[v]) {
tarjan(v);
low[x] = min(low[x], low[v]);
} else if (vis[v])
low[x] = min(low[x], dfn[v]);
}
if (low[x] == dfn[x]) {
++scnt;
int t;
do {
t = stk[sz--];
vis[t] = 0;
clr[t] = scnt;
++ssz[scnt];
} while (t != x);
}
}
int in[1000005];
bool sl[1000005];
bool lp[1000005];
int dest;
int dp[1000005];
bool tol[1000005];
bool tod[1000005];
void dfs(int x) {
if (vis[x])
return;
vis[x] = 1;
tol[x] |= lp[x];
for (int i = g2.head[x]; i; i = g2.nxt[i]) {
int v = g2.to[i];
dfs(v);
tod[x] |= tod[v];
if (tod[v]) {
dp[x] += dp[v];
tol[x] |= tol[v];
dp[x] = min(dp[x], 36501ll);
}
}
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
g1.add(u, v);
if (u == v)
sl[u] = 1;
}
for (int i = 1; i <= n + 1; i++) {
if (!dfn[i])
tarjan(i);
}
dp[dest = clr[n + 1]] = 1;
tod[dest] = 1;
for (int i = 1; i <= n + 1; i++) {
for (int j = g1.head[i]; j; j = g1.nxt[j]) {
int v = g1.to[j];
if (clr[i] != clr[v])
g2.add(clr[i], clr[v]), in[clr[v]]++;
}
}
for (int i = 1; i <= n + 1; i++) lp[clr[i]] |= sl[i];
for (int i = 1; i <= scnt; i++) lp[i] |= (ssz[i] > 1);
for (int i = 1; i <= scnt; i++) {
if (in[i] == 0)
dfs(i);
}
int ans = -1, acnt = 0;
for (int i = 1; i <= scnt; i++) {
if (dp[i]) {
if (tol[i] || dp[i] > 36500)
dp[i] = 36501;
if (dp[i] > ans)
ans = dp[i], acnt = 0;
if (dp[i] == ans)
acnt += ssz[i] - (dest == i);
}
}
if (ans > 36500)
cout << "zawsze\n";
else
cout << ans << "\n";
cout << acnt << "\n";
for (int i = 1; i <= n; i++) {
if (dp[clr[i]] == ans)
cout << i << " ";
}
cout << "\n";
return 0;
}
T2
洛谷 P3438 ZAB-Frogs
首先二分答案，check 时 bfs，然后就要求每个点是否会被某个圆覆盖。可以发现一个圆在每一列上覆盖的都是一条线段，而且中点在圆心所在横线上。又可以观察到圆心横坐标离当前列越近，则覆盖的线段越长，并且能够覆盖相同圆心纵坐标的圆所覆盖的线段。因此只需要对每列上的每个点求出在纵坐标与之相等且横坐标最近的圆心即可。每次二分一个距离（的平方），就对每个点都算一下它给所在列贡献了哪些被覆盖的点。差分一下即可。有一个细节就是这样做会使得原本距离正好为二分的距离的点被封掉不能走，所以这样求出的答案会比标准答案小 \(1\)。输出时加上即可。
代码
#include <iostream>
#include <queue>
#define int long long
using namespace std;
int sx, sy, tx, ty;
int n, m, X;
bool bad[1005][1005];
int a[1005][1005];
int b[1005][1005];
int d[1005][1005];
int s[1005][1005];
bool vis[1005][1005];
queue<pair<int, int> > q;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int srt[5000005];
bool bfs() {
if (s[sx][sy])
return 0;
if (sx == tx && sy == ty)
return 1;
while (!q.empty()) q.pop();
q.push(make_pair(sx, sy));
s[sx][sy] = 1;
while (!q.empty()) {
pair<int, int> tmp = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int xx = tmp.first + dx[i], yy = tmp.second + dy[i];
if (xx && yy && xx <= n && yy <= m && !s[xx][yy]) {
if (xx == tx && yy == ty)
return 1;
s[xx][yy] = 1;
q.push(make_pair(xx, yy));
}
}
}
return 0;
}
bool chk(int k) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
s[i][j] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (d[i][j] * d[i][j] > k)
continue;
int t = k - d[i][j] * d[i][j];
t = srt[t];
s[max(1ll, i - t)][j]++;
s[min(n + 1, i + t + 1)][j]--;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
s[i][j] += s[i - 1][j];
}
return bfs();
}
signed main() {
cin >> n >> m;
cin >> sx >> sy >> tx >> ty;
cin >> X;
for (int i = 1; i * i <= 5000000; i++) {
for (int j = i * i; j < min(5000000ll, (i + 1ll) * (i + 1)); j++)
srt[j] = i;
}
for (int i = 1; i <= X; i++) {
int x, y;
cin >> x >> y;
bad[x][y] = 1;
}
for (int i = 1; i <= n; i++) {
int lst = -10000;
for (int j = 1; j <= m; j++) {
if (bad[i][j])
lst = j;
a[i][j] = lst;
}
lst = n + 10000;
for (int j = m; j; j--) {
if (bad[i][j])
lst = j;
b[i][j] = lst;
d[i][j] = min(j - a[i][j], b[i][j] - j);
}
}
int l = 0, r = 5000000, mid, ans = -1;
while (l <= r) {
mid = (l + r) >> 1;
if (chk(mid))
l = mid + 1, ans = mid;
else
r = mid - 1;
}
cout << ans + 1 << "\n";
return 0;
}
T3
洛谷 P3439 MAG-Warehouse
首先切比雪夫转曼哈顿，将两维独立开。对每一维，发现答案选的点不在端点上上肯定不优，因为可以往左或往右移使得总答案变小。所以枚举一下所有点，求一个最小总距离。然后由于直接使用 double 算实在是有可能掉精度，所以把算出来的点在最后的时候除以 \(2\)，然后波动 \(\pm 1\)，就可以求出最小的点了。
切比雪夫距离转曼哈顿距离：
将 \((x, y)\) 变成 \((\frac{x + y}{2}, \frac{x - y}{2})\)，这样变换之后两点间的曼哈顿距离就是原本的切比雪夫距离。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#define abs(x) ((x) > 0 ? (x) : (-(x)))
#define int long long
using namespace std;
int n;
int xx[100005], yy[100005], t[100005];
pair<long double, int> x[100005], y[100005];
long double pre1[100005];
int pre2[100005];
int p1, p2;
long double cur;
int ax, ay;
int calc(int px, int py) {
int ret = 0;
for (int i = 1; i <= n; i++) ret += t[i] * max(abs(px - xx[i]), abs(py - yy[i]));
return ret;
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> xx[i] >> yy[i] >> t[i];
x[i].first = (xx[i] + yy[i]);
y[i].first = (xx[i] - yy[i]);
x[i].second = t[i];
y[i].second = t[i];
}
sort(x + 1, x + n + 1);
sort(y + 1, y + n + 1);
cur = 0x7fffffffffffffff;
for (int i = 1; i <= n; i++) pre1[i] = pre1[i - 1] + x[i].first * x[i].second;
for (int i = 1; i <= n; i++) pre2[i] = pre2[i - 1] + x[i].second;
for (int i = 1; i <= n; i++) {
double tmp = x[i].first * pre2[i] - pre1[i] + pre1[n] - pre1[i] - x[i].first * (pre2[n] - pre2[i]);
if (tmp < cur)
cur = tmp, p1 = x[i].first;
}
memset(pre1, 0, sizeof pre1);
memset(pre2, 0, sizeof pre2);
cur = 0x7fffffffffffffff;
for (int i = 1; i <= n; i++) pre1[i] = pre1[i - 1] + y[i].first * y[i].second;
for (int i = 1; i <= n; i++) pre2[i] = pre2[i - 1] + y[i].second;
for (int i = 1; i <= n; i++) {
double tmp = y[i].first * pre2[i] - pre1[i] + pre1[n] - pre1[i] - y[i].first * (pre2[n] - pre2[i]);
if (tmp < cur)
cur = tmp, p2 = y[i].first;
}
int x1 = (p1 + p2) / 2, y1 = (p1 - p2) / 2;
cur = 0x7fffffffffffffff;
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
int tmp;
if ((tmp = calc(x1 + i, y1 + j)) < cur)
cur = tmp, ax = x1 + i, ay = y1 + j;
}
}
cout << ax << " " << ay << "\n";
return 0;
}