admin 管理员组文章数量: 1086866
CF591CF01串的变换，找规律
这题知道应该是一个规律题，然而并没有什么卵用，规律找不到，AC不了，前面俩题手速不够快，只能掉rating。
说一下这题的规律：
首先只有101和010会变化，很明显可以知道，然后开个数组，记录需要变化的位置，
然后每一段需要变化的01串需要交换的次数为：len+1/2;
然后变化的规律：
- 若子串长度len为奇数,即首尾数字相同的,该子串变为同样长度,与首尾数字一致的串,如10101变为11111,而01010变为00000
- 若子串长度len为偶数,即首尾数字不同,子串中每个数字会变为与首尾数字中与其距离较近的一个,如101010变为111000,而01010101变为00001111，
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<climits>
#include<vector>
#include<cfloat>
#include<queue>
#include<cctype>
#include<cstdlib>
#include<string>
#define LL long long
using namespace std;
const int N=500010;
int a[N],b[N];
int main()
{int n;while(cin>>n){for(int i=0;i<n;i++)scanf("%d",&a[i]);memset(b,0,sizeof(b));for(int i=1;i<n-1;i++)b[i]=a[i]!=a[i-1]&&a[i]!=a[i+1];int ans=0;int i=1;while(i<n-1){if(!b[i]) i++;else{int j=i;while(b[j]) j++;ans=max(ans,(j-i+1)/2);if((j-i)%2) for(int k=i;k<j;k++) a[k]=a[i-1];elsefor(int k=i;k<j;k++) a[k]= (k<(i+j)/2) ?a[i-1]:a[j];i=j;}}cout<<ans<<endl;for(int i=0;i<n-1;i++)cout<<a[i]<<' ';cout<<a[n-1]<<endl;}return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<climits>
#include<vector>
#include<cfloat>
#include<queue>
#include<cctype>
#include<cstdlib>
#include<string>
#define LL long long
using namespace std;
const int maxn=40;
int s[30];
int main()
{int n,m;while(cin>>n>>m){string ss;cin>>ss;memset(s,0,sizeof(s));for(int i=0;i<m;i++){char x,y;cin>>x>>y;int x1=x-'a'+1;int y1=y-'a'+1;if(x1==y1)continue;for(int i=1;i<30;i++){if(s[i]==x1){s[i]=y1;continue;}if(s[i]==y1){s[i]=x1;continue;}}if(!s[x1])s[x1]=y1;if(!s[y1])s[y1]=x1;}//cout<<ss<<endl;for(int i=0;i<ss.length();i++){int t=ss[i]-'a'+1;if(s[t])printf("%c",s[t]-1+'a');elsecout<<ss[i];}cout<<endl;}return 0;
}
本文标签： CF591CF01串的变换，找规律
版权声明：本文标题：CF591CF01串的变换，找规律 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1697117936a261893.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论