Codeforces Round ＃800 (Div. 2)

A. Creep

Problem - A - Codeforceshttps://codeforces.com/contest/1694/problem/A Sign in , Don't talk about ideas

#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 The question : Here's a string for you . There are two operations , Put the adjacent "01" Turn into "1', Or the "10" become "0", Ask how many substrings can be changed into a number after the operation .

After we set the watch , Will find , As long as the last two letters are different , All previous characters can be deleted , conversely , Do not place .

#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 The question : We from 0 set out , Take a step to the right , So the weight of the place we were in +1, Take a step to the left to get the weight of the original place -1. Give you an array after the operation , Ask to return to the starting point after a series of operations , Can I get this array .

Want negative numbers on the right , So what is certain is that we must come from the left , So what is the negative number on the right , We must make sure that the positive value to the left of the path is its negative value , The two add up to 0( Because I have to walk back at last , The steps left and right are the same ). Then we can draw a conclusion , Find the prefix and of the array , Make sure that the last one is 0, The rest of the prefixes and must be >0.( Of course , We should put the following continuous 0 Get rid of , Because I didn't go to these parts ).

#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 The question : Give you a tree , The weight at the beginning of each point is 0, We can choose a point first v, And operate to make the root node 1 To this point v Add an increasing array to the weight of points on the path of . Ask to ensure that the weight of each point after the final operation is within the given range of the topic l,r( The array given by the title , Are the lower and upper bounds of the weight of the point respectively ) The minimum number of operation steps required .

We want to ensure that each point reaches the interval , You can try to be greedy , We try to make each node reach its maximum value , So when dealing with their parent nodes , It must be adding up all the values of the child nodes , This sum is the weight of the point obtained by our parent node without redundant operations after the operation of the child node . When this weight is less than the lower bound , One more step is needed , Make it eligible , conversely , Because it's greed , We can change the weight of the point into the minimum value of the child node weight and the upper bound of the point .( The root node must do one step , And take its upper bound ).

#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;
}