Codeforces Round #627(Div.3)题解

A题
Yet Another Tetris Problem

题意：
俄罗斯方块，从1到n每个位置的初始高度是ai，每行填满可以消掉，问能不能通过放2*1的方块（高2宽1，可以无限放）使全部的方块消去。

题解：
每次放2 *1的方块 每个ai的奇偶性不会改变，所以只要有偶数或者只有奇数才能全部消去，循环判断一下就可以了

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e5+10;
const ll inf=0x3f3f3f3f;

int a[110];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        int a=0,b=0;
        for(int i=1;i<=n;i++){
            int x;cin>>x;
            if(x&1)a++;
            else b++;
        }
        if(a&&b)cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

B题
Yet Another Palindrome Problem

题意：
给你n个数，判断n个数里能不能取出3个组成回文数

题解：
3个数组成回文数 第一个和第三个一定相等，所以只要找到有两个数相等的，但这两个数又不能相邻，所以如果有两个相等的数相邻只能算一个数，最后判断一下只要某个数超过两个就yes

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e5+10;
const ll inf=0x3f3f3f3f;

int a[5010],cnt[5010];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i],cnt[i]=0;
        bool f=0;
        for(int i=1;i<=n;i++){
            if(a[i]==a[i+1])cnt[a[i]]++,i++;
            else cnt[a[i]]++;
            if(cnt[a[i]]>1){f=1;break;}
        }
        if(f)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

C题
Frog Jumps

题意：
给你一段长度为n的字符串1-n，只有L和R，如果站在L只能往左跳，如果站在R只能往右跳，想要从0跳到n+1，每次跳d，问d的最小可能

题解：
只有每次能把最长的连续L跳过去才能到终点，所以只要统计一下最长的连续L子串

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e5+10;
const ll inf=0x3f3f3f3f;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;cin>>t;
    while(t--){
        string s;cin>>s;
        int n=s.length();
        s='.'+s;
        int b=0,c=0;
        for(int i=1;i<=n;){
            while(s[i]=='L')c++,i++;
            b=max(c+1,b);
            c=0;
            if(s[i]=='R')i++;
        }
        cout<<b<<endl;
    }
    return 0;
}

D题
Pair of Topics

题意：
给2个长度为n数组a[n],b[n]，假设i<j问有多少对（i,j）满足ai+aj>bi+bj（n<=2e5）

题解：
首先如果暴力查找，复杂度是n²，n较大，肯定超时，所以换一个思路想
将式子变一下 可以变成 (ai-bi)+(aj-bj)>0，所以直接用一个数组ci存ai-bi后排序一下，如果ai-bi,aj-bj都是正数式子一定成立，为了避免重复查找，统计是正数的情况两两组合，是负数的情况找正数，并且这个他俩的和应该是大于0，这里可以用upper_bound进行二分查找优化，复杂度是nlogn

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;

int a[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
        int n;cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++){int x;cin>>x;a[i]-=x;}
        sort(a+1,a+1+n);
        ll ans1=0,ans2=0;
        for(int i=1;i<=n;i++)
            if(a[i]>0)ans1++;
            else {
               int p=upper_bound(a+1,a+1+n,-a[i])-a-1;
               if(p<=n)ans2+=n-p;
            }
        cout<<ans1*(ans1-1)/2+ans2<<endl;
    return 0;
}

E题
Sleeping Schedule

题意：
给定一天有h个小时，Vova从0点开始睡觉，给长度为n的数组a[n],a[i]代表第i次睡觉的时间，Vova可能会睡a[i]或者a[i]-1的时间，如果醒来的时候刚好在[l,r]那就会感觉good，问他总共最多会多少次感觉good
题解：
n,h,l,r,ai的范围都在2000，所以可以采用n²算法，这道题肯定要枚举全部情况取最大的时候，所以需要用Dp进行状态转移，类似01背包
dp[i][j]已经睡了i次，现在的时间为j最多已经经历过多少次good
所以可以得到递推式

dp[i][j]=max(dp[i][j],max(dp[i][j-a[i]],dp[i][j-a[i]+1]); j>=l&&j<=r
dp[i][j]=max(dp[i][j],dp[i][j-a[i]]); others

当然如果j-a[i]是小于0需要加h并对h取余
这道题关键是需要初始化，排除一些无关条件，由于Vova是从0时刻开始睡觉的 如果不初始化就会导致其他的条件进入（我就是惨死在这个地方了）

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;

int a[2010],dp[2010][2010];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,h,l,r;
    cin>>n>>h>>l>>r;
    for(int i=0;i<=n;i++)
        for(int j=0;j<h;j++)
            dp[i][j]=-inf;
    dp[0][0]=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<h;j++){
            if(j>=l&&j<=r)dp[i][j]=max(dp[i][j],dp[i-1][(j-a[i]+h)%h]+1);
            else dp[i][j]=max(dp[i][j],dp[i-1][(j-a[i]+h)%h]);
            if(j>=l&&j<=r)dp[i][j]=max(dp[i][j],dp[i-1][(j-a[i]+1+h)%h]+1);
            else dp[i][j]=max(dp[i][j],dp[i-1][(j-a[i]+1+h)%h]);
        }
    int ans=0;
    for(int i=0;i<h;i++)
        ans=max(ans,dp[n][i]);
    cout<<ans<<endl;
    return 0;
}

F题
Maximum White Subtree

题意：
存在一颗无根树，每个结点是白色或者黑***r> 问对于每个结点，任意包含这个结点的连通块里，所有白色结点的数量减去黑色结点的数量最大是多少
题解：
DFS+树形DP
假设一个根进行DFS，记录每个结点的子树里能取到的最大值
然后在从这个根进行一次DFS，看每个结点的父节点最后取到的最大值是多少，如果是大于0，这个结点就可以加上他父节点的最大连通块（但是如果这个结点的值是大于0的，说明父节点的取到最大值的连通块里肯定包括这个结点所取到的连通块，所以要先减去，最后DFS结束再加上）

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
int dp[maxn],ans[maxn];
vector<int> g[maxn];
void dfs(int u,int fa){
    for(auto v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
        if(dp[v]>=0)dp[u]+=dp[v];
    }
}
void dfs1(int u,int fa){
    ans[u]=dp[u];
    if(dp[u]>0)ans[fa]-=dp[u];
    if(ans[fa]>0)ans[u]+=ans[fa];
    for(auto v:g[u]){
        if(v==fa)continue;
        dfs1(v,u);
    }
    if(dp[u]>0)ans[fa]+=dp[u];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>dp[i];
        if(dp[i]==0)dp[i]=-1;
    }
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1,0);
    dfs1(1,0);
    for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
    return 0;
}