【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

题目传送门:http://oi.cyo.ng/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;
}

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