## 【BZOJ 4236】JOIOJI

### Code

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

int n,vout;
map<pair<int,int>, int> m;

char c=getchar();
while (c!='J'&&c!='O'&&c!='I') c=getchar();
if (c == 'J') return 1;
else if (c == 'O') return 2;
else return 3;
}

int main() {
cin>>n;
pair<int,int> cur(0,0);
for (int i=1,w;i<=n;i++) {
if (w == 1) cur.first++;
else if (w == 2) cur.second++;
else cur.first--, cur.second--;
if (m[cur]) vout = max(vout, i - m[cur]);
else m[cur] = i;
if (!cur.first && !cur.second) vout = max(vout, i);
}
cout<<vout<<endl;
return 0;
}

## 【Codeforces 715C】Digit Tree

### Code

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

const int N = 200000 + 9;

int n,MOD; LL vout;

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, int w) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void gcd(int a, LL &x, int b, LL &y) {
if (!b) {x = 1, y = 0;}
else {gcd(b,y,a%b,x);y-=a/b*x;}
}

inline int gcd(int a, int b) {
static LL x,y;
gcd(a,x,b,y);
return (x % MOD + MOD) % MOD;
}

namespace Node_Decomposition{
#define ND Node_Decomposition
const int INF = 1e9;
int tot,node_sz,root,cur;
int sum[N],dep[N],vis[N];
map<int,int> cnt;

void Get_Root(int w, int f) {
sum[w] = 1; int mx = 0;
if (to[i] != f && !vis[to[i]]) {
Get_Root(to[i], w);
sum[w] += sum[to[i]];
mx = max(mx, sum[to[i]]);
}
}
mx = max(mx, node_sz - sum[w]);
if (mx < cur) cur = mx, root = w;
}

void DFS(int w, int f, int delta, LL p, int val) {
cnt[val] += delta;
if (!vis[to[i]] && to[i] != f) {
DFS(to[i], w, delta, p * 10 % MOD, (val + cost[i] * p) % MOD);
}
}
}

void cal(int w, int f, int t, LL val) {
vout += cnt[(-val*REV[t]%MOD+MOD)%MOD];
if (!vis[to[i]] && to[i] != f) {
cal(to[i], w, t+1, (val * 10 + cost[i]) % MOD);
}
}
}

void solve(int w, int sz) {
vis[w] = 1; cnt.clear();
if (!vis[to[i]]) {
DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
}
}
vout += cnt[0]; cnt[0]++;
if (!vis[to[i]]) {
DFS(to[i], w, -1, 10 % MOD, cost[i] % MOD);
cal(to[i], w, 1, cost[i] % MOD);
DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
}
}
if (!vis[to[i]]) {
node_sz = sum[to[i]] > sum[w] ? sz - sum[w] : sum[to[i]];
cur = INF; Get_Root(to[i], w);
solve(root, node_sz);
}
}
}

inline void solve() {
cur = INF; node_sz = n;
Get_Root(1,1);
solve(root,n);
}
};

int main() {
for (int i=1,u,v,w;i<n;i++) {
Add_Edge(u + 1, v + 1, w);
}
REV[0] = 1; REV[1] = gcd(10, MOD);
for (int i=2;i<=n;i++)
REV[i] = (LL)REV[i-1] * REV[1] % MOD;
ND::solve();
printf("%lld\n",vout);
return 0;
}

## 【BZOJ 3832】[POI2014] Rally

POI的题目质量真的还不错啊！

f[]表示顺着走能走多远
g[]表示反着走能走多远

### Code

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

const int N = 500000+9;
const int M = 4000000+9;
const int INF = 100000000;

int f[N],g[N],in[N],rin[N],vout=INF,Point;
struct CMP{inline bool operator () (const int a, const int b) {return b<a;}};
set<int,CMP> cur; unordered_map<int,int> CNT; queue<int> que;

inline void Add_Edge(int u, int v) {
static int TT = 1; in[v]++; rin[u]++;
}

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

void solve(int w, int *frt, int *ret, int *cnt) {
if (w != S && w != T) que.push(w);
for (int i=frt[w];i;i=nxt[i]) {
ret[to[i]] = max(ret[to[i]],ret[w]+1);
if (!--cnt[to[i]]) solve(to[i],frt,ret,cnt);
}
}

int main(){
n = read(); m = read(); S = 0; T = n+1;