Noip2016 校内训练 Round 1
1. 信息传递
AKP和WWF住在河的两岸,他们在河的两岸都建了n座房子,而且恰巧都是正对着建的,如下所示:
AKP: 房子1 房子2 房子3 房子4
=================河===============流==============
WWF: 房子3 房子2 房子4 房子1
他们对于房子的编号不一样,可能AKP的房子1对应着WWF的房子3,等等,但是每个人的房子编号都是1~n的一个排列。为了方便,我们假定他们房子间隔相同。
他们在河中铺下了光缆来连接各自相同编号的房子,进行信息传递。为了信息传递的方便,他们需要知道:从总共n条光缆中选出最多的光缆,使得这几条光缆之间两两相交。
【题解】
转化为最长下降子序列后用$O(nlogn)$的方法解决。
# include <stdio.h> # include <algorithm> // # include <bits/stdc++.h> using namespace std; const int M = 200010; int n; int A[M], B[M]; int ta[M], tb[M], a[M], f[M], c[M]; int main() { freopen("message.in", "r", stdin); freopen("message.out", "w", stdout); scanf("%d", &n); for (int i=1; i<=n; ++i) scanf("%d", &A[i]), ta[A[i]] = i; for (int i=1; i<=n; ++i) scanf("%d", &B[i]), tb[B[i]] = i; for (int i=1; i<=n; ++i) a[i] = tb[A[i]]; int ans; f[1] = 1, ans = 1; c[1] = 1; a[n+1] = -2147483647; for (int i=2; i<=n; ++i) c[i] = n+1; for (int i=2; i<=n; ++i) { int l=1, r=ans, anst = 0; while(1) { if(r-l<=3) { for (int j=r; j>=l; --j) if (a[c[j]] > a[i]) { anst = c[j]; break; } break; } int mid = l+r>>1; if(a[c[mid]] > a[i]) l = mid; else r = mid; } f[i] = f[anst] + 1; if(a[c[f[i]]] < a[i]) c[f[i]] = i; ans = max(ans, f[i]); } printf("%d\n", ans); return 0; }
2. 树上问题
AKP觉得WWF对树上的问题不大熟悉,于是向他提出了一个树上的问题。
首先AKP画出了一个n个节点的有根树(其中根为1号点),他对于其中一些节点很喜爱,于是就在这个节点上标记一下,当然过一会儿他可能就忘了他标记过的节点,所以一个节点可以被重复标记。在最开始,有且仅有1号节点上有标记。
AKP有q次操作,操作类型有两种:
1. 选取一个点,把它标记一下。
2. 选取一个点,询问它的祖先中(包括自己),离它最近的被标记过的节点是哪一个。
现在,AKP要请你对于每一个2操作,输出你计算出的答案。
$n,q \leq 1500000$
【题解】
离线询问逆序做,并查集维护即可。
# include <stdio.h> // # include <bits/stdc++.h> using namespace std; const int N = 2000010; int n, q; int opt[N], x[N]; int fa[N], f[N]; int tot = 0, next[N<<1], head[N], to[N<<1], tag[N]; int ans[N], an = 0; int read() { int n = 0; char a = getchar(); bool flag = 0; while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); } while(a >= '0' && a <= '9') n = n * 10 + a - '0',a = getchar(); if(flag) n = -n; return n; } inline int getf(int x) { return x == fa[x] ? x : fa[x] = getf(fa[x]); } inline void add(int u, int v) { ++tot; next[tot] = head[u]; head[u] = tot; to[tot] = v; } inline void dfs(int x, int father=0) { if(father) f[x] = father; for (int i=head[x]; i; i=next[i]) if(to[i] != father) dfs(to[i], x); } int main() { freopen("tree.in", "r", stdin); freopen("tree.out", "w", stdout); n = read(), q = read(); for (int i=1, u, v; i<n; ++i) { u = read(), v = read(); add(u, v); add(v, u); } dfs(1); tag[1] = 1; for (int i=1; i<=n; ++i) fa[i] = i; for (int i=q; i>=1; --i) { opt[i] = read(), x[i] = read(); if(opt[i] == 1) tag[x[i]]++; } for (int i=2; i<=n; ++i) { if(tag[i] != 0) continue; int fu = getf(i), fv = getf(f[i]); if(fu != fv) fa[fu] = fv; } for (int i=1; i<=q; ++i) { if(opt[i] == 1) { tag[x[i]] --; if(tag[x[i]] == 0) { int fu = getf(x[i]), fv = getf(f[x[i]]); if(fu != fv) fa[fu] = fv; } } else { ans[++an] = getf(x[i]); } } for (int i=an; i>=1; --i) printf("%d\n", ans[i]); return 0; }
3. 对抗比赛
AKP和WWF要进行一场对抗比赛。
AKP有n名记者,WWF也有n名记者,他们要比赛谁跑得快。AKP的每名记者有速度值,WWF的每名记者有速度值。记者们一共进行n轮比赛,每轮AKP选出一名记者,WWF选出一名记者进行比赛,速度值大的记者所在的一方获得一轮的胜利,胜利的一方获得1分,失败的一方不获得分数,一名记者只能比赛一次。在n轮比赛过后,AKP想知道,如果他和WWF的分差(取绝对值)在之间的话,那么一共有多少种方案?由于AKP好学,所以他一共问了q次问题。
方案数对于998244353取模。
$n,q \leq 3000$。
【题解】
首先,$f_{i,j}$表示到了第i个,AKP一定得了j分(其他可得可不得)的方案。
那么令$g_i$表示AKP得到至少i分的方案,$g_i = f_{n,i} \times (n-i)!$
令$h_i$表示AKP恰好得到$i$分的方案,$h_i = g_i - C_{j}^{i} \times \sum_{j>i}h_j$。
逆推即可。复杂度$O(n^2+qn)$。
# include <stdio.h> # include <algorithm> using namespace std; const int M = 3010; int n, a[M], b[M], q, f[M][M], hv[M], g[M], h[M]; const int mod = 998244353; int fac[M], inv[M]; inline int pwr(int x, int y) { int ret = 1; while(y) { if(y&1) ret = 1ll * ret*x % mod; x = 1ll * x*x % mod; y = y/2; } return ret; } inline void cadd(int &a, int b) { a = (a+b) % mod; a = (a+mod) % mod; } inline void csub(int &a, int b) { b = -b; b = (b+mod) % mod; cadd(a, b); } inline int C(int n, int k) { return 1ll * fac[n] * inv[k] % mod * inv[n-k] % mod; } int main() { freopen("match.in", "r", stdin); freopen("match.out", "w", stdout); scanf("%d%d", &n, &q); fac[0] = 1; for (int i=1; i<=n; ++i) fac[i] = 1ll * fac[i-1] * i % mod; for (int i=0; i<=n; ++i) inv[i] = pwr(fac[i], mod-2); for (int i=1; i<=n; ++i) scanf("%d", &a[i]); for (int i=1; i<=n; ++i) scanf("%d", &b[i]); sort(a+1, a+n+1); sort(b+1, b+n+1); for (int i=1; i<=n; ++i) hv[i] = upper_bound(b+1, b+n+1, a[i]) - b - 1; f[0][0] = 1; for (int i=1; i<=n; ++i) for (int j=0; j<=i; ++j) { f[i][j] = f[i-1][j]; if(j!=0 && hv[i]-(j-1)>0) cadd(f[i][j], 1ll * f[i-1][j-1] * (hv[i]-(j-1)) % mod); } for (int i=0; i<=n; ++i) g[i] = 1ll * f[n][i] * fac[n-i] % mod; //for (int i=0; i<=n; ++i) cerr<<i<<":"<<f[n][i]<<"\n"; for (int i=n; i>=0; --i) { h[i] = g[i]; for (int j=i+1; j<=n; ++j) csub(h[i], 1ll * h[j] * C(j, i) % mod); } for (int i=1, L, R; i<=q; ++i) { int ans = 0; scanf("%d%d", &L, &R); /* for (int j=L; j<=R; ++j) { if((n+j)&1) continue; int A = (n+j)/2, B = (n-j)/2; if(A!=B) cadd(ans, (1ll * h[A] + h[B]) % mod); else cadd(ans, 1ll * h[A] % mod); } */ for (int j=0; j<=n; ++j) { int k = n-j; if(abs(j-k)>=L && abs(j-k)<=R) cadd(ans, h[j]); } printf("%d\n", ans); } return 0;
}