admin管理员组

文章数量:815879

CF591CF01串的变换,找规律

这题知道应该是一个规律题,然而并没有什么卵用,规律找不到,AC不了,前面俩题手速不够快,只能掉rating。

说一下这题的规律:

首先只有101和010会变化,很明显可以知道,然后开个数组,记录需要变化的位置,

然后每一段需要变化的01串需要交换的次数为:len+1/2;

然后变化的规律:

  • 若子串长度len为奇数,即首尾数字相同的,该子串变为同样长度,与首尾数字一致的串,如10101变为11111,而01010变为00000
  • 若子串长度len为偶数,即首尾数字不同,子串中每个数字会变为与首尾数字中与其距离较近的一个,如101010变为111000,而01010101变为00001111,
具体细节看代码: 另外贴下B题的代码,写的比较繁琐,求喷。 C题:
#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;
}
B题:
#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串的变换,找规律