【BZOJ 4828】[HNOI2017] 大佬

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4828

解题报告

先$DP$出最多可以有多少天不做题
然后我们发现两次$D$人其实是独立的
于是我们再$DP$出攻击达到$x$的最小天数

最后回答每个询问的时候
用个双指针扫一扫

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

inline int read() {
	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() {
	n = read(); m = read(); mc = read();
	for (int i=1;i<=n;i++) {
		a[i] = read();
	}
	for (int j=1;j<=n;j++) {
		w[j] = read();
	}
	//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算法

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4837

解题报告

维护一个滑动窗口就可以了
时间复杂度是线性的

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];
  
inline int read() {
    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;
    for (int T=read();ans=0,T;T--) {
        memset(cnt,0,sizeof(cnt));
        memset(last,60,sizeof(last));
        n = read(); m = read(); p = read(); 
        A = read(); B = read(); MOD = read();
        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;
}

【Codeforces 309B】Context Advertising

题目传送门:http://codeforces.com/problemset/problem/309/B

鏼爷给的倍增的例题
先滑动窗口搞出每个单词开始的合法解
然后搞一搞倍增
于是枚举起点,总体O(nlogn)

然而我是面向数据编程的…..
感觉会被叉掉 ╥﹏╥…

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

inline int read(){
	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(){
	n = read(); r = read(); c = read();
	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

题目传送门:https://oi.qizy.tech/wp-content/uploads/2016/10/noip_test1_statements.pdf

std是O(n^3)的算法?
明明NOIP范围内可以O(n^2logn)搞的!
就是二分长度,然后用滑动窗口搞一搞

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

inline int read(){
	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);
	n = read(); k = read();
	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

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3962

这个玩意,貌似可以暴力?
预处理出斜着的线上的点有多少,这样在暴力转移的时候,可以做到O(1)
然后就是写代码的事情了,然而写了两个小时了,没写出来QAQ
弃疗………..

—– 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 n,m,q,sz,head[N],vout,X,Y;
int mat[N][N],f[2][N][N];

inline int read(){
	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 = head[j];
			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;
			head[j+1] = tmp;
		}
	}	 
	
}

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++) { 
		init(T); sz = read(); q = read();  
		for (int i=1,x,y;i<=sz;i++) x = read(), y = read(), mat[x][y]++;
		prework(); 
		for (int k=1;k<=q;k++) {
			solve(min(m+n,read()));
			printf("%d (%d,%d)\n",vout,X,Y);
		} 
	}
	return 0;
}

然而DZY告诉我们,这货可以变成正方形?
参见:http://dzy493941464.is-programmer.com/posts/86498.html
仔细想了一想:我们可以通过将整个图旋转45°,然后重新编号,然后就变成了正方形?
然后就是很常规的滑动窗口了?

—– 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;

inline int read(){
	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(){
	n = read(); k = read(); q = read(); MX = n * 2 - 1; 
	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];
	for (int i=1;i<=q;i++) solve(read());
	return 0;
} 

【Codeforces 701C】They Are Everywhere

题目传送门:http://codeforces.com/contest/701/problem/C

第一眼反应:这™不是O(nlogn)的滑动窗口吗?
然后看题解确定对错,发现是O(n)(╯‵□′)╯︵┻━┻
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];

inline int read(){
	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++) {
		arr[i] = read();
		if (!tag[arr[i]]) tag[arr[i]] = 1, tot++;
	}
	for (int i=1,bak=1,w=0;i<=n;i++) {
		if (!cnt[arr[i]]++) w++;
		while (cnt[arr[bak]] > 1) cnt[arr[bak++]]--;
		if (w == tot) vout = min(vout, i-bak+1);
	}
	printf("%d\n",vout);
	return 0;
}