2025牛客暑期多校训练营5 补题

Block Combination Minimal Perimeter

打表发现有规律，4 2 4 2 的递增

 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


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e5 + 7, mod = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    int ans = 4;
    n--;
    ans += (n / 2) * 6;
    if (n % 2 == 1) {
        ans += 4;
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Mysterious XOR Operation

被签到单防。。。

根据题意，易想到，按位处理。

对于当前位，通过 popcount 判断其是第偶数位还是第奇数位。

相同奇偶性的 0 和 1 才能做出贡献。

 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


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
#define int long long

const int N = 1e5 + 7, mod = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for (int i = 0; i < 31; i++) {
        int c0e = 0, c1e = 0, c0o = 0, c1o = 0;
        for (int j = 1; j <= n; j++) {
            int tmp = a[j] & ((1 << i) - 1);
            if (i == 0) tmp = 0;
            int bit = __popcount(tmp);
            if ((a[j] >> i) & 1) {
                if (bit % 2 == 0) {
                    c1e++;
                } else {
                    c1o++;
                }
            } else {
                if (bit % 2 == 0) {
                    c0e++;
                } else {
                    c0o++;
                }
            }
        }
        ans += ((c0e * c1e + c0o * c1o) * (1 << i));
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Fastest Coverage Problem

首先想到二分答案，难点在于如何 check。

先通过 bfs, 跑满 mid 秒覆盖，没被覆盖的区域要通过一个点在 t 秒被覆盖完全。

不难想到，我们选中的点 $(i, j)$ 要满足，所有未被覆盖的点$(x, y)$到他的曼哈顿距离都要小于 t，$|x - i| + |y - j| <= t$。

我们通过四次循环，用四种顺序遍历整个图像，记录每个点到达各个方向最远点的曼哈顿距离，之后遍历找到的这个距离，如果都小于等于 t，则返回 1。

  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
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126


#include <bits/stdc++.h>
#define rep(x,l,r) for(int x=l;x<=r;++x)
#define per(x,r,l) for(int x=r;x>=l;--x)
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
typedef double db;
typedef __int128 i128;
const ll N=1e6+7,M=1e7+7,mod=1e9+7;
const ll inf=1e18+7;
const db eps=1e-8,PI=acos(-1.0);
vector<vector<int>> a,vis;
int n,m,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool chk(int x,int y)
{
    if(x<1 || x>n || y<1 || y>m)  return false;
    return true;
}
void bfs(int t)
{
    deque<pii> q;
    rep(i,1,n) {
        rep(j,1,m) {
            vis[i][j]=-1;
            if(a[i][j])  vis[i][j]=0,q.push_back({i,j});
        }
    }
    while(!q.empty()) {
        auto [x,y]=q.front();
        q.pop_front();
        if(vis[x][y]==t)  continue;
        rep(i,0,3) {
            int xx=x+dx[i],yy=y+dy[i];
            if(!chk(xx,yy)||vis[xx][yy]!=-1)  continue;
            vis[xx][yy]=vis[x][y]+1;
            q.push_back({xx,yy});
        }
    }
}
bool check(int t) 
{
    bfs(t);
    vector<vector<int>> f(n+1, vector<int>(m+1, -1)),g(n+1, vector<int>(m+1, -1));
    rep(i,1,n) {
        rep(j,1,m) {
            g[i][j]=-1;
            if(vis[i][j]==-1)  g[i][j]=0;
            if(chk(i,j-1)&&g[i][j-1]!=-1)  g[i][j]=max(g[i][j],g[i][j-1]+1);
            if(chk(i-1,j)&&g[i-1][j]!=-1)  g[i][j]=max(g[i][j],g[i-1][j]+1);
            f[i][j]=max(g[i][j],f[i][j]);
        }
    }
    rep(i,1,n) {
        per(j,m,1) {
            g[i][j]=-1;
            if(vis[i][j]==-1)  g[i][j]=0;
            if(chk(i,j+1)&&g[i][j+1]!=-1)  g[i][j]=max(g[i][j],g[i][j+1]+1);
            if(chk(i-1,j)&&g[i-1][j]!=-1)  g[i][j]=max(g[i][j],g[i-1][j]+1);
            f[i][j]=max(g[i][j],f[i][j]);
        }
    }
    per(i,n,1) {
        rep(j,1,m) {
            g[i][j]=-1;
            if(vis[i][j]==-1)  g[i][j]=0;
            if(chk(i,j-1)&&g[i][j-1]!=-1)  g[i][j]=max(g[i][j],g[i][j-1]+1);
            if(chk(i+1,j)&&g[i+1][j]!=-1)  g[i][j]=max(g[i][j],g[i+1][j]+1);
            f[i][j]=max(g[i][j],f[i][j]);
        }
    }
    per(i,n,1) {
        per(j,m,1) {
            g[i][j]=-1;
            if(vis[i][j]==-1)  g[i][j]=0;
            if(chk(i,j+1)&&g[i][j+1]!=-1)  g[i][j]=max(g[i][j],g[i][j+1]+1);
            if(chk(i+1,j)&&g[i+1][j]!=-1)  g[i][j]=max(g[i][j],g[i+1][j]+1);
            f[i][j]=max(g[i][j],f[i][j]);
        }
    }
    if(f[1][1]==-1)  return 1;
    rep(i,1,n) {
        rep(j,1,m) {
            if(f[i][j]<=t)  return 1;
        }
    }
    return 0;
}
void solve()
{
    cin>>n>>m;
    a.resize(n+1, vector<int>(m+1,0));
    vis.resize(n+1, vector<int>(m+1,0));
    rep(i,1,n) {
        rep(j,1,m) {
            cin>>a[i][j];
        }
    }
    int l=0,r=n+m,ans=r;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(check(mid)) {
            ans=mid;
            r=mid-1;
        } else {
            l=mid+1;
        }
    }
    printf("%d\n",ans);
    a.clear();
    vis.clear();
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    // cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

Perfect Journey

注意到 m 极小，可作为突破点考虑。

对 m 条特殊边编号 i，对应的值为 $1 « i$。

定义 mask[u] 表示从根节点到 u 的路径上，所有特殊边对应值的按位或之和。

用 DFS 计算所有的 mask。

得到 u，v 后，mask[u] ^ mask[v] 得到这条路径上经过了多少个特殊边。

同时判断出是否能够经过所有的特殊边。

接着处理所有的 mask 即可

  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
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 2e5 + 7, M = 1 << 22, mod = 998244353;

vector<pair<int, int>> nx[N];
int f[N], val[N];
ll cnt[M], dp[M][2], st[N];

void dfs(int u, int fa) {
    for (auto [v, i] : nx[u]) {
        if (v == fa) continue;
        f[v] = f[u] | val[i];
        dfs(v, u);
    }
}

int find(int x) {
    int res = 0;
    for (int i = 1 << 22; i > 0; i >>= 1) {
        if (x & i) {
            return (i << 1) - 1;
        }
    }
    return 1;
}

void init(int n, int m, int k) {
    for (int i = 0; i <= n; i++) {
        nx[i].clear();
        f[i] = 0;
        val[i] = 0;
    }
    for (int i = 1; i <= (1 << m) - 1; i++) {
        dp[i][0] = 1e18;
        dp[i][1] = 0;
    }
    dp[0][0] = 0, dp[0][1] = 1;
    st[0] = 1;
}

void solve() {
    vector<int> a;
    int n, m, k;
    cin >> n >> m >> k;
    init(n, m, k);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        nx[u].push_back({v, i});
        nx[v].push_back({u, i});
    }
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        val[x] = 1 << i;
    }
    dfs(1, 0);
    int tmp = 0;
    for (int i = 1; i <= k; i++) {
        int u, v;
        cin >> u >> v;
        int t = f[u] ^ f[v];
        if (t == 0) {
            continue;
        }
        cnt[t]++;
        if (cnt[t] == 1) {
            a.push_back(t);
            tmp |= t;
        }
    }
    if (tmp != (1 << m) - 1) {
        cout << "-1" << endl;
        return;
    }

    sort(a.begin(), a.end());
    for (int i = 0; i < a.size(); i++) {
        st[i + 1] = find(a[i]);
    }
    int lst = 0;
    for (auto x : a) {
        for (int i = st[lst]; i >= 0; i--) {
            if (dp[i][0] == 1e18) continue;
            int j = i | x;
            if (dp[i][0] + 1 < dp[j][0]) {
                dp[j][0] = dp[i][0] + 1;
                dp[j][1] = dp[i][1] * cnt[x] % mod;
            } else if (dp[i][0] + 1 == dp[j][0]) {
                dp[j][1] = (dp[j][1] + dp[i][1] * cnt[x]) % mod;
            }
        }
        lst++;
    }
    cout << dp[(1 << m) - 1][0] << " " << dp[(1 << m) - 1][1] << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}