CFR-840(Div.2)解题报告

发表于 更新于 分类于

比赛传送门

C. Another Array Problem

题意：给你一个数组 aa，每次可以选两个位置 i,j(i<j)i,j(i<j)，将 [i,j][i,j] 内的所有数替换为 ∣ai−aj∣|a_i-a_j|。问最终数组的和最大为多少。

首先一个显然的结论为，任意位置最终结果都不会超过数组最大值。于是可以考虑能不能等于最大值。

注意到将一个区间操作两次则变为 00，再与最大值操作一次即变为最大值。于是对于最大值的两侧都满足大于等于两个元素，则一定可以变为最大值。如果只有一侧满足，则也可以：将满足的那一侧变为最大值，再将不满足的那个元素与最大值操作两次变为 00，最后用满足的那一侧来更新不满足的这一侧。如果两侧都只有不超过一个元素，则分类讨论所有情况即可。

By Um_nik

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
ll a[5];
int n;

void solve() {
    scanf("%d", &n);
    if (n <= 3) {
        for (int i = 0; i < n; i++)
            scanf("%lld", &a[i]);
        if (n == 2) {
            printf("%lld\n", max(a[0] + a[1], 2 * abs(a[0] - a[1])));
        } else {
            ll ans = max(max(a[0], a[2]), max(abs(a[0] - a[1]), abs(a[1] - a[2])));
            ans *= 3;
            ans = max(ans, a[0] + a[1] + a[2]);
            printf("%lld\n", ans);
        }
    } else {
        ll mx = 0;
        ll x;
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x);
            mx = max(mx, x);
        }
        printf("%lld\n", mx * n);
    }
}

int main()
{
    startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
    int t;
    scanf("%d", &t);
    while(t--) solve();

    return 0;
}

D. Valid Bitonic Permutations

题意：有一个排列，钦定了其中两位的值 ai=x,aj=y(i<j,x≠y)a_i=x,a_j=y(i<j,x\ne y)，问排列为严格山峰形（不能为斜坡）的方案数。

可以考虑区间 DP：设 f[i][j]f[i][j] 表示从大到小填，填完 [i,j][i,j] 区间的方案数，则转移考虑下一个元素放左边还是右边即可。

By tourist

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, pi, pj, vi, vj;
    cin >> n >> pi >> pj >> vi >> vj;
    --pi; --pj; --vi; --vj;
    auto Valid = [&](int p, int v) {
      if (p == pi && v != vi) return false;
      if (p == pj && v != vj) return false;
      return true;
    };
    vector<vector<Mint>> dp(n, vector<Mint>(n));
    for (int i = 1; i < n - 1; i++) {
      if (Valid(i, n - 1)) {
        dp[i][i] = 1;
      }
    }
    for (int i = n - 1; i >= 0; i--) {
      for (int j = i; j < n; j++) {
        int val = n - 1 - (j - i + 1);
        if (i > 0) {
          if (Valid(i - 1, val)) {
            dp[i - 1][j] += dp[i][j];
          }
        }
        if (j < n - 1) {
          if (Valid(j + 1, val)) {
            dp[i][j + 1] += dp[i][j];
          }
        }
      }
    }
    cout << dp[0][n - 1] << '\n';
  }
  return 0;
}

同样也可以直接组合数推式子：首先令 x<yx<y（否则对称反转一下）。对于 y=ny=n 单独计算一下，主要考虑 x<y<n,i<jx<y<n,i<j 的情况。假设 nn 放在位置 mm。

如果 i<m<ji<m<j，那么 (y,n)(y,n) 内的数需要在 mm 的左右两边依次放置，每个数有左右两种选择，为 2n−y−12^{n-y-1}。对于 (x,y)(x,y) 内的数，要么在 (i,j)(i,j) 中靠左放置，要么从 j+1j+1 开始往右放置。而 (i,j)(i,j) 中剩余空位是确定的，所以要在 (x,y)(x,y) 中选取固定的数量放到 (i,j)(i,j) 内，为 (y−x−1j−i−(n−y))\binom{y-x-1}{j-i-(n-y)}。对于 [1,x)[1,x) 内的数，要么放在 ii 左边，要么放在最右边，而左边只有 i−1i-1 个空位，所以为 (x−1i−1)\binom{x-1}{i-1}。

如果 j<mj<m，那么 (y,n)(y,n) 内的数可以放在 (j,m)(j,m) 内，也可以从 m+1m+1 开始往右放，为 2n−y−12^{n-y-1}。对于 (x,y)(x,y) 内的数，要么放在 (i,j)(i,j) 内，要么往右继续放，而 (i,j)(i,j) 内的空位是确定的，所以为 (y−x−1j−i−1)\binom{y-x-1}{j-i-1}。对于 [1,x)[1,x) 内的数，要么放在 ii 左边，要么放在最右边，而左边只有 i−1i-1 个空位，所以为 (x−1i−1)\binom{x-1}{i-1}。

综上所述，答案为 2n−y−1(y−x−1j−i−(n−y))(x−1i−1)+2n−y−1(y−x−1j−i−1)(x−1i−1)2^{n-y-1}\binom{y-x-1}{j-i-(n-y)}\binom{x-1}{i-1}+2^{n-y-1}\binom{y-x-1}{j-i-1}\binom{x-1}{i-1}。

需要注意的是，题目规定必须严格山峰，不能为斜坡，所以 m≠nm\ne n。如果 m=nm=n 唯一的排列方案为 1,2,⋯ ,n1,2,\cdots,n，只有在 x=i,y=jx=i,y=j 时才会出现，减去即可。

By cxm1024

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int MAXV=200;
int inv[MAXV+10],jc[MAXV+10],invjc[MAXV+10];
int ksm(int a,int b,int res=1) {
    for(;b;a=a*a%mod,b>>=1)
        if(b&1) res=res*a%mod;
    return res;
}
void init() {
    jc[0]=1;
    for(int i=1;i<=MAXV;i++)
        jc[i]=jc[i-1]*i%mod;
    invjc[MAXV]=ksm(jc[MAXV],mod-2);
    for(int i=MAXV;i>0;i--)
        invjc[i-1]=invjc[i]*i%mod;
    for(int i=1;i<=MAXV;i++)
        inv[i]=jc[i-1]*invjc[i]%mod;
}
int C(int x,int y) {
    if(y>x||y<0||x<0) return 0;
    return jc[x]*invjc[y]%mod*invjc[x-y]%mod;
}
signed main() {
    init();
    int t;
    cin>>t;
    while(t--) {
        int n,i,j,x,y;
        cin>>n>>i>>j>>x>>y;
        int ii=i,jj=j;
        if(x>y) i=n+1-jj,j=n+1-ii,swap(x,y);
        if(y==n) {
            if(j==n) cout<<0<<endl;
            else cout<<C(n-x-1,j-i-1)*C(x-1,i-1)%mod<<endl;
        }
        else cout<<((ksm(2,n-y-1)*C(y-x-1,j-i-1-(n-y))%mod*C(x-1,i-1)%mod+ksm(2,n-y-1)*C(y-x-1,j-i-1)%mod*C(x-1,i-1)%mod)%mod-(x==i&&y==j)+mod)%mod<<endl;
    }
    return 0;
}

E. Node Pairs

题意：你需要构造一个有向图，使得恰好有 pp 个点对能够互相到达。要求用的点尽可能少，在此基础上要使“只能单向可达”的点对尽可能多，分别输出两者的数量。

由于双向可达具有传递性，所以显然答案为若干个 n(n−1)2\frac{n(n-1)}{2} 的和。首先要让 m=∑nm=\sum n 尽可能小，然后考虑单向可达的点对数量：显然可以让这些连通块之间的点对全部单向可达（用单向完全图的构造方法即可），所以答案为 m(m−1)2−p\frac{m(m-1)}{2}-p。

这些答案可以用 DP 维护。设 f[i]f[i] 表要恰好有 ii 个点对能够互相到达的最少点数，则可以枚举最后一个连通块有几个点转移。复杂度 O(pp)O(p\sqrt{p})。

By tourist

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int p;
  cin >> p;
  const int inf = (int) 1e9;
  vector<int> dp(p + 1, inf);
  dp[0] = 0;
  for (int v = 2; v * (v - 1) / 2 <= p; v++) {
    int u = v * (v - 1) / 2;
    for (int i = 0; i <= p - u; i++) {
      dp[i + u] = min(dp[i + u], dp[i] + v);
    }
  }
  long long ans = dp[p];
  long long ans2 = ans * (ans - 1) / 2 - p;
  cout << ans << " " << ans2 << '\n';
  return 0;
}

F. Edge Queries

题意：给一个无向图，每次询问两个点 a,ba,b，判断 a,ba,b 之间的边中有多少条不是割边。a,ba,b 之间的边定义为存在一个 a−ba-b 的简单路径经过这条边。

首先可以边双连通分量缩点，转化成一颗树，问题转化为经过的连通分量的边数之和。但这样显然是有问题的，如下图：

在这种情况下，a,ba,b 之间上面和右面的连通分量都不应该计算贡献。即：一个强连通分量被计算贡献必须经过其中的边。如果只有一个点作为中转不需要计算贡献。

于是可以将缩之前的点之间的边全部删掉，将缩完的点与缩之前的连通分量内的点连起来（菊花图），边权为连通分量的点数。则如果强连通分量之经过了一个点中转，不会计入贡献，而经过边时会计算两次贡献。答案除以二即可。

以下为图示：

对于左边的连通分量，这个图会造成 88 的贡献，而上面和右面的贡献均为 00，所以总的贡献为 44。

By tourist

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  dfs_undigraph<int> g(n);
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    g.add(x, y);
  }
  int cnt;
  auto vc = find_bicone(g, cnt);
  lca_forest<long long> f(n + cnt);
  vector<int> weight(cnt);
  for (auto& e : g.edges) {
    if (vc[e.from] == vc[e.to]) {
      weight[vc[e.from]] += 1;
    } else {
      f.add(e.from, e.to, 0);
    }
  }
  for (int i = 0; i < n; i++) {
    f.add(i, n + vc[i], weight[vc[i]]);
  }
  f.dfs(0);
  f.build_lca();
  int q;
  cin >> q;
  while (q--) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    int w = f.lca(x, y);
    auto ans = f.dist[x] + f.dist[y] - 2 * f.dist[w];
    assert(ans % 2 == 0);
    cout << ans / 2 << '\n';
  }
  return 0;
}

这种把连通分量缩成的点与原图中点连菊花图的方式被称为圆方树，其中缩的点被称为方点，原图中点被称为圆点。一般的圆方树做法是将连通分量的权值存在方点中，询问的时候查询路径的点权和。在这道题中与上面的做法没有本质区别，但有的题中用点权和可以在圆点上记录一些其他信息。

用点权的示例代码 By gyh20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
#define re register
using namespace std;
const int Mxdt=100000;	//单次大小
inline char gc(){
    static char buf[Mxdt],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
    re int t=0;re char v=gc();
    while(v<'0')v=gc();
    while(v>='0')t=(t<<3)+(t<<1)+v-48,v=gc();
    return t;
}
int n,m,stk[400002],tot,head[400002],cnt,dfn[400002],low[400002],tim,val[400002],siz[400002],tp,fa[22][400002],sum[400002],dep[400002];
long long ans;
struct edge{int to,next;}e[800002];
inline void add(re int x,re int y){e[++cnt]=(edge){y,head[x]},head[x]=cnt;}
vector<int>g[400002];
inline void tj(re int x){
    dfn[x]=low[x]=++tim,stk[++tp]=x;
    for(re int i=head[x];i;i=e[i].next)
        if(!dfn[e[i].to]){
            tj(e[i].to);
            low[x]=min(low[x],low[e[i].to]);
            if(low[e[i].to]==dfn[x]){
                val[++tot]=1;
                map<int,int>vis;vis[x]=1;
                while(1){
                    ++val[tot];
                    g[tot].push_back(stk[tp]);
                    g[stk[tp]].push_back(tot);
                    for(re int j=head[stk[tp]];j;j=e[j].next)if(vis.count(e[j].to))++sum[tot];
                    vis[stk[tp]]=1;
                    if(stk[tp--]==e[i].to)break;
                }if(sum[tot]==1)sum[tot]=0;
                g[x].push_back(tot);
                g[tot].push_back(x);
            }
        }
        else low[x]=min(low[x],dfn[e[i].to]);
}
inline void dfs(re int x,re int y){
    fa[0][x]=y,dep[x]=dep[y]+1;
    for(re int i=1;i<=20;++i)fa[i][x]=fa[i-1][fa[i-1][x]];
    for(re int i=0;i<g[x].size();++i){
        re int z=g[x][i];
        if(z^y)sum[z]+=sum[x],dfs(z,x);
    }
}
int main(){
    tot=n=read(),m=read();
    for(re int i=1,x,y;i<=m;++i)x=read(),y=read(),add(x,y),add(y,x);
    tj(1),dfs(1,1);
    int q=read();
    while(q--){
        re int x=read(),y=read(),oo=sum[x]+sum[y];
        if(dep[x]<dep[y])swap(x,y);
        for(re int i=20;~i;--i)if(dep[fa[i][x]]>=dep[y])x=fa[i][x];
        for(re int i=20;~i;--i)if(fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y];
        if(x!=y)x=fa[0][x];
        oo-=sum[x],oo-=sum[fa[0][x]];
        printf("%d\n",oo);
    }
}

参考博客