20200528模拟-pb

pb的场

赛况大概是,rose100+100+40,xld100+55+10,lhy会A,yzh会A但炸

我和lxj以前做过A,但我回忆了1h,写了0.5h才搞定,剩下BC都没思路

CF1314B Double Elimination

题意:双败淘汰制,$2^n$参赛者中有k个关键人物,最大化有特殊关键参与的比赛总数,$n \le 17$

注意败者组每轮有两场比赛,两场中间是胜者组的一场比赛;参赛双方是根据可用编号排序后决定的

请先思考后再展开

将每次胜者组的一次比赛和败者组的两次比赛看作一个点,则构成一棵树,节点数约为$2^{n}$

发现只关心,每次最终胜者组和败者组的winner是不是关键人物,做个树形dp,状态为$dp(x,0/1,0/1)$

合并复杂度为$2^4*2$,即枚举各自状态,考虑胜者组的新winner来自哪个组,剩下的人或在一起构成第二维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct Data
{
int a[2][2];Data(){mem(a,-0x3f);}
void build(int cc)
{
a[0][0]=0;
if(cc>=1) a[0][1]=a[1][0]=1;
if(cc==2) a[1][1]=1;
}
Data friend operator + (Data x,Data y)
{
Data c;
fo(x0,0,1) fo(x1,0,1) fo(y0,0,1) fo(y1,0,1)
chmax( c.a[x0][x1|y0|y1],x.a[x0][x1]+y.a[y0][y1]+(x0|y0)+(x1|y1)+(x1|y0|y1) ),
chmax( c.a[y0][x1|x0|y1],x.a[x0][x1]+y.a[y0][y1]+(x0|y0)+(x1|y1)+(x1|x0|y1) );
return c;
}
}dp[N];
int cnt[N];
void main()
{
int n=qread(),k=qread();while(k--) cnt[(qread()-1)/2]++;
fo(s,0,bin(n-1)-1) dp[s].build(cnt[s]);
fo(i,0,n-2) fo(s,0,bin(n-1)-1) if(s&bin(i)) dp[s^bin(i)]=dp[s^bin(i)]+dp[s];//写的比较随便
int ans=0;fo(i,0,1) fo(j,0,1) chmax(ans, dp[0].a[i][j]+(i|j) );write(ans);
}

B

题意:$n \le 2e5$点$m \le 3e5$边的无向简单连通图,其中每条边都为白色。接下来,对于任意一对点,若在原图中它们之间的最短路为2,则在它们之间连一条黑边。每条白边的边权为$a$,每条黑边的边权为$b$,求出在新图中从 1 号点出发到其它所有点的最短路。

时限2s

请先思考后再展开

赛后想到了b=0(也就是会缩成一点)咋做:先枚举每个度数超过根号的点,把相邻点、相邻点间的边拉出来做一个$O(n+m)$的补图连通性;然后跑dij,dij途中更新x周围每个点y,除此之外,如果y没有标记,就打上标记,并枚举y周围所有点z更新。因为只有0和a的边,相当于只有0和1,即经典的双端队列最短路,总复杂度为$O(m \sqrt m)$


思维广度的问题并没有想起三元环……那么枚举三元环,枚举中介点取边出来的时候就不需要根号分治了,dij也不需要了,会好写不少,复杂度同三元环个数,$O(m \sqrt m)$

正解需要一步转化(没有也能做,rose就是这样,不过没那么优美,因为要使用dij处理白边)

先判掉$b>2a$也就是完全不用黑边的情况。随便bfs一下,如果到y的长度为偶数(不考虑边权),答案一定就是$dep/2*b$,否则答案不超过$(dep-1)/2*b+a$

将一个b换成两个a不优,所以我们只需要考虑每个点能否去掉a,也就是变成只使用b

只有一种边权可以bfs,对于当前拓展点x,枚举中介点y,枚举y旁边的点z,如果$(x,z) \notin E$,就成功把z加入队列,并且以后不再将$(y,z)$作为两步走中第二步(注意该过程中边有向,实现时可以每个点两个边表,然后在表示第二步的那个中删除该边),否则,这种失败的情况唯一对应一个三元环,所以失败次数不超过$O( m \sqrt m)$

删除边使用常规的链表即可,因为删该边时一定已知其编号;判断边存在的话用unorderedset常数巨大,可以考虑时间戳(先把x旁边的点打个标记);此时依然有点慢,加入一个不好卡的优化(实际跑得飞快),就是如果不考虑$(x,z)$的限制,x都不能让z更小,这条边也已经可以删除。总复杂度为$O(m \sqrt m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vc<int> to[N];//两步走中的第一步,不用删边
struct Edge{ int y,pre,nxt; }e[N];int id,hou[N];//第二步
void ins(int x,int y){ ++id;e[hou[x]].nxt=id,e[id]={y,hou[x],0};hou[x]=id,to[x].PB(y); }
int dep[N],ans[N],tim[N];
void main()
{
int n=qread(),m=qread();ll A=qread(),B=qread();while(m--){ int x=qread(),y=qread();ins(x,y),ins(y,x); }
queue<int> q;q.push(1);while(sz(q)){ int x=q.front();q.pop();for(auto y:to[x]) if(!dep[y] and y!=1) dep[y]=dep[x]+1,q.push(y); }
while(sz(q)) q.pop();q.push(1);
while(sz(q))
{
int x=q.front();q.pop();
for(auto y:to[x]) tim[y]=x;//时间戳,判断之间有没有边
for(auto y:to[x]) for(int k=hou[y],z=e[k].y;k>0;z=e[k].y)
if(tim[z]!=x or (ans[z]>0 and ans[z]<ans[x]+1))
{
int k1=e[k].pre,k2=e[k].nxt;
e[k1].nxt=k2,e[k2].pre=k1;if(k==hou[y]) hou[y]=k1;k=k1;
if(z>1 and !ans[z]) ans[z]=ans[x]+1,q.push(z);
}
else k=e[k].pre;
} fo(x,2,n) write2( min(min(ans[x]!=0?ans[x]*B:bin(60),dep[x]&1?dep[x]/2*B+A:dep[x]/2*B),dep[x]*A) );
}

C

题意: m次比赛,打第i次会失去i点体力,现在给出n个人的体力,选出n的倍数场要打的比赛,按照时间顺序一场一场打,每次排出第i个后会排出第i+1个(第n个后是第1个),要求每个人体力始终非负,最大化所有人损失体力总和,$n \le 2e5,m \le 1e9,ai \le m(m+1)/2$

请先思考后再展开

设轮数(n次比赛算一轮)为T,列出尽可能多的不等式

$$
use_i \le a_i,此为题意
\\
use_i \le \sum_{t=1}^T m-tn+i,即选最后的若干个
\\
i<j,use_i \le a_j-T*(j-i),对于j的每个位置,前面有j-i-1个要留给i+1 \sim j-1
\\
j<i,use_i \le a_j-j+(m-n+i)-(T-1)*(j+n-i)
\\
类似上面,考虑第z+1个j前要留多少位置后才能放第z个i,然后第1个j和最后一个i贪心放
$$

很明显已经是方案合法的充要条件,所以该上界足够紧,我们考虑怎么达到该上界

一种结论是,从后往前,如果放了后前面依然存在合法解(选最小的若干个),那么就放

正确性不会告辞

将T看作自变量,那么上面的四个限制其实是四个上凸函数(顶点远离原点),取min、做加法后依然是上凸函数,所以可以二分、三分,$O(n log \frac{m}{n})$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/1459bf9d.html
转载请注明出处,谢谢!