穷酸博主没有bz权限号， 也不会去$poi$官网， 在某咕刷的$poi$，按照某咕的难度排序刷， poi~
$Luogu3572 PTA-Little Bird$
单调队列， 队列内按照 步数为第一关键字递增， 高度为第二关键字递减
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
#define R register
#define N 1000005
using namespace std; int n, k, Q;
int d[N], f[N], q[N]; inline int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < '';c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} int main()
{
n = rd;
for (R int i = ; i <= n; ++i) d[i] = rd;
Q = rd;
for (; Q; Q--) {
k = rd;
int l = , r = ;
q[l] = ;
for (R int i = ; i <= n; ++i) {
while (l <= r && q[l] < i - k) l++;
f[i] = f[q[l]] + (d[q[l]] <= d[i] ? : );
while (l <= r && (f[q[r]] > f[i] || (f[q[r]] == f[i] && d[q[r]] <= d[i]))) r--;
q[++r] = i;
}
printf("%d\n", f[n]);
}
}
$Luogu3566KLO-Bricks$
贪心， 优先用右端点$ed$的颜色的来填， 如果$ed$用光了或者上一个颜色是$ed$， 则选取剩下来个数最多的去填
个数最多可以用线段树维护
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
#define N 1000005
using namespace std;
typedef pair<int, int > P; int n, m, cnt[N], st, ed, a[N]; int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} void up(int &A, int B) {
if (A < B) A = B;
} P cmax(P A, P B) {
return A > B ? A : B;
} namespace SegT {
#define lson nd << 1
#define rson nd << 1 | 1
#define mid ((l + r) >> 1)
P Max[N << ]; void pushup(int nd) {
Max[nd] = cmax(Max[lson], Max[rson]);
} void build(int l, int r, int nd) {
if (l == r) {
Max[nd] = P(cnt[l], l); return;
}
build(l, mid, lson); build(mid + , r, rson);
pushup(nd);
} void modify(int c, int l, int r, int nd) {
if (l == r) {
Max[nd].first-- ; return;
}
if (c <= mid) modify(c, l, mid, lson);
else modify(c, mid + , r, rson);
pushup(nd);
} P query(int L, int R, int l, int r, int nd) {
if (L > R) return P(, );
if (L <= l && r <= R) return Max[nd];
P tmp = P(, );
if (mid >= L)
tmp = cmax(tmp, query(L, R, l, mid, lson));
if (mid < R)
tmp = cmax(tmp, query(L, R, mid + , r, rson));
return tmp;
}
}using namespace SegT; int main()
{
m = rd; st = rd; ed = rd;
for (int i = ; i <= m; ++i)
n += (cnt[i] = rd);
cnt[st] --; cnt[ed] --;
a[] = st; a[n] = ed;
build(, m, );
for (int i = ; i < n; ++i) {
if (cnt[ed] && a[i - ] != ed) {
a[i] = ed;
cnt[a[i]]--;
modify(a[i], , m, );
} else {
P tmp = query(, a[i - ] - , , m, );
tmp = cmax(tmp, query(a[i - ] + , m, , m, ));
if (tmp.first == ) return printf(""), ;
a[i] = tmp.second;
cnt[a[i]]--;
modify(a[i], , m, );
}
}
if (a[n - ] == a[n])
return printf(""), ;
printf("%d", a[]);
for (int i = ; i <= n; ++i)
printf(" %d", a[i]);
return ;
}
$Luogu3575DOO-Around the world$
双指针扫一遍， 找到从 $i$ 往前最多能飞多少格。 并记录步数和起始位置。 当起始位置和当前位置相距不少于N， 则更新答案。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
#define N 2000005
#define R register
using namespace std; int n, m, f[N], head[N], maxn, a[N]; int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} void cmax(int &A, int B) {
if (A < B) A = B;
} void cmin(int &A, int B) {
if (A > B) A = B;
} void work(int d) {
if (d < maxn) {
puts("NIE"); return;
}
int ans = n;
for (R int i = n + , j = ; i <= * n; ++i) {
while (a[i] - a[j] > d) j++;
f[i] = f[j] + , head[i] = head[j];
if (i - head[i] >= n) cmin(ans, f[i]);
}
printf("%d\n", ans);
} int main()
{
n = rd; m = rd;
for (R int i = ; i <= n; ++i)
a[i] = a[i + n] = rd,
cmax(maxn, a[i]),
head[i] = i;
for (R int i = ; i <= * n; ++i)
a[i] += a[i - ];
for (R int i = ; i <= m; ++i) work(rd);
}
$Luogu3565Hotels$
枚举根节点为中心， 在根的不同儿子的子树中找$3$个相同深度的点的方案数。 时间复杂度$O(N^2)$，
不过好像用长链剖分可以做到$O(N)$。。。老年选手也懒得去学了唔
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
#define N 5005
#define ll long long
#define R register
using namespace std; int head[N], tot, dep[N], g[N], n;
ll ans, f[N][]; struct edge {
int nxt, to;
}e[N << ]; inline int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} void add(int u, int v) {
e[++tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
} void cmax(int &A, int B) {
if (A < B) A = B;
} void dfs(int u, int fa) {
g[dep[u]] ++;
for (R int i = head[u]; i; i = e[i].nxt) {
int nt = e[i].to;
if (nt == fa) continue;
dep[nt] = dep[u] + ;
dfs(nt, u);
}
} int main()
{
n = rd;
for (int i = ; i < n; ++i) {
int u = rd, v = rd;
add(u, v); add(v, u);
}
for (R int rt = ; rt <= n; ++rt) {
dep[rt] = ;
memset(f, , sizeof(f));
for (R int i = head[rt]; i; i = e[i].nxt) {
memset(g, , sizeof(g));
dep[e[i].to] = ;
dfs(e[i].to, rt);
for (R int j = ; j; --j)
for (R int k = ; k <= n; ++k)
f[k][j] += f[k][j - ] * g[k];
for (R int k = ; k <= n; ++k)
f[k][] += g[k];
}
for (R int i = ; i <= n; ++i)
ans += f[i][];
}
printf("%lld\n", ans);
}
$Luogu3580Freight$
列车肯定是 分批， 一批过去再回来， 才轮到下一批。
然后就开始$DP$, 设$F[i]$ 为前 $i$ 辆列车回来的最早时间， 同时为了防止不同列车同时出发， 令$t[i] = max(t[i], t[i-1] + 1)$
有状态转移方程：
$f[i] \ = \ min( \ max(f[j] + i -j-1, t[i])+2 \times S + i - j - 1)$
移项得：
$f[i] \ = \ 2 \times S + 2 \times i -1 \ + \ min( \ max(f[j] - j - 1, t[i] - i)-j)$
由于 $f[j] - j-1$ 和 $t[i] - i$ 是不下降的， 所以用单调队列找到第一个分界点， 并且队列 除第一位 按照 $f[j]-2 \times j - 1$ 递增
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
#define N 1000005
#define R register
#define ll long long
using namespace std; int n, t[N], q[N], S;
ll f[N]; inline int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} inline int cmax(int A, int B) {
return A > B ? A : B;
} template<typename T>
inline void down(T &A, T B) {
if (A > B) A = B;
} int main()
{
n = rd; S = rd;
for (R int i = ; i <= n; ++i)
t[i] = cmax(rd, t[i - ] + );
int l = , r = ;
for (R int i = ; i <= n; ++i) {
while (l < r && f[q[l + ]] - q[l + ] - <= t[i] - i) l++;
f[i] = 1LL * t[i] + i - q[l] + * S - ;
if (l < r) down(f[i], f[q[l + ]] - * q[l + ] - + * S + * i - );
while (l < r && f[q[r]] - * q[r] >= f[i] - * i) r--;
q[++r] = i;
}
printf("%lld\n", f[n]);
}
$Luogu3574FarmCraft$
贪心排序+树形DP
我们可以递归求出每颗子树所需要的最大时间，
子节点到父节点的转移方程：
$f[u] \ = \ max(2 \times \sum\limits_{k=1}^{i-1}sz[k] + f[i]+1)$ ， 父节点 $f[u]$ 初始为 $a[u]$
根据贪心， 把子树按照$2 \times sz[i]-f[i]$进行排序（证明挺简单的， 邻项交换 就可以证出）
由于根节点是要最后安装电脑的， $f[1] = max(f[1], a[1] + 2 \times (sz[1] - 1) )$
最后输出$f[1]$， 复杂度$O(NlogN)$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define N 500005
#define rd read()
using namespace std; int head[N], tot, n, f[N], sz[N], a[N];
vector<int> v[N]; struct edge {
int nxt, to;
}e[N << ]; inline int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} void add(int fr, int to) {
e[++tot].to = to;
e[tot].nxt = head[fr];
head[fr] = tot;
} int cmp(int A, int B) {
return * sz[A] - f[A] < * sz[B] - f[B];
} void dfs(int u, int fa) {
for (int i = head[u]; i; i = e[i].nxt) {
int nt = e[i].to;
if (nt == fa) continue;
dfs(nt, u);
v[u].push_back(nt);
}
} void cmax(int &A, int B) {
if (A < B) A = B;
} void dp(int u) {
sz[u] = ;
f[u] = a[u];
for (int i = , up = v[u].size(); i < up; ++i) {
int nt = v[u][i];
dp(nt);
}
sort(v[u].begin(), v[u].end(), cmp);
for (int i = , up = v[u].size(); i < up; ++i) {
int nt = v[u][i];
cmax(f[u], * sz[u] + f[nt] - );
sz[u] += sz[nt];
}
} int main()
{
n = rd;
for (int i = ; i <= n; ++i) a[i] = rd;
for (int i = ; i < n; ++i) {
int fr = rd, to = rd;
add(fr, to); add(to, fr);
}
dfs(, ); dp();
cmax(f[], * (n - ) + a[]);
printf("%d\n", f[]);
}
$Luogu3570Criminals$
挺早前就做了的题。。。看不惯当时的毒瘤代码， 空格有时有， 有时没有。
就是一个链表乱搞， 就不贴代码丢脸了（捂脸）
$Luogu3567Couriers$
主席树模板题
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
using namespace std; const int N = 1e5; int lson[N * ], rson[N * ], sum[N * ];
int a[N * ], n, m, root[N * ], b[N * ], tot, cnt; int read() {
int X = , p = ; char c = getchar();
for(; c > '' || c < ''; c = getchar()) if(c == '-') p = -;
for(; c >= '' && c <= ''; c = getchar()) X = X * + c - '';
return X * p;
} int fd(int x) {
return lower_bound(b + , b + + tot, x) - b;
} void build0(int &o, int l, int r) {
o = ++cnt;
if(l == r) return;
int mid = (l + r) >> ;
build0(lson[o], l, mid);
build0(rson[o], mid + , r);
} void build(int last, int &o, int pos, int l, int r) {
o = ++cnt;
sum[o] = sum[last] + ;
lson[o] = lson[last];
rson[o] = rson[last];
if(l == r)
return;
int mid = (l + r) >> ;
if(pos <= mid)
build(lson[last], lson[o], pos, l, mid);
else
build(rson[last], rson[o], pos, mid + , r);
} int query(int last, int now, int k, int l, int r) {
if(l == r)
return ( * (sum[now] - sum[last]) > k) ? l : ;
int mid = (l + r) >> ;
if( * (sum[lson[now]] - sum[lson[last]]) > k)
return query(lson[last], lson[now], k, l, mid);
else
return query(rson[last], rson[now], k, mid + , r);
} int main()
{
n = rd; m = rd;
for(int i = ; i <= n; ++i)
b[i] = a[i] = rd;
sort(b + , b + + n);
tot = unique(b + , b + + n) - b - ;
for(int i = ; i <= n; ++i)
build(root[i - ], root[i], fd(a[i]), , tot);
for(int i = ; i <= m; ++i) {
int l = rd, r = rd, ans;
ans = query(root[l - ], root[r], r - l + , , tot);
printf("%d\n", b[ans]);
}
}
$Luogu3572Ant colony$
倍增LCA+二分查找
$f[i][j]$ 表示 $i$ 的 $2^j$ 级祖先， $g[i][j]$ 表示从i 到 $f[i][j]$ 要分支成几份。 另外$g[i][j]$ 可能非常大， 最高约是 $3$的几万次方， 所以如果$g[i][j] \times k > a[m]$，直接赋为$-1$
然后就可以倍增求要几个分支，设分支数为 $x$， 则最后被吃掉的蚂蚁数就是 数组a中 $k \times x<= <=(k + 1) \times -1$的个数， 二分查找即可。
时间复杂度为$O(NlogN)$， (做POI习惯性卡常数了
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
#define N 1000005
#define ll long long
#define R register
using namespace std; const int base = ; int n, m, k, tot, st, ed;
int head[N], a[N], f[N][base], d[N], leaf[N], cnt, dep[N];
ll g[N][base], ans;
bool in[N]; struct edge {
int nxt, to;
}e[N << ]; inline int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} inline void add(int u, int v) {
e[++tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
} void dfs(int u, bool flag) {
in[u] = flag;
for (R int i = head[u]; i; i = e[i].nxt) {
R int nt = e[i].to;
if (nt == f[u][]) continue;
f[nt][] = u;
g[nt][] = (d[nt] - ) ? d[nt] - : ;
dep[nt] = dep[u] + ;
if ((u == e[].to && nt == e[].to) || (nt == e[].to && u == e[].to))
dfs(nt, true);
else dfs(nt, flag);
}
} inline int cal(int x) {
int maxn = upper_bound(a + , a + + m, 1LL * (k + ) * x - ) - a,
minn = lower_bound(a + , a + + m, k * x) - a;
return maxn - minn;
} int LCA(R int x, R int y) {
ll res = ;
if (dep[x] < dep[y]) swap(x, y);
for (R int j = base - ; ~j; --j)
if (dep[f[x][j]] >= dep[y]) {
res *= g[x][j];
if (res * k > a[m] || res < ) return -;
x = f[x][j];
}
if (x == y) {
res *= g[x][];
if (res * k > a[m] || res < ) return -;
else return res;
}
for (R int j = base - ; ~j; --j)
if (f[x][j] != f[y][j]) {
res *= g[x][j];
res *= g[y][j];
if (res * k > a[m] || res < ) return -;
x = f[x][j];
y = f[y][j];
}
res *= g[x][] * g[y][];
if (res * k > a[m] || res < ) return -;
return res;
} void work(int x) {
R int tmp = LCA(x, in[x] ? ed : st);
if (tmp != -) ans += 1LL * cal(tmp) * k;
} int main()
{
n = rd; m = rd; k = rd;
for (R int i = ; i <= m; ++i)
a[i] = rd;
for (R int i = ; i < n; ++i) {
int u = rd, v = rd;
add(u, v); add(v, u);
d[u] ++; d[v] ++;
}
dep[] = ;
dfs(, false);
g[][] = (d[] - ) ? d[] - : ;
sort(a + , a + + m);
if (dep[e[].to] > dep[e[].to]) st = e[].to, ed = e[].to;
else st = e[].to, ed = e[].to;
for (R int i = ; i <= n; ++i)
if (d[i] == ) leaf[++cnt] = i;
for (R int j = ; j < base; ++j)
for (R int i = ; i <= n; ++i) {
f[i][j] = f[f[i][j - ]][j - ],
g[i][j] = g[i][j - ] * g[f[i][j - ]][j - ];
if (g[i][j] * k > a[m]) g[i][j] = -;
else if (g[i][j] < ) g[i][j] = -;
}
for (R int i = ; i <= cnt; ++i)
work(leaf[i]);
printf("%lld\n", ans);
}
$Luogu3564Salad Bar$
树状数组
若$s[i]=='j'$， 则赋为 $-1$， 若为$'p'$， 则赋为 $1$。 定义 $sum$为前缀和。
则一个字符串 $[j,i]$ 从前往后 的$1$的个数 不少于 $-1$的个数， 则满足 $sum[j-1] <= sum[k]$ $(j<=k<=i)$ 恒成立。
根据这一点， 若要知道最多往后到哪里， 只需往后找到第一个 $i$，$sum[i]>sum[j]$。 单调栈$O(N)$即可维护。 往前同理可得。
我们设从 $i$往后最多到 $R[i]$， 往前最多到 $L[i]$。 一个字符串 $[j,i]$ 满足条件 必须使 $R[j]>=i \& \& L[i]<=j$
我们只需要先把 $i$ 按照 $R[i]$从小往大排序，用树状数组维护即可。
时间复杂度$O(NlogN)$
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rg register
#define rd read()
#define N 1000005
using namespace std; int a[N], b[N], n, pre[N], nxt[N];
int st[N], tp, Max[N], ans;
char s[N]; struct node {
int id, L, R;
bool operator < (const node &A) const {
return R < A.R;
}
}t[N]; int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} void init() {
for (rg int i = ; i <= n + ; ++i) {
int pr = ;
while (tp) {
if (b[st[tp]] >= b[i]) tp--;
else {
pr = st[tp]; break;
}
}
pre[i] = pr;
st[++tp] = i;
}
tp = ;
for (rg int i = n; ~i; --i) {
int nt = n + ;
while (tp) {
if (a[st[tp]] >= a[i]) tp--;
else {
nt = st[tp]; break;
}
}
nxt[i] = nt;
st[++tp] = i;
}
} inline int cmin(int A, int B) {
return A > B ? B : A;
} inline int cmax(int A, int B) {
return A > B ? A : B;
} inline void up(int &A, int B) {
if (A < B) A = B;
} int lowbit(int x) {
return x & -x;
} void add(int x, int val) {
for (; x <= n; x += lowbit(x))
up(Max[x], val);
} int query(int x) {
int res = ;
for (; x; x -= lowbit(x))
up(res, Max[x]);
return res;
} int main()
{
n = rd;
scanf("%s", s + );
for (rg int i = ; i <= n; ++i)
a[i] = a[i - ] + (s[i] == 'p' ? : -);
for (rg int i = n; i; --i)
b[i] = b[i + ] + (s[i] == 'p' ? : -);
init();
for (rg int i = ; i <= n; ++i)
pre[i] = pre[i + ] + ;
for (rg int i = n; i; --i)
nxt[i] = nxt[i - ] - ;
for (rg int i = ; i <= n; ++i) {
t[i].id = i;
t[i].L = pre[i];
t[i].R = nxt[i];
}
sort(t + , t + + n);
for (rg int i = , j = ; i <= n; ++i) {
while (j <= n && j <= t[i].R) add(pre[j], j), j++;
int res = query(t[i].id);
up(ans, res - t[i].id + );
}
printf("%d\n", ans);
}
$Luogu3579Solar Panels$
整除分块枚举。。。
发现Latex不支持下取整， 然后用markdown打的一篇博客→神奇的传送门
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
#define R register
using namespace std; inline int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} inline void cmax(int &A, int B) {
if (A < B) A = B;
} inline int cmin(int A, int B) {
return A > B ? B : A;
} void work() {
int ans = ;
int a = rd - , b = rd, c = rd - , d = rd;
for (R int i = , j = , up = cmin(b, d); i <= up; i = j + ) {
j = cmin(b / (b / i), d / (d / i));
if (b / j > a / j && d / j > c / j) cmax(ans, j);
}
printf("%d\n", ans);
} int main()
{
int n = rd;
for (; n; --n) work();
}
$Luogu3569Cards$
单点改， 线段树维护区间信息
对于每段区间， 我们分别求出如果第一个位置 取大的数 和 取小的数是否可行， 如果可行， 则最后一个位置尽量小的数是多少。
这种区间信息可以用线段树合并。 最后的答案在区间$[1,N]$。
复杂度$O(MlogN)$，数据比较卡常（我当然是吸了氧气才过去的）
我swap自己写的函数 挂了咕咕咕， 两个地址相同的时候就会都变成$0$， 算是一个教训QAQ
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
#define R register
using namespace std; const int N = 2e5 + ; int n, m;
int a[N], b[N]; inline int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} inline void sw(int &A, int &B) {
int tmp = A;
A = B; B = tmp;
} namespace SegT {
#define lson x << 1
#define rson x << 1 | 1
#define mid ((l + r) >> 1)
int ok[N << ][], rmin[N << ][], lval[N << ][]; inline void up(int x) {
ok[x][] = ok[x][] = ;
lval[x][] = lval[lson][];
lval[x][] = lval[lson][];
if (!ok[lson][] || !ok[rson][])
return;
if (lval[rson][] >= rmin[lson][]) {
ok[x][] = ; rmin[x][] = rmin[rson][];
}
else if (lval[rson][] >= rmin[lson][] && ok[rson][]) {
ok[x][] = ; rmin[x][] = rmin[rson][];
}
if (!ok[lson][]) return;
if (lval[rson][] >= rmin[lson][]) {
ok[x][] = ; rmin[x][] = rmin[rson][];
}
else if (lval[rson][] >= rmin[lson][] && ok[rson][]) {
ok[x][] = ; rmin[x][] = rmin[rson][];
}
} void build(int l, int r, int x) {
if (l == r) {
ok[x][] = ok[x][] = ;
rmin[x][] = lval[x][] = a[l];
rmin[x][] = lval[x][] = b[l];
return;
}
build(l, mid, lson);
build(mid + , r, rson);
up(x);
} void modify(int c, int val1, int val2, int l, int r, int x) {
if (l == r) {
lval[x][] = rmin[x][] = val1;
lval[x][] = rmin[x][] = val2;
return;
}
if (c <= mid) modify(c, val1, val2, l, mid, lson);
else modify(c, val1, val2, mid + , r, rson);
up(x);
}
}using namespace SegT; int main()
{
n = rd;
for (R int i = ; i <= n; ++i) {
a[i] = rd; b[i] = rd;
if (a[i] > b[i]) sw(a[i], b[i]);
}
build(, n, );
m = rd;
for (R int i = ; i <= m; ++i) {
R int x = rd, y = rd;
modify(x, a[y], b[y], , n, );
modify(y, a[x], b[x], , n, );
if (ok[][]) puts("TAK");
else puts("NIE");
sw(a[x], a[y]); sw(b[x], b[y]);
}
}
$Luogu3573Rally$
不看题解是不可能的， 这辈子都不可能的。。。
真的没有想到这种神仙做法QAQ。 cls神犇的题解 Orz
用可重集代替一下堆？
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<queue>
#define rd read()
#define rg register
using namespace std; const int N = 5e5 + ; int n, m, f[N][], st, ed, d[N], ans1, ans2 = N + ; vector<int> to[N], fr[N];
multiset<int> S;
queue<int> q; inline int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} inline void getmax(int &A, int B) {
if (A < B) A = B;
} int dp0(int u) {
if (u == ed) return ;
if (f[u][]) return f[u][];
for (rg int i = , up = to[u].size(); i < up; ++i)
getmax(f[u][], dp0(to[u][i]) + );
return f[u][];
} int dp1(int u) {
if (u == st) return ;
if (f[u][]) return f[u][];
for (rg int i = , up = fr[u].size(); i < up; ++i)
getmax(f[u][], dp1(fr[u][i]) + );
return f[u][];
} void del(int u) {
for (rg int i = , up = fr[u].size(); i < up; ++i)
S.erase(S.find(f[u][] + f[fr[u][i]][] - ));
} void Topsort() {
q.push(st);
for (; !q.empty();) {
int u = q.front(); q.pop();
if (u != st && u != ed) {
del(u); int tmp = *(--S.end());
if (tmp < ans2) ans2 = tmp, ans1 = u;
}
for (rg int i = , up = to[u].size(); i < up; ++i) {
int nt = to[u][i];
S.insert(f[u][] + f[nt][] - );
if (!(--d[nt])) q.push(nt);
}
}
} int main()
{
n = rd; m = rd;
st = ; ed = n + ;
for (rg int i = ; i <= m; ++i) {
int u = rd, v = rd;
to[u].push_back(v);
fr[v].push_back(u);
d[v]++;
}
for (rg int i = ; i <= n; ++i) {
to[st].push_back(i);
to[i].push_back(ed);
fr[ed].push_back(i);
fr[i].push_back(st);
d[i]++; d[ed]++;
}
dp0(st); dp1(ed);
Topsort();
printf("%d %d\n", ans1, ans2);
}