SRM672 div1 题解

Easy

题目大意：

给定一个无穷长的数列，一开始有$a_i=i$。从$i\geq{2}$开始，对于所有$i|j$且$j>i$的$j$进行操作$swap(a_j,a_{j+1})$。

问经过充分长的时间后$a_n$的值。

数据范围$n\leq{10^{10}}$。

题解：

我只能YY出有效的操作次数不是非常多，并且答案波动的范围非常小。

于是写了一个记忆化的因子分解。

然后暴力进行操作。

时间复杂度玄学。

结果在$n=2$时挂掉了。

官方的解好像就是这样的，但是看别人的代码好像还有别的姿势？

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

map<long long, int>M;
vector<long long>v[110];

int id;
int check(long long c){
	if(M[c] == 0){
		M[c] = ++id;
		for(int i = 1; (long long)i * i <= c; ++i){
			if(c % i == 0){
				v[id].push_back(i);
				if((long long)i * i != c)
					v[id].push_back(c / i);
			}
		}
		return id;
	}
	else
		return M[c];
}
int id1, id2;
class Procrastination {
public:
	long long findFinalAssignee(long long n) {
		long long now = 1;
		long long x = n;
		//int cnt = 0;
		while(now < n){
			//++cnt;
			id1 = check(x - 1), id2 = check(x);
			long long min1 = 1ll << 60, min2 = 1ll << 60;
			for(int i = 0; i < v[id1].size(); ++i)
				if(v[id1][i] > now)
					min1 = min(min1, v[id1][i]);
			for(int i = 0; i < v[id2].size(); ++i)
				if(v[id2][i] > now)
					min2 = min(min2, v[id2][i]);
			int type = -1;
			long long mn = 1ll << 60;
			if(min1 < x - 1 && min1 < mn){
				mn = min1;
				type = 1;
			}
			if(min2 < x && min2 < mn){
				mn = min2;
				type = 2;
			}
			if(type == -1)
				break;
			if(type == 1){
				--x;
				now = mn;
			}
			else{
				++x;
				now = mn;
			}
			//cout << x << endl;
		}
		//cout << cnt << endl;
		return x;
	}
};

Medium

题目大意：

求有多少张点数为$n$的无向图使得至多添加一条边之后存在一条欧拉回路。

输出答案对$10^9+7$取模的余数。

数据范围$n\leq{2000}$。

题解：

首先要求的无向图肯定是连通的。

如果直接就是欧拉回路的话，需要满足所有点的度数都是偶数。

如果需要添加一条边的话，则是有且仅有两个点的度数是奇数。

假设我们已经能够求出$g_n$表示$n$的点的所有点的度数都是偶数的连通图的个数。

那么答案就是$g_{n}\times(\frac{n(n-1)}{2}+1)$。

因为我们可以枚举哪两个点的度数为奇数，如果这两个点之间没有边则连上一条边，否则删除两个点之间的边。

我们再令$f_{n}$表示$n$个点所有点的度数均为偶数的无向图的个数。

这个可以直接计算，我们单独拿出某个点，于是剩下的无向图的个数为$2^{\frac{(n-1)(n-2)}{2}}$，对于我们得到的每个无向图，显然都会有偶数个度数为奇数的点。那么独立的那个点必须向无向图中所有度数为奇数的点连边，这能够保证独立的点的度数也为偶数，且连边的方法是唯一的。

于是我们就得到了$f_{n}=2^{\frac{(n-1)(n-2)}{2}}$。

显然我们可以再利用补集转化求$g_n$，只需要减去不连通的所有点度数均为偶数的图个数就行了。

对于某个点，枚举这个点所在连通块的大小，递推式是这样的：

$g_{n}=f_{n}-\sum_{i=1}^{n-1}\binom{n-1}{i-1}g_{i}f_{n-i}$

时间复杂度$O(n^2)$。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

typedef long long ll;
static const int mod = 1000000007;
void inc(int &x, int y){
	if((x += y) >= mod)
		x -= mod;
}
void dec(int &x, int y){
	if((x -= y) < 0)
		x += mod;
}

#define N 2010
int C[N][N], Pow[N * N];
int f[N], g[N];
class AlmostEulerianGraph {
public:
	int calculateGraphs(int n) {
		int i, j, k;
		for(Pow[0] = 1, i = 1; i <= n * n; ++i)
			Pow[i] = (Pow[i - 1] + Pow[i - 1]) % mod;
		for(C[0][0] = C[1][0] = C[1][1] = 1, i = 2; i <= n; ++i){
			C[i][0] = C[i][i] = 1;
			for(j = 1; j < i; ++j)
				inc(C[i][j] = C[i - 1][j], C[i - 1][j - 1]);
		}
		f[1] = g[1] = 1;
		for(i = 2; i <= n; ++i){
			f[i] = g[i] = Pow[(i - 1) * (i - 2) >> 1];
			for(j = 1; j < i; ++j)
				dec(g[i], (ll)g[j] * C[i - 1][j - 1] % mod * f[i - j] % mod);
		}
		int ans = (ll)g[n] * (1 + (n * (n - 1) >> 1)) % mod;
		return ans;
	}
};

hard

题目大意：

给定一个边带权的无向完全图，以$0$号点为根进行Prim算法求最大生成树，当边权相同时随便选一个点加入当前集合。

对于每一个点，你要求出这个点在Prim算法的所有可能情况中最早第几个被加入当前集合。

数据范围$n\leq{50}$，边权范围$0\leq{w}<10$。

题解：

考虑最终形成的最大生成树的形态。

我们可以考虑，先一并加入所有权值为$9$的边，再一并加入所有权值为$8$的边，。。。，依此类推。

那么我们这样想，假设我们要求的某个点$i$通过权值为$j$的边加入了集合，那么必然有所有权值$>j$的边对于连通性做出的贡献都已经被考虑过了。

不妨利用动态规划处理集合之间的合并：

对于每个根$i$，以及每个权值$j$，我们处理出只考虑$>j$的权值的$i$所在的最大连通块，大小为$cnt$。

那么对于这个连通块所有相邻点$k$，如果边权恰为$j$，点$k$就能在最多$cnt$个点之后加入$i$所在的集合。

我们可以新建一张有向图，连接$(i,k,cnt)$，于是这个问题转化为了一个图论中的最短路问题。

利用Folyd进行处理。

时间复杂度$O(wn^3)$。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;


void mini(int &x, int y){
	if(x > y)
		x = y;
}

#define N 50
bool vis[N];
int f[N][N], w[N][N];
int cnt;
void dfs(int x, int y, int n){
	++cnt;
	vis[x] = 1;
	for(int j = 0; j < n; ++j){
		if(j != x && !vis[j] && w[x][j] > y)
			dfs(j, y, n);
	}
}

class Tdetective {
public:
	int reveal(vector <string> s) {
		int n = s.size();
		int i, j, k, _k;
		for(i = 0; i < n; ++i)
			for(j = 0; j < n; ++j)
				w[i][j] = s[i][j] - '0';
		memset(f, 0x1f, sizeof f);
		for(i = 0; i < n; ++i){
			for(j = 0; j < 10; ++j){
				memset(vis, 0, sizeof vis);
				cnt = 0;
				dfs(i, j, n);
				for(k = 0; k < n; ++k){
					if(!vis[k])
						continue;
					for(_k = 0; _k < n; ++_k)
						if(!vis[_k] && w[k][_k] == j)
							mini(f[i][_k], cnt);
				}
			}
		}
		for(k = 0; k < n; ++k)
			for(i = 0; i < n; ++i)
				for(j = 0; j < n; ++j)
					mini(f[i][j], f[i][k] + f[k][j]);
		
		int ans = 0;
		for(i = 1; i < n; ++i)
			ans += i * f[0][i];
		
		return ans;
	}
};