反向挂分大王
Rank
A. 暴力操作（opt）
签，但是没有人签。
都想到了二分和更新 c 值，但是 c 多多少少没更到最优。
首先还是调和级数预处理，倒序取 min。然后考虑到超过 \(m\) 的也有可能产生更小的代价，因此 \(\mathcal{O(n)}\) 枚举一遍找到最小的 \(j\) 使 \(i\times j\gt m\)，全部赋到 \(c_{m+1}\) 上，然后再倒序取一遍 min 就能更好的更新。
check 有 \(\mathcal{O(n)}\) 的双指针写法，我直接没改赛时的 \(\mathcal{O(n\log n)}\) 的二分，所以复杂度是 \(\mathcal{O(n\ln n+n\log^2n)}\) 的。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#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 ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 5e5 + 5;
const int mod = 1e9 + 7;
ll n, m, k;
ll a[N], c[N];
namespace Wisadel
{
bool Wck(int x)
{
ll ned = 0;
fo(i, 1, n / 2 + 1) if(a[i] > x)
{
int l = 2, r = a[i] + 1;
while(l < r)
{
int mid = (l + r) >> 1;
if(a[i] / mid <= x) r = mid;
else l = mid + 1;
}
ned += c[r];
if(ned > k) return 0;
}
return 1;
}
short main()
{
freopen("opt.in", "r", stdin), freopen("opt.out", "w", stdout);
n = qr, m = qr, k = qr;
fo(i, 1, n) a[i] = qr;
fo(i, 1, m) c[i] = qr;
fo(i, 2, m) fo(j, 1, min(m / i, 1ll * i))
c[i * j] = min(c[i * j], c[i] + c[j]);
fu(i, m - 1, 1) c[i] = min(c[i], c[i + 1]);
c[m + 1] = 1e9;
fo(i, 2, m)
{
int zc = m / i + 1;
c[m + 1] = min(c[m + 1], c[i] + c[zc]);
}
fu(i, m, 1) c[i] = min(c[i], c[i + 1]);
sort(a + 1, a + 1 + n);
int l = 0, r = a[n / 2 + 1];
while(l < r)
{
int mid = (l + r) >> 1;
if(Wck(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", r);
return Ratio;
}
}
signed main(){return Wisadel::main();}
// Now there's only one thing I can do
// Fight until the end like I promised to
B. 异或连通（xor）
比较套路。
主要需要想到对询问建 trie 而不是边，那么容易发现一条边只会在 \(\log V\) 个子树中出现。按线段树分治的思想，直接在 trie 树上分治，找到对于每一个询问合法的线段存到点上，然后对 trie 树做一遍 dfs，过程中做启发式合并，回溯时撤销即可。
注意并查集不要路径压缩！复杂度 \(\mathcal{O(n\log n\log V)}\)。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#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
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int n, m, k, q;
struct rmm{int u, v, w;} e[N];
int que[N], pre[N];
namespace Wisadel
{
ll fx[N], siz[N];
int Wfind(int x)
{
if(x == fx[x]) return x;
return Wfind(fx[x]);
}
void Wmerge(int u, int v)
{
u = Wfind(u), v = Wfind(v);
if(u == v) return ;
if(siz[u] < siz[v])
fx[u] = v, siz[v] += siz[u];
else fx[v] = u, siz[u] += siz[v];
}
int t[N * 20][2], tot;
vector<pii> d[N * 20];
vector<int> v[N * 20];
ll ans[N * 20];
void Wins(int x, int id)
{
int now = 0;
fu(i, 30, 0)
{
int to = (x >> i) & 1;
if(!t[now][to]) t[now][to] = ++tot;
now = t[now][to];
}
pre[id] = now;
}
void Wupd(int x, int id)
{
int now = 0;
fu(i, 30, 0)
{
int to = (x >> i) & 1, pd = (k >> i) & 1;
if(pd)
{
if(t[now][to]) v[t[now][to]].P_B(id);
now = t[now][to ^ 1];
}
else now = t[now][to];
if(!now) return ;
}
}
void Wdfs(int now, ll sum)
{
ans[now] = sum;
for(int i : v[now])
{
int _ = Wfind(e[i].u), __ = Wfind(e[i].v);
if(_ == __) continue;
if(siz[_] < siz[__]) swap(_, __);
ans[now] += siz[_] * siz[__];
fx[__] = _, siz[_] += siz[__];
d[now].P_B(M_P(_, __));
}
if(t[now][0]) Wdfs(t[now][0], ans[now]);
if(t[now][1]) Wdfs(t[now][1], ans[now]);
fu(i, d[now].size() - 1, 0)
{
pii zc = d[now][i];
fx[zc.se] = zc.se;
siz[zc.fi] -= siz[zc.se];
}
}
short main()
{
freopen("xor.in", "r", stdin), freopen("xor.out", "w", stdout);
n = qr, m = qr, q = qr, k = qr;
fo(i, 1, n) fx[i] = i, siz[i] = 1;
fo(i, 1, m) e[i].u = qr, e[i].v = qr, e[i].w = qr;
fo(i, 1, q) que[i] = qr, Wins(que[i], i);
fo(i, 1, m) Wupd(e[i].w, i);
Wdfs(0, 0);
fo(i, 1, q) printf("%lld\n", ans[pre[i]]);
return Ratio;
}
}
signed main(){return Wisadel::main();}
// Now there's only one thing I can do
// Fight until the end like I promised to
C. 诡异键盘（keyboard）
huge：你们上届学长只有三个改出来了
放最后改了，懂了大概思路。
赛时纯唐纯暴力做法打的 20pts 拿到了 70pts。
先做删串需要的同余最短路，然后建 trie 做 dp，具体不太会。
D. 民主投票（election）
好像是真正的签，不过为什么我需要卡常才能过？
首先需要求得树上最多票数最少 \(k\) 是多少，这个容易想到二分去做，设 \(f_i\) 为子树 \(i\) 在某个票数限制下需要向上贡献的票数，判断可行与否只需根据 \(f1=0\)。然后对于子树大小减一大于 \(k\) 点一定可行，小于 \(k\) 的一定不行，这两点都很显然。
关键在处理子树大小减一等于 \(k\) 的点。办法是以 \(k-1\) 为限制再 dp 一次。此时只有当前点的限制为 \(k\)，则若 \(f_x=1\)，那么解除限制后才满足 \(f_x=0\)。只有 \(x\) 到根路径上的点的 \(f\) 都为 0 且 \(f_1=1\) 时才合法，因为只有此时 \(f_x\) 限制加一才能解除 \(f_1\) 的限制。
时间复杂度 \(\mathcal{O(n\log n)}\)，不知道为啥要卡常。
点击查看代码
// ubsan: undefined
// accoders
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#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 ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 2e6 + 5;
const int mod = 1e9 + 7;
int n;
int hh[N], to[N], ne[N], cnt;
int siz[N], f[N];
bool ok[N];
namespace Wisadel
{
inline void Wadd(int u, int v)
{
to[++cnt] = v;
ne[cnt] = hh[u];
hh[u] = cnt;
}
inline void Wdfs(int u, int fa)
{
siz[u] = 1;
for(int i = hh[u]; i != -1; i = ne[i])
{
int v = to[i];
Wdfs(v, u);
siz[u] += siz[v];
}
}
inline void Wck(int u, int tar)
{
f[u] = 0;
for(int i = hh[u]; i != -1; i = ne[i])
{
int v = to[i];
Wck(v, tar);
f[u] += f[v] + 1;
}
if(f[u] <= tar) f[u] = 0;
else f[u] -= tar;
}
inline void Wsol(int u)
{
if((u == 1 && f[u] != 1) || !f[u]) return ;
if(f[u] == 1) ok[u] = 1;
for(int i = hh[u]; i != -1; i = ne[i])
{
int v = to[i];
Wsol(v);
}
}
short main()
{
freopen("election.in", "r", stdin), freopen("election.out", "w", stdout);
int T = qr;
while(T--)
{
n = qr;
cnt = 0;
fill(hh + 1, hh + 1 + n, -1);
fo(i, 2, n)
{
int x = qr;
Wadd(x, i);
}
Wdfs(1, 0);
int l = 1, r = n, ke = 0;
while(l <= r)
{
int mid = (l + r) >> 1;
Wck(1, mid);
if(f[1] == 0) r = mid - 1, ke = mid;
else l = mid + 1;
}
memset(ok+1, 0, sizeof(bool)*n);
Wck(1, ke - 1);
Wsol(1);
fo(i, 1, n)
{
int zc = siz[i] - 1;
if(zc > ke) putchar('1');
else if(zc < ke) putchar('0');
else printf("%d", ok[i]);
}
puts("");
}
return Ratio;
}
}
signed main(){return Wisadel::main();}
// Now there's only one thing I can do
// Fight until the end like I promised to
邀请了 jijidawang 为特邀嘉宾帮助卡常，直接将一个 7000ms+ 的代码通过各种科技卡到了 accoder 上 1380ms。
jjdw 科技代码
// ubsan: undefined
// accoders
#include<bits/stdc++.h>
#define int unsigned
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#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 ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
constexpr int Ratio = 0;
constexpr int N = 1e6 + 5;
const int mod = 1e9 + 7;
int n;
int siz[N], f[N], qwq[N];
int ok[N];
namespace Wisadel
{
vector<int> g[N];
inline void Wadd(int u, int v){g[u].emplace_back(v);}
inline void Wck(int u, signed tar)
{
memset(f+1,0,sizeof(int)*n);
#pragma GCC unroll 16
for (int i=n; i>=2; i--)
{
f[i] = max<signed>((signed)f[i] - tar, 0);
f[qwq[i]] += f[i] + 1;
}
f[1] = max<signed>((signed)f[1] - tar, 0);
}
inline void Wsol(int u)
{
if((u == 1 && f[u] != 1) || !f[u]) return ;
if(f[u] == 1) ok[u] = 1;
#pragma GCC unroll 2
for (int v : g[u])
Wsol(v);
}
inline __int32_t main()
{
freopen("election.in", "r", stdin), freopen("election.out", "w", stdout);
int T = qr;
while(T--)
{
n = qr;
#pragma GCC unroll 32
for(int i=1;i<=n;i++)g[i].clear();
#pragma GCC unroll 8
for(int i=1;i<=n;i++){ok[i]=0;siz[i]=1;}
#pragma GCC unroll 32
fo(i, 2, n)
{
qwq[i] = qr;
Wadd(qwq[i], i);
}
#pragma GCC unroll 4
fu(j, n, 2) siz[qwq[j]] += siz[j];
int l = 1, r = n, ke = 0;
while(l <= r)
{
int mid = (l + r) >> 1;
Wck(1, mid);
if(f[1] == 0) r = mid - 1, ke = mid;
else l = mid + 1;
}
Wck(1, ke - 1);
Wsol(1);
#pragma GCC unroll 32
fo(i, 1, n)
{
if(siz[i] - 1 > ke) putchar('1');
else if(siz[i] - 1 < ke) putchar('0');
else printf("%d", ok[i]);
}
puts("");
}
return Ratio;
}
}
signed main(){return Wisadel::main();}
// Now there's only one thing I can do
// Fight until the end like I promised to