2025 牛客暑期多校训练营 7 个人题解

记录一下在比赛中遇到的几道个人认为较有挑战性的题目，分享一下解题思路和过程。

这场打的稀烂，惨遭队友压力。

A. Loopy Laggon#

题目大意#

给定一个 n*n 的矩阵，矩阵中的数字 1 到 n^2 恰好各出现一次。你可以对矩阵中任意一个 4x4 的子矩阵进行顺时针或逆时针旋转。问，给定的矩阵是否能通过若干次这样的操作，变回初始有序状态（即第一行是 1,2,…,n，第二行是 n+1,…,2n，以此类推）。

题解#

这个操作可以看作 12 次交换操作。排列的一次交换会改变逆序对的奇偶性，12 次不会。检查将其展开为一维数组后求逆序对，若为偶数则该矩阵可能可以由无数次旋转操作得到（题目保证 n=10 且允许不超过 10% 错误率）。

1
#include<bits/stdc++.h>
2
// #ifdef LOCAL_GCC
3
#define print cout<<format
4
// #endif
5
#define up(i,x,y) for (auto i=x;i<=y;i++)
6
#define upn(i,x,y) for (auto i=x;i<y;i++)
7
#define down(i,x,y) for (auto i=x;i>=y;i--)
8
#define elif else if
9
using ll=long long;
10
using namespace std;
11
void solve(){
12
  int id,m,k,n;
13
  cin>>id>>m>>k>>n;
14
  string res="";
15
  vector a(n*n,0);
16
  upn(_,0,m){
17
    bool flg=0;
18
    upn(__,0,k){
19
      int cur=0;
20
      upn(i,0,n*n){
21
        cin>>a[i];
22
        upn(j,0,i){
23
          if (a[j]>a[i]) cur++;
24
        }
25
      }
26
      flg|=(cur%2==1);
27
    }
28
    if (flg)res.push_back('1');
29
    else res.push_back('0');
30
  }
31
  print("{}",res);
32
}
33
int main(){
34
  ios::sync_with_stdio(false);
35
  cin.tie(nullptr);
36
  cout.tie(nullptr);
37
  int T=1;
38
  // cin>>T;
39
  while(T--) solve();
40
}

I. Lava Layer#

题目大意#

给定一个包含 k 个个位数的集合 D。首先，随机生成一个长度为 n 的数列 a，其中每个元素 a[i] 都等概率地从集合 D 中选取。然后，在 n−1 个空隙中，等概率地填入加，乘，与，或，异或这五种运算符中的一种。请求出最终表达式结果的期望值，答案对 998244353 取模。

题解#

这是典型的动态规划（DP）求期望问题，并且由于 n 的范围很大（可达 10^18），需要使用矩阵快速幂进行优化。

可以用 dp 解决这道题。以期望值的低 4bit 为键，维护期望值*概率与概率。这样可以同时维护加乘操作与二进制位运算操作（D 中的数都小于 2^4）。

1
#include<bits/stdc++.h>
2
// #ifdef LOCAL_GCC
3
#define print cout<<format
4
// #endif
5
#define up(i,x,y) for (auto i=x;i<=y;i++)
6
#define upn(i,x,y) for (auto i=x;i<y;i++)
7
#define down(i,x,y) for (auto i=x;i>=y;i--)
8
#define elif else if
9
using ll=long long;
10
using namespace std;
11
const ll mod=998244353;
12
template <typename T=long long>
13
T qpow(T a,T b){
14
    T res={1};
15
    while(b){
16
        if (b&1) res=res*a%mod;
17
        a=a*a%mod;
18
        b>>=1;
19
    }
20
    return res;
21
}
22
template <typename T=long long>
23
struct matrix{
24
  int n;
25
  vector<vector<T>>a;
26
  matrix(int _n,T x=0):n(_n),a(n,vector<T>(n,0)){
27
    upn(i,0,n){
28
      a[i][i]=x;
29
    }
30
  }
31

32
  vector<T>& operator[] (int i) {return a[i];}
33

34
  matrix operator * (matrix o){
35
    matrix ret={n};
36
    upn(i,0,n){
37
      upn(k,0,n){
38
        upn(j,0,n){
39
          ret[i][j]=(ret[i][j]+a[i][k]*o[k][j])%mod;
40
        }
41
      }
42
    }
43
    return ret;
44
  }
45
};
46
template <typename T=long long>
47
matrix<T> qpow(matrix<T> a,ll b){
48
    matrix<T> res={a.n,1};
49
    while(b){
50
        if (b&1) res=res*a;
51
        a=a*a;
52
        b>>=1;
53
    }
54
    return res;
55
}
56
void solve(){
57
  ll n,k;
58
  cin>>n>>k;
59
  ll inv5k=qpow(5ll*k,mod-2),invk=qpow(k,mod-2);;
60
  vector D(k,0ll);
61
  for (auto&&i:D)cin>>i;
62

63
  matrix b={32,0ll};
64
  // 期望 概率
65
  upn(i,0,16){
66
    for (auto&&j:D){
67
      // +
68
      b[i][(i+j)%16]=(b[i][(i+j)%16]+inv5k)%mod;
69
      b[i+16][(i+j)%16]=(b[i+16][(i+j)%16]+j*inv5k)%mod;
70
      b[i+16][(i+j)%16+16]=(b[i+16][(i+j)%16+16]+inv5k)%mod;
71
      // *
72
      b[i][(i*j)%16]=(b[i][(i*j)%16]+j*inv5k)%mod;
73
      b[i+16][(i*j)%16+16]=(b[i+16][(i*j)%16+16]+inv5k)%mod;
74
      // &
75
      b[i+16][(i&j)%16]=(b[i+16][(i&j)%16]+(i&j)*inv5k)%mod;
76
      b[i+16][(i&j)%16+16]=(b[i+16][(i&j)%16+16]+inv5k)%mod;
77
      // |
78
      b[i][(i|j)%16]=(b[i][(i|j)%16]+inv5k)%mod;
79
      b[i+16][(i|j)%16]=(b[i+16][(i|j)%16]+((i|j)-i)*inv5k)%mod;
80
      b[i+16][(i|j)%16+16]=(b[i+16][(i|j)%16+16]+inv5k)%mod;
81
      // ^
82
      b[i][(i^j)%16]=(b[i][(i^j)%16]+inv5k)%mod;
83
      b[i+16][(i^j)%16]=(b[i+16][(i^j)%16]+((i^j)-i)*inv5k)%mod;
84
      b[i+16][(i^j)%16+16]=(b[i+16][(i^j)%16+16]+inv5k)%mod;
85
    }
86
  }
87
  matrix a={32,0ll};
88
  for (auto&&i:D){
89
    upn(j,0,32){
90
      a[j][i]=i*invk%mod;
91
      a[j][i+16]=invk;
92
    }
93
  }
94
  matrix res=a*qpow(b,n-1);
95
  ll ans=0;
96
  upn(i,0,16) ans=(ans+res[0][i])%mod;
97
  print("{}\n",(ans%mod+mod)%mod);
98
}
99
int main(){
100
  ios::sync_with_stdio(false);
101
  cin.tie(nullptr);
102
  cout.tie(nullptr);
103
  int T=1;
104
  cin>>T;
105
  while(T--) solve();
106
}

D. Lost Woods#

题目大意#

给定一张 N 个点 M 条边的有向有权图。对于所有从起点 1 到终点 N 的路径（可以有环，路径长度不限），计算路径上所有边权的方差。请求出这个方差的下确界（infimum）。

题解#

这是一个在图上结合 DP 和数学期望/方差性质的题目。

维护 dp[n+1][n+1][n*20+1]，第一个维度表示走过的边，第二个维度表示当前点，第三个维度表示权值和，值表示平方和的最小值。

因为

D = \mathbb{E}[X^2] - \left( \mathbb{E}[X] \right)^2

我们希望方差 D(X) 小，所以平均数（权值和/边数）相同时，我们肯定希望平方和的期望越小。用 dp 从下往上维护即可。

注意特判环，可以通过无限绕环让方差趋近于环的方差（所以叫下确界）。

1
#include<bits/stdc++.h>
2
// #ifdef LOCAL_GCC
3
#define print cout<<format
4
// #endif
5
#define up(i,x,y) for (auto i=x;i<=y;i++)
6
#define upn(i,x,y) for (auto i=x;i<y;i++)
7
#define down(i,x,y) for (auto i=x;i>=y;i--)
8
#define elif else if
9
using ll=long long;
10
using namespace std;
11
void solve(){
12
  int n,m;
13
  cin>>n>>m;
14
  vector tu(n+1,vector(0,array<int,2>{0,0})),ru=tu;
15
  vector vis1(n+1,false),visn(n+1,false);
16
  up(i,1,m){
17
    int u,v,w;
18
    cin>>u>>v>>w;
19
    tu[u].push_back({v,w});
20
    ru[v].push_back({u,w});
21
  }
22
  auto bfs=[&](int st,vector<vector<array<int,2>>>&tu,vector<bool>&vis)->void{
23
    queue<int>q;
24
    q.push(st);
25
    while (not q.empty()){
26
      int p=q.front();
27
      q.pop();
28
      vis[p]=1;
29
      for (auto&&[to,w]:tu[p]){
30
        if (vis[to]) continue;
31
        q.push(to);
32
                vis[to]=1;
33
      }
34
    }
35
  };
36
  bfs(1,tu,vis1);
37
  bfs(n,ru,visn);
38
  if (not vis1[n]){
39
    print("-1\n");
40
    return;
41
  }
42
  int mx=n*20+1;
43
  const int inf=0x3f3f3f3f;
44
  vector dp(n+1,vector(n+1,vector(mx+1,inf)));
45
  auto f=[&](int st,int ed){
46
    up(i,0,n) up(j,0,n) up(k,0,mx) dp[i][j][k]=inf;
47
    dp[0][st][0]=0;
48
    double ret=1.0*inf;
49
    upn(i,0,n){
50
      up(j,1,n){
51
        up(k,0,mx){
52
          if (dp[i][j][k]>=inf) continue;
53
          for (auto&&[to,w]:tu[j]){
54
            if (k+w<=mx and dp[i][j][k]+w*w<dp[i+1][to][k+w]) {
55
              dp[i+1][to][k+w]=dp[i][j][k]+w*w;
56
              if (to==ed){
57
                ret=min(ret,((double)dp[i+1][to][k+w])/(i+1)-(((double)(k+w))/(i+1)*(k+w)/(i+1)));
58
              }
59
            }
60
          }
61
        }
62
      }
63
    }
64
    return ret;
65
  };
66
  double ans=f(1,n);
67
  up(i,1,n) if (vis1[i] and visn[i]) ans=min(ans,f(i,i));
68
  printf("%.9lf\n",ans);
69
}
70
int main(){
71
  ios::sync_with_stdio(false);
72
  cin.tie(nullptr);
73
  cout.tie(nullptr);
74
  int T=1;
75
  // cin>>T;
76
  while(T--) solve();
77
}