## 【日常小测】三明治

### Code

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

const int N = 500;
const int INF = 1e7;

char mp[N][N];
int n, m, ans[N];
bool up[N][N], dw[N][N], InStack[N][N], vis[N][N];

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 F(int x, int y, int t) {
InStack[y][x] = 1;
int nx = x + (t == 1? 1: -1), ny = y, nt = t, ret = 1;
ret += vis[ny][nx]? 0: (InStack[ny][nx]? INF: F(nx, y, t));
nx = x; ny = up[y][x] == t? y - 1: y + 1; nt = up[y][x] == t? up[ny][nx]: dw[ny][nx];
ret += vis[ny][nx] || ret >= INF? 0: (InStack[ny][nx]? INF: F(nx, ny, nt));
vis[y][x] = 1;
InStack[y][x] = 0;
return ret > INF? INF: ret;
}

inline void init() {
memset(vis, 0, sizeof(vis));
for (int j = 1; j <= m; j++) {
vis[j][0] = 1;
vis[j][n + 1] = 1;
}
for (int i = 1; i <= n; i++) {
vis[0][i] = 1;
vis[m + 1][i] = 1;
}
}

int main() {
for (int j = 1; j <= m; j++) {
scanf("%s", mp[j] + 1);
for (int i = 1; i <= n; i++) {
up[j][i] = 1;
dw[j][i] = 0;
if (mp[j][i] == 'Z') {
swap(up[j][i], dw[j][i]);
}
}
}
for (int j = 1; j <= m; j++) {
init();
for (int i = n; i; i--) {
ans[i] = ans[i + 1] < INF? F(i, j, 1) + ans[i + 1]: INF;
}
init();
for (int i = 1; i <= n; i++) {
ans[i] = min(ans[i], ans[i - 1] < INF? F(i, j, 0) + ans[i - 1]: INF);
printf("%d ", ans[i] >= INF? -1: ans[i] << 1);
}
putchar('\n');
}
return 0;
}


## 【BZOJ 2471】Count

### Code

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

const int N = 16;
const int M = 10;
const int SGZ = 10;
const int MOD = 1000000007;

int n, m, nxt[M];
char s[M];
struct Transfer{
LL pos, cnt;
inline Transfer() {
}
inline Transfer(LL a, LL b):pos(a), cnt(b) {
}
inline Transfer operator + (const Transfer &T) {
return Transfer(T.pos, cnt + T.cnt);
}
}t[M][SGZ];
map<int, Transfer> f[N][M];
struct MatchStatus{
int HashVal;
Transfer t[M];
inline void GetHashVal() {
const static int MOD = 1000000007;
const static int SEED1 = 13, SEED2 = 131;
HashVal = 0;
for (int i = 0; i < m; i++) {
HashVal = (HashVal + (LL)t[i].pos * SEED2 + t[i].cnt) * SEED1 % MOD;
}
}
inline bool operator < (const MatchStatus &MS) const {
return HashVal < MS.HashVal;
}
};

inline Transfer DFS(int w, int p, const MatchStatus &cur) {
if (w <= 0) {
return cur.t[p];
} else if (f[w][p].count(cur.HashVal)) {
return f[w][p][cur.HashVal];
} else {
Transfer ret(p, 0);
for (int i = 0; i < SGZ; i++) {
MatchStatus nw = cur;
for (int j = 0; j < m; j++) {
nw.t[j] = nw.t[j] + t[nw.t[j].pos][i];
}
nw.GetHashVal();
ret = ret + DFS(w - 1, ret.pos, nw);
}
return f[w][p][cur.HashVal] = ret;
}
}

int main() {
while (~scanf("%d %s", &n, s + 1) && n) {
m = strlen(s + 1);
for (int i = 1; i <= m; i++) {
s[i] -= '0';
}
nxt[1] = 0;
for (int i = 2, j = 0; i <= m; nxt[i++] = j) {
for (; j && s[j + 1] != s[i]; j = nxt[j]);
j += s[j + 1] == s[i];
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < SGZ; j++) {
int k = i;
for (; k && s[k + 1] != j; k = nxt[k]);
k += s[k + 1] == j;
t[i][j] = k == m? Transfer(nxt[k], 1): Transfer(k, 0);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
f[i][j].clear();
}
}
Transfer ans(0, 0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j < SGZ; j++) {
MatchStatus cur;
for (int k = 0; k < m; k++) {
cur.t[k] = t[k][j];
}
cur.GetHashVal();
ans = ans + DFS(i - 1, ans.pos, cur);
}
}
printf("%lld\n", ans.cnt);
}
return 0;
}


## 【TopCoder SRM713】PowerEquation

### Code

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

const int MOD = 1000000007;
const int N = 100000;

int gcd[100][100];
bool vis[N];

class PowerEquation {
public:
int count(int n) {
memset(vis, 0, sizeof(vis));
for (int i=1;i<=50;i++) {
for (int j=1;j<=50;j++) {
gcd[i][j] = GCD(i, j);
}
}

int ret = (LL)n * n % MOD, dec = 0;
for (int i=2;1;i++) {
if (i * i > n) {
ret = (ret + (n - i + 1ll - dec) * n) % MOD;
break;
} else {
if (vis[i]) continue;
for (LL j=i*i;j<=n;j*=i) {
if (j * j <= n) vis[j] = 1;
else ++dec;
}

int mx = 1, tmp = 0; LL cur = i;
while (cur * i <= n) cur *= i, ++mx;
for (int a=1;a<=mx;a++) {
for (int b=1;b<=mx;b++) {
int c = max(b,a) / gcd[a][b];
tmp = (tmp + n / c) % MOD;
}
}
ret = (ret + tmp) % MOD;
}
}
return ret;
}
private:
int GCD(int a, int b) {
return b? GCD(b, a%b): a;
}
};


## 【日常小测】tree

### 解题报告

$f_{i,j}$表示在$i$的子树里，选$j$个点，直径包含$i$的最小花费
$g_{i,j}$表示在$i$的子树里，选$j$个点，已经考虑过直径且直径不包含$i$的最小花费

### Code

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

const int N = 3009;
const int M = N << 1;
const LL INF = 1e18;

LL vout=INF,f[N][N],g[N][N],h[N][N];

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;
}

inline void AddEdge(int u, int v, int c) {
static int E = 1; cost[E+1] = cost[E+2] = c;
}

void update(int w, int fa) {
fill(f[w], f[w]+1+N, INF);
fill(g[w], g[w]+1+N, INF);
fill(h[w], h[w]+1+N, INF);
f[w][1] = g[w][1] = h[w][1] = 0; sz[w] = 1;
if ((t=to[i]) != fa) {
update(to[i], w);
for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
for (int j=1;j<=sz[t];j++) {
g[w][x+j] = min(g[w][x+j], g[w][x] + h[t][j] + tmp);
g[w][x+j] = min(g[w][x+j], f[w][x] + f[t][j] + cost[i]);
g[w][x+j] = min(g[w][x+j], h[w][x] + g[t][j] + tmp);
}
}
for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
for (int j=1;j<=sz[t];j++) {
f[w][x+j] = min(f[w][x+j], h[w][x] + f[t][j] + cost[i]);
f[w][x+j] = min(f[w][x+j], f[w][x] + h[t][j] + tmp);
}
}
for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
for (int j=1;j<=sz[t];j++)
h[w][x+j] = min(h[w][x+j], h[w][x] + h[t][j] + tmp);
}
sz[w] += sz[t];
}
}
vout = min(vout, f[w][k]);
vout = min(vout, g[w][k]);
}

int main() {
for (int i=2,u,v;i<=n;i++) {
}
update(1, 1);
printf("%lld\n",vout);
return 0;
}


## 【日常小测】市场

### 题目大意

1. 区间加$c(-10^4 \le c \le 10^4)$
2. 区间除$d$。即对于单个元素$a_i$，除以$d$后变为$\lfloor \frac{a_i}{d} \rfloor$
3. 询问区间和
4. 询问区间最值

## 【BZOJ 4725】[POI2017] Reprezentacje ró?nicowe

### 解题报告

$63$项之后的，我们可以推公式推出来答案是多少

### Code

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

const int N = 10000;

int n,tot,vis[N],L[N],R[N],que[N];
LL f[N];

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;
}

inline void insert(int w) {
for (int i=w-1;i;i--) {
if (abs(f[w]-f[i]) >= N) break;
vis[abs(f[w]-f[i])] = 1;
}
}

inline int query() {
for (int i=1;i;i++)
if (!vis[i]) return i;
}

inline void Get_Ans(int w, int id) {
for (int j=2;j;j++) {
for (int i=1;i<j;i++) {
if (f[j] - f[i] == w) {
L[id] = i; R[id] = j;
return;
}
}
}
}

inline void query(int w) {
for (int j=2;j;j++) {
for (int i=1;i<j;i++) {
if (f[j] - f[i] == w) {
cout<<j<<' '<<i<<endl;
return;
}
}
}
}

int main() {
f[1] = 1; f[2] = 2; vis[1] = 1;
for (int i=3;i<=120;i++) {
if (i&1) f[i] = f[i-1] << 1;
else f[i] = f[i-1] + query();
insert(i);
}
for (int j=2;j<=63;j++) {
for (int i=1;i<j;i++) {
if (f[j] - f[i] > 1e9) continue;
que[++tot] = f[j] - f[i];
}
}
que[++tot] = (1e9) + 10;
sort(que+1, que+1+tot);
for (int i=1;i<tot;i++) Get_Ans(que[i], i);
p = lower_bound(que+1, que+1+tot, x) - que;
if (que[p] == x) printf("%d %d\n",R[p], L[p]);
else if (x <= 90) query(x);
else printf("%lld %lld\n",(x-90-p+62)*2ll+120,(x-90-p+62)*2ll+119);
}
return 0;
}


## 【Codeforces 781E】Andryusha and Nervous Barriers

### Code

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

const int N = 5000000;
const int M = 200009;
const int MOD = 1000000007;

int hit,wid,n,cnt;
struct Pack{int h,sum,del;}p[N];
struct Wall{int h,l,r,s;}wall[M];

class Segment_Tree{
int ans_tmp,tot,root,ch[M][2];
stack<int> s[M];
public:
inline void insert(int p, int id) {
insert(root, 1, wid, p, id);
}
inline int query(int h, int l, int r) {
ans_tmp = 0;
query(root, 1, wid, l, r, h);
return ans_tmp;
}
private:
void insert(int &w, int l, int r, int p, int v) {
if (!w) w = ++tot; s[w].push(v);
if (l < r) {
int mid = l + r + 1 >> 1;
if (p < mid) insert(ch[w][0], l, mid-1, p, v);
else insert(ch[w][1], mid, r, p, v);
}
}
void query(int w, int l, int r, int L, int R, int h) {
if (L <= l && r <= R) {
while (!s[w].empty() && p[s[w].top()].h <= h) {
if (!p[s[w].top()].del) {
p[s[w].top()].del = 1;
(ans_tmp += p[s[w].top()].sum) %= MOD;
} s[w].pop();
}
} else {
int mid = l + r + 1 >> 1;
if (L < mid) query(ch[w][0], l, mid-1, L, R, h);
if (mid <= R) query(ch[w][1], mid, r, L, R, h);
}
}
}SGT;

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;
}

int main() {
for (int i=1;i<=n;i++) {
}
for (int i=1;i<=wid;i++) {
p[++cnt].h = hit + 1;
p[cnt].sum = 1;
SGT.insert(i, cnt);
}
sort(wall+1, wall+1+n, [](const Wall &A, const Wall &B){return A.h > B.h;});
for (int i=1,h_mx,tmp;i<=n;i++) {
tmp = SGT.query(wall[i].h + wall[i].s, wall[i].l, wall[i].r);
p[++cnt].sum = tmp; p[cnt].h = wall[i].h;
p[++cnt].sum = tmp; p[cnt].h = wall[i].h;
if (wall[i].l == 1) SGT.insert(wall[i].r+1, cnt-1);
else SGT.insert(wall[i].l-1, cnt-1);
if (wall[i].r == wid) SGT.insert(wall[i].l-1, cnt);
else SGT.insert(wall[i].r+1, cnt);
}
int vout = 0;
for (int i=1;i<=cnt;i++)
(vout += (p[i].del ^ 1) * p[i].sum) %= MOD;
printf("%d\n",vout);
return 0;
}


## 【BZOJ 3926】[ZJOI2015] 诸神眷顾的幻想乡

### Code

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

const int N = 200000+9;
const int M = 2000000;
const int C = 10;

class Suffix_Automaton{
int ch[M][C],pre[M],len[M],cnt;
public:
inline int insert(int last, int t) {
int w = ++cnt; len[w] = len[last] + 1; pre[0] = -1;
for (;~last&&!ch[last][t];last=pre[last]) ch[last][t] = w;
if (~last) {
if (len[ch[last][t]] == len[last] + 1) {
pre[w] = ch[last][t];
} else {
int nw = ++cnt, tmp = ch[last][t];
len[nw] = len[last] + 1;
pre[nw] = pre[tmp]; pre[tmp] = pre[w] = nw;
memcpy(ch[nw],ch[tmp],sizeof(ch[nw]));
for (;~last&&ch[last][t]==tmp;last=pre[last]) ch[last][t] = nw;
}
} return w;
}
inline LL solve() {
LL ret = 0;
for (int i=1;i<=cnt;i++)
ret += len[i] - len[pre[i]];
return ret;
}
}SAM;

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 void Add_Edge(int u, int v) {
static int E = 1; in[u]++; in[v]++;
}

void DFS(int w, int f, int s) {
int rt = SAM.insert(s, col[w]);
if (to[i] != f) DFS(to[i], w, rt);
}

int main() {
for (int i=1;i<=n;i++) col[i] = read();
for (int i=1;i<=n;i++) if (in[i] == 1) DFS(i, i, 0);
printf("%lld\n",SAM.solve());
return 0;
}


## 【BZOJ 4345】[POI2016] Korale

### 解题报告

—————————— UPD 2017.3.22 ——————————

## 【BZOJ 4712】洪水

### 解题报告

1. $w(i)$ 表示第i个点自己的权值
2. $f(i) = \sum\limits_{j \in son(i)} {d(j)}$
3. $d(i) = \min (w(i),f(i))$

## 【Codeforces 747F】Igor and Interesting Numbers

### Code

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

int k,t,C[21][21],res[21];
char ori[]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};

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 LL solve(int len, bool ty) {
static LL f[2][20]; bool w,p;
memset(f,0,sizeof(f));
f[p=0][ty] = 1; w = 1;
for (int i=0;i<16;i++,w^=1,p^=1) {
memset(f[w],0,sizeof(f[w]));
for (int j=len;~j;j--)
for (int k=min(len-j,res[i]-(ty&(i==0)));~k;k--)
f[w][j+k] += f[p][j] * C[k][len-j];
}
return f[p][len];
}

int main() {
for (int i=0;i<=20;i++) {
C[0][i] = C[i][i] = 1;
for (int j=1;j<i;j++)
C[j][i] = C[j-1][i-1] + C[j][i-1];
}
for (int i=0;i<=15;i++)
res[i] = t;
LL tmp; int len=1;
while ((tmp = solve(len,0) - solve(len,1)) < k)
k -= tmp, len++;
for (int i=len,ret=1;i;ret=0,i--) {
res[ret]--;
while ((tmp = solve(i-1,0)) < k)
res[ret++]++, res[ret]--, k -= tmp;
printf("%c",ori[ret]);
}
return 0;
}


## 【日常小测】素数

1k以内右168个素数，但第12个素数就大于33了

#include<bits/stdc++.h>
#define LL long long
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;

const int N = 1001;
const int M = 200;
const int MX = 2100;

bitset<N> vec[M],vis,ans;
int n,m,BAS[N],vout,sign,f[2][MX],w,p;

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;
}

inline void DFS(int t) {
if (!sign && t == m+1) {
vout = max(vout, (int)vis.count());
} else if (sign && t == 12) {
int ret = 0;
for (int i=1;i<=11;i++) {
if (ans[i]) {
ret += (1<<(i-1));
}
}
f[p][ret] = max(f[p][ret],(int)vis.count());
} else {
DFS(t + 1);
for (int i=1;i*BAS[t]<=n;i++)
vis[i*BAS[t]] = vis[i*BAS[t]] ^ 1;
ans[t] = 1;
DFS(t + 1);
for (int i=1;i*BAS[t]<=n;i++)
vis[i*BAS[t]] = vis[i*BAS[t]] ^ 1;
ans[t] = 0;
}
}

int main() {
freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);
if (m > 12) {
w = 1; p = 0;
memset(f,0,sizeof(f));
vis.reset(); ans.reset();

for (int i=1;i<=m;i++)
sort(BAS+1,BAS+1+m);
sign = 1; DFS(1);

for (int i=12;i<=m;i++,w^=1,p^=1) {
memset(f[w],0,sizeof(f[w]));
for (int j=0,sta,tmp;j<=2047;j++) {
tmp = 0;
for (int k=1,lim=n/BAS[i];k<=lim;k++) {
sta = 0;
for (int x=1,cur=1;x<=11;x++,cur<<=1) {
if ((j&cur) && k % BAS[x] == 0)
sta ^= 1;
}
if (sta) tmp--;
else tmp++;
}
f[w][j] = f[p][j] + max(0, tmp);
}
}
for (int i=0;i<=2047;i++)
vout = max(f[p][i], vout);
printf("%d\n",vout);
} else {
vis.reset();
for (int i=1;i<=m;i++)
sign = 0; DFS(1);
printf("%d\n",vout);
}
}
return 0;
}