## 【BZOJ 4828】[HNOI2017] 大佬

### Code

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

const int N = 109;
const int M = 930000;

int n,m,mc,tot,MX,ispri[N],w[N],a[N],f[N][N];
pair<int,int> itm[M];

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

void DFS(int t, LL sum) {
if (t > MX) return;
else {
DFS(t + 1, sum);
if (ispri[t]) {
for (;sum*=t,sum<=1e8;) {
itm[++tot].first = sum;
DFS(t + 1, sum);
}
}
}
}

inline int cal(int x) {
int ret = x + 1;
for (int i=min(MX,x-1),cnt,tmp;i;i--) {
if (x % i) continue;
cnt = i + 1; tmp = x;
for (int j=i;j>1&&tmp>1;j--) {
while (tmp % j == 0) {
tmp /= j;
++cnt;
}
}
if (tmp == 1) {
ret = min(ret, cnt);
} else {
break;
}
}
return ret;
}

int main() {
for (int i=1;i<=n;i++) {
}
for (int j=1;j<=n;j++) {
}
//DP最多空出来的天数
memset(f, -1, sizeof(f));
f[1][mc] = 0;
for (int i=1;i<=n;i++) {
for (int j=a[i];j<=mc;j++) {
if (f[i][j] == -1) continue;
int t1 = min(j - a[i] + w[i], mc), t2 = j - a[i];
if (t1 >= 0) {
f[i + 1][t1] = max(f[i + 1][t1], f[i][j]);
}
if (t2 >= 0) {
f[i + 1][t2] = max(f[i + 1][t2], f[i][j] + 1);
}
}
}
MX = -1;
for (int j=2;j<=n+1;j++) {
for (int i=0;i<=mc;i++) {
MX = max(MX, f[j][i]);
}
}
//搞出每一个物品的最小花费
for (int j=2;j<=100;j++) {
ispri[j] = 1;
for (int i=2;i*i<=j;i++) {
if (j % i == 0) {
ispri[j] = 0;
}
}
}
DFS(1, 1);
for (int i=1;i<=tot;i++) {
itm[i].second = cal(itm[i].first);
}
itm[++tot] = make_pair(0, 0);
sort(itm+1, itm+1+tot);
//对于每个询问用一个双端队列
for (int tt=1;tt<=m;tt++) {
int C = read(), ans = 0;
for (int i=tot,pfx=1,cur=-1e9;i;i--) {
while (pfx <= tot && itm[pfx].first <= C - itm[i].first) {
cur = max(cur, itm[pfx].first - itm[pfx].second);
pfx++;
}
if (cur + itm[i].first - itm[i].second >= C - MX) {
ans = 1;
break;
}
}
printf("%d\n",ans);
}
return 0;
}


## 【BZOJ 4837】LRU算法

### Code

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

const int N = 1000009;

int n,m,p,A,B,MOD,cnt[N],x[N],last[N];
ULL ans,pre[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;
}

int main() {
for (int i=1;i<N;i++) pre[i] = pre[i-1] + (ULL)i;
memset(cnt,0,sizeof(cnt));
memset(last,60,sizeof(last));
for (int i=1;i<=m;i++,p=((LL)A*p+B)%MOD) x[i] = p;
for (int i=m,cur=0,tl=m,r;i;i--) {
if (++cnt[x[i]] == 1) ++cur;
while (cur>n) if (--cnt[x[tl--]] == 0) cur--;
ans += (ULL)x[i] * (pre[min(last[x[i]], tl)] - pre[i-1]);
last[x[i]] = i - 1;
}
printf("%llu\n",ans);
}
return 0;
}


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

const int N = 6000000+9;
const int M = 1000000+9;

char pat[N];
int n,r,c,sta[M],len[M],trans[M][18],position,vout;

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(){
gets(pat+1);
for (int i=1,tmp=strlen(pat+1);i<=tmp;i++) if (pat[i] == ' ') {
pat[i] = 0;
}
for (int i=1,w=0;i<=n;i++) {
sta[i] = ++w;
len[i] = strlen(pat+w);
w += len[i];
}
for (int i=1,tail=1,tmp=len[1];i<=n;i++) {
if (len[i] > c) {
tail = (i + 1) % (n + 1);
tmp = len[tail];
} else {
while (tail < n && tmp + len[tail+1] + 1 <= c) {
tmp += len[++tail] + 1;
}
trans[i][0] = tail + 1;
tmp -= len[i] + (tail > i);
if (!tmp) {
tail = (i + 1) % (n + 1);
tmp = len[tail];
}
}
}
trans[n][0] = n;
for (int t=1;t<=17;t++) {
for (int i=1;i<=n;i++) {
trans[i][t] = max(trans[i][t-1],trans[trans[i][t-1]][t-1]);
}
}

for (int i=1,tmp=0,p=i;i<=n;tmp=0,p=++i) {
for (int j=17,w=1<<17;~j;j--,w>>=1) if (tmp+w <= r){
tmp += w;
p = max(p,trans[p][j]);
if (p == n+1) break;
}
if (p - i > vout) {
vout = p - i;
position = i;
}
}

if (vout) for (int i=1,beg=position,end;i<=r&&beg<=n;i++) {
end = trans[beg][0] - (beg != n || len[trans[beg][0]] > c);
if (end < beg) break;
for (int j=beg;j<=end;j++) {
printf("%s%c",pat+sta[j],j==end?'\n':' ');
}
beg = end + 1;
}
return 0;
}


## 【NOIP十连测】[D1T1] String Master

std是O(n^3)的算法？

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

const int N = 300+9;
const int SGZ = 27;

int n,k;
char S[N],T[N];
queue<int> que;

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 bool judge(int len) {
for (int d=0,cur=0,p1,p2,tmp;d<=n-len;d++,cur=0) {
while (!que.empty()) que.pop(); que.push(0); p1 = 0, p2 = p1 + d;
for (int i=1;i<len;i++)
tmp = (S[++p1] != T[++p2]),
cur += tmp, que.push(tmp);
while (p2 < n) {
tmp = (S[++p1] != T[++p2]);
cur += tmp, cur -= que.front();
que.pop(), que.push(tmp);
if (cur <= k) return true;
}
}
for (int d=0,cur=0,p1,p2,tmp;d<=n-len;d++,cur=0) {
while (!que.empty()) que.pop(); que.push(0); p1 = 0, p2 = p1 + d;
for (int i=1;i<len;i++)
tmp = (T[++p1] != S[++p2]),
cur += tmp, que.push(tmp);
while (p2 < n) {
tmp = (T[++p1] != S[++p2]);
cur += tmp, cur -= que.front();
que.pop(), que.push(tmp);
if (cur <= k) return true;
}
}
return false;
}

int main(){
freopen("master.in","r",stdin);
freopen("master.out","w",stdout);
scanf("%s%s",S+1,T+1);
int l=1,r=n,ret=0;
while (l <= r) {
int mid = l + r >> 1;
if (judge(mid)) ret = mid, l = mid+1;
else r = mid-1;
}
printf("%d\n",ret);
return 0;
}


## 【BZOJ 3962】[WF2011] Coffee Central

—– 2016.9.6 更新 —–

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 1000+9;

int mat[N][N],f[2][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 prework(){
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) f[0][i][j] = f[0][i-1][j-1] + mat[i][j];
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) f[1][i][j] = f[1][i+1][j-1] + mat[i][j];
}

inline int pro(int x1, int y1, int x2, int y2, int t) {
int ret = 0;
if (!t) {
x2--; y2--;
if (x1 < 1 || y1 < 1) ret += 0;
else if (x1 <= n && y1 <= m) ret += f[t][x1][y1];
else if (x1 > n) ret += (y1-(x1-n)<=m && y1-(x1-n)>=1)? f[t][n][y1-(x1-n)]: 0;
else ret += (1<=x1-(y1-m) && x1-(y1-m)<=n)? f[t][x1-(y1-m)][m]: 0;

if (x2 < 1 || y2 < 1) ret -= 0;
else if (x2 <= n && y2 <= m) ret -= f[t][x2][y2];
else if (x2 > n) ret -= (y2-(x2-n)<=m && y2-(x2-n)>=1)? f[t][n][y2-(x2-n)]: 0;
else ret -= (1<=x2-(y2-m) && x2-(y2-m)<=n)? f[t][m][2-(y2-m)]: 0;
} else {
x2++; y2--;
if (x1 > n || y1 < 1) ret += 0;
else if (x1 >= 1 && y1 <= m) ret += f[t][x1][y1];
else if (x1 < 1) ret += (y1-(1-x1)>=1 && y1-(1-x1)<=m)? f[t][1][y1-(1-x1)]: 0;
else ret += (x1+(y1-m)>=1 && x1+(y1-m)<=n)? f[t][x1 + (y1 - m)][m]: 0;

if (x2 > n || y2 < 1) ret -= 0;
else if (x2 >= 1 && y2 <= m) ret -= f[t][x2][y2];
else if (x2 < 1) ret -= (y2-(1-x2)>=1 && y2-(1-x2)<=m)? f[t][1][y2 -(1-x2)]: 0;
else ret -= (1<=x2+(y2-m) && x2+(y2-m)<=n)? f[t][x2+(y2-m)][m]: 0;
} return ret;
}

inline void solve(int lim){
vout = 0; X = 1; Y = 1;
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++)
if (i + j > lim + 2) break;
else vout += mat[i][j];
head[1] = vout; int tmp = vout;

for (int j=1;j<=m;j++) {
for (int i=1;i<n;i++) {
tmp += pro(i+lim+1,j,i+1,j-lim,0); // ¨J
tmp -= pro(i,j+lim,i-lim,j,0);     // ¨L
tmp += pro(i+1,j+lim,i+lim+1,j,1); // ¨K
tmp -= pro(i-lim,j,i,j-lim,1);     // ¨I
if (i + lim + 1 <= n) tmp -= mat[i+lim+1][j];
if (i - lim >= 1) tmp += mat[i-lim][j];
if (tmp > vout) vout = tmp, X = i+1, Y = j;
}
if (j < m) {
tmp += pro(1,j+lim+1,1+lim,j+1,1);//¨K
tmp += pro(1,j+lim+1,1-lim,j+1,0);//¨L
tmp -= pro(1+lim,j,1,j-lim,0);//¨J
tmp -= pro(1-lim,j,1,j-lim,1);//¨I
if (j + lim + 1 <= m) tmp -= mat[1][j+lim+1];
if (j - lim  >= 1) tmp += mat[1][j-lim];
if (tmp > vout) vout = tmp, X = 1, Y = j+1;
}
}

}

inline void init(int w){
memset(f,0,sizeof(f));
memset(mat,0,sizeof(mat));
printf("Case %d:\n",w);
}

int main(){
for (int T=1;scanf("%d%d",&n,&m) && n && m;T++) {
prework();
for (int k=1;k<=q;k++) {
printf("%d (%d,%d)\n",vout,X,Y);
}
}
return 0;
}


—– UPD 2016.6.9 —–

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

const int N = 2000+9;
int n,k,q,mat[N][N],sta[N],sum[N][N],MX;

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

#define SUM(x,y) sum[max(0,min(x,MX))][max(0,min(y,MX))]
inline void solve(int lim) { int vout = 0;
for (int j=1;j<=n;j++) for (int i=1,x,y;i<=n;i++) x = sta[i]-j+1, y = i+j-1,
vout = max(vout, SUM(x+lim,y+lim) + SUM(x-lim-1,y-lim-1) - SUM(x+lim,y-lim-1) - SUM(x-lim-1,y+lim));
printf("%d\n",vout);
}

int main(){
sta[1] = n; for (int i=2;i<=n;i++) sta[i] = sta[i-1] + 1;
for (int i=n+1;i<=n*2-1;i++) sta[i] = sta[i-1] - 1;
for (int i=k,x,y;i;--i) x = read(), y = read(), mat[sta[x]-y+1][x+y-1] = 1;
for (int j=1;j<=MX;j++) for (int i=1;i<=MX;i++) sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + mat[i][j];
return 0;
}


## 【Codeforces 701C】They Are Everywhere

ps:网上管这个叫“尺取法”？这不是滑动窗口吗？

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;

const int MAXN = 100000+9;
const int N = 60;
const int INF = 1000000;

int n,cnt[MAXN],arr[MAXN],tot,vout=INF;
bool tag[N];

char c=getchar();
while ((c < 'a' || c>'z') && (c < 'A' || c > 'Z')) c=getchar();
if (c <= 'z' && c >= 'a') return c-'a'+1;
else return c-'A'+27;
}

int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) {