Tree Destruction - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:树的直径。
定理：在一棵树上，从任意节点 y 开始进行一次 DFS，到达的距离其最远的节点 z 必为直径的一端。 第一次dfs1(),从任意一个点,到达的最远的点必然是直径两端的其中一个。 再从找到的端点开始dfs1(),找到另一个端点。这样就可以o(n)确定该树的直径.得到直径的端点S和T. 再两次dfs2(),分别得到S和T到达其他每个点的距离. 之后就可以从度为1的点x开始删除,每次都选和x更远的端点.并且删除x. 最后再处理剩下的直径的点.
int n;
vector<int> vct[200005];
int S=0,T=0,maxd=0,tag=0,typ=0;
int dis[2][200005];
int du[200005];
vector<array<int,3>> ans;
int sum=0;
queue<int> que;
void dfs1(int s,int d,int fa){ 求从s点出发,可以达到最远的点.
if(d>maxd){
if(!tag) S=s;
else T=s;
maxd=d;
}
for(auto v:vct[s]) if(v!=fa) dfs1(v,d+1,s);
}
void dfs2(int s,int d,int fa){ 从端点S/T出发到达其他点的距离
dis[typ][s]=d;
for(auto v:vct[s]) if(v!=fa) dfs2(v,d+1,s);
}
void process(int op){
while(que.size()){
int cur=que.front();
que.pop();
du[cur]--;
if(op==1){
if(dis[0][cur]>=dis[1][cur]) ans.emplace_back(array{S,cur,cur}),sum+=dis[0][cur];
else ans.emplace_back(array{T,cur,cur}),sum+=dis[1][cur];
}
else if(op==2) ans.emplace_back(array{S,cur,cur}),sum+=dis[0][cur];
for(auto v:vct[cur]) {
du[v]--;
if(du[v]==1) que.emplace(v);
}
}
}
题意:从树上选两个叶子节点，把他们的距离加到ans中，并且删去其中一个节点。求剩下一个点时的ans最大值。
Tree Destruction
https://www.luogu.com.cn/problem/CF911F
定理：在一棵树上，从任意节点 y 开始进行一次 DFS，到达的距离其最远的节点 z 必为直径的一端。
第一次dfs1(),从任意一个点,到达的最远的点必然是直径两端的其中一个。
再从找到的端点开始dfs1(),找到另一个端点。这样就可以o(n)确定该树的直径.得到直径的端点S和T.
再两次dfs2(),分别得到S和T到达其他每个点的距离.
之后就可以从度为1的点x开始删除,每次都选和x更远的端点.并且删除x.
最后再处理剩下的直径的点.
void solve(){ 补B 选叶子 o(n)
cin>>n;
for(int i=1;i<=n-1;i++){
int u,v; cin>>u>>v;
vct[u].emplace_back(v);
vct[v].emplace_back(u);
du[u]++,du[v]++;
}
tag=0,maxd=0,dfs1(1,0,0);
tag=1,maxd=0,dfs1(S,0,0);
typ=0,dfs2(S,0,0);
typ=1,dfs2(T,0,0);
for(int i=1;i<=n;i++) if(du[i]==1&&i!=S&&i!=T) que.emplace(i);
du[S]=0,du[T]=0;
process(1);
que.emplace(T);
process(2);
cout<<sum<<endl;
for(auto a:ans) cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
}DivRem Number - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:
N%m=N-(N/m)*m 移项N=(m+1)*(N/m), 那么(m+1)是N的因子 , 那么枚举N的因子即可
题意:给定N,求满足(N/m)=N%m的m的总和. 除法全都是向下取整
DivRem Number
https://www.luogu.com.cn/problem/AT_diverta2019_d
N%m=N-(N/m)*m
移项N=(m+1)*(N/m), 那么(m+1)是N的因子 , 那么枚举N的因子即可
void solve(){ 补G o(sqrt(N))
int N; cin>>N;
int ans=0;
for(int i=0;i<=sqrt(N);i++){
if(N%(i+1)==0){ i是在枚举m的值,但是i不是因子,i+1才是因子
int x=N/(i+1); 另一个因子
if(i!=0&&N==(i+1)*(N/i)) ans+=i;
if(x-1!=0&&N==x*(N/(x-1))) ans+=x-1; x=m+1,那么m=x-1.
}
}
cout<<ans;
}Beautiful Mirrors - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:还是不懂。。
const int mod=998244353;
int quickpow(int a,int b){
int res=1;
while(b){
if(b&1) res*=a,res%=mod;
a*=a,a%=mod;
b>>=1;
}
return res;
}
定义f[i]为到达第i天，并且第i天也快乐的期望天数.
思路:第i天询问失败，从头开始。此时概率为1-p，消耗天数为f[i-1]+1+f[i]。乘上概率，代价为(1-pi)(f[i-1]+1+f[i]).
第i天询问成功。此时概率为p，消耗天数为f[i-1]+1。乘上概率，代价为pi*(f[i-1]+1).
那么f[i]=pi*(f[i-1]+1)+(1-pi)(f[i-1]+1+f[i]).
整理有f[i]=( (f[i-1]+1) / (pi/100) ). 注意除法取mod用逆元.
此处解释,询问失败时消耗天数为 f[i-1]+1+f[i] 是因为：
当前要重新回到第i天，所以需要加f[i]. 而到达第i天之前需要先到达i-1天并且再+1才能回到第i天.
还是不懂。。为什么不用考虑回到i-2天然后加一天到达i-1天，然后再加一天回到第i天?i-3?i-4?..
官方题解: https://codeforces.com/blog/entry/71995
标签：cur,int,max,void,tr,热身,2024,tag,友谊赛
From： https://blog.csdn.net/qq_42643660/article/details/140656753