CFR621

CFR621 div1

倒开E,写了2、3k,狂fail,升天

upd:18号back完题,晚上凌晨1点睡不着逛b站发现dls发了个神奇的视频,然后17个人在看是什么鬼(而且三千关注一半播放量,dlsnb),这么多人睡不着的吗……感觉dls写题也挺急的(本身想题就很快),经常写错点小东西,不过很快就反应过来。然后G被识别后跑去自己课件找题解很nb(题意为在某条边加1的代价是ci,配额改为代价和)。而且全程还不断关照tourist

CF1307C Cow and Message

请先思考后再展开

显然只有长度为1或2的是有用的

我已经不记得上次犯没开ll是什么时候了

CF1307D Cow and Fields

请先思考后再展开

如果有$dis_{1 \to x}$相同的点,答案为原最短路,否则考虑$dis_{1 \to x}<dis_{1 \to y},贡献为dis_{1 \to x}+1+dis_{y \to n}$

code

CF1307E Cow and Treats

题意:一行$n \le 5e3$块草,种类为$s_i$,$m\le 5e3$头牛,给出喜欢的草和食量,选出两个不重集合L、R分别放在0和n+1处,最大化$|L|+|R|$,并求出此时的方案数(只考虑集合),要求这$|L|+|R|$头牛存在某种顺序,依次派出前往另一个方向,路上能吃掉食量那么多的喜欢的草,满足的那一刻停在那里阻断两侧。

请先思考后再展开

不知道出这种题有啥意义,没有思维含量,就是看你困不困……我的写法是枚举L中最大的,然后按颜色枚举其他牛(一个集合不能有两头牛颜色相同),具体见代码

其实讨论也不是特别多,代码也不能说长,但是真的就是一个不小心,写错两个字符这种破事

表示对更优复杂度这种事完全不感兴趣

CF1307F Cow and Vacation

题意:给出一棵树,给定r个特殊点和常数K,q次独立询问两点间是否存在一个不一定简单的路径,满足将起点终点看做特殊点后,路径上相邻两个特殊点的距离都不超过k

请先思考后再展开

将边也看做点,那么就是不超过2k步,于是可以每个特殊点跳k步,领域有交集的两个特殊点就是能相互到达的,实现时可以直接bfs走k步,经过的所有点都是连通的,DSU维护。回答询问时,判断「各自往对方的方向即沿着路径走k步」后到达的点是否连通即可(因为如果走过头了,因为两点间路径唯一,原本一定就不连通),$O(nlogn)$

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
27
28
29
30
31
32
vc<int> to[N];void ins(int x,int y){ to[x].PB(y),to[y].PB(x); }
int dep[N],ff[N][30];
void solve(int x,int fa)
{
dep[x]=dep[fa]+1;ff[x][0]=fa;fo(i,1,20) ff[x][i]=ff[ff[x][i-1]][i-1];
for(auto y:to[x]) if(y!=fa) solve(y,x);
}
int getlca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);fd(t,20,0) if(bin(t)<=dep[x]-dep[y]) x=ff[x][t];if(x==y) return x;
fd(t,20,0) if(ff[x][t]!=ff[y][t]) x=ff[x][t],y=ff[y][t];return ff[x][0];
}
int jump(int x,int wt){ fd(t,20,0) if(wt&bin(t)) x=ff[x][t];return x; }
queue<int> q;int dis[N];
struct DSU{
int fa[N];DSU(){ fo(i,1,N-1) fa[i]=i; }
int findfa(int x){return fa[x]==x?x:fa[x]=findfa(fa[x]);}
void merg(int x,int y){ fa[findfa(x)]=findfa(y);}
}dsu;
void main()
{
int n=qread(),K=qread(),rr=qread();fo(i,2,n){ int x=qread(),y=qread();ins(x,n+i),ins(y,n+i); } solve(1,0);
mem(dis,-1);while(rr--){ int x=qread();dis[x]=0,q.push(x); }
while(sz(q)){ int x=q.front();q.pop();if(dis[x]==K)break;for(auto y:to[x]){if(dis[y]<0)dis[y]=dis[x]+1,q.push(y);dsu.merg(x,y);} }
int q=qread();
while(q--)
{
int x=qread(),y=qread(),z=getlca(x,y);if(dep[x]+dep[y]-2*dep[z]<=K*2) {puts("YES");continue;}
puts( dsu.findfa(dep[x]-dep[z]>=K?jump(x,K):jump(y,dep[x]+dep[y]-2*dep[z]-K))==
dsu.findfa(dep[y]-dep[z]>=K?jump(y,K):jump(x,dep[x]+dep[y]-2*dep[z]-K))?"YES":"NO" );
}
}

CF1307G Cow and Exercise

题意:给出一个简单无向图,q次独立询问,给出配额ad,分配到任意某些边上,最大化1到n的最短路,$n \le 50,q \le 1e5$

请先思考后再展开

我的思路:将当前所有最短路的并集丢入最小割,构造出最小割方案后二分丢权值上去跑dij得出严格次短路并把对之前最小割的方案上每条边加相同的权,让长度与次短路相同,如此不断做,得到若干个阶段,就能回答这个阶段的询问了(n较小,对每个询问枚举每个阶段应该也行)

听起来有丁点道理,然而非常不优美

其实上面的过程中,两条路径长度相同且相交的话,去掉一条最小割不变,也就是重边是没有意义的。然后你会发现这个过程变成了一个最小费用最大流(但并不代表不需要加退流边,果然不懂原理还是不能瞎改),回答询问无脑枚举每个阶段,$ans=\frac{sum+ad}{cnt},sum=cost,cnt=flow$,code

我过了并不代表我上述文字是对的,因为不会所以没有用那种线性规划的方法,xyx有中文题解

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