2022/7/16

Mark and His Unfinished Essay

这题看了思路提示才会做，其实应该是可以自己做出来的，不难

把每次复制的l，r都存起来，并且求出每次复制完的长度的前缀和，每次k都二分去找到大于等于k的位置，然后去找它属于上一次的哪个位置，直到k<=n就可以直接输出

[二分]Mark and His Unfinished Essay CF1705C_CCloth的博客-CSDN博客

#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-小红的构造题_牛客练习赛100 (nowcoder.com)

看的官方题解，考虑rerere这样的序列，在第一个re后加1个d就会多出1个red，在第2个re后加d就会多出3个，在第k个re后就会多出k*(k+1)/2个，考虑每个re后都放一个d，那么总和就是1+3+...+k*(k+1)/2,也就是n*(n+1)*(n+2)/6,代码中靠这个找出最多需要多少个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] 食物链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)并查集

这个题是由二层的种类并查集变为3层的了，要注意三者循环的关系，假设x是本类，x+n是x能吃的类，x+2*n是能吃x的类，然后注意一些细节就可以了

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