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;
}
评论 (0)
