Codeforces Round ＃800 (Div. 2)

A. Creep

Problem - A - Codeforceshttps://codeforces.com/contest/1694/problem/A签到,思路就不讲了

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
void solve()
{
    int a,b;
    cin>>a>>b;
    //a0,b1
    if(a>=b)
    {
        for(int i=0;i<b;i++)
            cout<<"01";
        for( int i=0;i<a-b;i++)
            cout<<"0";
        cout<<"\n";
        return;
    }
    else if(a<b)
    {
        for(int i=0;i<a;i++)
            cout<<"01";
        for( int i=0;i<b-a;i++)
            cout<<"1";
        cout<<"\n";
        return;
    }
    return;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

B. Paranoid String

Problem - B - Codeforceshttps://codeforces.com/contest/1694/problem/B题意:给你一个串.有两种操作,把相邻的"01"变为"1',或者把"10"变成"0",问有多少子串可以在进行操作之后变成一个数字.

我们打表之后,会发现,只要是最后两个字母不相同的,之前的字符都可以全部消去,反之,则不可以.

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
    int n,ans=0;
    string s;
    cin>>n>>s;
    ans=s.size();
    for(int i=1;i<s.size();i++)
    {
        if(s[i]!=s[i-1])
            ans+=i-1+1;
    }
    cout<<ans<<"\n";
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

C. Directional Increase

Problem - C - Codeforceshttps://codeforces.com/contest/1694/problem/C题意:我们从0出发,向右走一步,那么我们原来在的地方的权值+1,向左走一步原来在的地方的权值-1.给你一个操作后的数组,问在经过一系列的操作之后回到起点,能否得到这个数组.

想让右边存在负数,那么可以肯定的是我们必须是从左边走过来的,所以右边的负数是多少,我们一定要保证此时走到的左边的正数值是它的负值,两者相加得0(因为最后要走回去,向左向右的步数是一样的).则可以推出结论,求该数组的前缀和,保证最后一位为0,其余的前缀和都要>0.(当然,要把后面连续的0排除掉,因为没有走到这些部分).

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
    int n,ans=0;
    string s;
    cin>>n>>s;
    ans=s.size();
    for(int i=1;i<s.size();i++)
    {
        if(s[i]!=s[i-1])
            ans+=i-1+1;
    }
    cout<<ans<<"\n";
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

D. Fake Plastic Trees

Problem - D - Codeforceshttps://codeforces.com/contest/1694/problem/D题意:给你一棵树,每个点一开始的权值为0,我们可以先择一个点v,并且进行操作让从根节点1到这个点v的路径上的点的权值去加上一个递增数组.问保证最后操作完了每个点权值在题目给定范围l,r(题目给的数组,分别是该点权值的下界和上界)所需要的的最小操作步数.

我们想要保证每个点达到区间,就可以尝试去贪心,我们尽量让每个节点到达他们的最大值,这样再处理他们的父节点时,肯定是把子节点的值全部加起来,这个和就是我们父节点可以在进行子节点操作后不进行多余操作所得到的该点的权值.当这个权值小于下界时,就需要多操作一步,让它符合条件,反之,因为是贪心,我们就把该点的权值变为子节点权值和与该点上界的最小值即可.(根节点必须进行一步操作,且取它的上界).

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
struct node
{
    int to,ne;
}edge[400005];
int h[200005],ans,tot,f[200005],cnt,l[200005],r[200005];
void add(int x,int y)
{
    edge[++tot].to=y;
    edge[tot].ne=h[x];
    h[x]=tot;
    return ;
}
void dfs(int x)
{
    int sum=0;
    for(int i=h[x];i!=-1;i=edge[i].ne)
    {
        int y=edge[i].to;
        dfs(y);
        sum+=f[y];
    }
    if(sum<l[x])
    {
        ans++;
        f[x]=r[x];
    }
    else
    {
        f[x]=min(sum,r[x]);
    }
}
void solve()
{
    ans=0,tot=0;
    memset(h,-1,sizeof h);
    int n,x;
    scanf("%lld",&n);
    for(int i=2;i<=n;i++)
    {
        scanf("%lld",&x);
        add(x,i);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&l[i],&r[i]);
    }
    dfs(1);
    printf("%lld\n",ans);
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}