做网站的公司 设计好,云南网络推广报价明细,wordpress官使用方法,柳州网站HDU6223 - Infinite Fraction Path 做法1#xff1a;枚举每个串取最大值#xff0c;只用判断前20位#xff0c;如果前20位都相同#xff0c;可以认定两个串相同。因为很容易进入循环节#xff0c;且循环节不太大。 #include bits/stdc.h
#define pb push_back
typ… HDU6223 - Infinite Fraction Path 做法1枚举每个串取最大值只用判断前20位如果前20位都相同可以认定两个串相同。因为很容易进入循环节且循环节不太大。 #include bits/stdc.h
#define pb push_back
typedef long long ll;
const int N 150077;
using namespace std;
int n,a[N];
char s[N], ans[N], tmp[N];
int TT, CC0;
int ck(int p1, int p2) {for(int i 1; i 20; i) {if(s[p1] ! s[p2]) return s[p1] s[p2];p1 (1LL*p1*p1 1LL) % n; //**p2 (1LL*p2*p2 1LL) % n;}return 0;
}
void output(int p) {for(int i 0; i n; i) {printf(%c,s[p]); p (1LL*p*p 1LL) % n;}puts();
}
int main() {scanf(%d,TT);while(TT--) {scanf(%d,n);scanf( %s,s);int ans 0;for(int i 1; i n; i) {if(ck(ans,i)) ans i;}printf(Case #%d: ,CC);output(ans);}
}做法2倍增hash处理以i为首长度为\(2^k\)的串的hash值那么比较两个串时就可以先比较前半部分如果不相同就朝前半部分递归否则朝右半部分递归串长为1时直接比较即可。 转载于:https://www.cnblogs.com/RRRR-wys/p/9717894.html
