题目链接：2018-2019 ACM-ICPC, Asia Xuzhou Regional Contest
A. Rikka with Minimum Spanning Trees
题意：
给出一个随机算法生成边的信息，然后求最小生成树的个数以及其权值的乘积。
题解：
这个随机算法有点神奇...基本不会有重复的边出现，所以其实只用求MST就行了。当然，其实通过样例也可以猜出来，样例生成了1W条边，但最后的answer就为最小生成树权值，所以可以直接根据这个来猜一发，注意一下判断是否连通就行了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5+;
const int MAXM = 3e5+;
const int MOD = 1e9+;
const double eps = 1e-;
typedef unsigned long long ull;
#define rep(i,a,b) for(int i = (a);i<=(b);i++)
struct Edge{
int u,v;
ull w;
bool operator <(const Edge &ds)const{
return w<ds.w;
}
}e[MAXM];
int n,m,fa[MAXN];
int t,tot;
//double G[MAXN][MAXN];
ull k1,k2;
ull ans=;
ull xorShift128Plus(){
ull k3=k1,k4=k2;
k1=k4;
k3 ^= k3<<;
k2 = k3 ^ k4 ^ (k3 >>) ^(k4 >>);
return k2 +k4;
}
void gen(){
cin >>n >>m >>k1 >>k2;
int u,v;
ull w;
tot = ans = ;
rep(i,,m){
u = xorShift128Plus()%n+;
v = xorShift128Plus()%n+;
w = xorShift128Plus();
if(u == v) continue ;
//cout <<u<<' ' <<v<<' ' <<w <<'\n';
e[++tot] = {u,v,w};
}
}
int find(int x){
return x==fa[x]?x:fa[x] = find(fa[x]);
}
bool kruskal(){
int ss=;
sort(e+,e++tot);
rep(i,,n)fa[i] =i;
rep(i,,tot){
int a = find(e[i].u),b =find(e[i].v);
if(a!=b){
fa[a] =b;
ans = (ans +e[i].w%MOD)%MOD;
ss++;
}
}
return ss==n-;
}
int main() {
ios::sync_with_stdio(false);cin.tie() ;
cin >>t;
while(t--){
gen();
if(!kruskal()){
cout << <<'\n';
}else{
cout << ans <<'\n';
}
}
return ;
}
G. Rikka with Intersections of Paths
题意：
树上给出若干条简单路径，问有多少选k条路径的方案，满足这些路径的交至少有一个点。
题解：
考虑求出LCA，因为树上简单路径至少存在一个交点为至少一条路径的两端点的LCA，同时可以利用树上差分求出有多少条路径经过当前点。
之后计算贡献就行了，但是这里直接计算C(cnt, k)会有重复计算的，我们这里可以考虑刚才关于LCA的性质，求出每个点为多少条路径端点的LCA，个数记为pi，那么最后答案就是C(cnt,k) - C(cnt - pi,k)，此时选出的路径中，至少有一条路径的两端点的LCA为当前点，此时就不会重复计算了。因为一条路径的LCA只有一个，我们只会计算经过LCA时的贡献。
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + , MOD = 1e9 + ;
int T, n, m, k;
struct Edge{
int u,v,next;
}e[N << ];
int head[N],tot;
void adde(int u, int v) {
e[tot].v = v;
e[tot].next = head[u] ;
head[u] = tot++ ;
}
int deep[N], st[N][], sum[N], cnt[N];
ll fac[N], inv[N];
void dfs(int u, int d, int fa) {
st[u][] = fa;
deep[u] = d;
for(int i = head[u]; i != -; i = e[i].next) {
int v = e[i].v;
if(v == fa) continue ;
dfs(v, d + , u);
}
}
ll qp(ll a, ll b) {
ll ans = ;
while(b) {
if(b & ) ans = ans * a % MOD;
a = a * a % MOD;
b >>= ;
}
return ans ;
}
void init() {
for(int i = ; i <= ; i++)
for(int j = ; j <= n ; j++)
st[j][i] = st[st[j][i - ]][i - ];
}
int LCA(int x, int y) {
if(deep[y] > deep[x]) swap(x , y) ;
while(deep[x] != deep[y]) {
int d = deep[x] - deep[y] ;
for(int i = ; i <= ; i++) {
if(d >> i & ) x = st[x][i] ;
}
}
if(x == y) return x ;
for(int i = ; i >= ; i--) {
if(st[x][i] != st[y][i]) {
x = st[x][i] ;
y = st[y][i] ;
}
}
return st[x][] ;
}
void pre(int u, int fa) {
for(int i = head[u] ; i != -; i = e[i].next) {
int v = e[i].v;
if(v == fa) continue ;
pre(v , u);
sum[u] += sum[v] ;
}
}
ll C(ll a ,ll b) {
if(b == || a < b) return ;
return fac[a] * inv[b] % MOD * inv[a - b] % MOD;
}
ll calc(ll x) {
ll ans = C(sum[x], k);
ans = ((ans - C(sum[x] - cnt[x], k) % MOD ) % MOD + MOD ) % MOD;
return ans ;
}
int main() {
ios::sync_with_stdio(false);cin.tie();
fac[] = ;
inv[] = ;
for(int i = ; i < N; i++) {
fac[i] = fac[i - ] * i % MOD;
inv[i] = qp(fac[i] , MOD - ) ;
}
cin >> T;
while(T--) {
memset(head,-,sizeof(head)); tot = ;
cin >> n >> m >> k ;
for(int i = ; i < n ; i++) {
int u, v;
cin >> u >> v;
adde(u, v);adde(v, u);
}
dfs(, , );
init() ;
for(int i = ; i <= m ;i++) {
int u, v;
cin >> u >> v ;
int x = LCA(u , v);
sum[u]++;sum[v]++;
sum[x]--;sum[st[x][]]--;
cnt[x]++;
}
pre(, ) ;
ll ans = ;
for(int i = ; i <= n; i++) {
ans = (ans + calc(i)) % MOD ;
}
cout << ans << '\n' ;
for(int i = ; i <= n ; i++) deep[i] = sum[i] = cnt[i] = ;
}
return ;
}
H. Rikka with A Long Colour Palette
题意：
给出n个区间，k个颜色，现在给区间染色，问怎么染色能使得覆盖有所有颜色的区间长度最大。
题解：
染色过程考虑贪心。我们先按照区间左端点排序，然后依次涂颜色，颜色涂完了之后该怎么涂呢？假设当前左端点为L，并且在之前的区间中，有Ri,Rj,Rk满足Ri < L < Rj < Rk，那么此时我们涂Ri的颜色肯定是最优的；如果不存在一个Ri，满足L < Ri，这时我们也只需要涂处于最左端的Ri，因为这样可以尽可能地增多所有颜色覆盖的区间长度。
最后就考虑如果计算答案了，将所有点排序后记录左端点为1，右端点为-1，累计前缀和，当和大于等于k时更新答案即可。
代码如下：
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 2e5 + ;
int T;
int n, k, cnt;
pair<pii,int> a[N << ];
int col[N], has[N], answer[N];
struct Node {
int l, r, id ;
bool operator < (const Node &A) const {
if(l == A.l) return r < A.r;
return l < A.l;
}
}p[N];
int main() {
ios::sync_with_stdio(false);cin.tie();
cin >> T;
while (T--) {
cin >> n >> k;
cnt = ;
for(int i = ; i <= n ; i++) {
int l, r;
cin >> l >> r;
p[i] = Node{l,r,i};
}
if(n < k) {
cout << << '\n' ;
for(int i = ; i < n; i++)
cout << << ' ' ;
cout << << '\n' ;
continue ;
}
sort(p + , p + n + );
priority_queue <pii> q;
for(int i = ; i <= k ; i++) {
q.push(mp(, i)) ;
}
for(int i = ; i <= n ; i++) {
int now = q.top().second;q.pop();
answer[p[i].id] = col[i] = now;
q.push(mp(-p[i].r,now)) ;
}
for(int i = ; i <= n ;i++) {
a[++cnt] = mp(mp(p[i].l,col[i]),) ;
a[++cnt] = mp(mp(p[i].r,col[i]),-) ;
}
sort(a + , a + cnt + ) ;
int ans = , cur = ;
for(int i = ; i <= cnt ; i++) {
if(has[a[i].first.second]) cur--;
has[a[i].first.second] += a[i].second ;
if(has[a[i].first.second]) cur++;
if(cur >= k )
ans += a[i + ].first.first - a[i].first.first;
}
cout << ans << '\n' ;
for(int i = ; i < n ; i++) cout << answer[i] << ' ';
cout << answer[n] << '\n' ;
for(int i = ; i <= k ; i++) has[i] = ;
}
return ;
}
I. Rikka with Sorting Networks
题意：
给出n个数，有k个排序器，每个排序器会使得au < av，即让他们的位置相对有序，问有多少个排列，最后通过这k个排序器后，形成的序列最长上升子序列至少为n - 1。
题解：
满足条件的最长上升子序列个数为(n - 1) ^ 2 + 1个，由于数据范围很小，我们直接构造出来爆搜求解即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = ;
int a[N], b[N] ;
int n, k, T, mod;
int from[N], to[N] ;
int ans;
void dfs(int i, int f) {
if(i == ) {
ans += f;
if(ans >= mod) ans -= mod;
return ;
}
if(a[from[i]] < a[to[i]]) {
dfs(i - , f) ;
swap(a[from[i]], a[to[i]]) ;
dfs(i - , f) ;
swap(a[from[i]], a[to[i]]) ;
}
}
int main() {
ios::sync_with_stdio(false);cin.tie();
cin >> T;
while(T--) {
cin >> n >> k >> mod;
for(int i = ; i <= k ; ++i) cin >> from[i] >> to[i] ;
for(int i = ; i <= n ; ++i) a[i] = i ;
ans = ;
dfs(k, ) ;
for(int i = ; i < n ; ++i) {
swap(a[i], a[i + ]);
dfs(k, -);
swap(a[i], a[i + ]);
}
for(int take = ; take <= n ; ++take) {
for(int i = ; i <= n ; ++i) {
if(i == take) continue ;
int cur = ;
for(int j = ; j <= n ; ++j) {
if(cur == take - ) cur++;
if(i == j) a[j] = take ;
else a[j] = ++cur;
}
dfs(k , );
}
}
cout << ans << '\n';
} return ;
}