首页 > 代码库 > BestCoder Round #88
BestCoder Round #88
传送门：BestCoder Round #88
分析：
A题统计字符串中连续字串全为q的个数，预处理以下或加个cnt就好了；
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <ctime> 5 #include <cmath> 6 #include <iostream> 7 #include <algorithm> 8 #include <string> 9 #include <set>10 #include <map>11 #include <queue>12 #include <stack>13 #include <vector>14 #include <bitset>15 using namespace std;16 17 #define ll long long18 #define F(i,a,b) for(int i=a;i<=b;++i)19 #define R(i,a,b) for(int i=a;i<b;++i)20 #define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)21 #define rek(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)22 #define mem(a,b) memset(a,b,sizeof(a))23 #define cpy(a,b) memcpy(a,b,sizeof(b))24 #pragma comment(linker, "/STACK:102400000,102400000")25 inline void read(int &x){x=0; char ch=getchar();while(ch<‘0‘) ch=getchar();while(ch>=‘0‘){x=x*10+ch-48; ch=getchar();}}26 char s[100100];27 int t,cnt;28 ll sum;29 int main()30 {31 for(scanf("%d",&t);t--;)32 {33 scanf("%s",s);int len=strlen(s);cnt=sum=0;34 for(int i=0;i<len;++i) if(s[i]==‘q‘) sum+=cnt,cnt++;else if(cnt) {sum+=cnt;cnt=0;}35 if(cnt) sum+=cnt;36 printf("%lld\n",sum);37 } 38 return 0;39 }
B题求出一个数字串的所有完全阿贝尔周期；
设S是一个数字串，定义函数occ(S,x)occ(S,x)表示S中数字x的出现次数。例如：S=(1,2,2,1,3),occ(S,1)=2,occ(S,2)=2,occ(S,3)=1S=(1,2,2,1,3),occ(S,1)=2,occ(S,2)=2,occ(S,3)=1。如果对于任意的i，都有occ(u,i)=occ(w,i)occ(u,i)=occ(w,i)，那么我们认为数字串u和w匹配。例如：(1,2,2,1,3)\approx(1,3,2,1,2)(1,2,2,1,3)≈(1,3,2,1,2)。对于一个数字串S和一个正整数k，如果SS可以分成若干个长度为k的连续子串，且这些子串两两匹配，那么我们称k是串S的一个完全阿贝尔周期。给定一个数字串S，请找出它所有的完全阿贝尔周期
那么对于给定的n，从1-n枚举它的因子比如k，然后判断1-k是否与k+1~2*k，2*k+1~3*k...（t*k<=n）匹配，这里要处理一下，详情见代码
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <ctime> 5 #include <cmath> 6 #include <iostream> 7 #include <algorithm> 8 #include <string> 9 #include <set>10 #include <map>11 #include <queue>12 #include <stack>13 #include <vector>14 #include <bitset>15 using namespace std;16 17 #define LL long long18 #define F(i,a,b) for(int i=a;i<=b;++i)19 #define R(i,a,b) for(int i=a;i<b;++i)20 #define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)21 #define rek(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)22 #define mem(a,b) memset(a,b,sizeof(a))23 #define cpy(a,b) memcpy(a,b,sizeof(b))24 #pragma comment(linker, "/STACK:102400000,102400000")25 inline void read(int &x){x=0; char ch=getchar();while(ch<‘0‘) ch=getchar();while(ch>=‘0‘){x=x*10+ch-48; ch=getchar();}}26 int t,n,cnt,a[100010],b[100010],p[100100],p1[100100];27 int main()28 {29 for(scanf("%d",&t);t--;)30 {31 scanf("%d",&n);cnt=0;32 F(i,1,n) scanf("%d",a+i);33 for(int i=1;i*i<=n;++i) if(n%i==0)34 {35 for(int i=0;i<=n;++i) p[i]=p1[i]=0;36 int x=n/i;37 for(int j=1;j<=i;++j) p[a[j]]++;38 for(int k=i*2;k<=n;k+=i) 39 {40 for(int j=k-i+1;j<=k;j++) p1[a[j]]++;41 for(int j=1;j<=i;++j) if(p[a[j]]*(k/i-1)!=p1[a[j]]) goto l;42 }43 b[cnt++]=i;l:;44 for(int i=0;i<=n;++i) p[i]=p1[i]=0;45 for(int j=1;j<=x;++j) p[a[j]]++;46 for(int k=x*2;k<=n;k+=x)47 {48 for(int j=k-x+1;j<=k;j++) p1[a[j]]++;49 for(int j=1;j<=x;++j) if(p[a[j]]*(k/x-1)!=p1[a[j]]) goto l1;50 } 51 b[cnt++]=x;l1:;52 }53 sort(b,b+cnt);54 printf("%d",b[0]);55 for(int i=1;i<cnt;++i) if(b[i]!=b[i-1])printf(" %d",b[i]);puts("");56 }57 return 0;58 }
BestCoder Round #88
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。