## 【Codeforces 212B】Polycarpus is Looking for Good Substrings

### Code

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

const int N = 1000009;
const int SGZ = 26;
const int M = 10009;

int n, m, nxt[N][SGZ], crt[N][SGZ], q[M], ans[M];
vector<int> val;
char s[N], qy[SGZ];

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

inline int index(int x) {
for (int l = 0, r = val.size() - 1, mid; l <= r; ) {
mid = l + r >> 1;
if (val[mid] == x) {
return mid;
} else if (val[mid] < x) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1;
}

int main() {
scanf("%s", s);
n = strlen(s);
for (int i = 1; i <= m; i++) {
scanf("%s", qy);
int len = strlen(qy);
for (int j = 0; j < len; j++) {
q[i] |= 1 << qy[j] - 'a';
}
val.push_back(q[i]);
}
sort(val.begin(), val.end());
val.resize(unique(val.begin(), val.end()) - val.begin());
int last_position[SGZ];
fill(last_position, last_position + SGZ, n);
for (int i = n - 1; ~i; i--) {
last_position[s[i] - 'a'] = i;
for (int j = 0; j < SGZ; j++) {
nxt[i][j] = last_position[j];
}
}
memset(crt, -1, sizeof(crt));
for (int i = 0; i < n; i++) {
for (int j = 0, p = i, sta = 0; j < 26 && p < n; j++) {
int np = n, c = -1;
for (int k = 0; k < 26; k++) {
if ((sta >> k & 1) == 0) {
if (np > nxt[p][k]) {
c = k;
np = nxt[p][k];
}
}
}
if (~c) {
sta |= 1 << c;
p = np;
crt[i][j] = sta;
if (!i || crt[i - 1][j] != sta) {
int idx = index(sta);
if (~idx) {
ans[idx]++;
}
}
}
}
}
for (int i = 1; i <= m; i++) {
printf("%d\n", ans[index(q[i])]);
}
return 0;
}


## 【Codeforces 734F】Anton and School

### Code

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

const int N = 200009;

int n, a[N], b[N], c[N];

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

inline bool check() {
static int cnt[100];
for (int i = 1; i <= n; i++) {
for (int t = 0, v = a[i]; v; v >>= 1, ++t) {
cnt[t] += v & 1;
}
}
for (int i = 1; i <= n; i++) {
int tb = 0, tc = 0;
for (int j = 0, cur = 1; j <= 30; j++, cur <<= 1) {
tb += (a[i] & cur)? cnt[j] * cur: 0;
tc += (a[i] & cur)? n * cur: cnt[j] * cur;
}
if (tb != b[i] || tc != c[i]) {
return false;
}
}
return true;
}

int main() {
for (int i = 1; i <= n; i++) {
}
LL sum = 0;
for (int i = 1; i <= n; i++) {
sum += a[i];
}
if (sum % (n << 1)) {
puts("-1");
exit(0);
}
sum /= n << 1;
for (int i = 1; i <= n; i++) {
if ((a[i] -= sum) % n) {
puts("-1");
exit(0);
} else {
a[i] /= n;
}
}
if (!check()) {
puts("-1");
exit(0);
}
for (int i = 1; i <= n; i++) {
printf("%d ", a[i]);
}
return 0;
}


## 【BZOJ 4881】[Lydsy2017年5月月赛] 线段游戏

### Code

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

const int N = 100009;
const int MOD = 998244353;

int n, p[N], mx[N], mn[N];
stack<int> stk;

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() {
for (int i = 1; i <= n; i++) {
}
mx[1] = p[1];
for (int i = 2; i <= n; i++) {
mx[i] = max(mx[i - 1], p[i]);
}
mn[n] = p[n];
for (int i = n - 1; i; i--) {
mn[i] = min(mn[i + 1], p[i]);
}
for (int i = 2; i < n; i++) {
if (mx[i - 1] > p[i] && p[i] > mn[i + 1]) {
puts("0");
exit(0);
}
}
for (int i = 1; i <= n; i++) {
if (stk.empty() || stk.top() < p[i]) {
stk.push(p[i]);
} else {
int tt = stk.top();
for (; !stk.empty() && stk.top() > p[i]; stk.pop());
stk.push(tt);
}
}
int ans = 1;
for (int i = 1; i <= (int)stk.size(); i++) {
ans = (ans << 1) % MOD;
}
cout<<ans<<endl;
return 0;
}


## 【BZOJ 2296】[POJ Challenge] 随机种子

### Code

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

const LL MX = 9876543201999999;
const LL MN = 9876543201000000;

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() {
for (int T = read(); T; T--) {
if (!x) {
puts("-1");
} else {
LL r = MX / x + 1, l = MN / x;
while (l <= r) {
LL mid = l + r >> 1;
if (x * mid < MN) {
l = mid + 1;
} else if (x * mid > MX) {
r = mid - 1;
} else {
printf("%lld\n", mid * x);
break;
}
}
}
}
return 0;
}


## 【TopCoder SRM712】LR

### Code

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

class LR {
public:
string construct(vector<long long> s, vector<long long> t) {
int n=s.size(),SPJ=1; LL s1=0,s2=0,pp,cnt=0;
for (int i=0;i<n;i++) s1 += s[i], s2 += t[i], SPJ = (t[i]!=s[i]?0:SPJ);
if (SPJ) return ""; pp = s1;
if (s2-s1 <= 0 || (!s1 && s2)) return "No solution";
while (pp<s2) pp<<=1,++cnt;
if (pp != s2) return "No solution";
for (int i=0;i<=cnt;i++) {
if (judge(s, t, i, cnt-i)) {
string ret="";
for (int j=1;j<=i;j++) ret += "L";
for (int j=i+1;j<=cnt;j++) ret += "R";
return ret;
}
}
return "No solution";
}
private:
inline bool judge(vector<LL> s, vector<LL> t, int L, int R) {
LL tmp[55],a[55],b[55],n=s.size();
for (int i=1;i<=n;i++) a[i] = s[i-1], b[i] = t[i-1];
for (int k=1;k<=L;k++) {
for (int i=1;i<=n;i++) tmp[i] = a[i]; tmp[0] = a[n];
for (int i=1;i<=n;i++) a[i] = tmp[i-1] + tmp[i];
}
for (int k=1;k<=R;k++) {
for (int i=1;i<=n;i++) tmp[i] = a[i]; tmp[n+1] = a[1];
for (int i=1;i<=n;i++) a[i] = tmp[i] + tmp[i+1];
}
for (int i=1;i<=n;i++) if (a[i] != b[i]) return 0;
return 1;
}
};


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


## 【BZOJ 4347】[POI2016] Nim z utrudnieniem

### Code

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

const int M = 500009;
const int N = 1100000;
const int MOD = 1000000007;

int n,D,XOR,f[N][10],g[2][10],arr[M];

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++) XOR ^= (arr[i] = read());
sort(arr+1, arr+1+n);
f[0][0] = 1;
for (int i=1,LIM=1;i<=n;i++) {
while (LIM <= arr[i]) LIM <<= 1;
for (int v=1,nv;v<LIM;v++) {
if ((nv=(arr[i]^v)) <= v) {
for (int d=0,t=1%D;d<D;++d,(++t)%=D) {
g[1][t] = (f[nv][t] + f[v][d]) % MOD;
g[0][t] = (f[nv][d] + f[v][t]) % MOD;
}
for (int d=0;d<D;d++) {
f[nv][d] = g[1][d];
f[v][d] = g[0][d];
}
}
}
}
if (n % D == 0) f[XOR][0]--;
printf("%d\n",(f[XOR][0]+MOD)%MOD);
return 0;
}


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


## 【TopCoder】[TCO2013 2C] Well Timed Search

### 解题报告

1. 我们可以根据一个节点左右儿子子树的大小，求得往左、往右走的概率
2. 每一个深度在$[A,B]$的节点都是一个合法的结束

### Code

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

class WellTimedSearch {
public:
double getProbability(int n, int A, int B) {
int vout = 0;
for (int i=1,up,down;i<=n;i++) {
if (A > 1) up = Get_Top(i+1>>1, A-1);
else {if (i == 1) up = 0; else up = 1e9;}
if (n - up - i < 0) break;
down = Get_Down(B-A, n - up - i, i<<1);
vout = max(vout, i + down);
}
return (double)vout / n;
}
private:
int Get_Top(int len, int t) {
if (t > 1) return min((int)1e9, len + (len>1? Get_Top(len+1>>1, t-1): t-1));
if (t == 1 && len > 1) return 1e9;
return 1;
}
int Get_Down(int t, int num_node, int cur) {
if (!t) return 0;
if (cur >= num_node) return num_node;
return cur + Get_Down(t-1, num_node - cur, cur<<1);
}
};


## 【UOJ 246】[UER #7] 套路

### 解题报告

1. 考虑 $len<S$ 的情况
我们枚举右端点，暴力向左扫 $S$ 个就可以了

2. 考虑 $len \ge S$ 的情况
我们发现相似度不会超过 $\frac{m}{{len – 1}}$
于是考虑在权值上暴力向两边扫 $S$ 个

### Code

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

const int N = 200000+9;

int n,m,K,S,a[N],gap[N],lst[N];
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;
}

int main() {
K = read(); S = sqrt(m) + 1;
for (int i=1;i<=n;i++) a[i] = read();

memset(gap,60,sizeof(gap));
for (int i=1;i<=n;i++) {
for (int j=i-1;j>=i-S&&j;--j) {
gap[j] = min(gap[j], gap[j+1]);
gap[j] = min(gap[j], abs(a[i] - a[j]));
if (i-j+1 >= K) vout = max(vout, (LL)(i - j) * gap[j]);
}
}
memset(gap,0,sizeof(gap));
for (int i=1;i<=n;i++) {
for (int j=0;j<=S;j++) {
if (j) gap[j] = max(gap[j], gap[j-1]);
if (a[i]-j >= 1) gap[j] = max(gap[j], lst[a[i]-j]);
if (a[i]+j <= m) gap[j] = max(gap[j], lst[a[i]+j]);
if (i-gap[j] >= K) vout = max(vout, (LL)(i-gap[j]-1) * (j+1));
}
lst[a[i]] = i;
}
printf("%lld\n",vout);
return 0;
}


## 【UOJ 278】[UTR #2] 题目排列顺序

### Code

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

const int N = 100000+9;

int n,vout[N];
pair<int,int> arr[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;
}

int main(){
for (int i=1;i<=n;i++) {
arr[i].second = -i;
}
sort(arr+1, arr+1+n);
for (int i=1;i<=n;i++)
vout[-arr[i].second] = i;
for (int i=1;i<=n;i++)
printf("%d ",vout[i]);
return 0;
}


### Code

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

const int N = 150000 + 9;
const int M = N << 1;
const int L = 6;

int n,m,p,STA,val[N];

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

class Segment_Tree{
int cnt,root,ch[M][2],tag[M],len[M],ans;
struct Data{int x,y;}sum[M][L],vout[L];
public:
inline void init() {
for (int i=1;i<=n;i++)
modify(i, i, val[i]);
}
inline void modify(int l, int r, int v) {
modify(root, 1, n, l, r, v);
}
inline void query(int l, int r) {
ans = 0;
query(root, 1, n, l, r);
printf("%d ",ans);
for (int i=1;i<=ans;i++)
printf("%d ",vout[i]);
putchar('\n');
}
private:
inline void maintain(Data *a1, int &l1, Data *a2, int l2, Data *a3, int l3) {
static Data ret[L];
memcpy(ret, a2, sizeof(ret));
for (int i=1,tag=0;i<=l3;i++,tag=0) {
for (int j=1;j<=l2;j++) {
if (ret[j].x == a3[i].x) {
ret[j].y += a3[i].y;
tag = 1; break;
}
}
if (!tag) ret[++l2] = a3[i];
}
if (l2 > STA) {
sort(ret+1, ret+1+l2, [](const Data &A, const Data &B){return A.y>B.y;});
for (int i=l2;i>STA;i--) {
for (int j=1;j<i;j++) {
ret[j].y -= ret[i].y;
}
}
l2 = STA;
}
while (ret[l2].y <= 0) l2--;
memcpy(a1, ret, sizeof(ret));
l1 = max(0, l2);
}
inline void push_down(int w, int l, int r, int mid) {
modify(ch[w][0], l, mid-1, l, mid-1, tag[w]);
modify(ch[w][1], mid, r, mid, r, tag[w]);
tag[w] = 0;
}
void modify(int &w, int l, int r, int L, int R, int v) {
if (!w) w = ++cnt;
if (L <= l && r <= R) {
tag[w] = v;
len[w] = 1;
sum[w][1].x = v;
sum[w][1].y = r - l + 1;
} else {
int mid = l + r + 1 >> 1;
if (tag[w]) push_down(w, l, r, mid);
if (L < mid) modify(ch[w][0], l, mid-1, L, R, v);
if (mid <= R) modify(ch[w][1], mid, r, L, R, v);
int ls = ch[w][0], rs = ch[w][1];
maintain(sum[w], len[w], sum[ls], len[ls], sum[rs], len[rs]);
}
}
void query(int w, int l, int r, int L, int R) {
if (!w) return;
else if (L <= l && r <= R) {
maintain(vout, ans, vout, ans, sum[w], len[w]);
} else {
int mid = l + r + 1 >> 1;
if (tag[w]) push_down(w, l, r, mid);
if (L < mid) query(ch[w][0], l, mid-1, L, R);
if (mid <= R) query(ch[w][1], mid, r, L, R);
}
}
}SGT;

int main() {
p = read(); STA = 100 / p;
for (int i=1;i<=n;i++)
SGT.init();
for (int i=1,l,r;i<=m;i++) {
} else {
SGT.query(l, r);
}
}
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;
for (int i=1;i<=n;++i) if (!CNT[g[i]]++) cur.insert(g[i]);
for (int op=1;op<=n;op++) {
int w = que.front(); que.pop();
for (int i=rhead[w];i;i=nxt[i]) if (!--CNT[f[to[i]]+g[w]]) cur.erase(f[to[i]]+g[w]);
if (vout > *(cur.begin())) vout = *(cur.begin()), Point = w;
for (int i=head[w];i;i=nxt[i]) if (!CNT[g[to[i]]+f[w]]++) cur.insert(g[to[i]]+f[w]);
} printf("%d %d\n",Point,vout-1);
return 0;
}