后：day3

衢州
2018.8.6

预计：? + ? + 50
实际：0 + 0 + 10
（T1：? 写的没调出的贪心，过小样例，不过大样例）
（T2：? 写的太快，过了小样例，不过大样例）

T1

开始想了贪心思路。
特别难写。
4个半小时。
不过大样例。

其中，感觉自己想的是正解，感觉会，感觉能调出来，也没有想其他思路。

其中，想到过，关于做法好像不对的地方，时间当时过半了，而且也没有继续去想。

T2

T1写不出的时候，看了一眼，感觉50分可做。但还想着T1，于是没有写，最后半个小时写的。
还写错了。
复杂度也错了，写成了n^3。

T3

T1写不出的时候，看了一眼，感觉50分可做。但还想着T1，于是没有写，最后半个小时写的。
还写错了。
炸成1分。

总结：

1、考试策略，时间安排，做题顺序，取舍。
2、思路没有证明
3、想到一些地方，没有抓住。抓住一闪而过的，冒出的思想。
4、挖掘性质。

T1

显然要么不亵渎，要么最后才会亵渎
设亵渎时最大元素为x，则此时[1,x]中每个整数均在集合内，且x<=n
初始时值较小的元素，在亵渎时值也较小
设f[i][j]表示前i小的元素，变成了[1,j]中的每个整数的最小代价
枚举第i-1小的元素是j-1还是j，得到转移方程f[i][j]=min(f[i-1][j],f[i-1][j-1])+w(a[i],j)，w(x,y)表示把x变成y的代价
最后对所有f[n][x]取min即可

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 5010;
LL f[N][N], A[N], p, q, r;
LL calcc(int x,int y) {
    if (x <= y) return p * (y - x);
    return (x - y) * q;
}
int main() {
    int n = read();
    LL sum = 0;
    for (int i=1; i<=n; ++i) A[i] = read(), sum += A[i];
    sort(A+1, A+n+1);
    p = read(), q = read(), r = read();
    for (int i=0; i<=n; ++i) 
        for (int j=0; j<=n; ++j) f[i][j] = 1e18;
    LL Ans = sum * q;
    f[0][0] = 0;
    for (int i=1; i<=n; ++i) 
        for (int j=1; j<=i; ++j) 
            f[i][j] = min(f[i-1][j], f[i-1][j-1]) + calcc(A[i], j);
    for (int i=1; i<=n; ++i) 
        Ans = min(Ans, f[n][i] + r);
    cout << Ans;
    return 0;
}

T2

一个环删掉连续的一段，剩下的也是连续的一段，所以考虑剩下的一段。
如果原串中有相邻的相同字符，则在相同字符处切开，然后把环切成了若干段（每一段内都没有相邻的相同的字符了），剩下的显然是某个段的一部分
判断某个段是否有长度为x的头尾不同的子段，相当于判断一个前缀和一个后缀是否相同，使用KMP或hash即可
如果原串中没有相邻的相同字符，求出原串的所有循环节，如果长度为gcd(n,x)的前缀是原串的循环节，则不存在某个长度为x+1的首尾不同的子段

kmp判断方法。
判断前缀和后缀是否相同，假设1~i和n-i+1~n是相同的，那么说明长度n-i+1的所有串一定是首尾相同的。
就是前缀的第一个，和后缀的第一个相同，前缀的第二个和后缀的第二个也相同...所以长度为（pos[后缀第一个]-pos[前缀第一个]+1）的字符串全部是首尾相同的。
（pos[后缀第一个]-pos[前缀第一个]+1）这里第几个都行。

//未评测，过大样例
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
inline int read() {
    int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f = -1;
    for (; isdigit(ch); ch=getchar()) x = x * 10 + ch - '0'; return x * f;
}
const int N = 2000100;
int p[N], ban[N], OK[N];
char s[N], t[N];
void calcc(int n) {
    p[1] = 0;
    for (int i=2; i<=n; ++i) {
        int j = p[i - 1];
        while (j && t[i] != t[j + 1]) j = p[j];
        if (t[i] == t[j + 1]) j ++;
        p[i] = j;
    }
    for (int i=p[n]; i; i=p[i]) ban[n - i + 1] = 1;
    for (int i=1; i<=n; ++i) if (!ban[i]) OK[i] = 1;
    for (int i=p[n]; i; i=p[i]) ban[n - i + 1] = 0;
}
void solve() {
    int n = strlen(s + 1), len = n << 1, cnt = 0;
    for (int i=1; i<=n; ++i) s[i + n] = s[i];
    t[++cnt] = s[1];
    for (int i=2; i<=len; ++i) {
        if (s[i] == s[i - 1]) calcc(cnt), cnt = 0;
        t[++cnt] = s[i];
    }
    if (cnt) calcc(cnt);
    for (int i=0; i<n; ++i) putchar(OK[n - i] + '0');puts("");
    for (int i=1; i<=len; ++i) OK[i] = 0;
}
int main() {
    freopen("ex_b2.in","r",stdin);
    freopen("b.txt","w",stdout);
    int Case = 0;
    while (~scanf("%s",s+1)) 
        printf("Case %d:",++Case), solve(); 
    return 0;
}