GRYZ10.26模拟赛解题报告
期望得分：\(100 + 6 + 12 = 118\)
实际得分：\(30+6+6 = 42\)
老吕找的，USACO 某场铂金组的题。
质量非常不错。
P6142 [USACO20FEB]Delegation P
你考虑二分答案 \(k\)。
对于一个 \(k\) 想一想如何判断他是否合法。
对于一个非根节点的点，假设他下面挂着 \(x\) 条链，我们考虑两两配对，从最小的开始，每次配对时要找刚好能满足长度和 \(\ge k\) 的链，因为这样是最优的，如果不能满足就留着上传给祖先，如果有多条不能满足，那就证明这个 \(k\) 不合法。为了方便配对，在 \(x \& 1 = 0\) 是可以加一条长度为 \(0\) 的边，可以证明这样不会对答案造成影响。
如果这个点是根节点，我们肯定要全部匹配完，因此在 \(x \& 1 = 1\) 时要再加一条长度为 \(0\) 的边。匹配的思路和上面差不多，显然如果不能匹配也能说明这个 \(k\) 是不合法的。
维护这些链可以用 multiset，总时间复杂度为 \(\mathcal O(n log^2 n)\)
/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"< S;
if(!Flag) return ;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == fa) continue;
dfs(v, u, lim);
S.insert(f[v] + 1);
}
bool flag = false;
if((u == 1 && (S.size() & 1)) || (u != 1 && !(S.size() & 1))) S.insert(0);
while(S.size()) {
multiset::iterator it = S.begin();
int x = *it;
S.erase(it);
it = S.lower_bound(lim - x);
if(u == 1) {
if(it == S.end()) {
Flag = false;
break;
}
S.erase(it);
} else {
if(it == S.end() && flag) {
Flag = false;
break;
} else if(it == S.end() && !flag) {
f[u] = x, flag = true;
} else {
S.erase(it);
}
}
}
}
bool Check(int lim) {
Flag = true;
memset(f, false, sizeof f);
dfs(1, 0, lim);
return Flag;
}
int main()
{
n = read();
for(int i = 1, u, v; i < n; ++i) {
u = read(), v = read();
add_edge(u, v), add_edge(v, u);
}
int l = 1, r = n, ans;
while(l <= r) {
int mid = (l + r) >> 1;
if(Check(mid)) {
ans = mid, l = mid + 1;
} else {
r = mid - 1;
}
}
printf("%d\n", ans);
return 0;
}
P6143 [USACO20FEB]Equilateral Triangles P
搬一张 @hyfhaha 神仙的图。
我们要发现一个结论：
如果我们固定 \(J,K\)，然后分别向 \(x,y\) 轴做垂线，交点为 \(H\)，延长 \(JH,KH\)，使得 \(KH = OH, JH = LH\)，连接 \(OL\)。
那么 \(OL\) 上的所有点都能和 \(J,K\) 配对。
所以我们可以枚举一个点 \(J\)，然后枚举一个距离 \(len\)，如果确定出来的 \(K\) 点存在，那么在预处理斜线前缀和后就可以 \(O(1)\) 求 \(OL\) 上有多少点了。
显然四个方向都要枚举一遍，每一次都要旋转 \(\LARGE\displaystyle\dfrac{\pi}{2}\)。
时间复杂度 \(\mathcal O(n^3)\)。
/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define int long long
#define orz cout<<"lkp AK IOI!"< n) break;
if(a[stc[i].x - j][stc[i].y + j] == 0) continue;
ans = ans + sum[sx][sy] - sum[ex][ey];
}
}
}
signed main()
{
n = read();
for(int i = 1; i <= n; ++i) {
cin >> s + 1;
for(int j = 1; j <= n; ++j) {
a[i][j] = (s[j] == '*');
}
}
for(int i = 1; i <= 4; ++i) {
Turn(), Solve();
}
printf("%lld\n", ans);
return 0;
}
P6144 [USACO20FEB]Help Yourself P
先考虑 \(k=1\) 的情况，P6146 就是这种情况。
考虑 DP。
考虑按照左端点排序，避免右边线段对左边线段的影响。
设 \(f_r\) 表示最右以 \(r\) 结尾的线段集合的联通块的数量的和。
考虑新加入一条线段 \([l,r]\)。考虑从前面的情况转移。
- 对于右端点在 \([1,l-1]\) 的情况，都可以使它们的联通块数量加一，然后统计到 \(f_r\) 里面。
- 对于右端点在 \([l,r]\) 的情况，因为加入后联通块数量不变，所以可以直接统计到 \(f_r\) 里面。
- 对于右端点 \(i \in [r+1,n]\) 的 \(f_i\) 要全部 \(\times 2\)，因为有关这条线段选或不选。
也就是说我们需要维护一个区间求和，区间 \(\times 2\) 的数据结构，直接上线段树即可。
对于 \(k\ \ != 1\) 的情况，可以考虑把它的 \(0 \sim k\) 次结果分别维护，计算的时候用二项式定理相加就好了。
什么是二项式定理？如下式：
\[(x+y)^k = \sum_{i=0}^{k} \binom{k}{i} x^i y^{k-i} \]在本题中，\(y=1\)。
具体实现细节看代码吧。
/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define int long long
#define orz cout<<"lkp AK IOI!"<> 1;
if(mid >= pos) Add(lson, l, mid, pos, b);
else Add(rson, mid + 1, r, pos, b);
Push_up(i);
}
void Mul(int i, int l, int r, int L, int R) {
if(L > R) return ;
if(L <= l && r <= R) {
tree[i].lazy = tree[i].lazy * 2 % mod;
for(int j = 0; j <= K; ++j) tree[i].a[j] = tree[i].a[j] * 2 % mod;
return ;
}
Push_down(i);
int mid = (l + r) >> 1;
if(mid >= L) Mul(lson, l, mid, L, R);
if(mid < R) Mul(rson, mid + 1, r, L, R);
Push_up(i);
}
qwq Query(int i, int l, int r, int L, int R) {
if(L > R) {
qwq b;
for(int j = 0; j <= K; ++j) b.a[j] = 0;
return b;
}
if(L <= l && r <= R) {
qwq d;
for(int j = 0; j <= K; ++j) d.a[j] = tree[i].a[j];
return d;
}
Push_down(i);
int mid = (l + r) >> 1; qwq res;
res.a[0] = 1;
for(int i = 0; i <= K; ++i) res.a[i] = 0;
if(mid >= L) {
qwq b = Query(lson, l, mid, L, R);
for(int j = 0; j <= K; ++j) res.a[j] = (res.a[j] + b.a[j]) % mod;
}
if(mid < R) {
qwq b = Query(rson, mid + 1, r, L, R);
for(int j = 0; j <= K; ++j) res.a[j] = (res.a[j] + b.a[j]) % mod;
}
return res;
}
#undef lson
#undef rson
}
signed main()
{
n = read(), K = read(); M = 2 * n;
for(int i = 1; i <= n; ++i) a[i].l = read(), a[i].r = read();
sort(a + 1, a + n + 1);
C[0][0] = 1;
for(int i = 1; i <= K; ++i) {
C[i][0] = 1;
for(int j = 1; j <= i; ++j) {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
}
qwq d;
for(int i = 0; i <= K; ++i) d.a[i] = 0;
d.a[0] = 1;
Seg::Add(1, 0, M, 0, d);
for(int p = 1; p <= n; ++p) {
int l = a[p].l, r = a[p].r;
qwq b = Seg::Query(1, 0, M, 0, l - 1);
qwq c;
for(int i = 0; i <= K; ++i) c.a[i] = 0;
for(int i = 0; i <= K; ++i) {
int res = 0;
for(int j = 0; j <= i; ++j) {
c.a[i] = (c.a[i] + b.a[j] * C[i][j] % mod) % mod;
}
}
b = Seg::Query(1, 0, M, l, r - 1);
for(int i = 0; i <= K; ++i) c.a[i] = (c.a[i] + b.a[i]) % mod;
Seg::Add(1, 0, M, r, c);
Seg::Mul(1, 0, M, r + 1, M);
}
printf("%lld\n", Seg::Query(1, 0, M, 0, M).a[K]);
return 0;
}