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


## 【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++) {