没学线性基输麻了，
Rank
A. 欧几里得的噩梦
线性基，输麻了。
B. 清扫
思维题，差点签了。（感觉其实不是很难啊，没有紫的水平）
一个叶子结点和另一个叶子结点的最短路径一定经过它的父节点。根据这一性质可以让整棵树的合法性拆分成每个节点的合法性。
考虑如何判断每个节点的合法性。设其子节点的石头数之和为 \(sum\)，最多的一堆数量为 \(maxn\)，该节点数量为 \(c\)，可知 \(c\) 的下界为 \(max\left(maxn,\lceil{\frac{sum}{2}}\rceil\right)\)，上界为 \(sum\)。考虑递归时要将 \(c\) 赋值为所需要选择的石子数，这个值其实就是多余的石子数，即 \(c-(sum-c)\)，最后要判断根节点的值是否为 0 才对。
算法有个细节在于根节点不能为叶子，所以对于没有叶子的情况（\(n=2\)）特判一下就好。复杂度 \(\mathcal{O(n)}\)。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch = getchar();lx x = 0 , f = 1;
for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n, rot;
int rd[N];
ll a[N];
int hh[N], to[N << 1], ne[N << 1], cnt;
namespace Wisadel
{
void Wadd(int u, int v)
{
to[++cnt] = v;
ne[cnt] = hh[u];
hh[u] = cnt;
}
void Wdfs(int u, int fa)
{
ll sum = 0, maxn = -1e9; int num = 0;
for(int i = hh[u]; i != -1; i = ne[i])
{
int v = to[i];
if(v == fa) continue;
Wdfs(v, u);
maxn = max(maxn, a[v]), sum += a[v], num++;
}
if(!num) return;
ll ned = max(maxn, sum / 2 + (sum % 2));
if(a[u] < ned || a[u] > sum)
{
printf("NO\n");
exit(0);
}
a[u] = 2 * a[u] - sum;
}
short main()
{
freopen("tree.in", "r", stdin) , freopen("tree.out", "w", stdout);
n = qr;
memset(hh, -1, sizeof hh);
fo(i, 1, n) a[i] = qr;
fo(i, 1, n - 1)
{
int a = qr, b = qr;
rd[a]++, rd[b]++;
Wadd(a, b), Wadd(b, a);
}
if(n == 2)
{
if(a[1] != a[2]) printf("NO\n");
else printf("YES\n");
return Ratio;
}
fo(i, 1, n) if(rd[i] >1){rot = i; break;}
Wdfs(rot, 0);
if(a[rot] == 0) printf("YES\n");
else printf("NO\n");
return Ratio;
}
}
int main(){return Wisadel::main();}
C. 购物
签，为什么放 T3。
每个价格 \(a\) 所能对应的 \(k\) 范围为 \(\left[\lceil{\frac{a}{2}}\rceil,a\right]\)，考虑向集合中加入一个数 \(b(b\gt a)\)，那么所新增的 \(k\) 范围是 \(\left[\lceil{\frac{b}{2}}\rceil,a+b\right]\)，只需要考虑与原来是否有交集即可，若有则贡献为 \(b\)，否则贡献为 \(a+b-\lceil{\frac{b}{2}}\rceil\)。无序的数组进行添加操作会很麻烦，所以要先排序，只用维护到当前的 \(k\) 区间最右边界，然后每次算一下左边界即可。瓶颈复杂度是排序的 \(\mathcal{O(n\log n)}\)。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch = getchar();lx x = 0 , f = 1;
for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n;
ll a[N], ans;
namespace Wisadel
{
short main()
{
freopen("buy.in", "r", stdin) , freopen("buy.out", "w", stdout);
n = qr;
fo(i, 1, n) a[i] = qr;
sort(a + 1, a + 1 + n);
ll l = 0, r = 0;
fo(i, 1, n)
{
l = a[i] / 2 + (a[i] % 2);
if(l > r) ans += r - l + 1 + a[i];
else ans += a[i];
r += a[i];
}
printf("%lld\n", ans);
return Ratio;
}
}
int main(){return Wisadel::main();}
D. ants
回滚莫队板子题，签，为什么放 T4。
一眼数据结构，再一眼莫队，再再一眼回滚莫队，然后打就完了，基本是纯板子，不会的来这学。
维护每个蚂蚁编号为左/右边界时的最大长度，发现不好进行删除操作，于是回滚。增加时赋值 \(llen_{a_i}\leftarrow llen_{a_i-1}+1\)，\(rlen_{a_i}\leftarrow rlen_{a_i+1}+1\)，此时最大值 \(maxn = max\left(llen_{a_i}+rlen_{a_i}-1\right)\)，然后更新该块的左右边界的最大长度即可。开栈存回退信息即可。复杂度 \(\mathcal{O(n\sqrt{m})}\)。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch = getchar();lx x = 0 , f = 1;
for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n, m, res = 0, zc = 0;
int a[N], bl[N], ed[N], ans[N], fx[N];
int llen[N], rlen[N], lcnt, rcnt;
pii lzc[N], rzc[N];
bool yz[N];
struct rmm
{
int l, r, id;
} q[N];
bool cmp(rmm a, rmm b)
{
if(bl[a.l] == bl[b.l]) return a.r < b.r;
return bl[a.l] < bl[b.l];
}
namespace Wisadel
{
int Wfind(int x)
{
if(x == fx[x]) return x;
return fx[x] = Wfind(fx[x]);
}
void Wadd(int x, bool fla)
{
llen[a[x]] = llen[a[x] - 1] + 1;
rlen[a[x]] = rlen[a[x] + 1] + 1;
int zc = llen[a[x]] + rlen[a[x]] - 1;
res = max(res, zc);
if(fla)
{
lzc[++lcnt] = {a[x] + rlen[a[x]] - 1, llen[a[x] + rlen[a[x]] - 1]};
rzc[++rcnt] = {a[x] - llen[a[x]] + 1, rlen[a[x] - llen[a[x]] + 1]};
}
llen[a[x] + rlen[a[x]] - 1] = rlen[a[x] - llen[a[x]] + 1] = zc;
}
void Wback(int l, int r)
{
res = zc;
fu(i, lcnt, 1) llen[lzc[i].fi] = lzc[i].se;
fu(i, rcnt, 1) rlen[rzc[i].fi] = rzc[i].se;
fo(i, l, r) llen[a[i]] = rlen[a[i]] = 0;
}
short main()
{
freopen("ants.in", "r", stdin) , freopen("ants.out", "w", stdout);
n = qr, m = qr;
int sq = sqrt(n);
fo(i, 1, sq) ed[i] = (n / sq) * i;
ed[sq] = n;
fo(i, 1, sq) fo(j, ed[i - 1] + 1, ed[i]) bl[j] = i;
fo(i, 1, n) a[i] = qr, fx[i] = i;
fo(i, 1, m) q[i].l = qr, q[i].r = qr, q[i].id = i;
sort(q + 1, q + 1 + m, cmp);
int l, r = 0;
fo(i, 1, m)
{
if(bl[q[i].l] != bl[q[i - 1].l])
{
res = 0;
fo(i, 1, n) llen[a[i]] = rlen[a[i]] = 0;
r = ed[bl[q[i].l]];
}
while(r < q[i].r) Wadd(++r, 0);
zc = res;
lcnt = rcnt = 0;
l = min(q[i].r, ed[bl[q[i].l]]);
fo(j, q[i].l, l) Wadd(j, 1);
ans[q[i].id] = res;
Wback(q[i].l, l);
}
fo(i, 1, m) printf("%d\n", ans[i]);
return Ratio;
}
}
int main(){return Wisadel::main();}
末
开题顺序立大功。由 T1 给出的：
所以先去做 T3 了（？），整体顺序 \(C\rightarrow D\rightarrow B \rightarrow A\)。
离 AK 最近的一场，不过现在也该学线性基了，而且 T2 漏 Corner Case 挺不应该的，还有进步空间吧。
剩下的改完 T1 再说。
没完结不撒花。
因为一会还会更新，所以现在的无意义评论会被删。