不知道为什么用算法竞赛进阶指南上的那个代码交上去会WA
#include#include #include #define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;const int MAXN = 2e4 + 10;char a[MAXN];int n;int main(){ int T; scanf("%d", &T); while(T--) { scanf("%s", a + 1); n = strlen(a + 1); _for(i, 1, n) a[n + i] = a[i]; int i = 1, j = 2, k; while(i <= n && j <= n) { for(k = 0; k <= n && a[i+k] == a[j+k]; k++); if(k == n) break; if(a[i+k] > a[j+k]) { i += k + 1; if(i == j) i++; } else { j += k + 1; if(i == j) j++; } } printf("%d\n", min(i, j)); } return 0;}
正解在i == j只有j++。我自己是觉得没有什么区别的，迷。
AC代码
#include#include #include #define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;const int MAXN = 2e4 + 10;char a[MAXN];int n;int main(){ int T; scanf("%d", &T); while(T--) { scanf("%s", a + 1); n = strlen(a + 1); _for(i, 1, n) a[n + i] = a[i]; int i = 1, j = 2, k; while(i <= n && j <= n) { for(k = 0; k <= n && a[i+k] == a[j+k]; k++); if(k == n) break; if(a[i+k] > a[j+k]) i += k + 1; else j += k + 1; if(i == j) j++; } printf("%d\n", min(i, j)); } return 0;}
好水。就处理出最小表示然后比较就好了。
#include#define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;const int MAXN = 1e6 + 10;char a[MAXN], b[MAXN], t[MAXN];int n;void deal(char* s){ int k, i = 1, j = 2; _for(i, 1, n) s[n + i] = s[i]; while(i <= n && j <= n) { for(k = 0; k <= n && s[i + k] == s[j + k]; k++); if(k == n) break; if(s[i + k] > s[j + k]) i += k + 1; else j += k + 1; if(i == j) j++; } int p = min(i, j); _for(i, 1, n) t[i] = s[p + i - 1]; _for(i, 1, n) s[i] = t[i];}int main(){ scanf("%s%s", a + 1, b + 1); n = strlen(a + 1); deal(a); deal(b); bool ok = true; _for(i, 1, n) if(a[i] != b[i]) { ok = false; break; } if(ok) { puts("Yes"); _for(i, 1, n) putchar(a[i]); puts(""); } else puts("No"); return 0;}