CF553
A
简单组合，略。
B
Kyoya and Permutation
定义一个长度为\(n\)的排列为仅由\(1..n\)的元素组成，且每个元素恰好只出现\(1\)次的序列。我们称数值\(i\ (1\leq i \leq |p|)\)在排列\(p\)中的映射为\(p_i\)。
Kyota Ootori 刚刚学习了排列的循环表示法。定义排列\(p\)上的一个循环是一个由\(1..n\)的一部分元素组成的序列，并且在这个序列中，任意一个元素在\(p\)中的映射等于下一个元素（特别地，最后一个元素的映射等于第一个元素）。
显然，我们可以将一个排列划分成多个循环。例如\(p=[4,1,6,2,5,3]\)可以被划分成\([1,4,2]\)，\([3,6]\)和\([5]\)三个循环。我们在每个循环周围加上括号，然后将它们连起来，得到的就是这个排列的循环表示法。例如\([4,1,6,2,5,3]\)的一种循环表示法是\((1\ 4\ 2)(3\ 6)(5)\)。
对于一个长度不为\(1\)的排列，其循环表示法不是唯一的。为了使问题得到统一，我们定义一种标准循环表示法。即，对于每个循环，都将其最大值放在最前面，然后将这若干个循环按照最大值从小到大排列。这样，\([4,1,6,2,5,3]\)的标准循环表示法就是\((4\ 2\ 1)(5)(6\ 3)\)。
现在，Kyota 发现，如果我们去掉一个排列的标准循环表示法中的括号，我们将得到另一个排列。比如，由\([4,1,6,2,5,3]\)可以得到\([4,2,1,5,6,3]\)。
他还发现，将某些排列的标准循环表示法中的括号去除后，得到的排列和原排列是一样的。我们称这种排列为“好的排列”。他按字典序递增的顺序在纸上写下了长度为\(n\)的所有好的排列，结果他的朋友 Tamaki Suoh 把这个列表搞丢了。Kyota 现在想要恢复这个列表。告诉你排列的长度\(n\)以及\(k\)，请你输出字典序从小到大第\(k\)个好的排列。
Solution
手玩一下就能够发现一个合法的排列一定是形如将一个 \([1,2,3,\dots ,n]\) 通过若干个不相交长度为 \(2\) 的区间翻转得到的。设 \(f_i\) 表示长度 \(i\) 的合法排列个数。
一个斐波那契数列，通过搜索判判就做完了。
Code
# include <bits/stdc++.h>
using namespace std;
# define int long long
const int N = 55;
int n , k , f[N] , s[N];
void work(int l , int r , int k)
{
int len = r - l + 1;
if(!len) return ;
if(len == 1) return s[l] = l , void();
if(k <= f[len])
{
s[l] = l;
s[l + 1] = l + 1;
work(l + 1 , r , k);
}
else
{
s[l] = l + 1;
s[l + 1] = l;
work(l + 2 , r , k - f[len]);
}
}
signed main()
{
cin >> n >> k;
f[1] = f[2] = 1;
for(int i = 3; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
work(1 , n , k);
for(int i = 1; i <= n; i++) cout << s[i] << ' ';
return 0;
}
- 这个迷人的数据范围一度让我以为是错的，但是数据范围只是因为斐波那契数列的大小。
C
Description
给出\(n \leq 10^5\)个点，要求构造合法的完全图，已经给出了一些边。
边有爱边和恨边，其中任意三个点，连成的边合法的组合有爱爱爱，爱恨恨。
问符合要求的完全图的数量，对\(1e9+7\)取模。
Solution
用 \((x,y)\) 表示一条连接 \(x,y\) 的边。
如果给出了一条 \((x,y)=1\)，那么 \(x,y\) 连接其他点的颜色一定是相同的；反之颜色一定不同。我们可以用扩展域并查集来维护这个东西。
我们对于每个点赋一个权值 \(w_i\)，那么 \((x,y)=w_x \oplus w_y\)，那么一个连通块内的点的权值是一样的。每个连通块有两个取值。最后还需要除二。
Code
# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5 , mod = 1e9 + 7;
int n , m , fa[N] , cnt , vis[N];
int Find(int x) {return x == fa[x] ? x : fa[x] = Find(fa[x]);}
int ksm(int a , int b) {int res = 1; for(; b; b >>= 1 , a = 1ll * a * a % mod) if(b & 1) res = 1ll * res * a % mod; return res;}
int main()
{
cin >> n >> m;
cnt = n;
for(int i = 1; i <= 2 * n; i++) fa[i] = i;
for(int i = 1 , u , v , w; i <= m; i++)
{
cin >> u >> v >> w;
if(w)
{
if(Find(u) == Find(v + n)) return cout << 0 , 0;
if(Find(u) != Find(v)) cnt--;
fa[Find(u)] = Find(v);
fa[Find(u + n)] = Find(v + n);
}
else
{
if(Find(u) == Find(v)) return cout << 0 , 0;
if(Find(u) != Find(v + n)) cnt--;
fa[Find(u)] = Find(v + n);
fa[Find(v)] = Find(u + n);
}
}
cout << ksm(2 , cnt - 1);
return 0;
}
D
Description
有 \(n \leq 10^5\) 座城市由 \(m \leq 10^5\) 条双向道路连接。现在所有的城市都已经被敌人攻陷了，敌人还在其中 \(k\) 座城市中建起了堡垒，这些城市无法被攻克；我们需要从敌人手中夺回一些城市，使得所有夺回的城市都尽可能安全，即最小的安全度尽可能大。定义一座城市的安全度为它的所有邻居中由我方控制的城市数量除以它的所有邻居数量。
Solution
显然二分，考虑怎么 check()。
先把所有能选的城市都选中，BFS 一步步删不合法的。
Code
# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const double eps = 1e-8;
int n , m , k , a[N] , vis[N] , rem[N];
vector< int > e[N];
bool check(double mid)
{
for(int i = 1; i <= n; i++) vis[i] = 1;
for(int i = 1; i <= k; i++) vis[a[i]] = 0;
queue< int > Q;
for(int i = 1; i <= n; i++) if(vis[i]) Q.push(i) , rem[i] = 1;
while(!Q.empty())
{
int u = Q.front(); Q.pop();
rem[u] = 0;
int cnt = 0;
for(int v : e[u]) if(vis[v]) cnt++;
if(cnt * 1.0 / e[u].size() < mid) vis[u] = 0;
if(!vis[u])
{
for(int v : e[u]) if(vis[v] && !rem[v]) Q.push(v) , rem[v] = 1;
}
}
for(int i = 1; i <= n; i++) if(vis[i]) return 1;
return 0;
}
int main()
{
cin >> n >> m >> k;
for(int i = 1; i <= k; i++) cin >> a[i];
for(int i = 1 , u , v; i <= m; i++)
{
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
double l = 0 , r = 1;
while(r - l > eps)
{
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
check(l);
int cnt = 0;
for(int i = 1; i <= n; i++) if(vis[i]) cnt++;
cout << cnt << '\n';
for(int i = 1; i <= n; i++) if(vis[i]) cout << i << ' ';
return 0;
}