【Codeforces 781D】Axel and Marston in Bitland

相关链接

题目传送门:http://codeforces.com/contest/781/problem/D

解题报告

话说这个题,你看他的路径定义多么奇怪
构造方式就是倍增嘛!

那我们也来倍增吧!
于是搞一个bitset记录哪些点可以到达就可以辣!
时间复杂度:$O(\frac{n^3 \log 10^{18}}{64})$

Code

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

const int N = 501;
const int M = N * N;
const LL INF = 1000000000 * 1000000000ll;

bitset<N> f[60][N][2],ans,pre; 
int n,m;

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(); m = read();
	for (int i=1,u,v;i<=m;i++) {
		u = read(); v = read();
		f[0][u][read()][v] = 1; 
	}
	for (int s=0;s<59;s++) {
		for (int i=1;i<=n;i++) {
			for (int t=0;t<=1;t++) {
				for (int j=1;j<=n;j++) {
					if (f[s][i][t][j]) {
						f[s+1][i][t] |= f[s][j][t^1];
					}
				}
			}
		}
	}
	ans[1] = 1; LL vout = 0;
	for (int s=59,t=0;~s;s--) {
		pre = ans; ans.reset();
		for (int i=1;i<=n;i++) 
			if (pre[i]) ans |= f[s][i][t];
		if (ans.count()) {
			vout += 1ll << s;
			t ^= 1; 
		} else ans = pre;
	} 
	printf("%lld\n",vout>INF?-1:vout);
	return 0;
}

【BZOJ 4722】由乃

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4722
神犇题解Ⅰ:http://blog.csdn.net/werkeytom_ftd/article/details/54429577
神犇题解Ⅱ:http://www.cnblogs.com/wxxlouisa/p/6139165.html

解题报告

这题看起来一眼不可做啊!
仔细想一想,发现确实不会做

看完题解后:果然是乱搞题!
先不管修改操作的话,如果询问的区间长度超过13的话,一定有解
相关证明可以参见:http://blog.csdn.net/werkeytom_ftd/article/details/54429577

现在考虑修改操作
因为单次询问最多涉及13个数
所以只需要支持单点查询+区间修改就可以了
于是用线段树打标记什么的就可以啦!

然而我们惊讶的发现,我们打的Tag在最后计算的时候会很大
More Formally:次数会爆 $ long long$
于是用不了快速幂了 QwQ
然后又不会了

于是接着去膜拜题解
发现我们可以用类似快速幂一样的东西搞出来
我们最终要求的是:$ {a_i}^{{3^x}}$
于是我们预处理出 $ f(i,j)$ 表示 $ {a_i}^{{3^{{2^j}}}}$
于是像快速幂一样搞一搞就可以啦!

最后我们求出了这13个数是什么,怎么判断有没有解呢?
我们可以 Meet in middle !

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