Educational Codeforces Round 119 (Rated for Div. 2) C E
前言: 夜深,睡不着。尽管今天的榜C题只过了毛$1k$人,但还是深深感觉到郁闷,接连上一场$761$让我深深感受到非常的难受,补个C睡觉把,剩下的慢慢补把,什么时候能看到突破呢......哎
C. BA-String(string+进制转化)
思路: 我们将本题转换为进制来看,因为通过观察可以发现每个$a$与其后面的$*$号可以构成一个进制,我们只需将目标字典序排名映射到各个位数表达出来即可,这处借鉴某个$AC$代码$+$自己理解进行改动注释,使用$dfs$.
- 参考代码+注释:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,x;
char s[2010];
void dfs(int d,int l){
if(d==0)return ;
int cnt=0;
while(d&&s[d--]=='*')cnt++;//表示从后往前扫描
dfs(d,l/(cnt*k+1));//此处的(cnt*k+1)表示进制。
if(s[d+1]=='a')cout<<'a';//如果s[d+1]是'a'那么输出a,反之不用如:**a***,最后一个dfs不用输出'a'.
for(int i=1;i<=l%(cnt*k+1);i++)cout<<'b';//将本次dfs进制内的数输出。
}
signed main(){
int t;
cin>>t;
while(t--){
cin>>n>>k>>x;
scanf("%s",s+1);//字符串下标从1开始
dfs(n,x-1);//全是a的排除掉。
cout<<endl;
}
return 0;
}
E. Replace the Numbers(并查集)
- 参考代码+注释:
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=5e5+10;
int a[N];
int cnt;
vector<PII>S[N];
int p[N];
signed main(){
snow;
int n;
cin>>n;
for(int i=1;i<=n;i++){
int id;
cin>>id;
if(id==1){
cin>>a[++cnt];//cnt存储数的数量
}
else{
int x,y;
cin>>x>>y;
S[cnt].pb(x,y);//并查集操作
}
}
for(int i=1;i<N;i++)p[i]=i;//初始化祖宗结点
for(int i=cnt;i>=1;i--){
reverse(S[i].begin(),S[i].end());//从最后一个替换操作开始回溯
for(auto [x,y]:S[i]){
p[x]=p[y];
}
a[i]=p[a[i]];
}
for(int i=1;i<=cnt;i++)cout<<a[i]<<' ';
cout<<endl;
return 0;
}
巨巨加油
orz
写的太好了,支持~(≥▽≤)/~
蟹蟹~