2022/7/17

Doremy's IQ

I have been thinking about repenting my greed yesterday , In the last few minutes, I found that I couldn't write it at all , Today I saw the boss's ideas , If you traverse backwards, you don't have to worry about the aftereffect , Let's make a variable x from 0 Start traversing backwards , Encounter greater than x The is x+1, Take this test, but x be equal to q You can't do it anymore , because iq The biggest is q, Less than x Directly participate in

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll t,n,q,a[200005],vis[200005];
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&q);
        ll x=0;
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]),vis[i]=0;
        for(int i=n;i>=1;i--){
            if(x<a[i]&&x<q) x++,vis[i]=1;
            else if(x>=a[i]) vis[i]=1;
        }
        for(int i=1;i<=n;i++) printf("%lld",vis[i]);
        printf("\n");
    }
    return 0;
}

D - Difference Array

Found b Array perceptual understanding, in fact, there are many repeated numbers , So it can be used mp Let's simulate the process , Probably o(n* Radical sign n) Complexity , Enough to get through this problem

Codeforces Round #808 (Div. 2) A~D - You know (zhihu.com)

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll t,n;
map<ll,ll>mp;
int main(){
    scanf("%lld",&t);
    while(t--){
        mp.clear();
        scanf("%lld",&n);
        ll x;
        for(int i=1;i<=n;i++) scanf("%lld",&x),mp[x]++;
        for(int i=1;i<n;i++){
            map<ll,ll>mp1;
            for(auto it=mp.begin();it!=mp.end();it++){
                if(it->second>1) mp1[0]+=it->second-1;
                auto it1=it;it1++;
                if(it1!=mp.end()) mp1[it1->first-it->first]++;
            }
            mp=mp1;
        }
        printf("%lld\n",mp.begin()->first);

    }
    return 0;
}

D - Mark and Lightbulbs

Observe feasible examples , Find that the adjacent ones are the same 1 or 0 After the merger s and t It's the same , also s and t The head and tail should be the same ; And then I found out s Change to t It's also regular , Take a look at the last example

000101 010011 After the merger, both are 0101 Formal , first 1 Before will s Turn into t In the form of ：011101  010011

the second 0 And before t In the form of ：010001, the second 1 And before t In the form of ：010011 010011, Then you can find that each time it is the absolute value of the subscript difference of the left endpoint of each block , That is to say 0101 In form 1 The absolute value of the sub block standard deviation ,0 The absolute value of the sub block standard deviation ,1 The absolute value of the sub block standard deviation , Add up to the answer

D. Mark and Lightbulbs_Vegetable newbie The blog of -CSDN Blog

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll q,n;
vector<ll>a,b;
string s,t;
int main(){
    scanf("%lld",&q);
    while(q--){
        scanf("%lld",&n);
        a.clear();b.clear();
        cin>>s>>t;
        for(int i=1;i<n;i++){
            if(s[i]!=s[i-1]) a.push_back(i);
            if(t[i]!=t[i-1]) b.push_back(i);
        }
        if(s[0]!=t[0]||s[n-1]!=t[n-1]||a.size()!=b.size()){printf("-1\n");continue;}
        ll ans=0;
        for(int i=0;i<a.size();i++) ans+=abs(b[i]-a[i]);
        printf("%lld\n",ans);
    }
    return 0;
}

How Many Answers Are Wrong - HDU 3038 - Virtual Judge (vjudge.net) Union checking set

Through this question, I have a deeper understanding of weighted and search set , I don't understand why I write like that when I read the solution , I want to write a prefix that fits the actual meaning and , Then I tried for a long time and found that I couldn't ,,, And check the weight in the set, like the distance between two points , When finding something like prefix and, it's best to regard an endpoint of the value range as the root node , Then calculate the distance between each point and him , Select different endpoints , Different consolidation methods will affect sum The value of the array ; In addition, it is given in the title c It contains weights at both ends , If you merge according to this, the left endpoint may be merged repeatedly , So the left endpoint should be reduced 1, This is also a classic problem , For example, if multiple skipping ropes are placed into a line, the handles of skipping ropes should not be stacked together, but connected together

Take the right and check the collection _syddf_shadow The blog of -CSDN Blog _ Take the right and check the collection

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#include<stack>
#include<set>
#include<ctime>
//HDU Special locomotive 
//#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll n,m,s[200005],sum[200005];
ll findd(ll x){
    if(x!=s[x]){
        ll tmp=s[x];
        s[x]=findd(s[x]);
        sum[x]+=sum[tmp];
    }
    return s[x];
}
void uni(ll x,ll y,ll z){
    ll xx=findd(x),yy=findd(y);
    if(xx!=yy){
        s[xx]=yy;
        sum[xx]=-sum[x]+sum[y]+z;
    }
}
int main(){
    while(scanf("%lld%lld",&n,&m)!=EOF){
    ll x,y,z,ans=0;
    for(int i=0;i<=n;i++) s[i]=i,sum[i]=0;
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld",&x,&y,&z);x--;
        if(findd(x)==findd(y)){
            //cout<<"qqq "<<sum[x]<<" "<<sum[y]<<" "<<endl;
            if(sum[x]-sum[y]!=z) ans++;
        }
        else{
            uni(x,y,z);
        }
    }
    printf("%lld\n",ans);
    }
    return 0;
}

P1196 [NOI2002] Ginga Eiyudensetsu - Luogu   Union checking set

The only difficulty in this problem is that the number of fleets contained in each column should be stored in a separate array , Others are the same as ordinary weighted and search sets , I thought about this point for a long time ,,,

Talking about and checking the collection & Type and search & Take the right and check the collection - Eleven Modest - Blog Garden (cnblogs.com)

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll t,s[30005],dis[30005],siz[30005];
ll findd(ll x){
    if(x!=s[x]){
        ll tmp=s[x];
        s[x]=findd(s[x]);
        dis[x]+=dis[tmp];
    }
    return s[x];
}
void uni(ll x,ll y){
    ll xx=findd(x),yy=findd(y);
    if(xx!=yy){
        s[xx]=yy;
        dis[xx]+=siz[yy];
        siz[yy]+=siz[xx];
    }
}
int main(){
    scanf("%lld",&t);
    for(int i=1;i<=30000;i++) s[i]=i,dis[i]=0,siz[i]=1;
    while(t--){
        ll x,y;
        char op;
        cin>>op>>x>>y;
        if(op=='M'){
            uni(x,y);
            //cout<<x<<" sss "<<" "<<findd(x)<<" "<<dis[findd(x)]<<" "<<dis[x]<<endl;
        }
        else{
            if(findd(x)==findd(y)){
                //cout<<x<<" "<<y<<" "<<dis[x]<<" ww "<<dis[y]<<" "<<dis[3]<<endl;
                printf("%lld\n",abs(dis[x]-dis[y])-1);
            }
            else printf("-1\n");
        }
    }
    return 0;
}