Articles10
Tags2
Categories0

Codeforces Round 627 (Div.3)


这篇题解更新于赛时,所以准确度不能保证(可能被hack

传送门

整体难度 都很简单

upd:看起来大家都AK了嘛,确实简单

A. Yet Another Tetris Problem

看起来很吓人,实际上就是俄罗斯方块的规则,判一下所有元素的奇偶性是否相同就好惹

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
int n,a[110];
void solve(){
    scanf("%d",&n);int f1=0,f2=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);if(a[i]%2) f1=1;else f2=1;
    }if(f1&&f2) printf("NO\n");else printf("YES\n");
}
int main(){
    int t;scanf("%d",&t);while(t--) solve();
}

B. Yet Another Palindrome Problem

找相距最远的相同数,一对就行 别读入一半就return,会WA5 呜呜呜

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
int n,a[5050];
map<int,int>mp;
void solve(){
    scanf("%d",&n);mp.clear();int flag=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(mp[a[i]]){
            if(i-mp[a[i]]>1) flag=1;
        }else mp[a[i]]=i;
    }if(flag) printf("YES\n");
    else printf("NO\n");
}
int main(){
    int t;scanf("%d",&t);while(t--) solve();
}

C. Frog Jumps

看起来很难,实际上发现,如果你能跳到L块,那为什么不跳他前面的R块呢,反正也是要会到R才能跳到终点。找最大的两个R的间距,模拟就完事了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
char ch[maxn];
void solve(){
    scanf("%s",ch+1);int n=strlen(ch+1);int now=0,ans=0;
    for(int i=1;i<=n;i++){
        if(ch[i]=='R') ans=max(ans,i-now),now=i;
    }ans=max(ans,n+1-now);printf("%d\n",ans);
}
int main(){
    int t;scanf("%d",&t);while(t--) solve();
}

D. Pair of Topics

简单的一批,把good公式转换为ai-bi+aj-bj>0就好了,另ci=ai-bi,对ci排个序二分就完事。

不用二分 双指针也是可以的 更快哦,不过我写炸了QAQ

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
ll a[maxn];
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++){
        ll x;scanf("%lld",&x);a[i]-=x;
    }sort(a+1,a+n+1);ll ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]>0){
            ans+=n-i;continue;
        }int po=upper_bound(a+1,a+n+1,-a[i])-a;
        ans+=(n-po+1);
    }printf("%lld\n",ans);
}

E. Sleeping Schedule

看这数据范围就知道dp

dpij表示到第i个,提前了j个小时睡的最大值,因为每次只能提前一个小时,所以最多提前n个小时,复杂度O(N2)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
int dp[2020][2020],a[2020];
int n,h,l,r;
int check(int x){
    x=(x+h)%h;
    if(x>=l&&x<=r) return 1;return 0;
}
int main(){
    scanf("%d%d%d%d",&n,&h,&l,&r);int now=0;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){ now+=a[i];
        for(int j=0;j<=i;j++){
            if(!j) dp[i][j]=dp[i-1][j]+check(now-j);
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+check(now-j);
        }
    }int ans=0;for(int i=0;i<=n;i++) ans=max(ans,dp[n][i]); printf("%d\n",ans);
}

F. Maximum White Subtree

DIV3 经典最后一题树的题

树上dp

思路:随便另一个点为根,这里我们另第一个点为根,那么先求出经过第一个点的答案(这里表示为ans[1],下面同理)那么我们接下来就要换根dp.既然是换根了,那么我们只要求出第一个点的转移方法,接下来如法炮制就好惹。

那么我们发现,如果从节点1要跳转到它的孩子节点,比如节点2,那么ans[2]=max(a[1],0)+a[i];

这里的a[i]代表的是i节点的子树的答案的最大值(肯定会取到i节点),而且,因为换根了,由父亲节点往子节点递归的时候,要减去当前要求的子节点的贡献,递归完再加上就好了,具体可以看代码。

其中 以i节点为根的子树对i的父亲节点产生的贡献为max(a[i],0)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
vector<int>g[maxn];
int a[maxn],n,ans[maxn],cl[maxn];
int dfs(int u,int f){ //求a[i]
    int res=0;int x=1;if(!cl[u]) x=-1;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];if(v==f) continue;
        a[v]=dfs(v,u);res+=max(a[v],0);
    }return res+x;
}void dp(int u,int f){
    ans[u]=max(ans[f],0)+a[u];//更新该点的答案
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];if(v==f) continue;
        ans[u]-=max(a[v],0);dp(v,u);ans[u]+=max(a[v],0);//减去贡献 再还原
    }
}
int main(){
    scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&cl[i]);
    for(int i=1;i<n;i++){
        int a,b;scanf("%d%d",&a,&b);
        g[a].push_back(b);g[b].push_back(a);
    }a[1]=dfs(1,0);dp(1,0);
    for(int i=1;i<=n;i++){
        printf("%d ",ans[i]);
    }
}

div1.2我唯唯诺诺 div3我重拳出击(然而并没有

Author:西瓜喵喵.
Link:https//:ForgGYLH.github.io/2020/03/12/cf627/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可