CCPC 2022 广州站 部分解题报告
Solved: 5/13 Rank:59
H
队友写的。签到题就不补了。
L
给定
n 个人,m 个不同的车站,求把人安排到车站中的方案数,考虑人的排列顺序以及强制每一个车站都要有人。
m \leq n \leq 10^5
经典组合问题。我们首先考虑对于所有的
发现先把
E
一栋
m 层的楼内有n 台电梯,第i 台会在a_i 时刻启动并开始以1 层 / 秒的速度上升。你可以在所有电梯开始前将
2\to m-1 之间某些层的按钮按下,这样第一个到这层的电梯就会在这时暂停一秒。求使第
i 台电梯第一个到楼顶的最小操作次数。
n \leq 5\times 10^5,m \leq 10^9
记录每个点的操作次数为
- 若
i < j ,那么有a_i + \Delta + 1 \geq a_j - 若
i > j ,那么有a_i + \Delta \geq a_j
按照
const int N = 1e6 + 10;
int t[N],n,m,ans[N],tr[N];
int lowbit(int x) {return x & (-x);}
void modify(int x,int v) {for (;x <= n;x += lowbit(x)) tr[x] += v;}
int query(int x) {
int ans = 0;
for (;x;x -= lowbit(x)) ans += tr[x];
return ans;
}
pii p[N];
signed main() {
read(n,m);
for (int i = 1;i <= n;++i) read(t[i]),p[i] = mp(t[i],i);
sort(p + 1,p + 1 + n);
int sum = 0;
for (int i = 1;i <= n;++i) {
sum += p[i].first;
ans[p[i].second] = (p[i].first * i) - sum + query(p[i].second);
modify(p[i].second,1);
}
for (int i = 1;i <= n;++i) {
if (ans[i] > m - 2) puts("-1");
else printf("%lld\n",ans[i]);
}
return 0;
}
I
给定一个
n(n\le 2000) 个节点的树,每个点都有点权a_i 。点
x 有\frac{a_x}{\sum\limits_{i = 1}^{n}{a_i}} 的概率被选择为初始传染源。初始传染源只会有一个。每个点都有一个概率
p_i (以分数的形式给出),表示,它周围相邻的点,如果有传染源的话。
- 有
p_i 的概率,这个点也变成传染源。- 有
1-p_i 概率,这个点不会变成传染源,且之后也不会变成传染源。问,感染恰好
k 个点的概率是多少。(1\le k \le n)
考虑每个树上的点集。我们发现,一个大小恰好为
显然树形 DP。
那么就有
注意一下
const int N = 2e3 + 10;
int a[N],n,b[N],c[N],siz[N],f[N][N],g[N][N],t1[N],t2[N],fat[N];
ll p[N],sum,ans[N];
vector <int> G[N];
ll ffpow(ll a,ll b) {
ll ans = 1;
for (;b;b >>= 1) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
}
return ans;
}
void DP(int x,int fa) {
siz[x] = 1;fat[x] = fa;
f[x][1] = p[x];g[x][1] = a[x] * sum % mod;
for (auto y : G[x]) {
if (y != fa) {
DP(y,x);
memset(t1,0,sizeof t1);memset(t2,0,sizeof t2);
for (int i = 0;i <= siz[x];++i) {
for (int j = 0;j <= siz[y];++j) {
if (!i && !j) continue;
t1[i + j] = (t1[i + j] + f[x][i] * f[y][j] % mod) % mod;
t2[i + j] = (t2[i + j] + g[x][i] * f[y][j] % mod) % mod;
if (j) {
t2[i + j] = (t2[i + j] + f[x][i] * g[y][j] % mod) % mod;
}
}
}
for (int i = 0;i <= siz[x] + siz[y];++i) f[x][i] = t1[i];
for (int i = 0;i <= siz[y] + siz[x];++i) g[x][i] = t2[i];
siz[x] += siz[y];
}
}
f[x][0] = g[x][0] = (1 - p[x] + mod);
}
signed main() {
read(n);
for (int i = 1;i < n;++i) {
int x,y;read(x,y);
G[x].emplace_back(y);G[y].emplace_back(x);
}
for (int i = 1;i <= n;++i) {
read(a[i],b[i],c[i]);
p[i] = b[i] * ffpow(c[i],mod-2) % mod;
sum = (sum + a[i]) % mod;
}
sum = ffpow(sum,mod - 2);
DP(1,1);
for (int i = 1; i<= n;++i) {
ans[i] = g[1][i];
for (int j = 2;j <= n;++j) {
ans[i] = (ans[i] + g[j][i] * (1 - p[fat[j]] + mod) % mod) % mod;
}
}
for (int i = 1;i <= n;++i) printf("%lld\n",ans[i]);
return 0;
}
C
给定一张 DAG,你需要构造一组点权令所有
1\to n 的路径权值相等。
n,m\leq 10^5
我们考虑从 1 出发到每个点的路径长
不难想到并查集。缩点之后注意到点权为正,那么不能出现环,所以生成的东西必然还是一个 DAG。这里注意特判一下,然后之后我们就可以在这张新图上求出每个点的
const int N = 5e5 + 10;
int n,m,f[N],d[N],dp[N];
vector <int> G[N],buc[N];
vector <pii> edg;
int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}
void solve() {
read(n,m);
for (int i = 1;i <= n;++i) f[i] = i,G[i].clear(),buc[i].clear(),d[i] = dp[i] = 0;
edg.clear();
for (int i = 1;i <= m;++i) {
int x,y;read(x,y);edg.push_back(mp(x,y));
G[y].push_back(x);
}
for (int x = 1;x <= n;++x) {
for (auto y : G[x]) {
f[find(y)] = find(G[x][0]);
}
}
for (auto e : edg) {
int x = e.first,y = e.second;
buc[find(x)].emplace_back(find(y));
d[find(y)]++;
}
int cnt = 0;
queue <int> q;
for (int i = 1;i <= n;++i) {
//printf("%d %d\n",find(i),i);
if (find(i) == i) {
++cnt;
if (!d[i]) {
q.push(i);dp[i] = 1;
}
}
}
while (!q.empty()) {
int x = q.front();q.pop();
--cnt;
for (auto y : buc[x]) {
dp[y] = max(dp[y],dp[x] + 1);
if (!--d[y]) {
q.push(y);
}
}
}
if (cnt) puts("No");
else {
puts("Yes");
for (int i = 1;i <= n;++i) {
int ans = dp[find(i)];
if (i != 1) ans -= dp[find(G[i][0])];
printf("%d ",ans);
}
puts("");
}
}
B
Coach 说了个 Segment Tree beats 的做法,不会,有会的老哥教教(
upd:我会了!
我们考虑把对
实现代码就是这样:
void change(int p,int x,int y,int c) {
if (tree[p].l >= x && tree[p].r <= y) {
tree[p].col = c;
return ;
}
pushdown(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (x <= mid) change(p << 1,x,y,c);
if (y > mid) change(p << 1 | 1,x,y,c);
pushup(p);
}
void query(int p,int x,int y) {
if (tree[p].l >= x && tree[p].r <= y && tree[p].col) {
b[tree[p].col] += tree[p].all;//下放操作
clr(p);
return ;
}
pushdown(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (x <= mid) query(p << 1,x,y);
if (y > mid) query(p << 1 | 1,x,y);
pushup(p);
}
if (opt == 1) {
int c;read(c);
query(1,l,r);
change(1,l,r,c);
}
其他操作就很简单了。最后记得下推,可以根据 segtreebeats 的相关理论证明时间复杂度为
const int N = 5e5 + 10;
int n,q,a[N];
ull b[N];
struct node {
int l,r;
int tagg;
ull col,all,tagh,t,tag,sum;
}tree[N<<2];
void addval(int p,ull val) {
tree[p].tag += val;
tree[p].sum += (ull)(tree[p].r - tree[p].l + 1) * val;
tree[p].tagh += val * tree[p].t;
}
void addtime(int p,ull tim) {
tree[p].all += tim * tree[p].sum;
tree[p].t += tim;
}
void pushup(int p) {
tree[p].all = tree[p << 1].all + tree[p << 1 | 1].all;
tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
tree[p].col = (tree[p << 1].col == tree[p << 1 | 1].col) ? tree[p << 1].col : 0;
}
void clr(int p) {
tree[p].tagg = 1;
tree[p].tagh = tree[p].all = tree[p].t = 0;
}
void pushdown(int p) {
if (tree[p].tagg) {
clr(p << 1);clr(p << 1 | 1);
tree[p].tagg = 0;
}
if (tree[p].tag) {
addval(p << 1,tree[p].tag);
addval(p << 1 | 1,tree[p].tag);
tree[p].tag = 0;
}
if (tree[p].tagh) {
tree[p << 1].all -= tree[p].tagh * (tree[p << 1].r - tree[p << 1].l + 1);
tree[p << 1].tagh += tree[p].tagh;
tree[p << 1 | 1].all -= tree[p].tagh * (tree[p << 1 | 1].r - tree[p << 1 | 1].l + 1);
tree[p << 1 | 1].tagh += tree[p].tagh;
tree[p].tagh = 0;
}
if (tree[p].t) {
addtime(p << 1,tree[p].t);
addtime(p << 1 | 1,tree[p].t);
tree[p].t = 0;
}
if (tree[p].col) {
tree[p << 1].col = tree[p].col;
tree[p << 1 | 1].col = tree[p].col;
}
}
void build(int p,int l,int r) {
tree[p].l = l,tree[p].r = r;
if (l == r) {
tree[p].col = a[l];
return ;
}
int mid = (tree[p].l + tree[p].r) >> 1;
build(p << 1,l,mid);
build(p << 1 | 1,mid + 1,r);
pushup(p);
}
void change(int p,int x,int y,int c) {
if (tree[p].l >= x && tree[p].r <= y) {
tree[p].col = c;
return ;
}
pushdown(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (x <= mid) change(p << 1,x,y,c);
if (y > mid) change(p << 1 | 1,x,y,c);
pushup(p);
}
void modify(int p,int x,int y,ull c) {
if (tree[p].l >= x && tree[p].r <= y) {
addval(p,c);
return ;
}
pushdown(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (x <= mid) modify(p << 1,x,y,c);
if (y > mid) modify(p << 1 | 1,x,y,c);
pushup(p);
}
void query(int p,int x,int y) {
if (tree[p].l >= x && tree[p].r <= y && tree[p].col) {
b[tree[p].col] += tree[p].all;
clr(p);
return ;
}
pushdown(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (x <= mid) query(p << 1,x,y);
if (y > mid) query(p << 1 | 1,x,y);
pushup(p);
}
signed main() {
read(n,q);
for (int i = 1;i <= n;++i) read(a[i]);
build(1,1,n);
for (int i = 1;i <= q;++i) {
int opt,l,r;read(opt,l,r);
if (opt == 1) {
int c;read(c);
query(1,l,r);
change(1,l,r,c);
} else {
ull c;read(c);
modify(1,l,r,c);
}
addtime(1,1);
}
query(1,1,n);
for (int i = 1;i <= n;++i) printf("%llu ",b[i]);
return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。