## 【Codeforces 819B】Mister B and PR Shifts

### Code

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

const int N = 1000009;

int n, p[N], chg[N], delta[2];

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

int main() {
LL cur = 0, ans, pos = 0;
for (int i = 1; i <= n; i++) {
cur += abs(p[i] - i);
delta[p[i] > i]++;
if (p[i] > i) {
++chg[p[i] - i];
} else {
++chg[n - i + p[i]];
}
--chg[n - i + 1];
}
ans = cur;
for (int i = 1; i < n; i++) {
cur += delta[0] - delta[1];
cur += abs(p[n - i + 1] - 1) - abs(p[n - i + 1] - n - 1);
if (cur < ans) {
ans = cur;
pos = i;
}
delta[1] -= chg[i];
delta[0] += chg[i];
}
cout<<ans<<' '<<pos<<endl;
return 0;
}


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


## 【AtCoder】[Grand Contest 013 B] Hamiltonish Path

### Code

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

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

int n, m, head[N], nxt[M], to[M], vis[N];
deque<int> ans;

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 AddEdge(int u, int v) {
static int E = 1;
}

int main() {
#ifdef DBG
freopen("11input.in", "r", stdin);
#endif
for (int i = 1; i <= m; i++) {
if (i == 1) {
ans.push_back(u);
ans.push_back(v);
vis[u] = vis[v] = 1;
}
}
for (int mk = 1; mk; ) {
mk = 0;
for (int i = head[ans.front()]; i; i = nxt[i]) {
if (!vis[to[i]]) {
mk = 1;
ans.push_front(to[i]);
vis[to[i]] = 1;
break;
}
}
}
for (int mk = 1; mk; ) {
mk = 0;
for (int i = head[ans.back()]; i; i = nxt[i]) {
if (!vis[to[i]]) {
mk = 1;
ans.push_back(to[i]);
vis[to[i]] = 1;
break;
}
}
}
cout<<ans.size()<<endl;
for (; !ans.empty(); ans.pop_front()) {
printf("%d ", ans.front());
}
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;
}
};


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


## 【日常小测】苹果

### Code

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

const int N = 200009;
const int M = 1000009;
const int TIMES = 30;
const double EPS = 0.5;

int n,tp,tot,vis[M],pri[M],cnt[N];
LL arr[N],que[N],ans=1; set<LL> VIS;

char c=getchar(); LL 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;
}

LL GCD(LL a, LL b) {
return b? GCD(b, a%b): a;
}

bool DFS(int t, LL v) {
if (t > tot) {
if (v <= ans || VIS.count(v)) return 1;
int ret = 0; VIS.insert(v);
for (int i=1;i<=n;i++) ret += (arr[i] % v == 0);
if (ret >= (n >> 1)) {ans = v; return 1;}
else return 0;
} else {
bool ret = 0;
for (int i=0;i<=cnt[t];i++,v*=que[t]) {
if (!DFS(t+1, v)) break;
else ret = 1;
} return ret;
}
}

int main() {
freopen("apple.in","r",stdin);
freopen("apple.out","w",stdout);
srand(19260817);
for (int i=2;i<M;i++) {
if (!vis[i]) pri[++tp] = i;
for (int j=1;j<=tp&&pri[j]*i<M;j++) {
vis[i*pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}

for (int i=1;i<=n;i++) arr[i] = read();
for (int i=2;i<=n;i++) swap(arr[i], arr[rand()%(i-1)+1]);
for (int a,b,kk=1;kk<=TIMES;kk++) {
a = rand() % n + 1; b = rand() % n + 1;
LL gcd = GCD(arr[a], arr[b]); tot = 0;
for (int i=1,v;i<=tp&&(v=pri[i])<=gcd;i++) {
if (gcd % v != 0) continue;
que[++tot] = v; cnt[tot] = 0;
for (;gcd%v==0;++cnt[tot]) gcd /= v;
}
if (gcd != 1) que[++tot] = gcd, cnt[tot] = 1;
DFS(1, 1);
}
printf("%lld\n",ans);
return 0;
}


## 【日常小测】摩尔庄园

### Code

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

const int N = 100009;
const int INF = 1e9;

int  n,m,vout,cnt[N],pos[N];
int sur[N],val[N],cost[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 int LCA(int u, int v) {
for (;u!=v;u>>=1)
if (u < v) swap(u, v);
return u;
}

inline void update(int w) {
static int ls, rs, cl, cr;
if (cnt[w]) sur[w] = w, val[w] = 0;
else sur[w] = 0, val[w] = INF;
if ((ls=w<<1) <= n) {
cl = cost[ls] > 0? -1: 1;
if(val[ls] + cl < val[w]) {
val[w] = val[ls] + cl;
sur[w] = sur[ls];
}
}
if ((rs=ls|1) <= n) {
int cr = cost[rs] > 0? -1: 1;
if(val[rs] + cr < val[w]) {
val[w] = val[rs] + cr;
sur[w] = sur[rs];
}
}
}

inline void modify(int w, int p, int delta) {
while (w != p) {
cost[w] += delta;
update(w); w >>= 1;
}
}

inline int query(int w, int &ans) {
static int ret, delta; delta = 0;
for (;w;w>>=1) {
if (val[w] + delta < ans) {
ans = val[w] + delta;
ret = sur[w];
}
delta += cost[w] >= 0? 1: -1;
} return ret;
}

int main() {
for (int i=1;i<=n;i++) cnt[i] = read();
for (int i=1;i<=m;i++) pos[i] = read();
for (int i=n;i;i--) update(i);
for (int i=1,u,v,ans=INF;i<=m;++i,ans=INF) {
cnt[v=query(u=pos[i], ans)]--;
printf("%d\n",vout+=ans);
int lca = LCA(u, v);
modify(u, lca, 1); modify(v, lca, -1);
for (;lca;lca>>=1) update(lca);
}
return 0;
}


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


DP的那个函数必须是一个凸包

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


## 【BZOJ 2456】mode

### Code

#include<cstdio>
#define LL long long

int main() {
int n,tot=0; LL num,cur;
for (scanf("%d",&n);n;n--) {
scanf("%lld",&cur);
if (num != cur) {
if (tot) tot--;
else tot = 1, num = cur;
} else tot++;
} printf("%lld\n",num);
return 0;
}


—– UPD 2016.12.29 —–

## 【BZOJ 4513】[SDOI2016] 储能表

—– UPD 2016.9.29 —–

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

LL f[62][2][2][2],g[62][2][2][2],n,m,MOD,k;

int main(){
int T; cin>>T; while (T--) {
cin>>n>>m>>k>>MOD;
memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
g[61][0][0][0] = 1;
for (int i=60;~i;i--) {
int t1 = (n>>i)&1, t2 = (m>>i)&1, t3 = (k>>i)&1;
for (int a=0;a<2;a++) for (int b=0;b<2;b++) for (int c=0;c<2;c++) if (g[i+1][a][b]) {
for (int x=0,w,wa,wb,wc;x<2;x++) for (int y=0;y<2;y++) {
if (w=x^y, (!a&&x>t1) || (!b&&y>t2) || (!c&&w<t3)) continue;
wa = (a||x<t1); wb = (b||y<t2); wc = (c||w>t3);
(g[i][wa][wb][wc] += g[i+1][a][b]) %= MOD;
(f[i][wa][wb][wc] += ((f[i+1][a][b] + (((w-t3)*((1LL<<i)%MOD))%MOD)*g[i+1][a][b]%MOD)%MOD + MOD) % MOD) %= MOD;
}
}
}
cout<<f[0][1][1][1]<<endl;
}
return 0;
}