【日常小测】学外语

相关链接

题目传送门:https://oi.qizy.tech/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;
}

【BZOJ 3832】[POI2014] Rally

相关链接:

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3832

解题报告

这题真的是妙不可言!
0MYHX~N~(WNGO)B6[N8ZL40
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;
}