2022/7/16

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)

看的官方题解，考虑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)并查集

这个题是由二层的种类并查集变为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;
}