Educational Codeforces Round 7

时间：2021-04-07 07:47:05

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=;;i++)

      if(i*(i+)/>=n)

        return printf("%I64d\n",n-i*(i-)/),;

}

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<)printf("0%d",k);

    else printf("%d",k);

}

int main()

{

    scanf("%d:%d%d",&h,&m,&a);

    m+=a;h+=m/;m%=;h%=;

    print(h);printf(":");print(m);

    return ;

}

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=;i<=n;i++)

      {

      scanf("%d",&a[i]);

      f[i]=f[i-]+(a[i]!=a[i-]);

      }

    for(int i=;i<=m;i++)

      {

      scanf("%d%d%d",&l,&r,&x);

      if(f[l]==f[r] && a[l]==x)

        {printf("-1\n");continue;}

      if(a[l]!=x)printf("%d\n",l);else

      printf("%d\n",upper_bound(f+l,f+r,f[l])-f);

      }

    return ;

}

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[];

int main()

{

    scanf("%d",&n);a=,b=n+;

    for(int i=;i<n;i++)f[a]=f[a+n-i]=i,a++,swap(a,b);f[a]=f[*n]=n;

    for(int i=;i<=*n;i++)printf("%d%c",f[i],i==*n?'\n':' ');

    return ;

}

622E - Ants in Leaves    20180919

考虑从根节点连出去的几个子树的答案是多少，对于每个子树，把子树中所有的叶子节点按深度排序，若设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=;

    for(auto nxt:d[cur])if(nxt!=pre)

      x=,dfs(nxt,cur,dep+);

    if(!x)f[++cnt]=dep;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

      scanf("%d%d",&u,&v),

      d[u].push_back(v),

      d[v].push_back(u);

    for(auto i:d[])

      {

      cnt=;

      dfs(i,,);

      sort(f+,f+cnt+);

      for(int i=;i<=cnt;i++)

        f[i]=max(f[i],f[i-]+);

      ans=max(ans,f[cnt]+);

      }

    return printf("%d\n",ans),;

}

622F - The Sum of the k-th Powers    20180317

拉格朗日插值法的经典应用

#include<stdlib.h>

#include<stdio.h>

#include<math.h>

#define N 1000005

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define LL long long

#define MOD 1000000007

LL n,k,t,ans,inv[N],y[N],f[N];

LL qow(LL X,LL Y){return Y?(Y&?X*qow(X,Y-)%MOD:qow(X*X%MOD,Y/)):;}

int main()

{

    scanf("%I64d%I64d",&n,&k);

    inv[]=f[]=t=;

    for(LL i=;i<=k+;i++)

      inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;

    for(LL i=;i<=k+;i++)

      f[i]=f[i-]*inv[i]%MOD;

    for(LL i=;i<=k+;i++)

      y[i]=(y[i-]+qow(i,k))%MOD;

    if(n<=k+)return printf("%I64d\n",y[n]),;

    for(LL i=;i<=k+;i++)

      t*=(n-i)%MOD,t%=MOD;

    for(LL i=;i<=k+;i++)

      {

      LL s=((i-k)%)?-:,res=y[i];

      res*=t*qow((n-i)%MOD,MOD-)%MOD,res%=MOD;

      res*=f[i-]*f[k+-i]%MOD,res%=MOD;

      ans+=(res*s+MOD)%MOD,ans%=MOD;

      }

    printf("%I64d\n",ans);

    return ;

}

相关文章