题目链接
Solved 6/11
Penalty 1652
Problem A
Problem B
Problem C
Problem D
Problem E
Problem F
预处理出一个pre数组
pre[i]表示i位字母数以内用掉多少个字母
然后就可以算出要计算的位置是第多少个字母数
最后就是转成26进制了
注意是没有0有26的26进制
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include
Problem G
Problem H
可以发现一定可以把所有的点连起来
因此可以不断的建立凸包
然后用一条边把外面的大凸包和里面的小凸包连起来
为了确保连成螺旋形
在建立里面的小凸包时将上一个大凸包最后一个点也加进去
然后依次连接即可
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include
Problem I打表发现ans <= 9
考虑BFS
不必把所有的状态都存进去
只要存能取的最大数的前面70个即可
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include
Problem J
Problem K
考虑字符串Hash
枚举两个断点，然后分成三段，总共有6个不同的排列。
对于每一段用预处理的Hash,O(1)判断即可。
有解就退出
#includeusing namespace std;#define rep(i, a, b) for (int i(a); i <= (b); ++i)#define dec(i, a, b) for (int i(a); i >= (b); --i)typedef long long LL;const int N = 5010;const LL mod = 1e9 + 7;LL base = 1e10 + 3;LL sHash[N], sbin[N];LL tHash[N], tbin[N];int n;char s[N], t[N];LL cc[N];int yy[N];void sHashtable(){ sbin[0] = 1LL; rep(i, 1, n) sbin[i] = (sbin[i - 1] * base); rep(i, 1, n) sHash[i] = (sHash[i - 1] * base + s[i]);}inline LL sgethash(const int &l, const int &r){ return (sHash[r] - sHash[l - 1] * sbin[r - l + 1]);}void tHashtable(){ tbin[0] = 1LL; rep(i, 1, n) tbin[i] = (tbin[i - 1] * base); rep(i, 1, n) tHash[i] = (tHash[i - 1] * base + t[i]);}inline LL tgethash(const int &l, const int &r){ return (tHash[r] - tHash[l - 1] * tbin[r - l + 1]);}void print(int l1, int r1, int l2, int r2, int l3, int r3){ puts("YES"); rep(i, l1, r1) putchar(t[i]); putchar(10); rep(i, l2, r2) putchar(t[i]); putchar(10); rep(i, l3, r3) putchar(t[i]); putchar(10); exit(0);}int main(){ scanf("%s", s + 1); n = strlen(s + 1); rep(i, 0, n) cc[i] = (LL)rand() * (LL)rand() * (LL)rand(); rep(i, 1, n) if (s[i] < 'a') s[i] = s[i] - 'A' + 'a'; scanf("%s", t + 1); rep(i, 1, n) if (t[i] < 'a') t[i] = t[i] - 'A' + 'a'; sHashtable(); tHashtable(); rep(i, 1, n - 2){ dec(j, n, i + 2){ int l1 = 1, r1 = i; int l2 = i + 1, r2 = j - 1; int l3 = j, r3 = n; int c1 = r1 - l1 + 1; int c2 = r2 - l2 + 1; int c3 = r3 - l3 + 1; if (sgethash(1, c1) == tgethash(l1, r1)){ if (sgethash(c1 + 1, c1 + c2) == tgethash(l2, r2)){ if (sgethash(c1 + c2 + 1, n) == tgethash(l3, r3)){ print(l1, r1, l2, r2, l3, r3); } } } swap(l2, l3); swap(r2, r3); swap(c2, c3); if (sgethash(1, c1) == tgethash(l1, r1)){ if (sgethash(c1 + 1, c1 + c2) == tgethash(l2, r2)){ if (sgethash(c1 + c2 + 1, n) == tgethash(l3, r3)){ print(l1, r1, l2, r2, l3, r3); } } } swap(l2, l1); swap(r2, r1); swap(c2, c1); if (sgethash(1, c1) == tgethash(l1, r1)){ if (sgethash(c1 + 1, c1 + c2) == tgethash(l2, r2)){ if (sgethash(c1 + c2 + 1, n) == tgethash(l3, r3)){ print(l1, r1, l2, r2, l3, r3); } } } swap(l2, l3); swap(r2, r3); swap(c2, c3); if (sgethash(1, c1) == tgethash(l1, r1)){ if (sgethash(c1 + 1, c1 + c2) == tgethash(l2, r2)){ if (sgethash(c1 + c2 + 1, n) == tgethash(l3, r3)){ print(l1, r1, l2, r2, l3, r3); } } } swap(l2, l1); swap(r2, r1); swap(c2, c1); if (sgethash(1, c1) == tgethash(l1, r1)){ if (sgethash(c1 + 1, c1 + c2) == tgethash(l2, r2)){ if (sgethash(c1 + c2 + 1, n) == tgethash(l3, r3)){ print(l1, r1, l2, r2, l3, r3); } } } swap(l2, l3); swap(r2, r3); swap(c2, c3); if (sgethash(1, c1) == tgethash(l1, r1)){ if (sgethash(c1 + 1, c1 + c2) == tgethash(l2, r2)){ if (sgethash(c1 + c2 + 1, n) == tgethash(l3, r3)){ print(l1, r1, l2, r2, l3, r3); } } } } } puts("NO"); return 0;}