对于CodeforcesRound#483(Div.1)[Thanks,BotanInvestmentsandVictorShaburov#!]E.NNcountry感兴趣的读者，本文将会是一篇不错的
对于Codeforces Round #483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov#!] E. NN country感兴趣的读者，本文将会是一篇不错的选择，并为您提供关于CF-Codeforces Round #483 (Div. 2) A~D、CF-Codeforces Round #483 (Div. 2)-C-Finite or not?、Codeforces 1099 B. Squares and Segments-思维(Codeforces Round #530 (Div. 2))、Codeforces 832D(Misha, Grisha and Underground,LCA)的有用信息。
本文目录一览：- Codeforces Round #483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov#!] E. NN country
- CF-Codeforces Round #483 (Div. 2) A~D
- CF-Codeforces Round #483 (Div. 2)-C-Finite or not?
- Codeforces 1099 B. Squares and Segments-思维(Codeforces Round #530 (Div. 2))
- Codeforces 832D(Misha, Grisha and Underground,LCA)
![Codeforces Round #483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov#!] E. NN country](http://www.gvkun.com/zb_users/upload/2025/02/3b46a789-6149-403f-a3ac-915ba953f6dd1738915564779.jpg "Codeforces Round #483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov#!] E. NN country")
Codeforces Round #483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov#!] E. NN country
总结
以上是小编为你收集整理的Codeforces Round #483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov#!] E. NN country全部内容。
如果觉得小编网站内容还不错，欢迎将小编网站推荐给好友。
CF-Codeforces Round #483 (Div. 2) A~D
总结
以上是小编为你收集整理的CF-Codeforces Round #483 (Div. 2) A~D全部内容。
如果觉得小编网站内容还不错，欢迎将小编网站推荐给好友。
CF-Codeforces Round #483 (Div. 2)-C-Finite or not?
总结
以上是小编为你收集整理的CF-Codeforces Round #483 (Div. 2)-C-Finite or not?全部内容。
如果觉得小编网站内容还不错，欢迎将小编网站推荐给好友。
Codeforces 1099 B. Squares and Segments-思维(Codeforces Round #530 (Div. 2))
B. Squares and Segments
Little Sofia is in fourth grade. Today in the geometry lesson she learned about segments and squares. On the way home, she decided to draw nn squares in the snow with a side length of 11. For simplicity, we assume that Sofia lives on a plane and can draw only segments of length 11, parallel to the coordinate axes, with vertices at integer points.
In order to draw a segment, Sofia proceeds as follows. If she wants to draw a vertical segment with the coordinates of the ends (x,y)(x,y) and (x,y+1)(x,y+1). Then Sofia looks if there is already a drawn segment with the coordinates of the ends (x′,y)(x′,y) and (x′,y+1)(x′,y+1) for some x′x′. If such a segment exists, then Sofia quickly draws a new segment, using the old one as a guideline. If there is no such segment, then Sofia has to take a ruler and measure a new segment for a long time. Same thing happens when Sofia wants to draw a horizontal segment, but only now she checks for the existence of a segment with the same coordinates xx, x+1x+1 and the differing coordinate yy.
For example, if Sofia needs to draw one square, she will have to draw two segments using a ruler:
After that, she can draw the remaining two segments, using the first two as a guide:
If Sofia needs to draw two squares, she will have to draw three segments using a ruler:
After that, she can draw the remaining four segments, using the first three as a guide:
Sofia is in a hurry, so she wants to minimize the number of segments that she will have to draw with a ruler without a guide. Help her find this minimum number.
The only line of input contains a single integer nn (1≤n≤1091≤n≤109), the number of squares that Sofia wants to draw.
Print single integer, the minimum number of segments that Sofia will have to draw with a ruler without a guide in order to draw nn squares in the manner described above.
122344
题意就是找最接近当前数的一个数的两个因数，比如41，就是6*7，就是6+7的结果。如果按照41来算，那么需要41+1=42，如果是按照42来算，就是6+7，还有10，最接近的是3+4，是12的，就是这样的题目。
代码:
1 //B
2 #include<iostream>
3 #include<cstdio>
4 #include<cstring>
5 #include<algorithm>
6 #include<bitset>
7 #include<cassert>
8 #include<cctype>
9 #include<cmath>
10 #include<cstdlib>
11 #include<ctime>
12 #include<deque>
13 #include<iomanip>
14 #include<list>
15 #include<map>
16 #include<queue>
17 #include<set>
18 #include<stack>
19 #include<vector>
20 using namespace std;
21 typedef long long ll;
22
23 const double PI=acos(-1.0);
24 const double eps=1e-6;
25 const ll mod=1e9+7;
26 const int inf=0x3f3f3f3f;
27 const int maxn=2e7+10;
28 const int maxm=100+10;
29 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
30
31 int main()
32 {
33 int n;
34 cin>>n;
35 int p=sqrt(n);
36 int ans=inf,flag=0;
37 if(n==1){
38 ans=2;
39 cout<<ans<<endl;
40 return 0;
41 }
42 if(p*p==n)ans=min(2*p,ans);
43 else if(p*(p+1)>=n) ans=min(p+p+1,ans);
44 else ans=min(2*(p+1),ans);
45 cout<<ans<<endl;
46 }
Codeforces 832D(Misha, Grisha and Underground,LCA)
题意：在一棵生成树上，给出了三个点，求三个点之间最大的相交点数，CF 难度 1900。
题解：求出三个 lca，并取深度最大的那个，就是我们要的三岔路口 K，然后分别求出 K 到 a，b，c 三点的路径长度，取最大值 + 1 就是答案。为什么是取深度最大的呢？因为只有当深度是最大的时候设该点为 K，这个 K 为三岔路口，每一个 a，b，c 到 K 的距离都不会用重复，否则如果取的不是最深的，可能造成重复的情况，这个需要避免。然后找到这个 K 之后，ans 就是 a，b，c 三点分别到 K 的距离 + 1 即可（+1 是因为本身也算）。
一开始没做出来的原因：不知道如何找这个岔口.... 以为需要把岔口当做 root 来弄，然后就需要一次又一次的重复更新建立 LCA 表，就很麻烦。其实求岔口只需要以 1 作为 root，然后 a，b，c 三个点两两求 LCA 然后取深度最大的 LCA 就行了.... 树上每 2 个点的距离 dis (u,v)=depth [u]+depth [v]-2*depth (LCA (u,v)], 好吧是我菜了
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define endl ''\n''
#define mem(a,b) memset(a,b,sizeof(a))
#define IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int maxn=1e5+5;
int tot,head[maxn];
struct E{
int to,next;
}edge[maxn<<1];
void add(int u,int v){
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
}
int n,m,a[maxn],fa[maxn][40],depth[maxn],vis[maxn];
void dfs(int s,int step){
depth[s]=step;vis[s]=1;
for(int i=head[s];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(!vis[v]) fa[v][0]=s,dfs(v,step+1);
}
}
void bz(){
for(ll j=1;j<=30;j++){
for(ll i=1;i<=n;i++){
fa[i][j]=fa[fa[i][j-1]][j-1];
}
}
}
ll LCA(ll u,ll v){
if(depth[u]<depth[v]) swap(u,v);
ll dc=depth[u]-depth[v];
for(ll i=0;i<30;i++){
if((1<<i)&dc){
u=fa[u][i];
}
}
if(u==v) return u;
for(ll i=29;i>=0;i--){
if(fa[u][i]!=fa[v][i]){
u=fa[u][i];
v=fa[v][i];
}
}
u=fa[u][0];
return u;
}
int dis(int u,int v){
return depth[u]+depth[v]-2*depth[LCA(u,v)];
}
int main(){
scanf("%d%d",&n,&m);mem(head,-1);
for(int i=2;i<=n;i++){
int x;scanf("%d",&x);
add(i,x);add(x,i);
}
dfs(1,1);
bz();
while(m--){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
int l1=LCA(a,b);
int l2=LCA(a,c);
int l3=LCA(b,c);
if(depth[l2]>depth[l1]) l1=l2;
if(depth[l3]>depth[l1]) l1=l3;
cout<<max(dis(l1,a),max(dis(l1,b),dis(l1,c)))+1<<endl;
}
}
今天关于Codeforces Round #483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov#!] E. NN country的分享就到这里，希望大家有所收获，若想了解更多关于CF-Codeforces Round #483 (Div. 2) A~D、CF-Codeforces Round #483 (Div. 2)-C-Finite or not?、Codeforces 1099 B. Squares and Segments-思维(Codeforces Round #530 (Div. 2))、Codeforces 832D(Misha, Grisha and Underground,LCA)等相关知识，可以在本站进行查询。
本文标签：
