A.Ekiden Race
题目描述：
有 \(n\) 个人参加了往返赛跑，每个人有一个编号 \(1\) 到 \(n\)。已知以下信息：
- 如果按照往路的成绩排序，那么任何两个人的成绩都不相同。同时第 \(i\) 个人在往路中排名第 \(i\)。
- 如果按照往返的成绩排序，那么任何两个人的成绩都不相同。同时第 \(i\) 个人在往返中排名第 \(p_i\)。
- 如果復路的成绩最快，那么获得復路奖的人是復路成绩最快的人。
请计算有多少人可能得到了復路奖项。
有 \(T\) 个测试用例，请对于每个测试用例输出答案。
(翻译者注：往路指来回的第一段路程，復路指来回的第二段路程。)
\(2 \le n \le 10^3\)
题目分析：
如果 \(a\) 在第一段路快于 \(b\)，而经过了第二段路之后 \(a\) 慢于 \(b\)，则必然有 \(a\) 第二段路慢于 \(b\)。
否则无法确定 \(a,b\) 的第二段路的快慢，也就是可以直接认为 \(a,b\) 都有可能。
直接这样判就可以了。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int a[N];
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T;scanf("%d",&T);
while(T--){
int n;scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
int ans = n+1;
int tot = 0;
for(int i=n; i>=1; i--){
if(a[i] < ans) ++tot;
ans = min(ans,a[i]);
}
printf("%d\n",tot);
}
return 0;
}
B.Insertion Sort 2
题目描述：
给定 \(1,2,...,N\) 的排列 \(P=(P_1,P_2,...,P_N)\)。
最多进行 \(2\times 10^3\) 次操作，每次操作满足 \(1\le i\le N-1, 0\le j\le N-2\)，选取整数 \(i,j\)，从 \(P\) 中取出 \((P_i,P_{i+1})\) 得到序列 \(Q=(Q_1,Q_2,...,Q_{N-2})\)，则将 \(P\) 中 \((P_i,P_{i+1})\) 替换成序列 \(Q\) 的 \(j\) 与 \(j+1\) 位置上的数，得到新的排列 \(P'\)。
判断是否能够通过这样的操作使 \(P\) 变成升序排列，如果可以，给出操作步骤。
$ 2\ \leq\ N\ \leq\ 10^3 $
题目分析：
一个显然的想法就是一个个数地确定，也就是先把 \(1\) 通过操作放到第一个，然后 \(2\) 放到第二个然后依次类推。
但是现在的有的一个问题就是如果我们现在要放 \(x\)，但是 \(x\) 是序列中的最后一个数就做不了这个操作了，可是我们可以做类似如下的操作：\((n-2,n-1,n)\) \(\to\) \((n-1,n,n-2)\) 这样 \(P_n\) 就不在最后了，我们就可以操作它了。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+5;
vector<pair<int,int> > v;
int n,a[N],b[N];
void solve(int pos1,int pos2){
if(!(1 <= pos1 && pos1 <= n-1)) return;
if(!(0 <= pos2 && pos2 <= n-2)) return;
v.push_back({pos1,pos2});
int tot = 0;
if(tot == pos2) b[++tot] = a[pos1],b[++tot] = a[pos1+1];
for(int i=1; i<=n; i++){
if(i == pos1 || i == pos1 + 1) continue;
b[++tot] = a[i];
if(tot == pos2) b[++tot] = a[pos1],b[++tot] = a[pos1+1];
}
for(int i=1; i<=n; i++) a[i] = b[i];
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
for(int i=1; i<=n; i++){
if(a[i] == i) continue;
if(a[n] == i) solve(n-1,n-3);
int pos = i;
for(int j=i+1; j<=n; j++){
if(a[j] == i) pos = j;
}
if(pos > i) solve(pos,i-1);
}
if(a[n] != n) printf("No\n");
else{
printf("Yes\n");
printf("%d\n",(int)v.size());
for(auto i : v) printf("%d %d\n",i.first,i.second);
}
return 0;
}
C.Mex Game on Tree
题目描述：
有一棵 \(n\) 个节点且以 \(1\) 为根的数。
每个节点上有一个数表示颜色。
- 如果为 \(-1\)，表示没有填颜色。
- 否则，表示填的颜色。
\(\text{Alice}\) 和 \(\text{Bob}\) 轮流对没填颜色的节点填上 \(0\) 到 \(n\)（\(\text{Alice}\) 先手）。
填完后，如果某个点和它的子树颜色的 \(\mathrm{mex}\) 为 \(k\)，\(\text{Alice}\) 胜，否则为 \(\text{Bob}\)。
$ 2\ \leq\ N\ \leq\ 10^3 $
题目分析：
BoB 的策略十分显然，就是填 \(k\)，所以只要让 Bob 走一步，那么 Alice 之前的所有布局就全没用了。
因为是考虑某一个子树，所以不妨对每一棵子树都求一下是不是可以使得它的 \(\mathrm{mex}\) 为 \(k\)。
因为我们对每一棵子树都考虑了，所以若 Alice 走两步可以让某个子树变成合法，要么就是那棵子树走一步就可以合法，要么就是受到前一步的影响，而第二种情况显然 Bob 可以直接堵掉 Alice 的第二步，就结束了。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
struct edge{
int nxt,to;
edge(){}
edge(int _nxt,int _to){
nxt = _nxt,to = _to;
}
}e[2 * N];
int n,k,cnt,head[N],a[N];
bool vis[N],ans;
vector<int> v;
void add_edge(int from,int to){
e[++cnt] = edge(head[from],to);
head[from] = cnt;
}
void get_val(int now,int fath){
v.push_back(a[now]);
for(int i=head[now]; i; i=e[i].nxt){
int to = e[i].to;
if(to == fath) continue;
get_val(to,now);
}
}
void dfs(int now,int fath){
for(int i=head[now]; i; i=e[i].nxt){
int to = e[i].to;
if(to == fath) continue;
dfs(to,now);
}
get_val(now,fath);
int flag = 0;
for(auto i : v){
if(i == -1){
flag++;
continue;
}
vis[i] = true;
}
int tmp = 0;
while(vis[tmp]) ++tmp;
if(flag && tmp < k){
++tmp;
while(vis[tmp]) ++tmp;
}
if(tmp == k && flag <= 1) ans = true;
for(auto i : v){
if(i != -1) vis[i] = false;
}
v.clear();
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
for(int i=2; i<=n; i++){
int fa;scanf("%d",&fa);
add_edge(fa,i);add_edge(i,fa);
}
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
dfs(1,0);
if(ans) printf("Alice\n");
else printf("Bob\n");
cnt = 0;
for(int i=1; i<=n; i++) head[i] = 0;
ans = false;
}
return 0;
}
D.Smallest Vertices
题目描述：
在本问题中，当我们提到有根有向树时，我们指的是所有边都指向从根到叶子的有根树。
给定一个使得其总和为 \(N-1\) 的非负整数序列 \(d=(d_1,d_2,\ldots,d_N)\)。
对于带编号从 \(1\) 到 \(N\) 的顶点，假设 \(1\) 是根，我们将其点度数定义为 \(d_i\)。
我们称满足以下条件的根付有向树为好树：
- 点 \(i\) 的出度是 \(d_i\)。
此外，对于好树的顶点 \(v\)，定义 \(f(v)\) 为“包含顶点 \(v\) 的子树中的顶点（包括 \(v\)）的顶点编号的最小值”。我们将满足 \(f(v)=v\) 的顶点称为好顶点。
求好树中所有好顶点的总数，将其对 \(998244353\) 取模后的余数。
- $ 2\ \leq\ N\ \leq\ 500 $
- $ 0\ \leq\ d_i\ \leq\ N-1 $
- $ d_1\ \geq\ 1 $
- $ \sum_{i=1}^N\ d_i\ =\ N-1 $
题目分析：
显然可以考虑对于每一个点作为好节点的方案数求和就是答案。
若 \(v = 1\) 或 \(d_v = 0\)，则任意一个好树都是合法的，这个时候根据 \(prufer\) 序列，显然方案数就是：
其中 \(d_{i,j}\) 表示以 \(i\) 为根的时候 \(j\) 的度数。
否则的话，考虑以 \(v\) 为根的子树只能包含 \([v,n]\) 这些点，但是好像除了这个就发现不了什么式子了，就不大能做。
所以不妨设 \(S\) 为 \(v\) 子树内的点的点集，看看这个时候的方案数是什么：
第一个式子就是考虑 \(v\) 的子树的方案数，乘以其余点构成一棵树的方案数，其中在其余点构成的树中 \(v\) 所在子树充当一个叶子。
第二个式子就是考虑如下的事实：
所以带入就得到了第二个式子。
注意为了可以组成一棵树，一个隐形的限制就是：\(\sum\limits_{u \in S} d_u = |S| - 1\)。
所以此时 \(dp\) 状态就相当显然了，\(dp[i][j][k]\) 表示大于等于 \(i\) 的点，选择了 \(j\) 个点，\(d_u\) 之和为 \(k\) 的方案数。
这样就可以直接统计方案数，然后乘以上面的系数就可以得到答案。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505;
const int MOD = 998244353;
int f[N][N][N],d[N],fac[N],inv[N];
int power(int a,int b){
int res = 1;
while(b){
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
void add(int &a,int b){
a = (a + b) % MOD;
}
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n;scanf("%lld",&n);
fac[0] = 1;
for(int i=1; i<=n; i++) fac[i] = fac[i-1] * i % MOD;
inv[n] = power(fac[n],MOD-2);
for(int i=n-1; i>=0; i--) inv[i] = inv[i+1] * (i+1) % MOD;
for(int i=1; i<=n; i++) scanf("%lld",&d[i]);
f[n+1][0][0] = 1;
for(int i=n; i>=1; i--){
for(int j=0; j<=n; j++){
for(int k=0; k<=n; k++){
add(f[i][j][k],f[i+1][j][k]);
if(j-d[i]>=0&&k-1>=0) add(f[i][j][k],f[i+1][j-d[i]][k-1]);
}
}
}
int tmp = fac[n-2];
for(int i=1; i<=n; i++){
if(i == 1) tmp = tmp * inv[d[i]-1] % MOD;
else tmp = tmp * inv[d[i]] % MOD;
}
int mul = 1,ans = 0;
for(int i=1; i<=n; i++) mul = mul * inv[d[i]] % MOD;
for(int i=1; i<=n; i++){ //统计 i 为好节点的贡献
if(i == 1 || d[i] == 0){
add(ans,tmp);
// printf("%lld %lld\n",i,tmp);
continue;
}
for(int j=1; j<=n; j++){ //枚举 [i,n] 选择了多少个节点
int sum_d = j - 1;
if(sum_d-d[i]>=0 && j-1>=0 && j-2>=0 && n-j-1>=0)
add(ans,f[i+1][sum_d-d[i]][j-1] * d[1] %MOD* d[i] %MOD* fac[j-2] %MOD* fac[n-j-1]%MOD * mul%MOD);
}
// printf("%lld %lld\n",i,ans);
// ans = 0;
}
printf("%lld\n",ans);
return 0;
}
E.Strange Constraints
题目描述：
给定长度为 \(n\) 的序列 \(A\)，求序列 \(B\) 的个数模 \(998244353\)，满足以下条件：
- 值域 \([1, n]\)。
- \(i\) 的个数不超过 \(A_i\)。
- \(B_i\) 的个数不超过 \(A_i\)。
\(1 \le n \le 500\)。
题目分析：
考虑设 \(d_i\) 表示数 \(i\) 出现的次数，则题目条件可以转化为：
- \(d_i \le A_i\)
- 若 \(i\) 可以放在位置 \(j\)，则必然满足 \(d_i \le A_j\)
设 \(c_i = \sum_{j=1}^n [i \le A_j]\)，则 \(c_i\) 就代表出现次数为 \(i\) 的数可选的种类数，以及出现次数为 \(i\) 的数在 \(B\) 中可以放的位置数。
所以这个东西直接 \(dp\) 去做就很简单了，也就是设 \(dp[i][j][k]\) 表示考虑了出现次数大于等于 \(i\) 的数，总共选择了 \(j\) 种数，放在 \(B\) 的 \(k\) 个位置上。
转移就是枚举出现次数等于 \(i\) 的数有 \(x\) 个：
转移的两个系数：第一个就是选择哪些数，第二个就是这些数放在哪些位置。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505;
const int MOD = 998244353;
int f[N][N][N],fac[N],inv[N],a[N],c[N];
int binom(int n,int m){
if(n < m || n < 0 || m < 0) return 0;
return fac[n] * inv[m] % MOD * inv[n-m]%MOD;
}
int power(int a,int b){
int res = 1;
while(b){
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
void add(int &a,int b){
a = (a + b)%MOD;
}
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n;scanf("%lld",&n);
fac[0] = 1;
for(int i=1; i<=n; i++) fac[i] = fac[i-1] * i % MOD;
inv[n] = power(fac[n],MOD-2);
for(int i=n-1; i>=0; i--) inv[i] = inv[i+1] * (i+1) % MOD;
for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
for(int i=0; i<=n; i++){
for(int j=1; j<=n; j++){
if(a[j] >= i) c[i]++;
}
}
f[n+1][0][0] = 1;
for(int i=n; i>=1; i--){
for(int j=0; j*i<=n; j++){
if(j > c[i]) break;
for(int k=0; k<=n; k++){
if(k > c[i]) break;
for(int x=0; x*i<=n; x++){
if(k + i * x > c[i]) break;
if(j+x<=n && k+i*x<=n && c[i]-j>=0 && c[i]-k>=0 && c[i]-k-i*x>=0)
add(f[i][j+x][k+i*x],f[i+1][j][k] * binom(c[i]-j,x) %MOD* fac[c[i]-k] %MOD* power(inv[i],x) %MOD* inv[c[i]-k-i*x]%MOD);
}
}
}
}
int ans = 0;
for(int i=1; i<=n; i++) add(ans,f[1][i][n]);
printf("%lld\n",ans);
return 0;
}
- 题解 AtCoder Regular Contest 162atcoder regular contest 162 题解atcoder regular contest atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 167 atcoder regular contest 164 atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest builder