碎碎念
忽然想起这个又断更了许久的blog，断更的起因是ll第一次集中的时候讲的话
”不要满足于每次打完cf，过掉了前面几道题，然后水出一篇题解“（大致意思）
自我总结下来，平时提升自我的方法只有两种，或者说一种
一是去学习新的算法，用这个新的算法去解题
二是去补题，补之前的比赛中遇到的不会做的题
本质上都是去学会自己不会的东西，而简单的打一场比赛，做出几道题，并不能改变什么
想起之前刷到的大佬的经历，一句话印象挺深刻的
”希望以后去翻cf的比赛记录时，看到的是一片绿而不是一片蓝“
距离比赛也只有一个月不到的时间了，所以赛前定一个小目标
在保持一定的vp频率以及每一场vp都补题到金牌线的前提下，补完打过的所有div1以下的题
CF1714F Build a Tree and That Is It
构造一棵树，使其满足节点数为n，dis(1,2)=x,dis(2,3)=y,dis(1,3)=z
solution
很显然的事情是将1作为根，那么x和z分别为2和3的深度
有dis(2,3)=dep(2)+dep(3)-2*dep(lca(2,3))即dep(lca(2,3))=(x+z-y)/2
直接以1,2,3,lca(2,3)四个点为基础构造即可
需要注意的是三种特殊情况即lca(2,3)=1/2/3的情况
#include<bits/stdc++.h>
using namespace std;
int T,n,x,y,z,f[2000010];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> T;
while(T--)
{
cin >> n >> x >> y >> z;
int k=x+z-y;
if(k&1||k<0)
{
cout << "NO\n";
continue;
}
k/=2;
if(k>x||k>z)
{
cout << "NO\n";
continue;
}
for(int i=1;i<=n;i++)
f[i]=1;
int cnt=4;
if(k==0)
{
cnt--;
f[2]=1,f[3]=1;
for(int i=1;i<x;i++)
f[++cnt]=f[2],f[2]=cnt;
for(int i=1;i<z;i++)
f[++cnt]=f[3],f[3]=cnt;
}
else if(k==x)
{
cnt--;
f[2]=1,f[3]=2;
for(int i=1;i<k;i++)
f[++cnt]=f[2],f[2]=cnt;
for(int i=k+1;i<z;i++)
f[++cnt]=f[3],f[3]=cnt;
}
else if(k==z)
{
cnt--;
f[3]=1,f[2]=3;
for(int i=1;i<k;i++)
f[++cnt]=f[3],f[3]=cnt;
for(int i=k+1;i<x;i++)
f[++cnt]=f[2],f[2]=cnt;
}
else
{
f[4]=1,f[2]=4,f[3]=4;
for(int i=1;i<k;i++)
f[++cnt]=f[4],f[4]=cnt;
for(int i=k+1;i<x;i++)
f[++cnt]=f[2],f[2]=cnt;
for(int i=k+1;i<z;i++)
f[++cnt]=f[3],f[3]=cnt;
}
if(cnt>n)
{
cout << "NO\n";
continue;
}
cout << "YES\n";
for(int i=2;i<=n;i++)
cout << i << " " << f[i] << endl;
}
return 0;
}CF1714G Path Prefixes
给你一棵树，其每一条边上有两种权值a，b
对于每一个节点求出，从根节点向该节点引出的最长路径
满足路径上b权值的和不超过根节点到该节点a权值的和
solution
对于每次询问直接倍增去找第一个不符合要求的点即可
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define N 200010
#define K 20
using namespace std;
struct node{int to,a,b;};
int T,n,d[N],f[N][K];
ll s[N][2];
vector<node>e[N];
void dfs(int u,int fa)
{
for(auto x:e[u])
{
int v=x.to;
if(v==fa)continue;
s[v][0]=s[u][0]+x.a;
s[v][1]=s[u][1]+x.b;
d[v]=d[u]+1,f[v][0]=u;
for(int i=1;i<K;i++)
f[v][i]=f[f[v][i-1]][i-1];
dfs(v,u);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> T;
while(T--)
{
cin >> n;
for(int i=1;i<=n;i++)
e[i].clear();
for(int i=2;i<=n;i++)
{
int x,y,z;
cin >> x >> y >> z;
e[x].pb({i,y,z});
}
dfs(1,0);
for(int i=2;i<=n;i++)
{
int k=i;
for(int j=K-1;j>=0;j--)
if(s[f[k][j]][1]>s[i][0])
k=f[k][j];
if(s[i][1]<=s[i][0])
cout << d[i] << " ";
else cout << d[k]-1 << " ";
}
cout << endl;
}
return 0;
}
Comments NOTHING