【日常小测】学外语

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/07/NOI2017-matthew99.pdf

解题报告

从$i$向$a_i$连边
不难发现这题就是求一个基环树森林与自身同构的情况
这个我们可以用$Hash$来搞一搞

Code

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

const int N = 1000009;
const int MOD = 1000000007;
const int INF = 2e9;

int n, E, ans, head[N], nxt[N], to[N];
int inv[N], pw[N], ipw[N], pw23[N], R1[N], R2[N];
int pre[N], dep[N], in[N], deg[N], vis[N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar()) {
		f = c == '-'? -1: 1;
	}
	for (; '0' <= c && c <= '9'; c = getchar()) {
		ret = ret * 10 + c - '0';
	}
	return ret * f;
}

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

inline void AddEdge(int u, int v) {
	in[v]++; deg[v]++; pre[u] = v;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline void mrk(int w) {
	vis[w] = 1;
	if (--in[pre[w]] == 0) {
		mrk(pre[w]);
	}
}

inline int cal_node(int w) {
	int ret = R2[deg[w]];
	vector<int> arr;
	for (int i = head[w]; i; i = nxt[i]) {
		if (!in[to[i]]) {
			dep[to[i]] = dep[w] + 1;
			int tmp = cal_node(to[i]);
			arr.push_back(tmp);
			ret = (ret + (LL)R1[dep[w]] * tmp) % MOD;
		}
	}
	sort(arr.begin(), arr.end());
	for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) {
		for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j);
		ans = (LL)ans * ipw[j - i + 1] % MOD;
	}
	return (LL)ret * ret % MOD;
}

inline int cal_cir(int w) {
	vector<int> node, arr;
	while (!vis[w]) {
		vis[w] = 1;
		node.push_back(w);
		for (int i = head[w]; i; i = nxt[i]) {
			if (in[to[i]]) {
				w = to[i];
				break;
			}
		}
	}
	for (int i = 0; i < (int)node.size(); i++) {
		dep[node[i]] = 6;
		arr.push_back(cal_node(node[i]));
	}
	int sta = 0, cnt = 1;
	for (int i = 0; i < (int)node.size(); i++) {
		sta = (sta + (LL)pw23[i] * arr[i]) % MOD;
	} 
	int ret = (LL)sta * pw23[n] % MOD;
	for (int i = 1, cur = sta; i < (int)node.size(); i++) {
		cur = (cur + (LL)arr[i - 1] * (pw23[i - 1 + node.size()] - pw23[i - 1])) % MOD;
		ret = min(ret, int((LL)cur * pw23[n - i] % MOD));
		cnt += ((cur = (cur + MOD) % MOD) == (LL)sta * pw23[i] % MOD);
	}
	ans = (LL)ans * inv[cnt] % MOD;
	return ret;
}

int main() {
	srand(19991216);
	inv[0] = pw[0] = ipw[0] = pw23[0] = 1;
	R1[0] = rand(); R2[0] = rand();
	for (int i = 1; i < N; i++) {
		pw[i] = (LL)pw[i - 1] * i % MOD;
		pw23[i] = pw23[i - 1] * 131ll % MOD;
		inv[i] = Pow(i, MOD - 2);
		ipw[i] = Pow(pw[i], MOD - 2);
		R1[i] = rand(); R2[i] = rand();
	}
	
	for (int T = read(); T; T--) {
		memset(head, 0, sizeof(head));
		memset(deg, 0, sizeof(deg));
		memset(vis, 0, sizeof(vis));
		memset(in, 0, sizeof(in));
		E = 0; ans = 1;
		
		n = read();
		for (int i = 1; i <= n; i++) {
			AddEdge(i, read());
		}	
		for (int i = 1; i <= n; i++) {
			if (!in[i] && !vis[i]) {
				mrk(i);
			}
		}
		vector<int> arr;
		for (int i = 1; i <= n; i++) {
			if (in[i] && !vis[i]) {
				arr.push_back(cal_cir(i));
			}
		}
		sort(arr.begin(), arr.end());
		for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) {
			for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j);
			ans = (LL)ans * ipw[j - i + 1] % MOD;
		}
		ans = ((LL)ans * pw[n] - 1) % MOD;
		printf("%d\n", (ans + MOD) % MOD);
	}
	return 0;
}

【日常小测】仰望星空

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/07/NOI2017-matthew99.pdf

解题报告

我们按照极角序来贪心匹配
不难发现这样一定有解

另外Dinic是不能求这种要求字典序最小的解的
似乎只能用最裸的匈牙利

Code

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

const int N = 1009;
const int M = 1000009;
const int INF = 1e9;
const double PI = acos(-1);

int n, R, D, S, T;
int in[N], ot[N], cnt_in, cnt_ot;
int head[N], nxt[M], to[M], mth[N], vis[N];
pair<double, int> arr[N];
struct Point{
	int x, y, ty;
	inline int dis(const Point &P) {
		return (x - P.x) * (x - P.x) + (y - P.y) * (y - P.y);
	}
}p[N];

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
} 

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline bool DFS(int w) {
	vis[w] = 1;
	for (int i = head[w]; i; i = nxt[i]) {
		if (!mth[to[i]] || (!vis[mth[to[i]]] && DFS(mth[to[i]]))) {
			mth[to[i]] = w;
			mth[w] = to[i];
			return 1;
		} 
	}
	return 0;
}

inline int solve() {
	int ret = 0;
	for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) {
		if (!mth[i]) {
			memset(vis, 0, sizeof(vis));
			ret += DFS(i);
		}
	}
	return ret;
}

inline void print(int w) {
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] == mth[w]) {
			vis[w] = vis[to[i]] = 1;
			printf("%d %d\n", w, mth[w]);
			return;
		} else if (!vis[to[i]]){
			print(mth[to[i]]);
		}
	}
}

int main() {
	n = read(); 
	R = read(); R *= R;
	D = read(); D *= D;
	S = 0; T = N - 1;
	for (int i = 1; i <= n; i++) {
		p[i].x = read();
		p[i].y = read();
		if (p[i].ty = p[i].dis(p[1]) > R) {
			in[++cnt_in] = i;
		} else {
			ot[++cnt_ot] = i;
		}
	}
	for (int ii = 1; ii <= cnt_in; ii++) {
		int i = in[ii], cnt_arr = 0;
		double mx = -PI, mn = PI;
		for (int jj = 1; jj <= cnt_ot; jj++) {
			int j = ot[jj];
			if (p[i].dis(p[j]) <= D) {
				double agl = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
				mx = max(mx, agl);
				mn = min(mn, agl);
				arr[++cnt_arr] = make_pair(agl, j);
			}
		}
		if (mx - mn >= PI) {
			for (int j = 1; j <= cnt_arr; j++) {
				arr[j].first += arr[j].first < 0? PI * 2: 0;
			}
		}
		sort(arr + 1, arr + 1 + cnt_arr);
		for (int j = 1; j <= cnt_arr; j++) {
			AddEdge(i, arr[j].second);
		}
	}
	printf("%d\n", solve() << 1);
	memset(vis, 0, sizeof(vis));
	for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) {
		if (mth[i] && !vis[i]) {
			print(i);
		}
	}
	return 0;
}

【日常小测】最长路径

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

首先我们要熟悉竞赛图的两个结论:

  1. 任意一个竞赛图一定存在哈密尔顿路径
  2. 一个竞赛图存在哈密尔顿回路当且仅当这个竞赛图强连通

现在考虑把强连通分量缩成一个点,并把新点按照哈密尔顿路径排列
那么$1$号点可以到达的点数就是$1$号点所在的$SCC$的点数加上$1$号点可以到达的其他$SCC$点数和

设$f_i$为$i$个点带标号竞赛图的个数
设$g_i$为$i$个点带标号强连通竞赛图的个数
有$f_i = 2^{\frac{n(n-1)}{2}}$
又有$g_i = f_i – \sum\limits_{j = 1}^{i – 1}{{{i}\choose{j}} g_j f_{i – j}}$

于是我们枚举$1$号点所在$SCC$的点数$i$和$1$号点可到达的其他$SCC$的点数和$j$
$ans_{x} = \sum\limits_{i = 1}^{x}{{{n – 1}\choose{i – 1}} g_i {{n – i}\choose{x – i}} f_{x – i} f_{n – x}}$

Code

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

const int N = 2009;

int n, MOD, f[N], g[N], pw[N * N], C[N][N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

int main() {
	freopen("path.in", "r", stdin);
	freopen("path.out", "w", stdout);
	n = read(); MOD = read();
	pw[0] = 1;
	for (int i = 1; i < n * n; i++) {
		pw[i] = (pw[i - 1] << 1) % MOD;
	}
	C[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= n; j++) {
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
		}
	}
	f[0] = g[0] = 1;
	for (int i = 1; i <= n; i++) {
		f[i] = g[i] = pw[i * (i - 1) >> 1];
		for (int j = 1; j < i; j++) {
			g[i] = (g[i] - (LL)C[i][j] * g[j] % MOD * f[i - j]) % MOD;
		}
	}
	for (int x = 1; x <= n; x++) {
		int ans = 0;
		for (int i = 1; i <= x; i++) {
			ans = (ans + (LL)C[n - 1][i - 1] * g[i] % MOD * C[n - i][x - i] % MOD * f[x - i] % MOD * f[n - x]) % MOD;
		}
		printf("%d\n", ans > 0? ans: ans + MOD);
	}
	return 0;
}

【算法笔记】Kosaraju算法

前言

今天考了一套$Claris$的题
$T1$就是$Claris$用$bitset$配合这个算法把求$SCC$优化到了$\frac{n^2}{32}$
吓得我赶紧来学了学

算法概述

$step \ 1.$ DFS一遍,记录下后序遍历的顺序
$step \ 2.$ 沿后续遍历的逆序、沿反向边再DFS一遍,每一个连通块即为一个SCC

算法解释

设原图为图$G$,将$SCC$缩点后的新图为$G’$
第一遍$DFS$保证了在若某个强连通分量$A$在$G’$中是另一个强连通分量$B$的祖先
那么在后续遍历的逆序中至少存在一个点$A$中的点在$B$中所有点的前面

这样在第二次$DFS$的时候,因为是逆序,所以只能往$G’$中的祖先走
又因为祖先的$SCC$已经标记过了,所以刚好把当前$SCC$搞完,不会有多

这算法太妙了

代码实现

int scc_cnt, vis[N];
vector<int> scc_cnt[N], que;
void DFS0(int w) {
	vis[w] = 0;
	for (int i = head[w]; i; i = nxt[i]) {
		if (!vis[to[i]]) {
			DFS0(to[i]);
		}
	}
	que[++tot] = w;
}
void DFS1(int w) {
	scc[scc_cnt].push_back(w);
	vis[w] = 1;
	for (int i = rev_head[w]; i; i = nxt[i]) {
		if (!vis[to[i]]) {
			DFS1(to[i]);
		}
	}
} 
void solve() {
	que.clear();
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			DFS0(i);
		}
	}
	scc_cnt = 0;
	memset(vis, 0, sizeof(vis));
	for (int i = (int)que.size() - 1; ~i; i--) {
		if (!vis[que[i]]) {
			scc_cnt++;
			DFS1(que[i]);
		}
	}
}

使用$bitset$优化

这货复杂度是$O(m)$的
不难发现算法瓶颈在查找与某个点相邻的所有点中还没有被访问过的点
这个可以用$bitset$压位并配合__builtin开头的系列函数优化到$O(\frac{n^2}{32})$
例题的话,可以参考:友好城市

【日常小测】友好城市

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

这题的前置知识是把求$SCC$优化到$O(\frac{n^2}{32})$
具体来说,就是使用$bitset$配合$Kosaraju$算法

有了这个技能以后,我们配合$ST$表来实现提取一个区间的边的操作
这样的话,总的时间复杂度是:$O(\frac{(\sqrt{m} \log m + q) n^2}{32}+q \sqrt{m})$

然后我懒,没有用$ST$表,用的莫队,时间复杂度是$O(\frac{(m + q) n^2}{32}+q \sqrt{m})$
调一调块大小,勉勉强强卡过去了

Code

#include<bits/stdc++.h>
#define LL long long
#define UI unsigned int 
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 159;
const int M = 300009;
const int QQ = 50009;
const int BlockSize = 1200;
const UI ALL = (1ll << 32) - 1;

int n, m, q, U[M], V[M], ans[QQ]; 
struct Query{
	int l, r, blk, id;
	inline bool operator < (const Query &Q) const {
		return blk < Q.blk || (blk == Q.blk && r < Q.r);
	}
}qy[QQ];
struct Bitset{
	UI v[5];
	inline void flip(int x) {
		v[x >> 5] ^= 1 << (x & 31);
	}
	inline void set(int x) {
		v[x >> 5] |= 1 << (x & 31);
	}
	inline void reset() {
		memset(v, 0, sizeof(v));
	}
	inline bool operator [](int x) {
		return v[x >> 5] & (1 << (x & 31));
	}
}g[N], rg[N], PreG[M / BlockSize + 9][N], PreRG[M / BlockSize + 9][N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline void AddEdge(int u, int v, Bitset *a1, Bitset *a2) {
 	a1[u].set(v);
 	a2[v].set(u);
}

class Kosaraju{
	vector<int> que;
	Bitset vis;
public:
	inline int solve() {
		vis.reset();
		que.clear();
		for (int i = 1; i <= n; ++i) {
			if (!vis[i]) {
				dfs0(i);
			}
		}
		vis.reset();
		int ret = 0;
		for (int j = n - 1; ~j; j--) {
			int i = que[j];
			if (!vis[i]) {
				int cnt = dfs1(i);
				ret += cnt * (cnt - 1) / 2;
			}
		}
		return ret;
	}
private:
	inline void dfs0(int w) {
		vis.flip(w);
		for (int i = 0; i < 5; i++) {
			for (UI j = g[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					dfs0(t);
				}
			}
		}
		que.push_back(w);
	}
	inline int dfs1(int w) {
		vis.flip(w);
		int ret = 1;
		for (int i = 0; i < 5; i++) {
			for (UI j = rg[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					ret += dfs1(t);
				}
			}
		}
		return ret;
	}
}scc;

int main() {
	freopen("friend.in", "r", stdin);
	freopen("friend.out", "w", stdout);
	n = read(); m = read(); q = read();
	for (int i = 1; i <= m; i++) {
		U[i] = read();
		V[i] = read();
		AddEdge(U[i], V[i], PreG[i / BlockSize], PreRG[i / BlockSize]);
	}
	for (int i = 1; i <= q; i++) {
		qy[i].l = read(); 
		qy[i].r = read();
		qy[i].blk = qy[i].l / BlockSize;
		qy[i].id = i;
	}
	sort(qy + 1, qy + 1 + q);
	Bitset CurG[N], CurRG[N];
	for (int i = 1, L = 1, R = 0; i <= q; i++) {
		if (qy[i].blk != qy[i - 1].blk || i == 1) {
			L = qy[i].blk + 1;
			R = L - 1;	
			for (int j = 1; j <= n; j++) {
				CurG[j].reset();
				CurRG[j].reset();
			}
		}
		if (qy[i].r / BlockSize - 1 > R) {
			for (int j = R + 1, lim = qy[i].r / BlockSize - 1; j <= lim; j++) {
				for (int k = 1; k <= n; k++) {
					for (int h = 0; h < 5; h++) {
						CurG[k].v[h] ^= PreG[j][k].v[h];
						CurRG[k].v[h] ^= PreRG[j][k].v[h];
					}
				}
			}
			R = qy[i].r / BlockSize - 1;
		}
		if (L <= R) {
			for (int i = 1; i <= n; i++) {
				g[i] = CurG[i];
				rg[i] = CurRG[i];
			}
			for (int l = qy[i].l; l < L * BlockSize; l++) {
				AddEdge(U[l], V[l], g, rg);
			}
			for (int r = (R + 1) * BlockSize; r <= qy[i].r; r++) {
				AddEdge(U[r], V[r], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		} else {
			for (int i = 1; i <= n; i++) {
				g[i].reset();
				rg[i].reset();
			}
			for (int j = qy[i].l; j <= qy[i].r; ++j) {
				AddEdge(U[j], V[j], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		}
	}
	for (int i = 1; i <= q; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

【Codeforces 802C】Heidi and Library (hard)

相关链接

题目传送门:http://codeforces.com/contest/802/problem/C
官方题解:http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf
消圈定理:https://blog.sengxian.com/algorithms/clearcircle

解题报告

被这题强制解锁了两个新姿势qwq

  1. 上下界最小费用流:
    直接按照上下界网络流一样建图,然后正常跑费用流
  2. 带负环的费用流
    应用消圈定理,强行将负环满流

然后考完之后发现脑残了
换一种建图方法就没有负环了_(:з」∠)_

Code

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

const int N = 5000000;
const int M = 200;
const int INF = 1e9;

int n,k,S,T,tot,SS,TT,ans,a[M],np[M],cc[M];
int head[N],nxt[N],to[N],flow[N],cost[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 AddEdge(int u, int v, int c, int f) {
	static int E = 1;
    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;
}

class Minimum_Cost_Flow{
    int dis[N],sur[N],inq[N],vis[N]; 
    queue<int> que; 
    public:
        inline void MaxFlow() {
        	while (clearCircle()); 
            for (int ff; ff = INF, SPFA();) {
            	for (int w = TT; w != SS; w = to[sur[w]^1]) {
					ff = min(ff, flow[sur[w]]);
				}
                for (int w = TT; w != SS; w = to[sur[w]^1]) {
					flow[sur[w]] -= ff;
					flow[sur[w]^1] += ff;
				}
				ans += dis[TT] * ff;
            }
        }
    private:
        bool SPFA() {
            memset(dis,60,sizeof(dis));
            que.push(SS); dis[SS] = 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[TT] < INF;
        }
        bool clearCircle() {
        	memset(dis, 0, sizeof(dis));
        	memset(vis, 0, sizeof(vis));
			for (int i = 1; i <= tot; ++i) { 
   	    		if (!vis[i] && DFS(i)) {
					return 1;   
				}
			}
			return 0;
    	}
    	bool DFS(int w) {
    		vis[w] = 1;
    		if (inq[w]) {
    			int cur = w;
    			do {
					flow[sur[cur]]--;
					flow[sur[cur]^1]++;
					ans += cost[sur[cur]];
					cur = to[sur[cur]];
				} while (cur != w);
				return 1;
			} else {
    			inq[w] = 1;
				for (int i = head[w]; i; i = nxt[i]) {
					if (flow[i] && dis[to[i]] > dis[w] + cost[i]) {
						dis[to[i]] = dis[w] + cost[i];
						sur[w] = i;
						if (DFS(to[i])) {
							inq[w] = 0;
							return 1;
						}
					}
				}
				inq[w] = 0;
				return 0;
			}
			
		}
}MCMF;

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif 
	n = read(); k = read();
	S = tot = n + 4; T = n + 1;
	SS = n + 2; TT = n + 3; 
	AddEdge(T, S, 0, k); 
	AddEdge(S, 1, 0, INF);
	for (int i = 1; i <= n; i++) {
		np[i] = ++tot;
		AddEdge(np[i], i + 1, 0, INF);
		AddEdge(i, np[i], 0, INF);
		AddEdge(i, TT, 0, 1);
		AddEdge(SS, np[i], 0, 1);
		a[i] = read();
	}
	for (int i = 1; i <= n; i++) {
		cc[i] = read();
	}
	for (int i = 1; i <= n; i++) {
		ans += cc[a[i]];
		for (int j = i + 1; j <= n; j++) {
			if (a[i] == a[j]) {
				AddEdge(np[i], j, -cc[a[i]], 1);
				break;
			} 
		}
	}
	MCMF.MaxFlow();
	cout<<ans<<endl; 
	return 0;
}

【BZOJ 4886】[Lydsy2017年5月月赛] 叠塔游戏

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4886
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/05/ludsy_may_contest_solution.pdf

解题报告

我们把权值看做点,矩形看作边
不难发现一个大小为$n$连通块如果是树,那么最多选$n-1$个点
否则可以选完$n$个点

所以用并查集维护一下连通性之后
直接贪心即可

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int N = 500009;
  
int n,tot,u[N],v[N],fa[N],val[N],cir[N],sz[N]; 
LL ans;
  
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 find(int x) {
    return x == fa[x]? x: fa[x] = find(fa[x]);
}
  
int main() {
    n = read();
    for (int i=1;i<=n;i++) {
        u[i] = val[++tot] = read(); 
        v[i] = val[++tot] = read();
        ans += u[i];
        ans += v[i];
    }
    sort(val+1, val+1+tot);
    tot = unique(val+1, val+1+tot) - val - 1;
    for (int i=1;i<=tot;i++) {
        fa[i] = i;
        sz[i] = 1;
    }
    for (int i=1;i<=n;i++) {
        int x = lower_bound(val+1, val+1+tot, u[i]) - val;
        int y = lower_bound(val+1, val+1+tot, v[i]) - val;
        if (find(x) != find(y)) {
            sz[fa[y]] += sz[fa[x]];
            if (cir[fa[x]]) {
                cir[fa[y]] = 1;
            }
            fa[fa[x]] = fa[y];
        } else {
            cir[fa[x]] = 1;
        }
    } 
    for (int i=1;i<=tot;i++) {
        if (find(i) == i) {
            sz[i] -= (cir[i] ^ 1);
        }
    }
    for (int i=1,w=1;i<=n;i++,w++) {
        while (sz[find(w)] == 0) ++w;
        ans -= val[w]; 
        sz[fa[w]]--;
    }
    printf("%lld\n",ans);
    return 0;
}

【BZOJ 3577】玩手机

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3577
神犇题解:http://www.cnblogs.com/clrs97/p/4403242.html

解题报告

之前一直都是线段树优化建图
这题需要用$ST$表来优化建图

Code

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

const int INF = 1e9;
const int N = 500000;
const int M = 2000000;

int S,T,E,tot,A,B,Y,X,n2[2][70][70][8]; 
int head[N],nxt[M],to[M],flow[M],n1[2][70][70];

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 AddEdge(int u, int v, int f) {
	assert(u); assert(v);
	to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}

class NetworkFlow{
	int dis[N],cur[N];
	queue<int> que;
	public:
		inline int MaxFlow() {
			int ret = 0;
			while (BFS()) {
				memcpy(cur, head, sizeof(cur));
				ret += DFS(S, INF);
			}
			return ret;
		}
	private:
		inline bool BFS() {
			memset(dis, 60, sizeof(dis));
			dis[S] = 0;
			for (que.push(S); !que.empty(); que.pop()) {
				int w = que.front();
				for (int i = head[w]; i; i = nxt[i]) {
					if (flow[i] && dis[to[i]] > INF) {
						dis[to[i]] = dis[w] + 1;
						que.push(to[i]);
					}
				}
			}
			return dis[T] <= INF;
		}
		inline int DFS(int w, int f) {
			if (w == T) {
				return f;
			} else {
				int ret = 0;
				for (int &i = cur[w]; i; i = nxt[i]) {
					if (flow[i] && dis[to[i]] == dis[w] + 1) {
						int tmp = DFS(to[i], min(f, flow[i]));
						ret += tmp; f -= tmp;
						flow[i] -= tmp; flow[i ^ 1] += tmp;
						if (!f) {
							break;
						}
					}
				}
				return ret;
			}
		}
}Dinic;

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	X = read(); Y = read(); 
	A = read(); B = read();
	S = ++tot; T = ++tot;
	E = 1; 
	for (int i = 1; i <= X; ++i) {
		for (int j = 1; j <= Y; ++j) {
			n1[0][i][j] = ++tot;
			n1[1][i][j] = ++tot;
			AddEdge(n1[0][i][j], n1[1][i][j], read());
		}
	}
	for (int i = X; i; --i) {
		for (int j = Y; j; --j) {
			for (int a = 0, len = 1; i + len - 1 <= X && j + len - 1 <= Y; ++a, len <<= 1) {
				n2[0][i][j][a] = ++tot;
				n2[1][i][j][a] = ++tot;
				if (!a) {
					AddEdge(n2[0][i][j][a], n1[0][i][j], INF);
					AddEdge(n1[1][i][j], n2[1][i][j][a], INF);	
				} else {
					int llen = len >> 1;
					AddEdge(n2[0][i][j][a], n2[0][i][j][a - 1], INF);
					AddEdge(n2[0][i][j][a], n2[0][i + llen][j][a - 1], INF);
					AddEdge(n2[0][i][j][a], n2[0][i][j + llen][a - 1], INF);
					AddEdge(n2[0][i][j][a], n2[0][i + llen][j + llen][a - 1], INF);
					
					AddEdge(n2[1][i][j][a - 1], n2[1][i][j][a], INF);
					AddEdge(n2[1][i][j + llen][a - 1], n2[1][i][j][a], INF);
					AddEdge(n2[1][i + llen][j][a - 1], n2[1][i][j][a], INF);
					AddEdge(n2[1][i + llen][j + llen][a - 1], n2[1][i][j][a], INF);
				} 
			}	
		}
	}
	for (int i = 1, w, x1, x2, y1, y2, p0, p1; i <= A; ++i) {
		p0 = ++tot; p1 = ++tot;
		w = read(); 
		x1 = read(); y1 = read();
		x2 = read(); y2 = read();
		AddEdge(S, p0, INF);
		AddEdge(p0, p1, w);
		
		int len = x2 - x1 + 1, lg = 0, d = 1;
		for (; (d << 1) <= len; lg++, d <<= 1);
		AddEdge(p1, n2[0][x1][y1][lg], INF);
		AddEdge(p1, n2[0][x1][y2 - d + 1][lg], INF);
		AddEdge(p1, n2[0][x2 - d + 1][y1][lg], INF);
		AddEdge(p1, n2[0][x2 - d + 1][y2 - d + 1][lg], INF);
	}
	for (int i = 1, w, x1, x2, y1, y2, p0, p1; i <= B; ++i) {
		p0 = ++tot;	p1 = ++tot;
		w = read();
		x1 = read(); y1 = read();
		x2 = read(); y2 = read();
		AddEdge(p0, p1, w);
		AddEdge(p1, T, INF);
		
		int len = x2 - x1 + 1, lg = 0, d = 1;
		for (; (d << 1) <= len; lg++, d <<= 1);
		AddEdge(n2[1][x1][y1][lg], p0, INF);
		AddEdge(n2[1][x1][y2 - d + 1][lg], p0, INF);
		AddEdge(n2[1][x2 - d + 1][y1][lg], p0, INF);
		AddEdge(n2[1][x2 - d + 1][y2 - d + 1][lg], p0, INF);
	}
	assert(tot < N);
	assert(E < M);
	printf("%d\n", Dinic.MaxFlow());
	return 0;
}

【Codeforces 804C】Ice cream coloring

相关链接

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

解题报告

不难发现这货是个弦图
然后仔细想想,只要保证

在原图中,一个一个结点处理
所有处理过的结点组成一个连通块

就可以了

至于这样为什么是对的?
因为最小染色数很好确定,就是$\max(s_i)$
所以我们只需要求出染色方案数,所以只要染色随时是一个连通块就可以了

Code

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

const int N = 600009;

int n,m,ans,head[N],to[N],nxt[N],sz[N],col[N];
vector<int> vis[N],lst[N];
set<int> que[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 AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline void solve(int w, int f) {
	int cur = 1;
	for (int jj=0;jj<lst[w].size();jj++) {
		int j = lst[w][jj];
		if (!col[j]) {
			while (!que[w].empty() && cur == *que[w].begin()) {
				++cur;
				que[w].erase(que[w].begin());
			}
			col[j] = cur;
			for (int k=0;k<vis[j].size();k++) {
				que[vis[j][k]].insert(cur);
			}
		} 
	}
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			solve(to[i], w);
		}
	}
}

int main() {
	n = read(); m = read();
	ans = 1;
	for (int i=1;i<=n;i++) {
		sz[i] = read();
		ans = max(ans, sz[i]);
		for (int j=1,p;j<=sz[i];j++) {
			p = read();
			vis[p].push_back(i);
			lst[i].push_back(p);
		}
	}
	for (int i=1;i<n;i++) {
		AddEdge(read(), read());
	}
	solve(1, 1);
	cout<<ans<<endl;
	for (int i=1;i<=m;i++) {
		printf("%d ",col[i]? col[i]: 1);
	}
	return 0;
}

【BZOJ 3103】[ONTAK2010] Palindromic Equivalence

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3103
神犇题解:http://foreseeable97.logdown.com/posts/194507-herbicidalontak2010palindromic-equivalence

解题报告

这些字符串相关的计数题已经做过很多了吧?
这题显然就是给定$O(n)$个相等与不等的关系,让你求染色方案数
这样直接做好像是一个$NP$的问题?就是四色定理那个一般化后的问题

但这题有一个非常好的性质,如果我们把一个等价类看成点,不等关系看成边
那么每一个联通块都是一个完全图!也就是一个弦图!
弦图的染色方案数是可以使用完美消除序列在$O(n)$的时间复杂度内解决的
有因为这题是完全图,所以任意一个$1 \sim n$的排列都是完美消除序列
于是直接从$1 \to n$进行计算即可

至于这图是个弦图图的证明,想一想还是很简单的(虽然不怎么容易观察出来)
我们可以参考:http://foreseeable97.logdown.com/posts/194507-herbicidalontak2010palindromic-equivalence

Code

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

const int N = 2000009;
const int M = N << 1;
const int MOD = 1000000007;

char pat[N],s[N];
int n,ans=1,fa[N],rid[N],col[N];
int vis[N],head[N],nxt[M],to[M]; 
vector<pair<int,int> > e;

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 find(int x) {
	return x == fa[x]? x: fa[x] = find(fa[x]);
}

inline void manacher() {
	for (int i=1,r=1,p=1,t;i<=n*2;i++) {
		t = min(r - i, rid[p - (i - p)]);
		while (s[i+t+1] == s[i-t-1]) t++, fa[find(i+t)] = find(fa[i-t]);
		if ((rid[i] = t) + i > r) r = t + i, p = i;
		e.push_back(make_pair(i - t - 1, i + t + 1));
	}
}

inline void AddEdge(int u, int v) {
	static int E = 1; 
	if (u == v || !(u & 1) || !(v & 1)) return;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

int main() {
	scanf("%s",pat+1); n = strlen(pat+1); 
	s[0] = '#'; s[n*2] = '@';
	for (int i=1;i<=n;i++) s[i*2-1] = pat[i], s[i*2] = '*';
	for (int i=1;i<=n*2;i++) fa[i] = i;
	manacher();
	for (int i=0;i<e.size();i++) AddEdge(find(e[i].first), find(e[i].second));
	for (int i=1,cnt;cnt=26,i<=n*2;i+=2) {
		if (find(i) != i) continue; col[i] = 1;
		for (int j=head[i];j;j=nxt[j]) {
			if (col[to[j]] && vis[to[j]] < i) 
				--cnt, vis[to[j]] = i;
		}  
		if (cnt <= 0) ans = 0; 
		else ans = (LL)ans * cnt % MOD;
	}
	cout<<ans;
	return 0;
}

—————————— UPD 2017.4.26 ——————————
今天我们机房讨论了一下,这货是个弦图,不一定是一个完全图

【Codeforces 788C】The Great Mixing

相关链接

题目传送门:http://codeforces.com/contest/788/problem/C
官方题解:http://codeforces.com/blog/entry/51312

解题报告

假设取$x$个物品的时候原问题有解,且第$i$个物品的编号为$b_i$
那么此时满足这个等式:$\sum\limits_{i=1}^{x}{a_{b_i}}=nx$

这个看起来既不满足单调性,又不能方便地$DP$
但如果我们把$n$给减到$a_i$里去,那么就是$\sum\limits_{i=1}^{x}{a_{b_i}}=0$
这个就好办了,直接搞一个$O(n^2)$的那个$BFS$

这个技巧应用较为广泛,还有一些升级版本
比如这个题:http://oi.cyo.ng/?p=3069

Code

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

const int N = 2009;
const int M = 2000009;
const int BAS = 1000;

int n,m,tot,dis[N],head[N];
int nxt[M],to[M],_hash[M];
queue<int> que;

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();
	for (int i=1;i<=m;i++) _hash[++tot] = read() - n;
	sort(_hash+1, _hash+1+tot);
	tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
	for (int i=1;i<=tot;i++) {
		dis[_hash[i] + BAS] = 1;
		que.push(_hash[i] + BAS);
	} 
	while (!que.empty()) {
		int w = que.front(); que.pop();
		for (int i=1,t;t=w+_hash[i],i<=tot;i++) {
			if (t < 0 || t > BAS*2 || dis[t]) continue;
			dis[t] = dis[w] + 1; que.push(t);
		}
	}
	cout<<(dis[BAS]?dis[BAS]:-1);
	return 0;
}

【CodeChef DINING】[January Cook-off 2014] Dining

相关链接

题目传送门:https://www.codechef.com/problems/DINING
官方题解:https://discuss.codechef.com/questions/70332/dining-editorial

解题报告

这题套路啊,神™套路啊!

关键问题是它的概率是乘起来的,不是加起来
于是很多东西都不能用啊!
于是题解说我们可以取对数,因为$\log(a \cdot b) = \log (a) + \log (b)$
于是就变成了加法,于是就可以跑一个费用流了

把乘法换搞成加法,在模意义下还有一种做法,参见:
http://oi.cyo.ng/?p=2702

【BZOJ 2118】墨墨的等式

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2118
神犇题解:https://blog.sengxian.com/solutions/bzoj-2118

解题报告

先来看一道简单的题目:

给定$a,b,c(a,b,c \le 10^5)$,规定$x,y,z \in \mathbb{N}$
问$ax+by+cz$不能表示出的正整数中,最大的那一个是多少

我们不妨在$\bmod c$的意义下做,这样就可以只考虑$0 \sim c-1$
于是暴力用$a,b$连边,跑一边最短路
这样就可以求出在$\bmod c$的剩余系中,每一个等价类最早出现的位置
于是扫一遍,取一个$\max$就可以了

然后再看看这个题,也就是多连几条边的事吧?

Code

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

const int N = 500009;
const int M = N * 12;
const LL INF = 1e17;

int n,a[N],done[N];
int nxt[M],to[M],cost[M],head[N];
LL dis[N],bmn,bmx,mn=INF;
priority_queue<pair<LL,int> > que;

inline void AddEdge(int u, int v, int c) {
	static int E = 1; cost[++E] = c;
	to[E] = v; nxt[E] = head[u]; head[u] = E;
}

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 Dijkstra() {
	for (int i=0;i<mn;i++) dis[i] = INF;
	dis[0] = 0; que.push(make_pair(0, 0));
	while (!que.empty()) {
		int w = que.top().second; que.pop();
		if (done[w]) continue; else done[w] = 1;
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] > dis[w] + cost[i]) {
				dis[to[i]] = dis[w] + cost[i];
				que.push(make_pair(-dis[to[i]], to[i]));
			}
		}
	}
}

inline LL cal(LL lim) {
	LL ret = 0, tmp;
	for (int i=0;i<mn;i++) {
		if (lim < dis[i]) continue;
		ret += (lim - dis[i]) / mn + 1;
	}
	return ret;
}

int main() {
	n = read(); cin>>bmn>>bmx;
	for (int i=1;i<=n;i++) {
		a[i] = read();
		if (a[i]) mn = min(mn, (LL)a[i]);
	}
	for (int i=1;i<=n;i++) {
		if (a[i] == mn) continue;
		for (int j=0;j<mn;j++) {
			AddEdge(j, (j+a[i])%mn, a[i]);
		}
	}
	Dijkstra();
	printf("%lld\n",cal(bmx)-cal(bmn-1));
	return 0;
}

【BZOJ 3033】太鼓达人

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3033
神犇题解:http://blog.csdn.net/clover_hxy/article/details/56003661

解题报告

这个东西,看一看样例,感觉答案是$2^k$,然后写一发无脑贪心就过了

不过这题的证明非常妙妙啊:

考虑将每一个$0 \sim 2^{k+1}-1$的数看成一个点,标号为这个数
把在这个数末尾或者开头加$0/1$看作边
那么每个点度数恰好为$4$,并且整个图显然连通
那么这图显然存在欧拉回路,那么就能够一笔画

于是在这个图上贪心走就可以了

Code

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

const int N = 3000;

int n,k,arr[N];
set<int> S;

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 get(int p) {
	int ret = 0;
	for (int i=0;i<k;i++) ret += (1 << i) * arr[p + i];
	return ret; 
}

int main() {
	k = read(); n = 1 << k;
	for (int i=1;i<=k;i++) arr[i] = 0; S.insert(0);
	for (int i=n;i>n-k;i--) arr[i] = 1, S.insert(get(i));
	for (int i=2;i<=n-k;i++) {
		if (S.count(get(i))) arr[i+k-1] = 1;
		S.insert(get(i));
	}
	printf("%d ",n);
	for (int i=1;i<=n;i++) printf("%d",arr[i]);
	return 0;
}

【HDU 5772】String problem

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5772
神犇题解:http://www.cnblogs.com/qscqesze/p/5715939.html

解题报告

日常看错题系列:

  1. 子序列看成子串
  2. 值域范围$0 \sim 9$看漏

于是只会跑$n$遍网络流的算法了 QwQ
大概就是枚举左端点,然后暴力跑

考虑原题的话,唯一的Trick就是如何处理一个数第一次选的代价不同
我们可以使用最大权闭合子图来解决这个问题:

每一类数字新建一个结点,权值为$b_i – a_i$
值为该数字的所有序列上的点向这个新建的点连一条有向边

至于本题的其他部分就没什么好玩的了

【BZOJ 1937】[SHOI2004] Mst最小生成树

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1937
神犇题解:https://blog.sengxian.com/solutions/bzoj-1937

解题报告

我们首先可以得到一个结论:$T$中的边的边权只会减少,其他边的边权只会增加
于是我们将$T$中的边放在左边,其他边放在右边,都作为二分图的点,点权为边权
然后左右两两连边,边权$v_i$为右边点的权值减左边点的权值

此时问题转化为,每一个点设一个$d_i$,满足二分图中任意一条边$i \to j$满足$v_{i \to j} \le d_i + d_j$,求最小化$\sum{d_i}$
这是$KM$算法的关键步骤。于是直接上$KM$算法就可以了

但我不会$KM$算法
←为什么这个频率这个鬼畜啊 QwQ

但不会$KM$算法我们也能做,回忆$KM$算法顶标的作用
最小的顶标和就是最大权匹配的权值和
于是我们用费用流增广这个二分图,直到增广到权值为负就可以了