Rank
原来不止我一个人在赤石
Upd：T2 数据多次更改，Rank 变化 4→2→4
A. 岛屿
唐氏题。
赛时找规律+分讨+递推出了正解，时间不够没测直接交了，然后 long double 用了 %lf 直接寄掉。赛时思路很复杂啊，讨论了一大堆，发现其实合并起来就是题解的做法（？）。
初始图中一共分为两种，同色相连和异色相连。考虑五种情况得出递推式：红同接蓝同，\(f_{i,j}=f_{i-1,j+1}\)；红同/蓝同 接异，\(f_{i,j}=f_{i,j-1}\)；异接异，首尾接，\(f_{i,j}=f_{i,j-1}+1\)；接不同的异，\(f_{i,j}=f_{i,j-1}\)。根据数量得出概率，最后发现同色和异色的贡献互不干扰，可以分别求，然后 \(\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()
{lx x = 0, f = 1; char ch = getchar();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 fi first
#define se second
#define pii pair<int, int>
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
#define qr qr()
const int Ratio = 0;
const int N = 2e5 + 5;
int n, x, y;
namespace Wisadel
{short main(){freopen("island.in", "r", stdin) , freopen("island.out", "w", stdout);x = qr, y = qr;n = 2 * x + y;long double ans = 0;fo(i, 1, x) ans += (long double)1.0 / (i * 2 - 1);fo(i, 1, y) ans += (long double)1.0 / (i + x * 2);printf("%.10Lf\n", ans);return Ratio;}
}
int main(){return Wisadel::main();}
B. 最短路
最签的了。最短路树，没看出来，打了个不知道什么做法，不怕重边，不知道怕什么，分数 80 → 88 → 76pts。
这么一想好像就是最短路树板子，题目还贴心地给了保证最短路唯一。那么考虑求一个点删去最后一条边后的最短路，应该从该点的子树内找到一点与子树外的一点，此时最短路为 \(dis_u+dis_v+w_{u,v}-dis_x\)，那么我们只需要找到所有的边 \(u,v\) 并按 \(dis_u+dis_v+w_{u,v}\) 升序排序即可。
对有没有重边比较有争议。如果有只需要在找边时判一下就行了，没啥太要注意的，复杂度大概是 \(\mathcal{O(n\log n+m\log 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()
{lx x = 0, f = 1; char ch = getchar();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 pii pair<int, int>
#define fi first
#define se second
#define qr qr()
const int Ratio = 0;
const int N = 2e5 + 5;
int n, m, tot;
int hh[N], to[N << 1], ne[N << 1], cnt;
int fx[N], dep[N], fa[N];
ll dis[N], ans[N], w[N << 1];
bool yz[N], vis[N << 1];
struct rmm
{int u; ll w;bool operator < (const rmm &A) const{return A.w < w;}
};
struct edge{int u, v; ll val;} e[N];
namespace Wisadel
{int Wfind(int x){if(x == fx[x]) return x;return fx[x] = Wfind(fx[x]);}void Wadd(int u, int v, int val){to[++cnt] = v;w[cnt] = val;ne[cnt] = hh[u];hh[u] = cnt;}void Wdij(int x){priority_queue<rmm> q;memset(dis, 0x3f, sizeof dis);dis[x] = 0;q.push({x, dis[x]});while(q.size()){int u = q.top().u; q.pop();if(yz[u]) continue;yz[u] = 1;for(int i = hh[u]; i != -1; i = ne[i]){int v = to[i];if(dis[v] > dis[u] + w[i]){vis[i] = vis[i ^ 1] = 1;fa[v] = u, dep[v] = dep[u] + 1;dis[v] = dis[u] + w[i];q.push({v, dis[v]});}}}}short main(){freopen("path.in", "r", stdin) , freopen("path.out", "w", stdout);n = qr, m = qr;cnt = -1;memset(hh, -1, sizeof hh);fo(i, 1, m){int a = qr, b = qr, c = qr;Wadd(a, b, c), Wadd(b, a, c);}Wdij(1);fo(u, 1, n){fx[u] = u, ans[u] = 1e18;for(int i = hh[u]; i != -1; i = ne[i]){int v = to[i]; ll val = w[i];if((!vis[i] || (fa[u] != v && fa[v] != u)) && u < v)e[++tot] = {u, v, val};}}sort(e + 1, e + 1 + tot, [](edge &A, edge &B){return dis[A.u] + dis[A.v] + A.val < dis[B.u] + dis[B.v] + B.val;});fo(i, 1, tot){int u = e[i].u, v = e[i].v;ll zc = dis[u] + dis[v] + e[i].val;int _ = Wfind(u), __ = Wfind(v);while(_ != __){if(dep[_] < dep[__]) swap(_, __);ans[_] = zc - dis[_];fx[_] = fa[_];_ = Wfind(_);}}fo(i, 2, n) printf("%lld\n", ans[i] == 1e18 ? -1 : ans[i]);return Ratio;}
}
int main(){return Wisadel::main();}
C. 列表
byd 为什么不让我们听多校讨论？
考虑对于原长度为 \(m=2\times n +1\) 的序列中每一个元素可能加入集合 \(S\) 的时间。简单手模就能发现，每个点从第 \(|x-(n+1)|\) 轮开始到最后 \(n+1\) 轮都可以加入，实质上是一个后缀。这道题每个右端点对应的左端点显然是单调的，我们双指针枚举连续值域端点，问题就转化为了判断这些点能否全部加入集合内，结合上面的后缀思路，也就转化为了一个匹配问题，线段树维护 hall 定理即可。
大致做法是，在后缀域上建线段树，维护每个区间当前长度和区间内点的个数，合法当且仅当区间的长度减去子集后缀点数大于 0。
复杂度 \(\mathcal{O(n\log n)}\)。记得线段树范围是 \(\left[1,n+1\right]\)。
点击查看代码
#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()
{lx x = 0, f = 1; char ch = getchar();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 pii pair<int, int>
#define fi first
#define se second
#define qr qr()
const int Ratio = 0;
const int N = 4e5 + 5;
int n, m, ans = 1;
int a[N], p[N];
int las[N << 2], use[N << 2];
namespace Wisadel
{#define ls (rt << 1)#define rs (rt << 1 | 1)#define mid ((l + r) >> 1)void Wpushup(int rt){use[rt] = use[ls] + use[rs];las[rt] = min(las[ls], las[rs] - use[ls]);}void Wbuild(int rt, int l, int r){if(l == r){las[rt] = l;return ;}Wbuild(ls, l, mid), Wbuild(rs, mid + 1, r);Wpushup(rt);}void Wupd(int rt, int l, int r, int x, int k){if(l == r){las[rt] -= k, use[rt] += k;return ;}if(x <= mid) Wupd(ls, l, mid, x, k);else Wupd(rs, mid + 1, r, x, k);Wpushup(rt);}short main(){freopen("list.in", "r", stdin) , freopen("list.out", "w", stdout);n = qr;m = 2 * n + 1;fo(i, 1, m) a[i] = qr, p[a[i]] = min(i, m - i + 1);Wbuild(1, 1, n + 1);int l = 1;fo(r, 1, m){Wupd(1, 1, n + 1, p[r], 1);while(las[1] < 0) Wupd(1, 1, n + 1, p[l++], -1);ans = max(ans, r - l + 1);}printf("%d\n", ans);return Ratio;}
}
int main(){return Wisadel::main();}
D. 种植
难难题。
送了 45pts。十分爆搜，复杂度 \(\mathcal{O(2^n\times n^2)}\)；35pts 性质，比较一眼，必须斜着摆满才合法。
正解咕咕先。
末
赤石局，赤爽乐。
开局 T1 不会，T2 不确定，T3 不会，T4 有点会但不会实现，然后几乎都在坐牢。
下午在赤 T3，唐氏消费股不给放多校讨论导致一直没往 hall 定理上想（虽然我刚知道。
还有两场就要 CSP 了，加油！
完结撒花~
银狼助你一切问题迎刃而解。
