Codeforces Round #627 (Div. 3)

A.
给n个数,可以进行无限次操作,每次可以使某个数+2,或者使所有数-1,问能否使得最后都为0
解 因为只能单个+2和总体-1,那么奇偶性不变,判断全奇全偶即可

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
int b[2];
void work()
{
    b[0]=b[1]=0;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        b[x&1]++;
    }
    if(b[0]&&b[1]){
        printf("NO\n");
    }else{
        printf("YES\n");
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

B.
给n个数,问是否存在3个以上的回文序列。
最少3个,那么就是只需要2个相同的,需要注意的是 这两个相同的数不能相邻,不然中间找不到第三个数。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
int a[5005];
int b[5005];
void work()
{
    memset(b,0,sizeof(b));
    int n;
    scanf("%d",&n);
    bool f=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(b[a[i]]>=2||b[a[i]]==1&&a[i-1]!=a[i]){
            f=1;
        }else{
            b[a[i]]++;
        }
    }
    if(f){
        printf("YES\n");
    }else{
        printf("NO\n");
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

C.
给一段字符串,在L时可以往左走1-d步,在R时可以往右走1-d步,问能走完的最小的d
如果存在一段连续的L,那么如果d小于这段连续的L,那么不管怎么走,都会落在这一段L上,那么必定走不到这一段的后面,所以答案就是连续L的最大值+1。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
char a[200005];
void work()
{
    scanf("%s",a);
    int l=strlen(a);
    int ans=0;
    int cnt=0;
    for(int i=0;i<l;i++){
        if(a[i]=='L'){
            cnt++;
        }else{
            ans=max(ans,cnt);
            cnt=0;
        }
    }
    ans=max(ans,cnt);
    printf("%d\n",ans+1);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

D.
求i<j并且\(a_i+b_i>a_j+b_j\)的对数。
可以变成 \(a_i-a_j+b_i-b_j>0\),那么按照\(a_i-a_j\)从小到大排序,枚举每一项,二分找到满足该条件的最前面一项,后面的均满足,加上即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
int a[200005],b[200005],c[200005];
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    }
    for(int i=1;i<=n;i++){
        c[i]=a[i]-b[i];
    }
    sort(c+1,c+n+1);
    ll ans=0;
    for(int i=1;i<=n;i++){
        int l=i+1,r=n;
        while(l<=r){
            int m=(l+r)>>1;
            if(c[i]+c[m]>0)r=m-1;
            else l=m+1;
        }
        ans+=n-l+1;
    }
    printf("%lld\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

E.
给n个时间和每天的时间长度h,然后给了一个l和r,如果醒来的时间落在L,R中,那么满意度加1,问满意度最大值,n个时间a[i]为每次睡眠的时间,可以睡满a[i]或者睡a[i]-1小时。
dp,dp[i][j]代表第i次睡眠后,落在j时间的最高满意度,然后根据a[i]和a[i]-1转移即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
ll dp[2005][2005];
int a[2005];
int b[2005];
void work()
{
    int n,h,l,r;
    scanf("%d%d%d%d",&n,&h,&l,&r);
    for(int i=l;i<=r;i++){
        b[i]=1;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<h;j++){
            dp[i][j]=-99999;
        }
    }
    dp[1][a[1]]=b[a[1]];
    dp[1][a[1]-1]=b[a[1]-1];
    for(int i=2;i<=n;i++){
        for(int j=0;j<h;j++){
            dp[i][(a[i]+j)%h]=max(dp[i][(a[i]+j)%h],dp[i-1][j]+b[(a[i]+j)%h]);
            dp[i][(a[i]+j-1)%h]=max(dp[i][(a[i]+j-1)%h],dp[i-1][j]+b[(a[i]+j-1)%h]);
        }
    }
    ll ans=0;
    for(int j=0;j<h;j++){
        ans=max(ans,dp[n][j]);
    }
    printf("%d\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

F.
给n个点的树,每个点涂上了白色和黑色,1为白,0为黑,然后给出n-1条边,问每个点的子树(包含这个点的树均可)的白色-黑色的最大值。
换根dp,先就把1当做根, 跑一个dp,求出每个点的白色-黑色的最大值(这个应该是很简单的)。然后就是换根dp(就是把当前的点作为根,把当前点的父节点作为子节点),换根时注意past已经不是父节点了,所以要将past在第一次dp时求出来的答案减去now这边的贡献(那么得到的就是以now为根时,past的子树的贡献),等算完now之后再加回去。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
vector<int>v[200005];
int a[200005];
int b[200005];
int ans[200005];
int dfs(int past,int now){
    int res=0;
    for(int i=0;i<v[now].size();i++){
        if(v[now][i]==past)continue;
        b[v[now][i]]=dfs(now,v[now][i]);
        res+=max(b[v[now][i]],0);
    }
    return res+a[now];
}
void dp(int past,int now)
{
    ans[now]=max(ans[past],0)+b[now];//计算父节点方向的贡献
    for(int i=0;i<v[now].size();i++){
        if(v[now][i]==past)continue;
        ans[now]-=max(b[v[now][i]],0);
        dp(now,v[now][i]);
        ans[now]+=max(b[v[now][i]],0);
    }
}
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]==0){
            a[i]=-1;
        }
    }
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    b[1]=dfs(0,1);
    dp(0,1);
    for(int i=1;i<=n;i++){
        printf("%d ",ans[i]);
    }
    printf("\n");
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注