2022/7/16

Mark and His Unfinished Essay

This question can only be done after reading the train of thought tips , In fact, it should be made by yourself , It's not hard to

Copy every time l,r They all survive. , And find the prefix sum of the length copied each time , Every time k Two points to find greater than or equal to k The location of , Then find out where it belongs last time , until k<=n You can output it directly

[ Two points ]Mark and His Unfinished Essay CF1705C_CCloth 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 t,n,c,q,sum[55];
struct node{
    ll l,r;
}a[55];
char s[8000005];
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld%lld",&n,&c,&q);
        scanf("%s",s+1);
        sum[0]=n;
        for(int i=1;i<=c;i++) scanf("%lld%lld",&a[i].l,&a[i].r),sum[i]=sum[i-1]+a[i].r-a[i].l+1;
        while(q--){
            ll k;
            scanf("%lld",&k);
            ll x=lower_bound(sum,sum+c+1,k)-sum;
            while(k>n){
                k=a[x].l+k-sum[x-1]-1;
                x=lower_bound(sum,sum+c+1,k)-sum;
            }
            cout<<s[k]<<'\n';
        }
        for(int i=1;i<=c;i++) sum[i]=0;
    }
    return 0;
}

D- Xiao Hong's construction problem _ The bullock practice match 100 (nowcoder.com)

See the official solution , consider rerere This sequence , At the first re After add 1 individual d There will be more 1 individual red, In the 2 individual re After add d There will be more 3 individual , In the k individual re There will be more k*(k+1)/2 individual , Consider each re Put one in the back d, Then the sum is 1+3+...+k*(k+1)/2, That is to say n*(n+1)*(n+2)/6, Use this to find out the maximum number needed in the code re

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll n,tx[101010];
int main(){
    cin>>n;
    ll x;
    if(n==0) return cout<<"d",0;
    for(x=1;x*(x+1)*(x+2)/6<=n;x++);x--;
    for(ll j=x;j>=1;j--){
        tx[j]+=n/(j*(j+1)/2);
        n%=j*(j+1)/2;
    }
    for(ll j=1;j<=x;j++){
        cout<<"re";
        while(tx[j]--) cout<<"d";
    }
    return 0;
}

P2024 [NOI2001] The food chain - Luogu | New ecology of computer science education (luogu.com.cn) Union checking set

This problem is changed from two-level category and search set to 3 On the floor , Pay attention to the relationship between the three cycles , hypothesis x This class ,x+n yes x Edible class ,x+2*n Yes, it can be eaten x Class , Then pay attention to some details

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll n,k,s[200005],ans=0;
ll findd(ll x){
    return x==s[x]?x:s[x]=findd(s[x]);
}
void uni(ll x,ll y){
    ll xx=findd(x),yy=findd(y);
    if(xx!=yy) s[xx]=yy;
}
int main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++) s[i]=i,s[i+n]=i+n,s[i+2*n]=i+2*n;
    for(int i=1;i<=k;i++){
        ll op,x,y;
        scanf("%lld%lld%lld",&op,&x,&y);
        if(x>n||y>n){ans++;continue;}
        if(op==1){
            if(findd(x+n)==findd(y)||findd(x)==findd(y+n)){ans++;continue;}
            uni(x,y);
            uni(x+n,y+n);
            uni(x+2*n,y+2*n);
        }
        else{
            if(findd(x)==findd(y)||findd(x)==findd(y+n)||findd(x+2*n)==findd(y)||x==y){ans++;continue;}
            uni(x,y+2*n);
            uni(x+n,y);
            uni(x+2*n,y+n);
        }
    }
    printf("%lld\n",ans);
    return 0;
}