欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #627 (Div. 3) A~F 解题报告

程序员文章站 2022-03-14 19:20:44
...

题目传送门

A:Yet Another Tetris Problem

思路:如果奇数偶数都存在,则答案为NO,否则为YES

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define dep(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int maxn=4e5+5;
//const double pi=acos(-1.0);
//const double eps=1e-9;
//const ll mo=1e9+7;
int n,m,k;
int a[maxn],c[maxn];
int ans,tmp,cnt;
int flag;
char s[maxn];
bool ok[maxn];
int main()
{
    int T,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        rep(i,0,101) c[i]=0;
        ans=0; flag=0;
        rep(i,1,n)
        {
            scanf("%d",&a[i]);
            if(a[i]&1) ans++;
            else flag++;
        }
        if(ans&&flag) puts("NO");
        else puts("YES");
        //printf("%d\n",ans);
    }
    return 0;
}

B:Yet Another Palindrome Problem

思路:需要注意本题问的是是否有长度大于等于3的子序列构成回文。不难发现,当有两个相同的数距离超过1时答案就存在。否则不存在。

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define dep(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int maxn=4e5+5;
//const double pi=acos(-1.0);
//const double eps=1e-9;
//const ll mo=1e9+7;
int n,m,k;
int a[maxn],c[maxn];
int ans,tmp,cnt;
int flag;
char s[maxn];
bool ok[maxn];
int main()
{
    int T,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        rep(i,0,n+1) c[i]=0;
        ans=0; flag=0;
        rep(i,1,n)
        {
            scanf("%d",&a[i]);
            if(c[a[i]]&&c[a[i]]<i-1) flag=1;
            if(!c[a[i]]) c[a[i]]=i;
        }
        if(!flag) puts("NO");
        else puts("YES");
        //printf("%d\n",ans);
    }
    return 0;
}

C:Frog Jumps

思路:直接二分答案(即最大的一步),然后每次跳最大的一步,再根据LR指令走即可。走不了就继续跳最大的一步。

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define dep(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int maxn=4e5+5;
//const double pi=acos(-1.0);
//const double eps=1e-9;
//const ll mo=1e9+7;
int len,m,k;
int a[maxn],c[maxn];
int ans,tmp,cnt;
int flag;
char s[maxn];
bool ok[maxn];
int jud(int d)
{
    int i=0;
    while(i<=len)
    {
        //cout<<d<<" "<<i<<endl;
        int j=min(i+d,len+1);
        if(j==len+1) return 1;
        while(j>i&&s[j]=='L') j--;
        if(j==i) return 0;
        i=j;
    }
    return 0;
}
int main()
{
    int T,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s+1);
        len=strlen(s+1);
        int ans=len+1;
        int l=1,r=len+1;
        while(l<r){
            int m=(l+r)>>1;
            if(jud(m)) {r=m;ans=m;}
            else l=m+1;
        }
       printf("%d\n",ans);
    }
    return 0;
}

D:Pair of Topics

思路:这道题可以用二分做,也可以用树状数组做。

把ai+aj>bi+bj移项可得bj-aj<ai-bi (i<j)

因此我们把bi-ai和ai-bi都进行排序,然后用两个指针,保证bi-ai<ak-bk,再利用树状数组查询k中小于i的下标数量即可。

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define dep(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int maxn=4e5+5;
//const double pi=acos(-1.0);
//const double eps=1e-9;
//const ll mo=1e9+7;
int n,m,k;
int a[maxn],c[maxn];
int ans,tmp,cnt;
int flag;
char s[maxn];
bool ok[maxn];
struct node
{
    int val;
    int id;
    bool operator<(node aa)const{
        return val<aa.val||(val==aa.val&&id<aa.id);
    }
}aa[maxn];
struct nod
{
    int val;
    int id;
    bool operator<(nod a)const{
        return val<a.val||(val==a.val&&id<a.id);
    }
}bb[maxn];
int lb(int x){return x&(-x);}
void add(int x,int v){
    while(x<maxn){
        c[x]+=v;
        x+=lb(x);
    }
}
int query(int x){
    int sum=0;
    while(x>0){
        sum+=c[x];
        x-=lb(x);
    }
    return sum;
}
int main()
{
    int T,cas=1;
    //scanf("%d",&T);
    //while(T--)
    {
        scanf("%d",&n);
        rep(i,1,n) scanf("%d",&a[i]);
        rep(i,1,n) {
            int x;
            scanf("%d",&x);
            aa[i].val=x-a[i];
            aa[i].id=i;
            bb[i].val=a[i]-x;
            bb[i].id=i;
        }
        ll ans=0;
        sort(aa+1,aa+1+n);
        rep(i,0,maxn-1) c[i]=0;
        rep(i,1,n) add(i,1);
        sort(bb+1,bb+1+n);
        int j=1;
        rep(i,1,n){
            while(aa[i].val>=bb[j].val&&j<=n){
                add(bb[j].id,-1);
                j++;
            }
            ans+=query(aa[i].id-1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

E:Sleeping Schedule

题意:给你n,h,l,r(<=2e3),表示一天有h小时,如果在一天的[l,r]时间内开始睡觉,他就会开心。

再给你n个数a[i],刚开始时刻为0,会依次在上一次睡觉的a[i]小时或者a[i]-1小时后再睡觉。问你最大的开心数。

思路:直接dp[i][j]表示前i天,上一次在第j小时睡觉的最大开心数,然后用a[i]和a[i]-1进行转移即可。注意初始化。

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define dep(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int maxn=2e3+5;
//const double pi=acos(-1.0);
//const double eps=1e-9;
//const ll mo=1e9+7;
int n,m,k,h,l,r;
int a[maxn],c[maxn];
int ans,tmp,cnt;
int flag;
char s[maxn];
bool ok[maxn];
int dp[maxn][maxn];
int main()
{
    int T,cas=1;
    //scanf("%d",&T);
    //while(T--)
    {
        scanf("%d%d%d%d",&n,&h,&l,&r);
        rep(i,0,n)
        rep(j,0,h+1) dp[i][j]=-inf;
        dp[0][0]=0;
        rep(i,1,n)
        {
            scanf("%d",&a[i]);
            rep(j,0,h-1)
            {
                int k=(j+a[i])%h;
                if(l<=k&&k<=r)
                dp[i][k]=max(dp[i][k],dp[i-1][j]+1);
                else dp[i][k]=max(dp[i][k],dp[i-1][j]);
                k=(j+a[i]+h-1)%h;
                if(l<=k&&k<=r)
                dp[i][k]=max(dp[i][k],dp[i-1][j]+1);
                else dp[i][k]=max(dp[i][k],dp[i-1][j]);
            }
        }
        int ans=0;
        rep(i,0,h-1) ans=max(ans,dp[n][i]);
        printf("%d\n",ans);
    }
    return 0;
}

F:Maximum White Subtree

题意:给你n(<=2e5)个点(构成树),再给你每个点为白点还是黑点(白点为1黑点为0),然后给你n-1条边构成树,问你每个点所在的子结构中,白点的数量-黑点的数量的最大值是多少。

思路:我们先确定一个根root,进行树形dp,初始化dp[u]=(1,白点)(-1,黑点)

dp[u]+=max(0,dp[v]) (存在边(u,v))(利用子树更新答案)

这样dp[root]就是root的答案,然后把根加入队列中,再依次往下更新答案(利用父节点更新子节点的答案)

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define dep(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int maxn=2e5+5;
//const double pi=acos(-1.0);
//const double eps=1e-9;
//const ll mo=1e9+7;
int n,m,k,h,l,r;
int a[maxn],c[maxn],fa[maxn];
int ans,tmp,cnt;
int flag;
char s[maxn];
bool ok[maxn];
vector<int>vc[maxn];
int dp[maxn];
void dfs(int u,int f){
    fa[u]=f;
    dp[u]=a[u];
    for(int j=0;j<vc[u].size();j++){
        int v=vc[u][j];
        if(v==f) continue;
        dfs(v,u);
        dp[u]+=max(0,dp[v]);
    }
    //cout<<u<<" "<<dp[u]<<endl;
}
int p[maxn];
int main()
{
    int T,cas=1;
    //scanf("%d",&T);
    //while(T--)
    {
        scanf("%d",&n);
        rep(i,1,n) {c[i]=-1;scanf("%d",&a[i]);if(!a[i]) a[i]=-1;}
        rep(i,1,n-1)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            vc[x].push_back(y);
            vc[y].push_back(x);
        }
        dfs(1,-1);
        rep(i,1,n)c[i]=dp[i];
        queue<int>q;
        q.push(1);
        while(!q.empty()){
            int x=q.front();
            q.pop();ok[x]=1;
            int u=x;
            for(int j=0;j<vc[u].size();j++){
                int v=vc[u][j];
                //cout<<v<<" * "<<endl;
                if(v==fa[u]) continue;
                c[v]=max(c[v],c[u]-max(0,dp[v])+dp[v]);
                if(!ok[v]) q.push(v);
            }
        }
        rep(i,1,n)
        printf("%d%c",c[i],i==n?'\n':' ');
    }
    return 0;
}
/*
8
0 0 0 0 1 0 0 0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
*/

总体来说,这场的题目还是十分简单的,适合新手练习。

相关标签: 比赛总结