【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 !

【BZOJ 4551】[TJOI2016&HEOI2016] 树

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4551
双倍经验:http://www.lydsy.com/JudgeOnline/problem.php?id=3319
神犇题解:http://medalplus.com/?p=1685

题解

  1. 强制在线做法 O(nlogn)
    考虑每一次标记点:只会影响其子树中的点
    所以使用DFS序+线段树就可以辣!

  2. 离线做法 O(nlogn)
    考虑将每一次标记的时间记录到点上
    然后使用倍增LCA的思想向上倍增

  3. 离线做法 O(nα(n))
    考虑离线之后进行逆序操作
    这样的话,操作就变成了删除标记
    这个可以形象地想成:打通了向上走地道路
    于是使用并查集即可
    ps:和BZOJ_3319是一毛一样的

Code

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

const int N = 100000+9;

int head[N],to[N],nxt[N],anc[N],fa[N];
int n,m,tot,opt[N],tag[N],vout[N];
char pat[10];

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 int find(int w) {
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w], fa[w]=f, w=tmp;
	return f;
}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

void DFS(int w, int last) {
	if (tag[w]) last = fa[w] = w;
	else fa[w] = last;
	for (int i=head[w];i;i=nxt[i]) {
		anc[to[i]] = w;
		DFS(to[i],last);
	}
}

int main(){
	n = read(); m = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		Add_Edge(u,v);
	}
	for (int i=1;i<=m;i++) {
		scanf("%s",pat+1);
		opt[i] = read(); 
		if (pat[1] == 'C') tag[opt[i]]++;
		else opt[i] *= -1;
	}
	tag[1]++; DFS(1,1);
	for (int i=m;i;i--) {
		if (opt[i] > 0) {
			if (!(--tag[opt[i]])) {
				fa[opt[i]] = anc[opt[i]];
			}
		} else {
			vout[++tot] = find(-opt[i]);
		}
	}
	while (tot) printf("%d\n",vout[tot--]); 
	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;
}