Educational Codeforces Round 15 套题

时间：2024-01-18 09:28:56

这套题最后一题不会，然后先放一下，最后一题应该是大数据结构题

A:求连续最长严格递增的的串，O（n）简单dp

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

using namespace std;

typedef  long long LL;

const int N = 1e5+;

const int INF = 0x3f3f3f3f;

int n,dp[N],a[N],cnt,mx;

int main(){

  scanf("%d",&n);a[]=INF;

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

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

    dp[i]=;

    if(a[i]>a[i-])dp[i]=dp[i-]+;

    mx=max(mx,dp[i]);

  }

  printf("%d\n",mx);

  return ;

}

B:水题，map乱搞

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

typedef  long long LL;

const int N = 1e5+;

const int INF = 2e9;

map<int,int>mp;

int a[],cnt;

int main(){

  for(int i=;;++i){

    if((1ll<<i)>INF)break;

    a[++cnt]=(<<i);

  }

  LL ret=;

  int x,n;scanf("%d",&n);

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

    scanf("%d",&x);

    for(int j=cnt;j>;--j){

      if(a[j]<=x)break;

      int tmp=a[j]-x;

      if(mp.find(tmp)!=mp.end())

        ret+=mp[tmp];

    }

    if(mp.find(x)==mp.end())mp[x]=;

    ++mp[x];

  }

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

  return ;

}

C:一个典型的二分题，judge如何判断全被覆盖？只要用一下离线求和数组非0就好

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

typedef  long long LL;

const int N = 1e5+;

const int INF = 2e9;

LL a[N],b[N];

int n,m,c[N];

bool judge(LL r){

  memset(c,,sizeof(c));

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

    int x=lower_bound(a+,a++n,b[i]-r)-a;

    int y=upper_bound(a+,a++n,b[i]+r)-a;

    ++c[x];--c[y];

  }

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

    c[i]+=c[i-];

    if(!c[i])return false;

  }

  return true;

}

int main(){

  scanf("%d%d",&n,&m);

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

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

  sort(a+,a++n);

  n=unique(a+,a++n)-a-;

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

    scanf("%I64d",&b[i]);

  sort(b+,b++m);

  m=unique(b+,b++m)-b-;

  LL l=,r=INF;

  while(l<r){

    LL mid=(l+r)>>;

    if(judge(mid))r=mid;

    else l=mid+;

  }

  printf("%I64d\n",(l+r)>>);

  return ;

}

D：一个简单的分类讨论，因为最多走k，以k为周期即可

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

typedef  long long LL;

const int N = 1e5+;

const int INF = 2e9;

LL d,k,a,b,t;

int main(){

  scanf("%I64d%I64d%I64d%I64d%I64d",&d,&k,&a,&b,&t);

  if(d<=k){

    printf("%I64d\n",d*a);

    return ;

  }

  LL ret=k*a;d-=k;

  if(d<=k){

    ret+=min(d*a+t,d*b);

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

    return ;

  }

  LL t1=k*a+t,t2=k*b;

  if(t2<=t1){

    printf("%I64d\n",ret+d*b);

    return ;

  }

  else {

    ret+=d/k*t1;

    d-=d/k*k;

    if(d==){printf("%I64d\n",ret);return ;}

    t1=t+d*a,t2=d*b;

    ret+=min(t1,t2);

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

  }

  return ;

}

E:求从每个点出发路径长度为k的边权和以及边权最小值，刚开始还以为是快速幂，结果发现发现这条路唯一确定，直接倍增即可

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

typedef  long long LL;

const int N = 1e5+;

const int INF = 2e9;

struct Node{

  int v,mn;

  LL sum;

}f[N][];

LL retsum[N],k;

int n,retmin[N],cur[N];

void solve(){

  for(int j=;(1ll<<j)<=k;++j)if(k&(1ll<<j)){

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

        retsum[i]+=f[cur[i]][j].sum;

        if(retmin[i]==-)retmin[i]=f[cur[i]][j].mn;

        else retmin[i]=min(retmin[i],f[cur[i]][j].mn);

        cur[i]=f[cur[i]][j].v;

     }

  }

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

    printf("%I64d %d\n",retsum[i],retmin[i]);

}

int main(){

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

  for(int i=;i<n;++i)scanf("%d",&f[i][].v),cur[i]=i,retmin[i]=-;

  for(int i=;i<n;++i)scanf("%d",&f[i][].mn),f[i][].sum=f[i][].mn;

  for(int j=;(1ll<<j)<=k;++j){

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

        f[i][j].v=f[f[i][j-].v][j-].v;

        f[i][j].sum=f[i][j-].sum+f[f[i][j-].v][j-].sum;

        f[i][j].mn=min(f[i][j-].mn,f[f[i][j-].v][j-].mn);

     }

  }

  solve();

  return ;

}

F：不会，看了看别人的代码，并不能看懂，还是太弱

相关文章