目录
复健复健！ 终于来到了我的回合！
1 dp（打牌）
1.1 斜率优化
\[f_n=f_m+(n-m+s_n-s_m-L)^2\\ f_n=f_m+(T_n-T_m-L)^2\\ f_n-T_n^2-L^2+2LT_n+2T_nT_m=f_m+T_m^2+2LT_m\\ \]点为\((T_m,f_m+T_m^2+2LT_m)\)，
#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a), en = (b); i <= en; ++i)
#define Rof(i, a, b) for(int i = (a), en = (b); i >= en; --i)
#define Tra(u, i) for(int i = hd[u]; ~i; i = e[i].net)
#define cst const
#define LL long long
#define DD double
#define LD long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define eps 1e-12
#define maxn 50000
using namespace std;
int n, L, a[maxn + 5];
LL sum[maxn + 5], f[maxn + 5], t[maxn + 5];
template <class T>
void read(T &x){
char ch;
bool ok;
for(ok = 0, ch = getchar(); !isdigit(ch); ch = getchar()) if(ch == '-') ok = 1;
for(x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
if(ok) x = -x;
}
LL get_y(int x){
return f[x] + t[x] * t[x] + 2ll * L * t[x];
}
double get_k(int x, int y){
return (double)(get_y(x) - get_y(y)) / (t[x] - t[y]);
}
int st[maxn + 5], l = 1, r = 1;
int main(){
//freopen("in", "r", stdin);
read(n); read(L); L++;
For(i, 1, n) read(a[i]), sum[i] = sum[i - 1] + a[i], t[i] = sum[i] + i;
For(i, 1, n){
while(l < r && get_k(st[l], st[l + 1]) < 2ll * t[i]) l++;
f[i] = f[st[l]] + (t[i] - t[st[l]] - L) * (t[i] - t[st[l]] - L);
while(l < r && get_k(st[r - 1], st[r]) > get_k(st[r], i)) r--;
st[++r] = i;
}
printf("%lld\n", f[n]);
return 0;
}
2 字符串
2.1 kmp（看猫片）
#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a), en = (b); i <= en; ++i)
#define Rof(i, a, b) for(int i = (a), en = (b); i >= en; --i)
#define Tra(u, i) for(int i = hd[u]; ~i; i = e[i].net)
#define cst const
#define LL long long
#define DD double
#define LD long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define eps 1e-12
#define maxn 1000000
using namespace std;
int n, m, to[maxn + 5];
char s1[maxn + 5], s2[maxn + 5];
template <class T>
void read(T &x){
char ch;
bool ok;
for(ok = 0, ch = getchar(); !isdigit(ch); ch = getchar()) if(ch == '-') ok = 1;
for(x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
if(ok) x = -x;
}
int main(){
//freopen("in", "r", stdin);
scanf("%s %s", s1 + 1, s2 + 1);
n = strlen(s1 + 1); m = strlen(s2 + 1);
int now = 0;
For(i, 2, m){
while(now && s2[now + 1] != s2[i]) now = to[now];
if(s2[now + 1] == s2[i]) to[i] = ++now;
}
now = 0;
For(i, 1, n){
while(now && s2[now + 1] != s1[i]) now = to[now];
if(s2[now + 1] == s1[i]) now++;
if(now == m) printf("%d\n", i - m + 1);
}
For(i, 1, m) printf("%d ", to[i]);
return 0;
}
2.2 ac自动机（树上看猫片）
#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a), en = (b); i <= en; ++i)
#define Rof(i, a, b) for(int i = (a), en = (b); i >= en; --i)
#define Tra(u, i) for(int i = hd[u]; ~i; i = e[i].net)
#define cst const
#define LL long long
#define DD double
#define LD long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define eps 1e-12
#define maxn 1000000
using namespace std;
int n, tot = 0, pos[maxn + 5], as = 0;
char s[maxn + 5];
struct Node{
int ch[30], to, ok;
} tr[maxn + 5];
template <class T>
void read(T &x){
char ch;
bool ok;
for(ok = 0, ch = getchar(); !isdigit(ch); ch = getchar()) if(ch == '-') ok = 1;
for(x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
if(ok) x = -x;
}
int q[maxn + 5], l = 1, r = 0;
void sol(){
For(i, 0, 25) if(tr[0].ch[i]) q[++r] = tr[0].ch[i];
while(l <= r){
int now = q[l++];
For(i, 0, 25){
int to = tr[now].ch[i];
if(to) tr[to].to = tr[tr[now].to].ch[i], q[++r] = to;
else tr[now].ch[i] = tr[tr[now].to].ch[i];
}
}
}
int main(){
// freopen("in", "r", stdin);
read(n);
For(i, 1, n){
scanf("%s", s + 1);
int len = strlen(s + 1), now = 0;
For(j, 1, len){
int x = s[j] - 'a';
if(!tr[now].ch[x]) tr[now].ch[x] = ++tot;
now = tr[now].ch[x];
}
pos[i] = now;
}
sol();
scanf("%s", s + 1);
int len = strlen(s + 1), now = 0;
For(i, 1, len){
now = tr[now].ch[s[i] - 'a'];
tr[now].ok = 1;
}
Rof(i, r, 1) tr[tr[q[i]].to].ok |= tr[q[i]].ok;
For(i, 1, n) as += tr[pos[i]].ok;
printf("%d\n", as);
return 0;
}