一位在退学边缘疯狂试探的学渣为了高代不挂科做出的最终努力

33281378432849
## 1. 爪形行列式

1. 求$D_n = \left| {\begin{array}{*{20}{c}} {{x_1}}&1& \cdots &1\\ 1&{{x_2}}& \cdots &0\\ \vdots & \vdots & \ddots &0\\ 1&0&0&{{x_n}} \end{array}} \right|$

## 2. 两三角型行列式

1. 求$D_n = \left| {\begin{array}{*{20}{c}} {{x_1}}&b& \cdots &b\\ b&{{x_2}}& \cdots &b\\ \vdots & \vdots & \ddots &b\\ b&b&b&{{x_n}} \end{array}} \right|$
2. 求${D_n} = \left| {\begin{array}{*{20}{c}} {{x_1}}&b&b& \cdots &b\\ a&{{x_2}}&b& \cdots &b\\ a&a&{{x_3}}& \cdots &b\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a&a&a& \cdots &{{x_n}} \end{array}} \right|$
3. 求${D_n} = \left| {\begin{array}{*{20}{c}} d&b&b& \cdots &b\\ c&x&a& \cdots &a\\ c&a&x& \cdots &a\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c&a&a& \cdots &x \end{array}} \right|$

## 3. 两条线型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}} {{a_1}}&{{b_1}}&0& \cdots &0\\ 0&{{a_2}}&{{b_2}}& \cdots &0\\ 0&0&{{a_3}}& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {{b_n}}&0&0& \cdots &{{a_n}} \end{array}} \right|$

## 4. 范德蒙德型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}} {{a_1^n}}&{{a_1^{n-1}b_1}}& \cdots &a_1b_1^{n-1}&b_1^n\\ a_2^n&a_2^{n-1}b_2&\cdots & a_2b_2^{n-1} &b_2^n\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_n^n & a_n^{n-1}b_n & \cdots & a_nb_n^{n-1}& b_n^n \\ a_{n+1}^n&a_{n+1}^{n-1}b_{n+1}&\cdots&a_{n+1}b_{n+1}^{n-1} &b_{n+1}^n \end{array}} \right|$

## 5. Hessenberg型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}} 1&2&3& \cdots &n\\ 1&{ - 1}&0& \cdots &0\\ 0&2&{ - 2}& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0&0&0& \cdots &{1 - n} \end{array}} \right|$

## 6. 三对角型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}} a&b&0& \cdots &0\\ c&a&b& \cdots &0\\ 0&c&a& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0&0&0& \cdots &a \end{array}} \right|$

## 7. 各行元素和相等型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}} {1 + {x_1}}&{{x_1}}&{{x_1}}& \cdots &{{x_1}}\\ {{x_2}}&{1 + {x_2}}&{{x_2}}& \cdots &{{x_2}}\\ {{x_3}}&{{x_3}}&{1 + {x_3}}& \cdots &{{x_3}}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {{x_n}}&{{x_n}}&{{x_n}}& \cdots &{1 + {x_n}} \end{array}} \right|​$

## 8. 相邻两行对应元素相差K倍型行列式

1. 求${D_n} = \left| {\begin{array}{*{20}{c}} 0&1&2& \cdots &{n - 1}\\ 1&0&1& \cdots &{n - 2}\\ 2&1&0& \cdots &{n - 3}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {n - 1}&{n - 2}&1& \cdots &0 \end{array}} \right|$
2. 求${D_n} = \left| {\begin{array}{*{20}{c}} 1&a&{{a^2}}& \cdots &{{a^{n - 1}}}\\ {{a^{n - 1}}}&1&a& \cdots &{{a^{n - 2}}}\\ {{a^{n - 2}}}&{{a^{n - 1}}}&1& \cdots &{{a^{n - 3}}}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a&{{a^2}}&{{a^3}}& \cdots &1 \end{array}} \right|$


莫比乌斯反演与容斥原理

mobius_and_inclusion_exclusion_principle

【Tricks】Hello World！

#define _________ }
#define ________ putchar
#define _______ main
#define _(a) ________(a);
#define ______ _______(){
#define __ ______ _(0x48)_(0x65)_(0x6C)_(0x6C)
#define ___ _(0x6F)_(0x2C)_(0x20)_(0x77)_(0x6F)
#define ____ _(0x72)_(0x6C)_(0x64)_(0x21)
#define _____ __ ___ ____ _________
#include<stdio.h>
_____


【BZOJ 4817】[SDOI2017] 树点涂色

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = N << 1;
const int LOG = 20;

int n, m, head[N], nxt[M], to[M];
int in[N], ot[N], dep[N], num[N], ff[N][LOG];

inline int read() {
char c = getchar(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline void AddEdge(int u, int v) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E;
to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline int LCA(int u, int v) {
if (dep[u] < dep[v]) {
swap(u, v);
}
for (int j = LOG - 1; ~j; j--) {
if (dep[ff[u][j]] >= dep[v]) {
u = ff[u][j];
}
}
if (u == v) {
return u;
}
for (int j = LOG - 1; ~j; j--) {
if (ff[u][j] != ff[v][j]) {
u = ff[u][j];
v = ff[v][j];
}
}
return ff[u][0];
}

class SegmentTree{
int root, ch[M][2], tag[M], mx[M];
public:
inline void init() {
build(root, 1, n);
}
inline void modify(int l, int r, int d) {
modify(root, 1, n, l, r, d);
}
inline int query(int l, int r = -1) {
return query(root, 1, n, l, r >= 0? r: l);
}
private:
inline void PushDown(int w) {
if (tag[w]) {
int ls = ch[w][0], rs = ch[w][1];
mx[ls] += tag[w];
mx[rs] += tag[w];
tag[ls] += tag[w];
tag[rs] += tag[w];
tag[w] = 0;
}
}
inline int query(int w, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return mx[w];
} else {
PushDown(w);
int mid = l + r + 1 >> 1, ret = 0;
if (L < mid) {
ret = max(ret, query(ch[w][0], l, mid - 1, L, R));
}
if (mid <= R) {
ret = max(ret, query(ch[w][1], mid, r, L, R));
}
return ret;
}
}
inline void modify(int w, int l, int r, int L, int R, int d) {
if (L <= l && r <= R) {
tag[w] += d;
mx[w] += d;
} else {
PushDown(w);
int mid = l + r + 1 >> 1;
if (L < mid) {
modify(ch[w][0], l, mid - 1, L, R, d);
}
if (mid <= R) {
modify(ch[w][1], mid, r, L, R, d);
}
mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]);
}
}
inline void build(int &w, int l, int r) {
static int cnt = 0;
w = ++cnt;
if (l == r) {
mx[w] = dep[num[l]];
} else {
int mid = l + r + 1 >> 1;
build(ch[w][0], l, mid - 1);
build(ch[w][1], mid, r);
mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]);
}
}
}SGT;

int ch[N][2], fa[N];
public:
inline void SetFather(int w, int f) {
fa[w] = f;
}
inline void access(int x) {
for (int last = 0; x; last = x, x = fa[x]) {
splay(x);
if (fa[x]) {
int p = GetMin(x);
SGT.modify(in[p], ot[p], -1);
}
if (ch[x][1]) {
int p = GetMin(ch[x][1]);
SGT.modify(in[p], ot[p], 1);
}
ch[x][1] = last;
}
}
private:
inline bool IsRoot(int x) {
return !fa[x] || (ch[fa[x]][0] != x && ch[fa[x]][1] != x);
}
inline int GetMin(int x) {
return ch[x][0]? GetMin(ch[x][0]): x;
}
inline void splay(int x) {
for (int f, ff; !IsRoot(x); ) {
f = fa[x], ff = fa[f];
if (IsRoot(f)) {
rotate(x);
} else {
if ((ch[ff][0] == f) ^ (ch[f][0] == x)) {
rotate(x);
rotate(x);
} else {
rotate(f);
rotate(x);
}
}
}
}
inline void rotate(int x) {
int f = fa[x], t = ch[f][1] == x;
fa[x] = fa[f];
if (!IsRoot(f)) {
ch[fa[f]][ch[fa[f]][1] == f] = x;
}
ch[f][t] = ch[x][t ^ 1];
fa[ch[x][t ^ 1]] = f;
ch[x][t ^ 1] = f;
fa[f] = x;
}
}LCT;

inline void DFS(int w, int f) {
static int ID = 0;
LCT.SetFather(w, f);
ff[w][0] = f;
dep[w] = dep[f] + 1;
num[in[w] = ++ID] = w;
for (int i = head[w]; i; i = nxt[i]) {
if (to[i] != f) {
DFS(to[i], w);
}
}
ot[w] = ID;
}

int main() {
for (int i = 1; i < n; i++) {
}
DFS(1, 0);
for (int j = 1; j < LOG; j++) {
for (int i = 1; i <= n; i++) {
ff[i][j] = ff[ff[i][j - 1]][j - 1];
}
}
SGT.init();
for (int i = 1; i <= m; i++) {
int opt = read();
if (opt == 1) {
} else if (opt == 2) {
int u = read(), v = read(), lca = LCA(u, v);
printf("%d\n", SGT.query(in[u]) + SGT.query(in[v]) - 2 * SGT.query(in[lca]) + 1);
} else {
int x = read();
printf("%d\n", SGT.query(in[x], ot[x]));
}
}
return 0;
}


【BZOJ 4589】Hard Nim

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int MOD = 1000000007;
const int REV = 500000004;

bool vis[N];
int arr[N];

inline int read() {
char c = getchar(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline int Pow(int w, int t) {
int ret = 1;
for (; t; t >>= 1, w = (LL)w * w % MOD) {
if (t & 1) {
ret = (LL)ret * w % MOD;
}
}
return ret;
}

inline void FWT(int *a, int len, int opt = 1) {
for (int d = 1; d < len; d <<= 1) {
for (int i = 0; i < len; i += d << 1) {
for (int j = 0; j < d; j++) {
int t1 = a[i + j], t2 = a[i + j + d];
if (opt == 1) {
a[i + j] = (t1 + t2) % MOD;
a[i + j + d] = (t1 - t2) % MOD;
} else {
a[i + j] = (LL)(t1 + t2) * REV % MOD;
a[i + j + d] = (LL)(t1 - t2) * REV % MOD;
}
}
}
}
}

int main() {
for (int n, m; ~scanf("%d %d", &n, &m); ) {
memset(arr, 0, sizeof(arr));
for (int i = 2; i <= m; i++) {
if (!vis[i]) {
arr[i] = 1;
for (int j = i << 1; 0 <= j && j <= m; j += i) {
vis[j] = 1;
}
}
}
int len = 1;
for (; len <= m; len <<= 1);
FWT(arr, len);
for (int i = 0; i < len; i++) {
arr[i] = Pow(arr[i], n);
}
FWT(arr, len, -1);
printf("%d\n", (arr[0] + MOD) % MOD);
}
return 0;
}


【BZOJ 4599】[JLOI2016] 成绩比较

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200;
const int MOD = 1000000007;

int n,m,K,r[N],u[N],f[N],g[N],h[N],alpha[N],C[N][N];

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int Pow(int w, int t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD) {
if (t & 1) {
ret = (LL)ret * w % MOD;
}
}
return ret;
}

inline int LagrangePolynomial(int x, int len, int *ff, int *xx) {
int ret = 0;
for (int i=1;i<=len;i++) {
int tmp = ff[i];
for (int j=1;j<=len;j++) {
if (i == j) continue;
tmp = (LL)tmp * (x - xx[j]) % MOD;
tmp = (LL)tmp * Pow(xx[i] - xx[j], MOD-2) % MOD;
}
ret = (ret + tmp) % MOD;
}
return (ret + MOD) % MOD;
}

int main() {
for (int i=1;i<=m;i++) {
}
for (int i=1;i<=m;i++) {
}
//预处理组合数
C[0][0] = 1;
for (int i=1;i<=n;i++) {
C[i][0] = 1;
for (int j=1;j<=i;j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
//拉格朗日插值
for (int w=1;w<=m;w++) {
for (int i=1;i<=n+1;i++) {
f[i] = 0; h[i] = i;
for (int j=1;j<=i;j++) {
f[i] = (f[i] + (LL)Pow(i-j, r[w]-1) * Pow(j, n-r[w])) % MOD;
}
}
g[w] = LagrangePolynomial(u[w], n+1, f, h);
}
//广义容斥原理
int ans = 0;
for (int i=K,t=1;i<=n;i++,t*=-1) {
alpha[i] = C[n-1][i];
for (int j=1;j<=m;j++) {
alpha[i] = (LL)alpha[i] * C[n-1-i][r[j]-1] % MOD * g[j] % MOD;
}
ans = (ans + t * (LL)C[i][K] * alpha[i]) % MOD;
}
printf("%d\n",(ans+MOD)%MOD);
return 0;
}


【BZOJ 4318】OSU!

解题报告

$E_{(i,x^2)}，E_{(i,x)}$分别表示$x^2,x$的期望

$E_{(i,x^3)}=p_i \times E_{(i-1,(x+1)^3)}$
$E_{(i,x^2)}=p_i \times E_{(i-1,(x+1)^2)}$
$E_{(i,x)}=p_i \times (E_{(i-1,x)} + 1)$

$E_{(i,x^3)}=p_i \times (E_{(i-1,x^3)} + 3E_{(i-1,x^2)} + 3E_{(i-1,x)} + 1)$
$E_{(i,x^2)}=p_i \times (E_{(i-1,x^2)} + 2E_{(i-1,x)} + 1)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int main() {
double e1=0,e2=0,e3=0,ans=0,p;
for (int i=1;i<=n;i++) {
scanf("%lf",&p);
ans += e3 * (1 - p);
e3 = p * (e3 + 3 * e2 + 3 * e1 + 1);
e2 = p * (e2 + 2 * e1 + 1);
e1 = p * (e1 + 1);
}
printf("%.1lf\n",ans+e3);
return 0;
}


【BZOJ 3881】[COCI2015] Divljak

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 2000009;
const int LOG = 26;
const int SGZ = 26;

int in[N];

inline int read() {
char c = getchar(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

class Ac_Automaton{
int root, cnt, ch[N][SGZ], fail[N], pos[N], dep[N];
int head[N], to[N], nxt[N], ot[N], fa[N][LOG];
class FenwickTree{
int mx, sum[N];
public:
inline void init(int nn) {
mx = nn;
}
inline void modify(int p, int d) {
for (int i = p; i <= mx; i += lowbit(i)) {
sum[i] += d;
}
}
inline int query(int l, int r) {
int ret = 0;
for (int i = l - 1; i > 0; i -= lowbit(i)) {
ret -= sum[i];
}
for (int i = r; i; i -= lowbit(i)) {
ret += sum[i];
}
return ret;
}
private:
}bit;
public:
inline void insert(char *s, int nn, int id) {
int w = root;
for (int i = 1; i <= nn; i++) {
int cc = s[i] - 'a';
if (!ch[w][cc]) {
ch[w][cc] = ++cnt;
}
w = ch[w][cc];
}
pos[id] = w;
}
inline void build() {
static queue<int> que;
for (int i = 0; i < SGZ; i++) {
if (ch[root][i]) {
que.push(ch[root][i]);
}
}
for (; !que.empty(); que.pop()) {
int w = que.front();
for (int i = 0; i < SGZ; i++) {
if (!ch[w][i]) {
ch[w][i] = ch[fail[w]][i];
} else {
que.push(ch[w][i]);
fail[ch[w][i]] = ch[fail[w]][i];
}
}
}
DFS(0, 0);
for (int j = 1; j < LOG; j++) {
for (int i = 0; i <= cnt; i++) {
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
}
bit.init(cnt + 1);
}
inline void match(char *s, int nn) {
static vector<int> vt[N];
static int que[N], stk[N], vis[N];
int qtot = 0, stot = 0, vtot = 0;
que[++qtot] = root;
for (int i = 1, w = root; i <= nn; i++) {
w = ch[w][s[i] - 'a'];
que[++qtot] = w;
}
sort(que + 1, que + 1 + qtot);
qtot = unique(que + 1, que + 1 + qtot) - que - 1;
sort(que + 1, que + 1 + qtot, cmp);
for (int i = 1; i <= qtot; i++) {
if (stot) {
int lca = LCA(que[i], stk[stot]);
for (; stot && dep[stk[stot]] > dep[lca]; --stot) {
if (stot > 1 && dep[stk[stot - 1]] >= dep[lca]) {
vt[stk[stot - 1]].push_back(stk[stot]);
} else {
vt[lca].push_back(stk[stot]);
}
}
if (stot && stk[stot] != lca) {
stk[++stot] = lca;
vis[++vtot] = lca;
}
}
stk[++stot] = que[i];
vis[++vtot] = que[i];
}
for (; stot > 1; --stot) {
vt[stk[stot - 1]].push_back(stk[stot]);
}
update(root, vt);
for (int i = 1; i <= vtot; i++) {
vt[vis[i]].clear();
}
}
inline int query(int id) {
return bit.query(in[pos[id]], ot[pos[id]]);
}
private:
inline void update(int w, vector<int> *vt) {
for (int i = 0; i < (int)vt[w].size(); i++) {
bit.modify(in[w], -1);
bit.modify(in[vt[w][i]], 1);
update(vt[w][i], vt);
}
}
inline int LCA(int a, int b) {
if (dep[a] < dep[b]) {
swap(a, b);
}
for (int j = SGZ - 1; ~j; j--) {
if (dep[fa[a][j]] >= dep[b]) {
a = fa[a][j];
}
}
if (a == b) {
return a;
}
for (int j = SGZ - 1; ~j; j--) {
if (fa[a][j] != fa[b][j]) {
a = fa[a][j];
b = fa[b][j];
}
}
return fa[a][0];
}
static bool cmp(int a, int b) {
return in[a] < in[b];
}
inline void DFS(int w, int f) {
static int tt = 0;
in[w] = ++tt;
dep[w] = dep[fa[w][0] = f] + 1;
for (int i = head[w]; i; i = nxt[i]) {
DFS(to[i], w);
}
ot[w] = tt;
}
inline void AddEdge(int u, int v) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E;
}
}ac;

int main() {
static char ss[N];
int n = read();
for (int i = 1; i <= n; i++) {
scanf("%s", ss + 1);
int len = strlen(ss + 1);
ac.insert(ss, len, i);
}
ac.build();
int m = read();
for (int i = 1; i <= m; i++) {
if (read() == 1) {
scanf("%s", ss + 1);
int len = strlen(ss + 1);
ac.match(ss, len);
} else {
}
}
return 0;
}


【BZOJ 3672】[NOI2014] 购票

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;
const int M = N << 1;
const LL INF = 6e18;

int n, head[N], nxt[M], to[M], fa[N];
LL q[N], p[N], len[N], dep[N], f[N];

struct Point{
LL x, y, id, range;
inline Point() {
}
inline Point(LL a, LL b, LL c, LL d):x(a), y(b), id(c), range(d) {
}
inline bool operator < (const Point &P) const {
return x > P.x || (x == P.x && y > P.y);
}
inline Point operator - (const Point &P) {
return Point(x - P.x, y - P.y, 0, 0);
}
inline double operator * (const Point &P) {
return (double)x * P.y - (double)y * P.x;
}
inline double slope(const Point &P) {
return (double)(y - P.y) / (x - P.x);
}
static bool update(const Point &P1, const Point &P2) {
return P1.range > P2.range;
}
};

inline LL read() {
char c = getchar(); LL ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline void AddEdge(int u, int v) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E;
to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

class DivideAndConquer{
int sz[N], vis[N];
public:
inline void solve(int w, int universe) {
int top = w;
vis[w = FindRoot(w, universe)] = 1;
if (fa[w] && !vis[fa[w]]) {
solve(top, universe - sz[w]);
}
vector<Point> cvx;
for (int nw = fa[w]; dep[nw] >= dep[top]; nw = fa[nw]) {
cvx.push_back(Point(dep[nw], f[nw], nw, dep[nw] - len[nw]));
}
vector<Point> que;
que.push_back(Point(dep[w], 0, w, dep[w] - len[w]));
for (int i = head[w]; i; i = nxt[i]) {
if (dep[to[i]] > dep[w] && !vis[to[i]]) {
DFS(to[i], w, que);
}
}

sort(que.begin(), que.end(), Point::update);
sort(cvx.begin(), cvx.end());
for (int i = 0, j = 0, tot = 0; i < (int)que.size(); i++) {
for (; j < (int)cvx.size() && cvx[j].x >= que[i].range; j++) {
for (; tot > 1 && (cvx[tot - 1] - cvx[tot - 2]) * (cvx[j] - cvx[tot - 2]) >= 0; --tot);
cvx[tot++] = cvx[j];
}
int ret = tot - 1, l = 0, r = tot - 2, mid, k = que[i].id;
while (l <= r) {
mid = l + r >> 1;
if (cvx[mid].slope(cvx[mid + 1]) <= p[k]) {
ret = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (ret >= 0) {
f[k] = min(f[k], cvx[ret].y + (dep[k] - cvx[ret].x) * p[k] + q[k]);
}
}
for (int i = 0, j; i < (int)que.size(); i++) {
if (j = que[i].id, que[i].range <= dep[w]) {
f[j] = min(f[j], f[w] + (dep[j] - dep[w]) * p[j] + q[j]);
}
}
que.clear();
cvx.clear();

for (int i = head[w]; i; i = nxt[i]) {
if (dep[to[i]] > dep[w] && !vis[to[i]]) {
solve(to[i], sz[to[i]]);
}
}
}
private:
inline int FindRoot(int w, int universe) {
int ret = 0, ans;
FindRoot(w, w, universe, ret, ans);
return ret;
}
inline void FindRoot(int w, int f, int universe, int &ret, int &ans) {
int mx = 1; sz[w] = 1;
for (int i = head[w]; i; i = nxt[i]) {
if (!vis[to[i]] && to[i] != f) {
FindRoot(to[i], w, universe, ret, ans);
sz[w] += sz[to[i]];
mx = max(mx, sz[to[i]]);
}
}
mx = max(mx, universe - sz[w]);
if (!ret || mx < ans) {
ans = mx;
ret = w;
}
}
inline void DFS(int w, int f, vector<Point> &ret) {
ret.push_back(Point(dep[w], 0, w, dep[w] - len[w]));
for (int i = head[w]; i; i = nxt[i]) {
if (!vis[to[i]] && to[i] != f) {
DFS(to[i], w, ret);
}
}
}
}DAC;

int main() {
for (int i = 2; i <= n; i++) {
dep[i] = dep[fa[i]] + c;
}
fill(f, f + N, INF);
f[1] = 0; dep[0] = -1;
DAC.solve(1, n);
for (int i = 2; i <= n; i++) {
printf("%lld\n", f[i]);
}
return 0;
}


【BZOJ 4198】[NOI2015] 荷马史诗

k叉哈夫曼树

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

struct Data{
LL apt, mx;
inline Data() {
}
inline Data(LL a, LL c):apt(a), mx(c) {
}
inline Data operator + (const Data &d) {
return Data(apt + d.apt, max(mx, d.mx + 1));
}
inline bool operator < (const Data &d) const {
return apt > d.apt || (apt == d.apt && mx > d.mx);
}
};
priority_queue<Data> que;

inline LL read() {
char c=getchar(); LL ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int main() {
int n = read(), k = read();
for (int i = 1; i <= n; i++) {
}
LL ans = 0;
for (bool frt = (n - 1) % (k - 1); (int)que.size() > 1; frt = 0) {
Data np(0, 0);
for (int i = frt? 1 + (n - 1) % (k - 1): k; i; --i) {
np = np + que.top();
que.pop();
}
ans += np.apt;
que.push(np);
}
printf("%lld\n%lld\n", ans, que.top().mx);
return 0;
}


【BZOJ 3940】[Usaco2015 Feb] Censoring

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int SGZ = 26;

char ctn[N], wrd[N];

inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

class AC_Automaton{
int Root, cnt, ch[N][SGZ], apt[N], dep[N], fail[N];
queue<int> que;
public:
inline void insert(char *s, int len) {
int w = Root;
for (int i = 1; i <= len; i++) {
int  cc = s[i] - 'a';
if (!ch[w][cc]) {
ch[w][cc] = ++cnt;
dep[cnt] = dep[w] + 1;
}
w = ch[w][cc];
}
apt[w] = len;
}
inline void build() {
for (int i = 0; i < SGZ; i++) {
if (ch[Root][i]) {
que.push(ch[Root][i]);
}
}
for (; !que.empty(); que.pop()) {
int w = que.front();
for (int i = 0; i < SGZ; i++) {
if (ch[w][i]) {
fail[ch[w][i]] = ch[fail[w]][i];
apt[ch[w][i]] = max(apt[ch[w][i]], apt[fail[ch[w][i]]]);
que.push(ch[w][i]);
} else {
ch[w][i] = ch[fail[w]][i];
}
}
}
}
inline int root() {
return Root;
}
inline int move(int &w, int cc) {
w = ch[w][cc];
return apt[w];
}
}aca;

int main() {
scanf("%s", ctn + 1);
int n = read(), m = strlen(ctn + 1);
for (int i = 1; i <= n; i++) {
scanf("%s", wrd + 1);
aca.insert(wrd, strlen(wrd + 1));
}
aca.build();
vector<int> ans, pos;
for (int i = 1; i <= m; i++) {
int w = pos.empty()? aca.root(): *--pos.end();
int len = aca.move(w, ctn[i] - 'a');
ans.push_back(ctn[i]);
pos.push_back(w);
for (int j = 1; j <= len; j++) {
ans.pop_back();
pos.pop_back();
}
}
for (int i = 0; i < (int)ans.size(); i++) {
putchar(char(ans[i]));
}
return 0;
}


【BZOJ 4566】[HAOI2016] 找相同字符

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 800009;
const int SGZ = 27;

int n, m;
char s[N];

class Suffix_Automaton{
int cnt, tail, ch[N][SGZ], fail[N], sz[N][2], len[N], head[N], nxt[N], to[N];
public:
inline void init() {
cnt = tail = 1;
for (int i = 1; i <= n; i++) {
append(s[i] - 'a', 0);
}
append(SGZ - 1, -1);
for (int i = n + 2; i <= n + m + 1; i++) {
append(s[i] - 'a', 1);
}
for (int i = 1; i <= cnt; i++) {
}
DFS(0, 0);
}
inline LL query() {
LL ret = 0;
for (int i = 1; i <= cnt; i++) {
ret += (LL)(len[i] - len[fail[i]]) * sz[i][0] * sz[i][1];
}
return ret;
}
private:
inline void DFS(int w, int f) {
for (int i = head[w]; i; i = nxt[i]) {
if (to[i] != f) {
DFS(to[i], w);
sz[w][0] += sz[to[i]][0];
sz[w][1] += sz[to[i]][1];
}
}
}
inline void AddEdge(int u, int v) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E;
}
inline void append(char cc, int t) {
int w = tail, cur = ++cnt;
if (t != -1) {
sz[cur][t] += 1;
}
len[cur] = len[tail] + 1;
for (tail = cur; w && !ch[w][cc]; ch[w][cc] = cur, w = fail[w]);
if (w) {
if (len[ch[w][cc]] == len[w] + 1) {
fail[cur] = ch[w][cc];
} else {
int nt = ++cnt, pt = ch[w][cc];
memcpy(ch[nt], ch[pt], sizeof(ch[nt]));
len[nt] = len[w] + 1;
fail[nt] = fail[pt];
fail[cur] = fail[pt] = nt;
for (; w && ch[w][cc] == pt; ch[w][cc] = nt, w = fail[w]);
}
} else {
fail[cur] = 1;
}
}
}sam;

int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
s[n + 1] = 'z' + 1;
scanf("%s", s + n + 2);
m = strlen(s + n + 2);
sam.init();
printf("%lld\n", sam.query());
return 0;
}


【BZOJ 4195】[NOI2015] 程序自动分析

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;
const int M = 300009;

int n, fa[N], cet[M], val[N], dif[N];

inline int read() {
char c = getchar(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline int find(int x) {
return fa[x] == x? x: fa[x] = find(fa[x]);
}

int main() {
freopen("prog.in", "r", stdin);
freopen("prog.out", "w", stdout);
for (int T = read(); T; T--) {
int tot = 0, cnt = 0, tt = 0;
for (int i = 1; i <= n; i++) {
cet[++tot] = val[++cnt] = read();
cet[++tot] = val[++cnt] = read();
}
sort(val + 1, val + 1 + cnt);
cnt = unique(val + 1, val + 1 + cnt) - val - 1;
for (int i = 1; i <= cnt; i++) {
fa[i] = i;
}
for (int i = 1; i <= n; i++) {
int t = cet[tot--];
int u = cet[tot--], v = cet[tot--];
u = lower_bound(val + 1, val + 1 + cnt, u) - val;
v = lower_bound(val + 1, val + 1 + cnt, v) - val;
if (t == 1) {
fa[find(u)] = find(v);
} else {
dif[++tt] = u;
dif[++tt] = v;
}
}
bool ok = 1;
for (int i = 1; i <= tt; i += 2) {
int u = dif[i], v = dif[i + 1];
if (find(u) == find(v)) {
ok = 0;
break;
}
}
puts(ok? "YES": "NO");
}
return 0;
}


【BZOJ 4196】[NOI2015] 软件包管理器

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 200009;

int n, m, head[N], nxt[N], to[N], beg[N], ot[N];
int fa[N], top[N], hvy[N], sz[N], dep[N];

inline int read() {
char c = getchar(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline void AddEdge(int u, int v) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E;
}

inline void DFS1(int w, int f) {
fa[w] = f;
dep[w] = dep[f] + 1;
sz[w] = 1;
for (int i = head[w]; i; i = nxt[i]) {
DFS1(to[i], w);
sz[w] += sz[to[i]];
if (sz[to[i]] > sz[hvy[w]]) {
hvy[w] = to[i];
}
}
}

inline void DFS2(int w, int t) {
static int dfc = 0;
beg[w] = ++dfc;
top[w] = t;
if (hvy[w]) {
DFS2(hvy[w], t);
for (int i = head[w]; i; i = nxt[i]) {
if (to[i] != hvy[w]) {
DFS2(to[i], to[i]);
}
}
}
ot[w] = dfc;
}

class Segment_Tree{
int cnt, root, ch[M][2], sum[M], tag[M];
public:
inline void init() {
init(root, 1, n);
}
inline int install(int w) {
int ret = 0, tmp;
while (true) {
int l = beg[top[w]], r = beg[w], len = r - l + 1;
tmp = len - modify(root, 1, n, beg[top[w]], beg[w], 1);
ret += tmp;
if (fa[top[w]] != w && tmp) {
w = fa[top[w]];
} else {
break;
}
}
return ret;
}
inline int uninstall(int w) {
return modify(root, 1, n, beg[w], ot[w], -1);
}
private:
inline void init(int &w, int l, int r) {
w = ++cnt;
if (l < r) {
int mid = l + r + 1 >> 1;
init(ch[w][0], l, mid - 1);
init(ch[w][1], mid, r);
}
}
inline void PushDown(int w, int l, int mid, int r) {
if (tag[w]) {
int ls = ch[w][0], rs = ch[w][1];
if (tag[w] == 1) {
sum[ls] = mid - l;
sum[rs] = r - mid + 1;
} else {
sum[ls] = sum[rs] = 0;
}
tag[ls] = tag[rs] = tag[w];
tag[w] = 0;
}
}
inline int modify(int w, int l, int r, int L, int R, int t) {
if (L <= l && r <= R) {
int ret = sum[w];
sum[w] = t == -1? 0: r - l + 1;
tag[w] = t;
return ret;
} else {
int mid = l + r + 1 >> 1, ret = 0;
PushDown(w, l, mid, r);
if (L < mid) {
ret += modify(ch[w][0], l, mid - 1, L, R, t);
}
if (mid <= R) {
ret += modify(ch[w][1], mid, r, L, R, t);
}
sum[w] = sum[ch[w][1]] + sum[ch[w][0]];
return ret;
}
}
}SGT;

int main() {
freopen("manager.in", "r", stdin);
freopen("manager.out", "w", stdout);
for (int i = 2; i <= n; i++) {
}
DFS1(1, 1);
DFS2(1, 1);
SGT.init();