神题 – Page 4 – Qizy's Database

【BZOJ 4621】Tc605

2017年1月18日2017年2月7日 Qizy Leave a comment

解题报告

想了两个小时，确定是 $ O({n^2})$ 的DP，但就是推不出来式子 QwQ

观察最终的序列可以发现其有一下性质

数的相对位置与原本的位置相同

一种数字一定是连续的一段

更近一步，不难发现：满足上述条件的式子一定可以通过合法的操作构造出来
于是我们就可以DP了：$ f(i,j)$ 表示用了i个位置，进行了j次操作的方案数
对于原序列上的每一个数，枚举所有合法的存在区间 $ (l,r)$ 并进行转移$ f(r,j) + = f(l – 1,j – 1)$
于是就可以 $ O(n^3)$ DP辣！

【BZOJ 4552】[TJOI2016&HEOI2016] 排序

2017年1月17日2017年1月17日 Qizy 13 Comments

解题报告

之前在BC上看到过这道题：http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=680&pid=1004
这就不知道是谁抄谁的了

考虑直接做的话，似乎没法用任何数据结构来维护的样子
于是二分最后的答案 $ p$ ，将小于 $ p$ 的置为0，大于 $ p$ 的搞成1
这样的话，排序操作就变成了区间查询和区间赋值
于是搞一个线段树什么的就可以啦！

【UOJ 246】[UER #7] 套路

2017年1月14日2017年6月13日 Qizy 2 Comments

解题报告

这题真™是套路深啊！
一言不合就根号大军了

具体来说的话，我们考虑答案的区间长度为 $ len$
并且钦定一个阀值 $ S$

考虑 $ len<S$ 的情况
我们枚举右端点，暴力向左扫 $ S$ 个就可以了
考虑 $ len \ge S$ 的情况
我们发现相似度不会超过 $ \frac{m}{{len – 1}}$
于是考虑在权值上暴力向两边扫 $ S$ 个

这样的话，我们就可以在 $ O(nS + n\frac{m}{s})$ 的复杂度内解决这个问题了
不难发现，当 $ S = \sqrt m$ 时复杂度最优

Code

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

const int N = 200000+9;

int n,m,K,S,a[N],gap[N],lst[N];
LL vout;

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() {
	n = read(); m = read(); 
	K = read(); S = sqrt(m) + 1;
	for (int i=1;i<=n;i++) a[i] = read();
	
	memset(gap,60,sizeof(gap));
	for (int i=1;i<=n;i++) {
		for (int j=i-1;j>=i-S&&j;--j) {
			gap[j] = min(gap[j], gap[j+1]);
			gap[j] = min(gap[j], abs(a[i] - a[j]));
			if (i-j+1 >= K) vout = max(vout, (LL)(i - j) * gap[j]);
		}
	}
	memset(gap,0,sizeof(gap));
	for (int i=1;i<=n;i++) {
		for (int j=0;j<=S;j++) {
			if (j) gap[j] = max(gap[j], gap[j-1]);
			if (a[i]-j >= 1) gap[j] = max(gap[j], lst[a[i]-j]);
			if (a[i]+j <= m) gap[j] = max(gap[j], lst[a[i]+j]);
			if (i-gap[j] >= K) vout = max(vout, (LL)(i-gap[j]-1) * (j+1)); 
		}
		lst[a[i]] = i;
	}
	printf("%lld\n",vout);
	return 0;
}

【AtCoder】[CODE FESTIVAL 2016 Final G] Zigzag MST

2017年1月2日2017年1月2日 Qizy 175 Comments

解题报告

这题好神啊！现在感觉每道题都好神啊！

先来看任意一个连边操作：

考虑正常的最小生成树算法，如果用到了价值为 $ c+1$ 的边，那么价值为 $ c$ 的边一定已经考虑过了
于是我们就可以把图等价地变换为下面这个样子：

这样的话，我们可以把价值为 $ c$ 地那一类边拿出来单独考虑
余下的边搞一个堆，连一圈
这样的话，我们的图就改造成了这个样子：

此时我们的边就只剩 $ N+Q$ 条了，直接跑最小生成树算法就可以啦！

Code

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

const int N = 400000+9;

struct Edge{int u,v,w;}e[N];
struct Operation{int p,c;}op[N];
priority_queue<Operation> que;
int n,m,tot,vis[N],fa[N]; LL vout;

inline bool operator < (const Edge &A, const Edge &B) {return A.w < B.w;}
inline bool operator < (const Operation &A, const Operation &B) {return A.c > B.c;}

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

inline int find(int w) {
	int f = fa[w], tmp;
	while (f != fa[f]) f = fa[f];
	while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
	return f;
}

int main() {
	n = read(); m = read();
	for (int i=1,a,b,c;i<=m;i++) {
		a = read(); b = read(); c = read();
		e[++tot] = (Edge){a, b, c};
		que.push((Operation){a, c+1});
		que.push((Operation){b, c+2});
	}
	while (!que.empty()) {
		Operation w = que.top(); que.pop();
		if (!vis[w.p]) {
			vis[w.p] = 1;
			e[++tot] = (Edge){w.p, (w.p+1)%n, w.c};
			que.push((Operation){(w.p+1)%n, w.c+2});
		}
	}
	sort(e+1, e+1+tot);
	for (int i=0;i<=n;i++) fa[i] = i;
	for (int i=1;i<=tot;i++) {
		if (find(e[i].u) != find(e[i].v)) {
			fa[fa[e[i].u]] = fa[e[i].v];
			vout += e[i].w;
		}
	}
	printf("%lld\n",vout);
	return 0;
}

【Codeforces 722E】Research Rover

2017年1月2日2017年7月6日 Qizy 13 Comments

解题报告

这题在考虑如何去重的方面真的是好神啊！

定义：

$ h(i,j)$ 表示点i走到点j的方案数
$ f(i)$ 表示从起点，不经过特殊点，走到点i的方案数
$ g(i,j)$ 表示从点i出发，经过j个特殊点走到终点的方案数
$ val(i)$ 表示经过i个特殊点后剩余的值

现在考虑如何计算这四个量：
1. $ h(i,j) = C_{\Delta (x) + \Delta (y)}^{\Delta (x)}$
2. $ f(i) = h(start,i) – \sum {f(j) \cdot h(j,i)}$
3. $ g(i,j) = h(i,end) – \sum\limits_p {g(p,j) \cdot h(p,i)} – \sum\limits_{p = 1}^{j – 1} {g(i,p)}$
4. $ val(i)$ 随便预处理就好

现在考虑如何使用这四个量计算答案：
$ ans = \sum\limits_{i = 1}^k {f(i) \cdot \sum\limits_{j = 0}^{{{\log }_{2(s)}}} {g(i,j) \cdot val(j)} }$
于是我们就可以在 $ O({n^2}lo{g_2}(s))$ 的时间复杂度内解决这个问题啦！

Code

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

const int N = 2000+9;
const int M = 200000+9;
const int MOD = 1000000007;
const int L = 25;

int n,m,tot,cnt,K,S,tag,POW[M],REV[M];
int ans,val[L],vout[L],g[N][L],f[N];
struct Point{
	int x,y;
	inline bool operator < (const Point &B) const {
		return x < B.x || (x == B.x && y < B.y);
	}	
	inline bool operator <= (const Point &B) {
		return x <= B.x && y <= B.y;
	}
}p[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;
}

inline int Pow(int w, int t) {
	int ret = 1;
	while (t) {
		if (t & 1) ret = (LL)ret * w % MOD;
		w = (LL)w * w % MOD; t >>= 1;
	}
	return ret;
}

inline void prework() {
	for (int w=S;w>1;w=ceil(w*0.5)) 
		val[tot++] = w;
	val[tot] = 1;
	POW[0] = REV[0] = 1;
	for (int i=1;i<M;i++)
		POW[i] = (LL)POW[i-1] * i % MOD;
	REV[M-1] = Pow(POW[M-1], MOD-2);
	for (int i=M-2;i;i--)
		REV[i] = (LL)REV[i+1] * (i+1) % MOD;
}

inline int Path(int a, int b) {
	if (p[a].x > p[b].x || p[a].y > p[b].y) return 0;
	else {
		int x = p[b].x - p[a].x;
		int y = p[b].y - p[a].y + x;
		return ((LL)POW[y] * REV[x] % MOD) * REV[y-x] % MOD;
	}
}

int main() {
	n = read(); m = read();
	K = read(); S = read();
	prework();
	for (int i=1,x,y;i<=K;i++) {
		x = read(); y = read();
		if (x == 1 && y == 1) tag++;
		else if (x == n && y == m) tag++;
		else p[++cnt] = (Point){x, y}; 
	}
	sort(p+1, p+1+cnt);
	p[cnt+1] = (Point){n,m};
	p[0] = (Point){1,1};
	for (int i=cnt;i;i--) {
		for (int j=0;j<=tot;j++) {
			g[i][j] = Path(i, cnt+1);
			for (int k=i+1;k<=cnt&&j<tot;k++) {
				if (p[i] <= p[k]) {
					(g[i][j] -= (LL)g[k][j] * Path(i, k) % MOD) %= MOD;
				}
			}
			for (int k=0;k<j;k++)
				(g[i][j] -= g[i][k]) %= MOD;
		}
	}
	for (int i=1;i<=cnt;i++) {
		f[i] = Path(0, i);
		for (int j=1;j<i;j++) {
			if (p[j] <= p[i]) {
				(f[i] -= (LL)f[j] * Path(j, i) % MOD) %= MOD;
			}
		}
		for (int j=0;j<=tot;j++) 
			(vout[min(tot,j+1)] += (LL)f[i] * g[i][j] % MOD) %= MOD;
	}
	vout[0] = Path(0, cnt+1);
	for (int j=1;j<=tot;j++)
		(vout[0] -= vout[j]) %= MOD;
	for (int j=tag,tmp;j;j--) {
		tmp = vout[tot];
		for (int i=tot;i;i--) 
			vout[i] = vout[i-1];
		vout[0] = 0;
		vout[tot] = (vout[tot] + tmp) % MOD;
	}
	for (int i=0;i<=tot;i++)
		(ans += (LL)vout[i] * val[i] % MOD) %= MOD;
	ans = (LL)ans * Pow(Path(0, cnt+1), MOD-2) % MOD;
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}

【Codeforces 653G】Move by Prime

2017年1月1日2017年7月6日 Qizy 20 Comments

解题报告

不难发现质因数之间相互独立
于是我们就可以将每一个质因数单独考虑
这样问题转化为：

给定一个序列 {$ { {a_i}}$} ，每一次操作可以选一个数加一或者减一
问：将序列中所有数变为相同至少需要多少次操作

这个经典的问题，我们都知道全部变到中位数是较优的策略
但如何考虑每一个子序列？似乎没有比较优雅的方法…

于是我们换一个角度考虑：

设序列排序后为 {${ {b_i}}$}, 中位数为 $ {b_{mid}}$
那么这个序列的花费为 $ \sum\limits_{i = 1}^{mid – 1} {({b_{mid}} – {b_i})} + \sum\limits_{i = mid + 1}^n {({b_i} – {b_{mid}})}$

打开∑之后发现 $ {b_{mid}}$ 全部抵消掉了！
于是我们统计一个数有有多少次是加上或是减去就好啦！

考虑当前处理 $ {b_k}$ 这样的话，枚举有i个数比他小
那么有 $ i+1 \sim n-k$ 个数比他大的情况全部是减去
有 $ 0 \sim i-1$ 个数比他大的情况全部是加上
写出来就是 $ \sum\limits_{i = 0}^{{\rm{k – 1}}} {(\sum\limits_{j = {\rm{0}}}^{i – 1} {C_{n – k}^j} – \sum\limits_{j = i + 1}^{n – k} {C_{n – k}^j} )} \cdot {b_k}$

但这样计算的话，复杂度不对，于是再化简一下：

考虑选法1：左边选 $ l$ 个，右边选 $ r$ 个，$ r-l=x$
这样的话，我们总共选了 $ r+l$ 个数
考虑将右边选的数反选（方案间仍然一一对应），此时我们选择了 $ n-k-x$ 个数

再考虑选法二：我们任选 $ n-k-x$ 个数
因为 $ r-l=x$，所以一定可以构造出唯一一组 $ (l,r)$ 使得 $ l+r=n-k-x$

于是我们就证明了上述两种选法存在一种一一对应的映射
换一句话来说，我们可以直接统计第二种选法的方案数 $ C_{n – 1}^{n – k – x}$ 即可

这样的话，答案就成了 $ (\sum\limits_{i = – 1}^{ – (k – 1)} {C_{n – 1}^{n – k – i} – \sum\limits_{i = 1}^{n – k} {C_{n – 1}^{n – k – i}} ) \cdot {b_k} = } (\sum\limits_{i = n – k + 1}^{n – 1} {C_{n – 1}^i – \sum\limits_{i = 0}^{n – k – 1} {C_{n – 1}^i} ) \cdot {b_k}}$
这样的话，我们处理一下组合数的前缀和就可以 $ O(n)$ 处理完每一个质因数了
又因为 $ {b_k}$ 的值域很小，于是再预处理一下组合数的前缀和的前缀和
就可以得到 $ O(nlog(n))$ 的复杂度辣！

当然上面数学推导那一块还可以用生成函数来推导
然而我不会 QwQ

Code

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

const int N = 300000+9;
const int L = 22;
const int MOD = 1000000007;

int n,tot,vout,pri[N],vis[N],sur[N],cnt[N][L];
int POW[N],REV[N],sum[N],pre1[N],pre2[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;
}

inline int C(int a, int b) {
	if (a > b || a < 0 || b < 0) return 0;
	else return ((LL)POW[b] * REV[a] % MOD) * REV[b-a] % MOD;
}

inline int pre_sum(int l, int r) {
	if (l > r) return 0;
	return (sum[r] - (l?sum[l-1]:0)) % MOD;
}

inline int Pow(int w, int t) {
	int ret = 1;
	while (t) {
		if (t & 1) ret = (LL)ret * w % MOD;
		w = (LL)w * w % MOD; t >>= 1;
	}
	return ret;
}

inline void prework() {
	n = read(); sur[1] = 1;
	for (int i=2;i<N;i++) {
		if (!vis[i]) pri[++tot] = i, sur[i] = tot;
		for (int j=1;j<=tot&&pri[j]*i<N;j++) {
			vis[i*pri[j]] = 1;
			sur[i*pri[j]] = j;
			if (i % pri[j] == 0) break;
		}
	}
	for (int i=1;i<=tot;i++)
		cnt[i][0] = n;
	
	POW[0] = REV[0] = 1;
	for (int i=1;i<N;i++)
		POW[i] = (LL)POW[i-1] * i % MOD;
	REV[N-1] = Pow(POW[N-1], MOD-2);
	for (int i=N-2;i;i--)
		REV[i] = (LL)REV[i+1] * (i+1) % MOD;
	sum[0] = 1;
	for (int i=1;i<N;i++) 
		sum[i] = (sum[i-1] + C(i, n-1)) % MOD;
	for (int i=1;i<=n;i++)
		pre1[i] = (pre_sum(n-i+1, n-1) - pre_sum(0, n-i-1)) % MOD;
	for (int i=1;i<=n;i++)
		pre2[i] = (pre2[i-1] + pre1[i]) % MOD;
}

int main() {
	prework();
	for (int i=1,w;i<=n;i++) {
		w = read();
		for (int j=sur[w],tmp;w>1;j=sur[w]) {
			for (tmp=0;w%pri[j]==0;tmp++,w/=pri[j]);
			cnt[j][tmp]++;
			cnt[j][0]--;
		}
	}
	for (int i=1;i<=tot;i++) {
		if (cnt[i][0] < n) {
			for (int j=0,l=0,r=0;j<L;j++) {
				if (cnt[i][j]) {
					r += cnt[i][j];
					(vout += (LL)(pre2[r] - pre2[l]) * j % MOD) %= MOD;
					l = r;
				}
			}
		}
	}
	printf("%d\n",(vout+MOD)%MOD);
	return 0;
}

【TopCoder SRM578】DeerInZooDivOne

2016年12月27日2017年7月6日 Qizy 19 Comments

解题报告

给定一棵树，让你求两个没有重叠部分的连通块，使得这个连通块同构

这样的话，真的是不会啊！
直接说正解吧！

枚举将两个连通块分开的那条边
定义 $f(i,j)$ 为以i的子树和j的子树最大同构部分有多大
不难发现答案就是 $\max (f(i,j))$

考虑如何求 $f(i,j)$：
递归处理的话，实际上就是将两个节点的儿子进行配对
于是搞在这里搞二分图带权匹配就可以啦！

Code

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

const int N = 60;
const int M = 100000;
const int INF = 1e9;

int n,m,S,T;

class Minimum_Cost_Flow{
	int head[N],nxt[M],to[M],flow[M],cost[M];
    int E,vout,dis[N],sur[N],inq[N];
    queue<int> que;
    public:
    	inline void init() {
			E = 1; S = 0; T = N - 1;
			memset(head,0,sizeof(head));
		}
        inline void Add_Edge(int u, int v, int f, int c) {
			to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
			to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
		}
        inline int MaxFlow() {
        	vout = 0; 
            for (int f=INF,w;SPFA();f=INF) {
                for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
                for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
                vout += dis[T] * f;
            }
            return vout;
        }
    private:
        bool SPFA() {
            memset(dis,60,sizeof(dis));
            que.push(S); dis[S] = 0;
             
            while (!que.empty()) {
                int w = que.front(); que.pop(); inq[w] = 0;
                for (int i=head[w];i;i=nxt[i]) {
                    if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
                        dis[to[i]] = dis[w] + cost[i];
                        sur[to[i]] = i;
                        if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
                    }
                }
            }
            return dis[T] < INF;
        }
}MCMF;

class DeerInZooDivOne {
	int ret,t1,t2,q1[N],q2[N],fa[N],f[N][N];
	int E,head[N],to[M],nxt[M],vis[N];
    public:
    	int getmax(vector<int> a, vector<int> b) {
    	    n = a.size(); init();
    	    for (int i=0;i<n;i++) 
				Add_Edge(a[i]+1, b[i]+1);
			for (int i=0;t1=t2=0,i<n;i++) {
				DFS(a[i]+1, b[i]+1, q1, t1);
				DFS(b[i]+1, a[i]+1, q2, t2);
				vis[i*2+1] = vis[(i+1)*2] = 1;
				for (int p1=1;p1<=t1;p1++) {
					Make_Root(q1[p1], q1[p1]);
					for (int p2=1;p2<=t2;p2++) {
						Make_Root(q2[p2], q2[p2]);
						memset(f,-1,sizeof(f));
						ret = max(ret, F(q1[p1], q2[p2]));
					}
				}
				vis[i*2+1] = vis[(i+1)*2] = 0;
			}
			return ret;
		}
   	private:
   		inline void init() {
			E = 0; ret = 1;
			memset(head,0,sizeof(head));		
		}
   		inline void Add_Edge(int u, int v) {
			to[++E] = v; nxt[E] = head[u]; head[u] = E; 
			to[++E] = u; nxt[E] = head[v]; head[v] = E;   
		}
		void DFS(int w, int f, int *arr, int &cnt) {
			arr[++cnt] = w; 
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f) {
					DFS(to[i], w, arr, cnt);
				}
			}
		}
		void Make_Root(int w, int f) {
			fa[w] = f;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && !vis[i]) {
					Make_Root(to[i], w);
				} 
			}
		}
		inline int F(int a, int b) {
			if (a > b) swap(a, b);
			if (~f[a][b]) return f[a][b];
			else {
				for (int i=head[a];i;i=nxt[i]) {
					if (to[i] != fa[a] && !vis[i]) {
						for (int j=head[b];j;j=nxt[j]) {
							if (to[j] != fa[b] && !vis[j]) {
								F(to[i], to[j]);	
							}
						}
					}
				}
				MCMF.init();
				for (int i=head[a];i;i=nxt[i]) {
					if (to[i] != fa[a] && !vis[i]) {
						MCMF.Add_Edge(S, to[i], 1, 0);
						for (int j=head[b];j;j=nxt[j]) {
							if (to[j] != fa[b] && !vis[j]) {
								MCMF.Add_Edge(to[i], to[j], 1, -F(to[i], to[j]));	
							}
						}
					}
				}
				for (int i=head[b];i;i=nxt[i]) {
					if (to[i] != fa[b] && !vis[i]) {
						MCMF.Add_Edge(to[i], T, 1, 0);
					}
				}
				f[a][b] = -MCMF.MaxFlow();
				return ++f[a][b];
			}
		}
};

【CodeChef BTREE】Union on Tree

2016年12月21日2016年12月23日 Qizy 103 Comments

WJMZBMR Orz

又是 青年计算机科学家陈立杰 出的神题！
真的是跪烂！_(:з」∠)_

解题报告

看一看数据范围就可以知道这题复杂度一定只跟 ∑士兵数 相关
于是考虑先把虚树建出来，那么剩下的问题就是在利用虚树的边来统计答案了

1）函数式线段树的做法

考虑k=1，这样的话不用处理重复的问题，于是直接点分治就可以做
但现在有很多的点，于是我们可以将树剖成很多块，每块中恰好又一个城市a有卫兵
更进一步，我们规定这个联通块中任意一个点i到a的距离不大于到其他任意有卫兵的城市的距离
于是我们如果能在每一个联通块中单独处理每一个卫兵的话，就可以不用考虑去重的问题了

我们再仔细观察一下建出来的虚树，发现每一个块就是虚树上的一部分
对于a所在联通块深度最小的那个点，统计一下、加到答案里去
对于a所在联通块的其余边缘节点，再统计一下、从答案中减去

于是剩下的就是如何具体如何统计一条边对于答案的贡献了
我们分两种情况考虑：

v不是u在虚树中的祖先，统计v的子树中、到u的距离为d的点的个数
这个的话，直接用函数式线段树查就好

v是u的父亲，其余条件相同
这样的话，似乎与v的距离就不固定了（lca在u ~ v中移动）
于是先用点分治做出所有点到u的距离为d的点的个数n1
然后需要减掉v子树外的部分，这样的话，发现到v的距离就固定了
于是减掉所有点到v的距离为d-dis(u,v)的点数n2
再加上v子树中到v距离为d-dis(u,v)的点数n3就可以辣！

2）直接用点分治的做法

先用把点分树搞出来，这样就可以O(log^2(n))的时间复杂度内求dis(w,d)
其中dis(w,d)的定义为 到点w距离在d以内的点有多少 （不会的同学可以先去做BZOJ_3730）

再考虑把虚树建出来，这样的话唯一的问题就是如何去重了
考虑如果虚树上一条边的两个点的管辖范围没有交集，那么就肯定没有重复
如果有交集，那么设交集的重点为m，交集半径为r'那么直接减掉dis(m,r')就可以辣！

另外还需要预先将完全包含的管辖区间给修改成“相切”的情况，这样才能保证去重完整
还有的话，中点可能落在边上，于是可以在每边的中点加一个点

这样的做法是不是比主席树的做法清真了很多？
然而我还是写了5k+ _ (:з」∠) _
而且如果边带权的话，这题就很难这样做了

Code

最近为什么写啥常数都大到不行啊 QwQ
又是垫底…..

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

const int N = 100000 + 9;
const int M = N << 1;
const int INF = 1e8;

int n,m,T,head[N],to[M],nxt[M],num[N],cost[N];
int anc[N][18],dep[N],val[N],p[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;
}
		
inline void Add_Edge(int u, int v) {
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

void DFS(int w, int f) {
	static int cnt = 0;
	dep[w] = dep[f] + 1;
	anc[w][0] = f; num[w] = ++cnt;
	for (int i=head[w];i;i=nxt[i]) {
		if (!dep[to[i]]) {
			DFS(to[i], w);
		}
	}
}

inline int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=17;~i;i--) 
		if (dep[anc[x][i]] >= dep[y]) 
			x = anc[x][i];
	if (x == y) return x;
	for (int i=17;~i;i--) {
		if (anc[x][i] != anc[y][i]) {
			x = anc[x][i];
			y = anc[y][i];
		}
	} 
	return anc[x][0];
}

inline int dis(int x, int y) {
	int lca = LCA(x, y);
	return dep[x] + dep[y] - dep[lca] * 2;
}

class Point_Based_Divide_and_Conquer{
	int fa[N][18],tot[N],sum[N];
	int ans_tmp,root,block_size;
	vector<int> q[N],mul[N];
	bool vis[N];
	
	public: 	
		inline void init() {
			block_size = n;
			ans_tmp = INF;
			Get_Root(1, 1);
			tot[root] = 1;
			build(root, n);	
		}
		
		inline int query(int w, int rag) {
			int ret = Query(w, rag, q);
			for (int i=1,t;i<tot[w];i++) {
				t = rag - dis(fa[w][i], w);
				if (t >= 0) {
					ret += Query(fa[w][i], t, q);
					ret -= Query(fa[w][i-1], t, mul);
				}
			}
			return ret;
		}
	private:
		void Get_Root(int w, int f) {
			int mx = 0; sum[w] = 1;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && !vis[to[i]]) {
					Get_Root(to[i], w);
					mx = max(mx, sum[to[i]]);
					sum[w] += sum[to[i]];
				}
			}
			mx = max(block_size - sum[w], mx);
			if (mx < ans_tmp) {
				ans_tmp = mx;
				root = w;
			}
		}
		
		void build(int w, int sz) {
			vis[w] = 1; fa[w][0] = w;
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]]) {
					block_size = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
					ans_tmp = INF; Get_Root(to[i], w);
					memcpy(fa[root]+1, fa[w], sizeof(fa[w])-sizeof(int));
					tot[root] = tot[w] + 1;
					build(root, block_size);
				}
			}
			
			if (val[w]) {
				for (int i=0;i<tot[w];i++) 
					q[fa[w][i]].push_back(dis(w, fa[w][i]));
				for (int i=0;i<tot[w]-1;i++)
					mul[fa[w][i]].push_back(dis(w, fa[w][i+1]));	
			}
			sort(q[w].begin(), q[w].end());
			sort(mul[w].begin(), mul[w].end());
		} 
		
		inline int Query(int w, int r, vector<int> *a) {
			return upper_bound(a[w].begin(), a[w].end(), r) - a[w].begin();
		}
}PDC; 

class Virtual_Tree{
	int stk[N],rag[N],top,lca,cnt,root;
	queue<int> que;
	bool inq[N];
	
	public:	
		inline void build(int &tot) {
			cnt = tot; T = 0;
			root = p[1] = read(); 
			newnode(p[1], read());
			for (int i=2;i<=tot;i++) {
				p[i] = read();
				newnode(p[i], read());
				root = LCA(root, p[i]);
			}
			static auto cmp = [](int a, int b) {return num[a] < num[b];};
			sort(p+1, p+1+tot, cmp);
			if (root != p[1]) p[++tot] = root, newnode(root, -1);
			stk[top=1] = root;
			for (int i=1+(p[1]==root);i<=cnt;i++) {
				lca = LCA(p[i], stk[top]);
				for (;dep[stk[top]] > dep[lca];top--) 
					if (dep[stk[top-1]] >= dep[lca]) AddEdge(stk[top-1], stk[top]);
					else newnode(lca, -1), AddEdge(lca, stk[top]);
				if (lca != stk[top]) 
					stk[++top] = p[++tot] = lca;
				if (p[i] != stk[top])
					stk[++top] = p[i];
			}
			for (int i=1;i<top;i++)
				AddEdge(stk[i], stk[i+1]);
		}
		
		inline int solve(int tot) {
			prework(tot);
			int ret = 0;
			for (int i=1,u,v,r,mid,t;i<T;i+=2) {
				u = to[i]; v = to[i+1];
				r = rag[u] + rag[v] - cost[i] >> 1;
				if (r >= 0) {
					mid = move(u, v, r);
					ret -= PDC.query(mid, r);
				}
			} 
			for (int i=1;i<=tot;i++) 
				ret += PDC.query(p[i], rag[p[i]]);
			return ret;
		}
	private:
		inline void newnode(int w, int v) {
			rag[w] = v << 1;
			head[w] = 0;
		}
		
		inline int move(int x, int y, int r) {
			if (dep[x] < dep[y]) swap(x, y);
			r = rag[x] - r;
			for (int i=0;r;i++,r>>=1)
				if (r & 1) x = anc[x][i];
			return x;	 
		}
		
		inline void prework(int tot) {
			for (int i=1;i<=tot;i++) {
				que.push(p[i]);
				inq[p[i]] = 1;
			}
			
			while (!que.empty()) {
				int w = que.front(); 
				que.pop(); inq[w] = 0;
				for (int i=head[w];i;i=nxt[i]) {
					if (rag[w] > rag[to[i]] + cost[i]) {
						rag[to[i]] = rag[w] - cost[i];
						if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
					}
				}
			}
		}
		
		inline void AddEdge(int u, int v) {
			int w = dis(u, v);
			to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
			to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
		}
}VT; 

int main() {
	n = read();
	fill(val+1, val+1+n, 1);
	for (int i=1,lim=n,u,v;i<lim;i++) {
		u = read(); v = read();
		Add_Edge(u, ++n);
		Add_Edge(n, v);
	}
	
	DFS(1, 1);
	for (int j=1;j<=17;j++) {
		for (int i=1;i<=n;i++) {
			anc[i][j] = anc[anc[i][j-1]][j-1];
		}
	}
	PDC.init();
	
	m = read();
	for (int y=1,k;y<=m;y++) {
		VT.build(k = read());
		printf("%d\n",VT.solve(k)); 
	}
	return 0;
}

【BZOJ 2654】tree

2016年12月16日2016年12月16日 Qizy 23 Comments

链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2654
神犇题解：http://blog.csdn.net/PoPoQQQ/article/details/47980565

题解

感觉这个题很好玩的样子！
考虑给每一个白边加上一个固定的权值
那么使用白边的数量可以用这个权值来调整
唯一需要注意的就是，这种变化可能不是线性的
也就是说可能会有断层的情况，需要特殊处理一下

值得注意的是，这种方法具有较高的可移植性：
在某一套小火车的模拟题中，一道很恶心的DP也可以用此方法来解决

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100000+9;
 
struct Edge{int u,v,val,col;}e[N]; 
int n,m,STA,fa[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 int find(int w) {
    int f = fa[w], tmp;
    while (f != fa[f]) f = fa[f];
    while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
    return f;
} 
 
bool cmp_mx(const Edge &A, const Edge &B) {return A.val < B.val || (A.val == B.val && A.col > B.col);}
bool cmp_mn(const Edge &A, const Edge &B) {return A.val < B.val || (A.val == B.val && A.col < B.col);}
 
inline bool judge(int delta) {
    int cnt = 0;
    sort(e+1, e+1+m, cmp_mx);
    for (int i=1;i<=n;i++) fa[i] = i;
    for (int i=1;i<=m;i++) {
        if (find(e[i].u) != find(e[i].v)) {
            fa[find(e[i].u)] = find(e[i].v);
            cnt += e[i].col;
        }
    }
    if (cnt < STA) return 1;
     
    int cost = 0; cnt = 0;
    sort(e+1, e+1+m, cmp_mn);
    for (int i=1;i<=n;i++) fa[i] = i;
    for (int i=1;i<=m;i++) {
        if (find(e[i].u) != find(e[i].v)) {
            fa[fa[e[i].u]] = fa[e[i].v];
            cnt += e[i].col;
            cost += e[i].val; 
        }
    }
    if (cnt > STA) return 0;
    else {
        printf("%d\n",cost-STA*delta);
        exit(0);
    }
}
 
int main(){
    n = read(); m = read(); STA = read();
    for (int i=1;i<=m;i++) {
        e[i].u = read() + 1; e[i].v = read() + 1;
        e[i].val = read(); e[i].col = read() ^ 1;
    } 
     
    int l=-100,r=100,mid;
    while (l <= r) {
        mid = l + r >> 1;
        for (int i=1;i<=m;i++) if (e[i].col) e[i].val += mid;
        if (judge(mid)) r = mid - 1;
        else l = mid + 1;
        for (int i=1;i<=m;i++) if (e[i].col) e[i].val -= mid;
    } 
    return 0;
}

【BZOJ 2653】middle

2016年12月16日2016年12月19日 Qizy 2 Comments

链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2653
神犇题解：http://blog.csdn.net/wzq_qwq/article/details/48809845

题解

先来考虑一个子问题：

假如序列左端点在[l1,r1]之间，右端点在[l2,r2]之间
给定中位数x，问能否找出一个区间使得中位数大于等于x

这个问题很简单的样子：将小于x的赋值-1，大于x赋值为1
这样问题就转化为能否找到一个区间使得区间和大于等于0
这个可以用线段树在 log(n) 的时间内处理

如何在可以接受的时间复杂度内搞出每一个中位数对应的那颗线段树
考虑将原序列排序后从小到大来建树
第i棵线段树和第i+1棵线段树就只有第i个位置需要从1变成-1
这个用函数式线段树就好啦！

Code

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

const int N = 25000 + 9;
const int M = 400000;

int n,m,tot,arr[N],_hash[N],last_ans;
vector<int> pos_que[N];

namespace Chair_Tree{
	#define CT Chair_Tree
	int ch[M][2],ls[M],rs[M],sum[M],root[N],cnt;
	
	void Build(int &w, int l, int r) {
		sum[w=++cnt] = r - l + 1;
		ls[w] = rs[w] = sum[w];
		if (l < r) {
			int mid = l + r + 1 >> 1;
			Build(ch[w][0], l, mid-1);
			Build(ch[w][1], mid, r);
		} 
	}inline void init() {Build(root[1],1,n);}
	
	void insert(int p, int &w, int l, int r, int pur) {
		sum[w=++cnt] = sum[p] - 2;
		memcpy(ch[w],ch[p],sizeof(ch[w]));
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (pur < mid) insert(ch[p][0], ch[w][0], l, mid-1, pur);
			else insert(ch[p][1], ch[w][1], mid, r, pur);
			ls[w] = max(ls[ch[w][0]], sum[ch[w][0]] + ls[ch[w][1]]);
			rs[w] = max(rs[ch[w][1]], sum[ch[w][1]] + rs[ch[w][0]]);
		} else {
			ls[w] = rs[w] = 0;
		}		
	} inline void insert(int p, int w, int val) {
		insert(root[p],root[w],1,n,val);
	}
	
	int Get_sum(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return sum[w];
		} else {
			int mid = l + r + 1 >> 1, ret = 0;
			if (L < mid) ret += Get_sum(ch[w][0], l, mid-1, L, R);
			if (mid <= R) ret += Get_sum(ch[w][1], mid, r, L, R);
			return ret;
		}
	} inline int Get_Sum(int w, int l, int r) {
		return Get_sum(root[w],1,n,l,r);
	}
	
	int query_left(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return ls[w];
		} else {
			int mid = l + r + 1 >> 1;
			if (R < mid) return query_left(ch[w][0], l, mid-1, L, R);
			else if (mid <= L) return query_left(ch[w][1], mid, r, L, R);
			else {
				int t1 = query_left(ch[w][0], l, mid-1, L, mid-1);
				int t2 = query_left(ch[w][1], mid, r, mid, R) + Get_sum(ch[w][0], l, mid-1, L, mid-1);
				return max(t1, t2);
			}	
		}
	} inline int Left_Max(int w, int l, int r) {
		return query_left(root[w],1,n,l,r);
	}
	
	int query_right(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return rs[w];
		} else {
			int mid = l + r + 1 >> 1;
			if (R < mid) return query_right(ch[w][0], l, mid-1, L, R);
			else if (mid <= L) return query_right(ch[w][1], mid, r, L, R);
			else {
				int t1 = query_right(ch[w][1], mid, r, mid, R);
				int t2 = query_right(ch[w][0], l, mid-1, L, mid-1) + Get_sum(ch[w][1], mid, r, mid, R);
				return max(t1, t2);
			}
		}
	} inline int Right_Max(int w, int l, int r) {
		return query_right(root[w], 1, n, l, r);
	}
};

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

inline bool judge(int sta, int *lim) {
	int ret = CT::Get_Sum(sta, lim[2], lim[3]);
	ret += lim[1] < lim[2] ? CT::Right_Max(sta, lim[1], lim[2] - 1) : 0;
	ret += lim[3] < lim[4] ? CT::Left_Max(sta, lim[3] + 1, lim[4]) : 0;
	return ret >= 0;
}

int main() {
	n = read();
	for (int i=1;i<=n;i++) 
		arr[i] = _hash[i] = read();
	sort(_hash+1, _hash+1+n);
	tot = unique(_hash+1, _hash+1+n) - _hash - 1;
	for (int i=1;i<=n;i++) {
		arr[i] = lower_bound(_hash+1, _hash+1+tot, arr[i]) - _hash;
		pos_que[arr[i]].push_back(i);
	}
	CT::init();
	for (int i=2;i<=tot;i++) {
		CT::insert(i-1,i,pos_que[i-1][0]);
		for (int j=1,lim=pos_que[i-1].size();j<lim;j++) 
			CT::insert(i,i,pos_que[i-1][j]);
	}
	
	m = read();
	for (int i=1,lim[5],l,r,mid,ret;i<=m;i++) {
		for (int j=1;j<=4;j++)
			lim[j] = (read() + last_ans) % n + 1;
		sort(lim+1, lim+1+4);
		
		l = 1, r = tot;
		while (l <= r) {
			mid = l + r >> 1;
			if (!judge(mid,lim)) r = mid-1;
			else ret = mid, l = mid + 1; 
		}
		printf("%d\n",last_ans = _hash[ret]);
	}
	return 0;
}

【BZOJ 4262】Sum

2016年12月14日2017年2月2日 Qizy 26 Comments

链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4262
神犇题解-1：http://www.cnblogs.com/clrs97/p/4824806.html
神犇题解-2：http://blog.csdn.net/qq_34637390/article/details/51313126

题解

我们不妨将所有询问按照右端点$r_i$ 排序
假设当前处理的所有询问右端点统一为last
定义$val_i^{last} = \min (\{ {a_j}|j \in [i,last]\} )$
定义$sum_i^{last} = \sum\limits_{j = i}^{last} {val_i^j}$
不难发现对于左右端点在l-r的所有区间的min和为$\sum\limits_{i = l}^r {sum_i^r}$
更进一步，每一个原题中提到的询问可以拆成：$\sum\limits_{i = {l_1}}^{{r_1}} {sum_i^{{r_2}}} – \sum\limits_{i = {l_1}}^{{r_1}} {sum_i^{{l_2} – 1}}$

接下来的事情就是用线段树来维护val和sum辣！
考虑last向右移动一个单位，我们首先需要将一些点的val更新
然后我们需要将每一个点当前的val累加到sum里面去

每一个点维护四个变量a,b,c,d来表示标记
定义 new_val = a * val + b * len
定义 new_sum = sum + c * val + d * len
显然更新val需要用到的参数是 {0,val',0,0}
而默认的参数则应该为 {1,0,0,0}
更新sum的参数则应该为 {1,0,1,0}

于是就可以将这两种标记一起下传了
至于为什么可以混在一起？
因为这货是矩阵乘法啊！
ps：矩阵乘法并没有交换律，只有结合律，所以在修改时也得下传标记

Code

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

const int N = 100000+9;
const int M = N << 1;
const int MOD = 1000000000;
const int SEED1 = 1023;
const int SEED2 = 1025;

int n,m,tot,arr[N],stk[N];
LL vout[N];
struct Query{
	int lim,l,r,t,id;
	inline bool operator < (const Query &B) const {
		return lim < B.lim;
	}
}q[M];

namespace Segment_Tree{
	#define SEG Segment_Tree
	int ch[M][2],L,R,cnt,root;
	LL sum[M],val[M],ans_tmp;
	struct Tag{
		LL a,b,c,d;
		inline Tag() {a=1;b=c=d=0;}
		inline Tag(LL a, LL b, LL c, LL d):a(a),b(b),c(c),d(d) {}
		inline Tag operator * (const Tag &B) {
			return (Tag){a*B.a, B.b+b*B.a, a*B.c+c, B.d+d+b*B.c};
		}
	}tag[M],delta;
	
	void Build(int &w, int l, int r) {
		w = ++cnt;
		tag[w] = Tag(1,0,0,0);
		val[w] = sum[w] = 0;
		if (l < r) {
			int mid = l + r + 1 >> 1;
			Build(ch[w][0],l,mid-1);
			Build(ch[w][1],mid,r);
		}
	} 
	
	inline void init() {
		cnt = 0;
		Build(root,1,n);
	}
	
	inline void Add(int w, int l, int r, Tag v) {
		static int len; len = r - l + 1;
		sum[w] += val[w] * v.c + len * v.d;
		val[w] = val[w] * v.a + len * v.b;
		tag[w] = tag[w] * v;
	}
	
	inline void push_down(int w, int l, int mid, int r) {
		Add(ch[w][0],l,mid-1,tag[w]);
		Add(ch[w][1],mid,r,tag[w]);
		tag[w] = Tag(1,0,0,0);
	}
	
	inline void GetSum() {
		Add(root,1,n,Tag(1,0,1,0));
	}
	
	void Modify(int w, int l, int r) {
		if (L <= l && r <= R) {
			Add(w,l,r,delta);
		} else {
			int mid = l + r + 1 >> 1;
			if (tag[w].a != 1 || tag[w].b || tag[w].c || tag[w].d) 
				push_down(w,l,mid,r);
			if (L < mid) Modify(ch[w][0], l, mid-1);
			if (R >= mid) Modify(ch[w][1], mid, r);
			val[w] = val[ch[w][0]] + val[ch[w][1]];
			sum[w] = sum[ch[w][0]] + sum[ch[w][1]];
		}
	}
	
	inline void modify(int l, int r, int v) {
		delta = Tag(0,v,0,0);
		L = l, R = r;
		Modify(root,1,n);
	}
	
	void query(int w, int l, int r) {
		if (L <= l && r <= R) {
			ans_tmp += sum[w];
		} else {
			int mid = l + r + 1 >> 1;
			if (tag[w].a != 1 || tag[w].b || tag[w].c || tag[w].d) 
				push_down(w,l,mid,r);
			if (L < mid) query(ch[w][0], l, mid-1);
			if (R >= mid) query(ch[w][1], mid, r);
		}
	}
	
	inline LL query(int l, int r) {
		ans_tmp = 0;
		L = l; R = r;
		query(root,1,n);
		return ans_tmp;
	}
};

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() {
	m = read();
	for (int i=1,l1,l2,r1,r2;i<=m;i++) {
		l1 = read(); r1 = read();
		l2 = read(); r2 = read();
		if (l2 > 1) q[++tot] = (Query){l2-1,l1,r1,-1,i};	
		q[++tot] = (Query){r2,l1,r1,1,i};
		n = max(n, max(r1, r2));
	}
	sort(q+1, q+1+tot);
	for (int i=1,c1=SEED1,c2=SEED2;i<=n;i++) {
		arr[i] = c1 ^ c2;
		c1 = (LL)SEED1 * c1 % MOD;
		c2 = (LL)SEED2 * c2 % MOD;
	}
	
	SEG::init();
	for (int i=1,top=0,cur=1;i<=n;i++) {
		while (top && arr[stk[top]] > arr[i]) top--;
		SEG::modify(stk[top]+1, i, arr[i]);
		SEG::GetSum(); stk[++top] = i;
		while (cur <= tot && q[cur].lim == i) {
			vout[q[cur].id] -= SEG::query(q[cur].l, q[cur].r) * q[cur].t;
			cur++;
		}
	}
	SEG::init();
	for (int i=1,top=0,cur=1;i<=n;i++) {
		while (top && arr[stk[top]] < arr[i]) top--;
		SEG::modify(stk[top]+1, i, arr[i]);
		SEG::GetSum(); stk[++top] = i;
		while (cur <= tot && q[cur].lim == i) {
			vout[q[cur].id] += SEG::query(q[cur].l, q[cur].r) * q[cur].t;
			cur++;
		}
	}
	
	for (int i=1;i<=m;i++) 
		printf("%lld\n",vout[i]);
	return 0;
}

【BZOJ 3832】[POI2014] Rally

2016年9月27日2017年4月10日 Qizy 197 Comments

解题报告

这题真的是妙不可言！

POI的题目质量真的还不错啊！

先DP预处理一下：
f[]表示顺着走能走多远
g[]表示反着走能走多远
对于边(u,v)给一个权值g[u]+f[v]
不难发现，一个图的最长链此时为权值最大的那一条边

考虑删点，如果会影响到最长链的话
新的最长链一定是从拓扑序小于他的连向拓扑序大于他的某条边的权值
于是搞一搞堆来维护这个东西即可

Code

代码方面，我偷懒写的set+map的写法
想要常数小，请参见：https://blog.sengxian.com/solutions/bzoj-3832

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

const int N = 500000+9;
const int M = 4000000+9; 
const int INF = 100000000;

int head[N],nxt[M],to[M],rhead[N],n,m,S,T;
int f[N],g[N],in[N],rin[N],vout=INF,Point;
struct CMP{inline bool operator () (const int a, const int b) {return b<a;}};
set<int,CMP> cur; unordered_map<int,int> CNT; queue<int> que;

inline void Add_Edge(int u, int v) {
	static int TT = 1; in[v]++; rin[u]++;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT;
	to[++TT] = u; nxt[TT] = rhead[v]; rhead[v] = TT;
}

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

void solve(int w, int *frt, int *ret, int *cnt) {
	if (w != S && w != T) que.push(w);
	for (int i=frt[w];i;i=nxt[i]) {
		ret[to[i]] = max(ret[to[i]],ret[w]+1);
		if (!--cnt[to[i]]) solve(to[i],frt,ret,cnt);
 	}
}

int main(){
	n = read(); m = read(); S = 0; T = n+1;
	for (int i=1;i<=n;i++) Add_Edge(S,i), Add_Edge(i,T);
	for (int i=1,u,v;i<=m;i++) u = read(), v = read(), Add_Edge(u,v); 
	solve(S,head,f,in); solve(T,rhead,g,rin);
	for (int i=1;i<=n;++i) if (!CNT[g[i]]++) cur.insert(g[i]);
	for (int op=1;op<=n;op++) {
		int w = que.front(); que.pop(); 
		for (int i=rhead[w];i;i=nxt[i]) if (!--CNT[f[to[i]]+g[w]]) cur.erase(f[to[i]]+g[w]);
		if (vout > *(cur.begin())) vout = *(cur.begin()), Point = w; 
		for (int i=head[w];i;i=nxt[i]) if (!CNT[g[to[i]]+f[w]]++) cur.insert(g[to[i]]+f[w]);
	} printf("%d %d\n",Point,vout-1);
	return 0;
}

【BZOJ 3569】DZY Loves Chinese II

2016年9月25日2016年12月14日 Qizy 88 Comments

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3569
数据生成器：http://paste.ubuntu.com/23227745/

这个题，是我到目前为止，做过的最妙的一道题
没有之一

给每一个非树边搞一个权值
然后亦或到它所覆盖的每一条树边上去
考虑不联通的情况：删掉了一条树边和所有覆盖他的非树边
及一个子集的亦或和为0
于是像求线性基一样，判一下是否线性无关即可

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

const int N = 100000+9;
const int M = 1000000+9;
const int MOD = 9999971; 
const int SGZ = 40;

int head[N],nxt[M],to[M],n,m,q,val[M];
int vis[N],c[SGZ],cnt,bas[SGZ],sym[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 Add_Edge(int u, int v) {
	static int T = 1;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; 
	to[++T] = u; nxt[T] = head[v]; head[v] = T; 
}

void DFS1(int w, int f) {
	vis[w] = 1;
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
		if (vis[to[i]]) {
			int W = rand()*(rand()%MOD); val[i] ^= W; val[i^1] ^= W;
			sym[w] ^= W; sym[to[i]] ^= W;	
		} else DFS1(to[i],w);
	}
}

void DFS2(int w, int f) {
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f && !val[i]) 
		DFS2(to[i], w), val[i] ^= sym[to[i]], 
		val[i^1] ^= sym[to[i]], sym[w] ^= sym[to[i]];
}

inline bool update(int w) {
	for (int i=0,tmp=val[w];i<=30;i++) if (tmp&(1<<i)) {
		if (!bas[i]) {bas[i] = tmp; return false;}
		else {tmp ^= bas[i]; if (!tmp) return true;}
	} return val[w]?false:true;
}

int main(){
	srand(9999971); n = read(); m = read(); 
	for (int i=1;i<=m;i++) Add_Edge(read(),read());
	DFS1(1,1); DFS2(1,1);
	for (int q=read(),k,tag;q;q--) {
		k = read(); tag = 1; memset(bas,0,sizeof(bas));
		for (int i=1;i<=k;i++) c[i] = read()^cnt;
		for (int i=1;i<=k && tag;i++) if (update(c[i]*2)) puts("Disconnected"), tag = 0;
		if (tag) puts("Connected"), cnt++;
	}
	return 0;
}

【UOJ 241】破坏发射台

2016年8月31日2017年1月12日 Qizy 21 Comments

题目传送门：http://uoj.ac/problem/241
官方题解：http://c-sunshine.blog.uoj.ac/blog/2026

考试的时候，推这个题推了两个半小时QAQ
一直觉得马上就可以推出来辣！结果一直没有推出来
不过最后还是成功把奇数的式子推出来了（虽然和std不同，但是正确的）
至于偶数的式子嘛，感觉题解说的不是很清楚，我也就来哔哔两句：
不难发现，如果我们仍然按位来递推，不方便处理穿过发射台的情况
于是我们定义二元组（f，g）表示第i位与i+n/2位的颜色情况
于是我们发现这样的定义就可以按二元组为阶段来递推了，因为这货就无后效性了
于是搞一搞矩阵乘法即可
ps：为什么我做这题的时候老想着数位DP

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
#define S(x,y) ((x)*3+(y)+1)
using namespace std;

const int MOD = 998244353;
const int N = 100000;
const int M = 9;

int n,m,vout;

struct Matrix{
	int a[M][M];
	inline Matrix() {}
	inline Matrix(int v) {memset(a,0,sizeof(a));for(int i=1;i<M;i++) a[i][i]=v;}
	inline Matrix operator = (const Matrix &B) {memcpy(&(*this),&B,sizeof(a));}
	inline Matrix operator * (const Matrix &B) {
		Matrix ret(0);
		for (int i=1;i<M;i++) for (int j=1;j<M;j++) for (int k=1;k<M;k++) 
			ret.a[i][j] = ((LL)a[k][j]*B.a[i][k] + ret.a[i][j]) % MOD;
		return ret;
	}
	inline Matrix operator ^ (int t) {
		Matrix ret(1),w=*this;
		while (t) {
			if (t & 1) ret = ret*w;
			w = w*w; t >>= 1;	
		}
		return ret;
	}
};

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 pow(int w, int t){
	int ret = 1;
	while (t) {
		if (t & 1) ret = (LL)ret*w % MOD;
		w = (LL)w*w % MOD; t >>= 1;
	}
	return ret;
} 

int main(){
	n = read(), m = read();
	if (n%2 == 0) {
		Matrix ori(0),tra(0); ori.a[S(1,2)][1]=1;
		if (m > 3) tra.a[S(0,0)][S(1,2)] = tra.a[S(0,0)][S(2,1)] = (LL)(m - 2) * (m - 3) % MOD;
		if (m > 3) tra.a[S(0,0)][S(1,0)] = tra.a[S(0,0)][S(0,1)] = (LL)(m - 3) * (m - 3) % MOD;
		if (m > 3) tra.a[S(0,0)][S(2,0)] = tra.a[S(0,0)][S(0,2)] = (LL)(m - 3) * (m - 3) % MOD;
		if (m > 3) tra.a[S(0,0)][S(0,0)] = ((LL)(m-4) * (m-4) + m - 3) % MOD;
		
		if (m > 2) tra.a[S(1,0)][S(2,1)] = tra.a[S(0,1)][S(1,2)] = m - 2;
		if (m > 2) tra.a[S(1,0)][S(0,1)] = tra.a[S(0,1)][S(1,0)] = m - 2;
		if (m > 2) tra.a[S(1,0)][S(0,2)] = tra.a[S(0,1)][S(2,0)] = m - 2;
		if (m > 3) tra.a[S(1,0)][S(2,0)] = tra.a[S(0,1)][S(0,2)] = m - 3;
		if (m > 3) tra.a[S(1,0)][S(0,0)] = tra.a[S(0,1)][S(0,0)] = m - 3;
		
		if (m > 2) tra.a[S(2,0)][S(1,2)] = tra.a[S(0,2)][S(2,1)] = m - 2;
		if (m > 2) tra.a[S(2,0)][S(0,2)] = tra.a[S(0,2)][S(2,0)] = m - 2;
		if (m > 2) tra.a[S(2,0)][S(0,1)] = tra.a[S(0,2)][S(1,0)] = m - 2;
		if (m > 3) tra.a[S(2,0)][S(1,0)] = tra.a[S(0,2)][S(0,1)] = m - 3;
		if (m > 3) tra.a[S(2,0)][S(0,0)] = tra.a[S(0,2)][S(0,0)] = m - 3;
		
		tra.a[S(1,2)][S(0,1)] = tra.a[S(2,1)][S(1,0)] = 1;
		tra.a[S(1,2)][S(2,0)] = tra.a[S(2,1)][S(0,2)] = 1;
		tra.a[S(1,2)][S(2,1)] = tra.a[S(2,1)][S(1,2)] = 1;
		tra.a[S(1,2)][S(0,0)] = tra.a[S(2,1)][S(0,0)] = 1;
		
		tra = tra^(n/2-1); ori = ori * tra;
		vout = ((LL)ori.a[S(0,2)][1] + ori.a[S(1,0)][1] + ori.a[S(1,2)][1] + ori.a[S(0,0)][1]) % MOD;
		vout = ((LL)vout * m % MOD) * (m-1) % MOD;
		printf("%d\n",vout);
	}
	else {
		if (n == 3) printf("%d\n",((LL)(pow(m-1,n-1)-(m-1))*m % MOD + MOD) % MOD);
		else {
			Matrix ori(0); ori.a[1][1] = 1; ori.a[2][1] = m-2;
			Matrix tra(0); tra.a[1][2] = 1; tra.a[2][1] = m-1; tra.a[2][2] = m-2; 
			tra = tra^(n-5); ori = ori * tra; ori.a[1][1] = (LL)ori.a[1][1]*(m-1)%MOD;
			vout = (((LL)(m-1)*(m-2)%MOD)*ori.a[2][1]%MOD + (LL)ori.a[1][1]*(m-1)%MOD) % MOD;
			vout = (LL)(pow(m-1,n-1)-vout)*m % MOD;
			printf("%d\n",(vout+MOD)%MOD);
		}
	}
	return 0;
}

—– UPD 2017.1.12 —–
今天听毛爷爷讲这个题
居然感觉自己只会做奇数情况 QwQ
其实重点是，这货偶数情况的转移似乎非常神奇的样子
定义状态的方式，非常值得借鉴

相关链接

解题报告

相关链接

解题报告

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

解题报告

Code

相关链接

WJMZBMR Orz

解题报告

1）函数式线段树的做法

2）直接用点分治的做法

Code

链接

题解

Code

链接

题解

Code

链接

题解

Code

相关链接：

解题报告

Code