Educational Codeforces Round 7
分类:
IT文章
•
2025-01-07 22:02:37
622A - Infinite Sequence 20171123
暴力枚举(n)在哪个区间即可，时间复杂度为(O(sqrt{n}))
![]()
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long n;
int main()
{
scanf("%I64d",&n);
for(long long i=1;;i++)
if(i*(i+1)/2>=n)
return printf("%I64d
",n-i*(i-1)/2),0;
}
View Code
622B - The Time 20171123
没什么好说的......
![]()
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int h,m,a;
void print(int k)
{
if(k<10)printf("0%d",k);
else printf("%d",k);
}
int main()
{
scanf("%d:%d%d",&h,&m,&a);
m+=a;h+=m/60;m%=60;h%=24;
print(h);printf(":");print(m);
return 0;
}
View Code
622C - Not Equal on a Segment 20171123
设f[i]为前i个数里不同数的个数，然后瞎几把乱搞就好了_(:з」∠)_
![]()
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#define N 1000001
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,a[N],l,r,x,_,f[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i]=f[i-1]+(a[i]!=a[i-1]);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&l,&r,&x);
if(f[l]==f[r] && a[l]==x)
{printf("-1
");continue;}
if(a[l]!=x)printf("%d
",l);else
printf("%d
",upper_bound(f+l,f+r,f[l])-f);
}
return 0;
}
View Code
622D - Optimal Number Permutation 20171123
构造题...朝着让结果为0的目标去就好了
![]()
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,a,b,f[1000001];
int main()
{
scanf("%d",&n);a=1,b=n+1;
for(int i=1;i<n;i++)f[a]=f[a+n-i]=i,a++,swap(a,b);f[a]=f[2*n]=n;
for(int i=1;i<=2*n;i++)printf("%d%c",f[i],i==2*n?'
':' ');
return 0;
}
View Code
考虑从根节点连出去的几个子树的答案是多少，对于每个子树，把子树中所有的叶子节点按深度排序，若设f[i]为第i个叶子爬到子树的根结点所需要的时间，则f[i]的初始值为他的深度，且有(f_i=max(f_{i},f_{i-1}+1))。最终答案就是所有子树对应答案的最大值
![]()
#include<bits/stdc++.h>
using namespace std;
#define N 500001
int n,u,v,ans,cnt,f[N];
vector<int>d[N];
void dfs(int cur,int pre,int dep)
{
int x=0;
for(auto nxt:d[cur])if(nxt!=pre)
x=1,dfs(nxt,cur,dep+1);
if(!x)f[++cnt]=dep;
}
int main()
{
scanf("%d",&n);
for(int i=2;i<=n;i++)
scanf("%d%d",&u,&v),
d[u].push_back(v),
d[v].push_back(u);
for(auto i:d[1])
{
cnt=0;
dfs(i,1,0);
sort(f+1,f+cnt+1);
for(int i=2;i<=cnt;i++)
f[i]=max(f[i],f[i-1]+1);
ans=max(ans,f[cnt]+1);
}
return printf("%d
",ans),0;
}
