2025 ICPC 上海市大学生程序设计竞赛 个人补题笔记（正在补题中）

赛事信息

• 题目链接：https://codeforces.com/gym/105992
• 赛事榜单：https://board.xcpcio.com/provincial-contest/2025/shanghai?group=official

这场打的有点倒闭，只出了3道题，感觉心态还是比较炸，唉，好好补题了。

D. 与或博弈

题意：

gsh 与 AI 轮流操作两个非负整数 \(a\) 和 \(b\)，gsh 先手。

• gsh 目标：将 \((a, b)\) 变为目标状态 \((x, y)\)，达成则获胜；
• AI 目标：阻止 gsh 达成目标，阻止成功则获胜。

gsh 操作（二选一）

1. 按位与操作：\(a := a \& v\)（\(v\) 为任意非负整数，满足 \(0 \le v < 2^{60}\)）；
2. 按位或操作：\(b := b \mid v\)（\(v\) 为任意非负整数，满足 \(0 \le v < 2^{60}\)）。

AI 操作（二选一）

1. 按位或操作：\(a := a \mid v\)（\(v\) 为任意非负整数，满足 \(0 \le v < 2^{60}\)）；
2. 按位与操作：\(b := b \& v\)（\(v\) 为任意非负整数，满足 \(0 \le v < 2^{60}\)）。

双方均采取最优策略，若在 \(10^{100}\) 回合内，某一时刻满足 \(a = x\) 且 \(b = y\)，则 gsh 获胜；否则 AI 获胜。

思路+代码：

  这道题可以大胆猜一个结论，然后来分析这个结论，那就是 gsh 的操作只要一次不能成功，那么之后就都不能成功。

  接下来从证明的角度来证明为啥这个结论是对的，证明如下：

    我们先假设能操作成功，那么这一步成功操作必然是 gsh 进行的，因为无论是什么结果 Ai都有能力保证操作至少不会向着成功方向靠近。由于 gsh 每一次操作只能操作 \(a\) 或 \(b\) 两个数字中的一个，所以最后一步必然要保证 \(a=x\) 或者 \(b=y\) 有一个成立，由于 AI 会进行干扰，所以对于出现最后一步这种情况就只有以下两种比较合理的可能：

1. 刚开始的时候 \(a=x\) 或者 \(b=y\) 就有一个成立。
2. gsh 可以先满足 \(a=x\) 或者 \(b=y\) 有一个成立，且确保这种成立不会被 AI 改变，然后 gsh 再试图让另一个数字成立。

  对于第一种情况而言，可以充分说明如果 gsh 的操作只要一次不能成功，因为 AI 可以让 gsh 不能成功的数保持不变，那么 gsh 无论如何都不会成功。

  对于第二种情况而言，就需要好好思考 \(\&\) 和 \(|\) 运算了。从二进制的角度考虑，对于 \(\&\) 运算而言， \(\&\) 无法让 0 变成 1 ，而对于 \(|\) 运算而言，\(|\) 无法让 1 变成 0 。所以对于 \(a\) 和 \(x\) 而言，如果某一位 \(a\) 是 0 而 \(x\) 是 1 则本质上 \(a\) 就不能变成 \(x\) ，如果 某一位 \(a\) 是 1 而 \(x\) 是 0 那么 AI 仍可以让 0 变成 1 来使得 \(a ≠ x\)，然后退回到 \(a≠x\) 且 \(b≠y\) 的时候。 对于 \(b\) 和 \(y\) 而言，如果某一位 \(b\) 是 1 而 \(y\) 是 0 则本质上 \(b\) 就不能变成 \(y\) ，如果 某一位 \(b\) 是 0 而 \(y\) 是 1 那么 AI 仍可以让 1 变成 0 来使得 \(b ≠ y\)，然后退回到 \(a≠x\) 且 \(b≠y\) 的时候，因此第二种情况并不存在。

  因此 gsh 的操作只要一次不能成功，那么之后就都不能成功。

AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,x,y;

void solve(){
    cin>>a>>b>>x>>y;
    bool st=false;
    if(a==x){
        for(int i=60;i>=0;i--){
            if(((b>>i)&1)&&!((y>>i)&1))
                st=true;
        }
    }else if(b==y){
        for(int i=60;i>=0;i--){
            if(!((a>>i)&1)&&((x>>i)&1))
                st=true;
        }
    }else
        st=true;
    if(st)
        cout<<"No"<<'\n';
    else
        cout<<"Yes"<<'\n';
}

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

G. 矩阵

题意：

给定一个正整数 \(n\)，你需要构造一个 \(n \times n\) 的矩阵。

矩阵的第 \(i\) 行第 \(j\) 个元素，记作 \(A_{i,j}\)。

你的目标是使得：对于所有 \(1 \le i \le n\) 且 \(1 \le j \le n\)，都有

• 如果 \(i > 1\)，有 \(\gcd(A_{i,j}, A_{i-1,j}) = 1\)
• 如果 \(j > 1\)，有 \(\gcd(A_{i,j}, A_{i,j-1}) = 1\)

并且所有的数字都满足 \(1 \le A_{i,j} \le n^2 + 40n\)，且所有数字互不相同。

也就是说，矩阵中，所有的数字与它上下左右相邻的四个数字都互质，并且矩阵中的数都不超过 \(n^2 + 40n\)。

\(\gcd(x,y)\) 表示 \(x\) 和 \(y\) 的最大公约数。

思路+代码：

  我们先考虑如何让一行相邻的的数如何使其 \(\gcd= 1\) ，很直接，直接连续的 \(n\) 个数即可。而一列的数又如何使其 \(\gcd= 1\) 呢？其实本质上只需要保证对于任意比较小的 \(i\) 满足 \(i\) 和 \(i+x\) 互质即可，如何找到这个 \(x\) 呢？假设 \(\gcd(i, i+x) = a\) ，则必然存在以下的式子：

• \(i=k_{1}*a\)
• \(i+x=k_{2}*a\)

  两个式子相互一减，就发现 \(x=(k_{2}-k_{1})*a\)，若想让 \(a\) 为 1，则需要保证 \(x=k_{2}-k_{1}\)。当 \(x\) 为一个不为 \(i\) 的质数的时候可以满足，若想尽可能满足，就需要让这个质数最好避开所有在矩阵中出现的数字。可以从大于 \(n\) 的最小质数出发，设这个最小质数为 \(prime\) ，然后构造成如下格式：

  我们对最大的那个数分析，由于在 \(10^{4}\) 范围内两个质数的间隔最大为 36 ，所以 \(n+(n-1)*prime ≤ n+(n-1)*(n+36) = n^{2}+36*n-36<n^{2}+40*n\)

AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2510;
int a[N][N];

bool check(ll x){
    for(int i=2;i<=x/i;i++)
        if(x%i==0)
            return 0;
    return 1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,x;
    cin>>n;
    x=n+1;
    while(1){
        if(check(x))
            break;
        x++;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=j+(i-1)*x;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cout<<a[i][j]<<' ';
        cout<<'\n';
    }
    return 0;
}

H. V 我 112.5

题意：

• 基础费用固定为 50元；
• 额外费用 = 基础费用 \(×\) 关税百分比 ( x% )；
• 总费用 = 基础费用 \(+\) 额外费用；
• 输入关税百分比 ( \(x\) )，计算并输出最终需要支付的总金额。

思路+代码：

  非常简单的语法题，感觉能看到这份题解的应该都能随便写这道题，就不讲了。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    double x;
    cin >> x;
    cout << fixed << setprecision(3) << "Vivo " << 50.0 + 50.0 * 0.01 * x;
}

I. 真相

题意：

给定一棵以节点 1 为根、共 \(n\) 个节点的有根树，每个节点上的人要么是诚实者（永远说真话），要么是说谎者（永远说假话）。

每个节点 \(i\) 的人都陈述：「以我为根的子树中，恰好有 \(a_i\) 个诚实者」。

需要统计满足以下逻辑自洽条件的真假分配方案数，结果对 \(998244353\) 取模：

1. 若节点 \(i\) 是诚实者，则其陈述的 \(a_i\) 必须等于该子树中诚实者的实际总数；
2. 若节点 \(i\) 是说谎者，则其陈述的 \(a_i\) 必须不等于该子树中诚实者的实际总数。

思路+代码：

  这道题是一道很直接的树形背包 DP ，我们直接考虑每个节点和其相邻子节点的转移即可，我从思路和时间复杂度两部分分别说一下。


从思路上的角度分析：

  方案数和诚实者的数量以及当前处理的节点有关系，由于方案数之间的关系是乘的关系，为了避免在转移过程中出现新旧状态混乱等问题，我们可以再为 \(dp\) 开一维。我们设 \(dp_{i,j,k}\) 为节点 \(i\) 有 \(j\) 个诚实者时有效的方案数，对于要处理的子节点 \(v\) ，我们设 \(k=0\) 为考虑节点 \(v\) 之前的方案数， \(k=1\) 为考虑节点 \(v\) 之后的方案数。

  对于要处理的节点 \(u\) ，最开始的时候由于节点 \(u\) 没有处理任何一个节点，自然就没有一个诚实者，所以我们设 \(dp_{u,0,0}=1\) 。我们要处理节点 \(u\) 的子节点 \(v\) ，就需要考虑节点 \(v\) 能给节点 \(u\) 带来什么，节点 \(v\) 有 \(x\) 个诚实者的方案数与节点 \(u\) 在未考虑节点 \(v\) 时候有 \(y\) 个诚实者的方案数二者就可以进行组合，然后组成节点 \(u\) 在考虑节点 \(v\) 时候有 \(x+y\) 个诚实者的方案数，转化成转移表达式为：

  然后处理完节点 \(v\) 的所有情况后再滚轮如下：

• \[dp_{u,i,0}=dp_{u,i,1} \]

• \[dp_{u,i,1}=0 \]

  处理完节点 \(u\) 所有子节点组合成的不同诚实者对应的方案数，就需要考虑节点 \(u\) 是否是诚实者对于方案数的影响：

• 若节点 \(u\) 是诚实者，那么其子节点的诚实者数量必须是 \(a_{u}-1\)
• 若节点 \(u\) 是撒谎者，那么其子节点的诚实者数量必须不能是 \(a_{u}\)

  因此，我们直接让 \(dp_{u,a_{u},0}=0\) ,\(dp_{u,a_{u},0}=dp_{u,a_{u}-1,0}\) 即可。

  由于 \(1≤n≤5000\) ，而上面思路如果不进行特殊处理的话很容易达到 \(O(n^{3})\) 级别（不进行一些处理的情况下每次转移都是 \(O(n^{2})\) 的转移，共有 \(n-1\) 条边，每次处理一条边的时候就会进行一次转移），因此我们就需要考虑对转移这块进行一个优化。其实每次转移处理的诚实者数量只和当前节点已经处理的子树节点的总数以及待处理的子节点其子树节点总数有关系，也就是当前节点已经处理的子树节点的总数 * 待处理的子节点其子树节点总数 的复杂度。

  直观的数学证明不太好考虑，我们从其本质上考虑。上面的文字描述本质上就是当前节点的两个子树节点之间任意的配对。这样考虑下来最后的时间复杂度最坏情况下就是树上的任意两个节点之间配对，也就是 \(O(n^{2})\) 。

  因此我们按照当前节点已经处理的子树节点的总数 * 待处理的子节点其子树节点总数 这一思路不断维护即可。

AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=5010;
ll dp[N][N][2];
ll cnt[N];
vector<int>eg[N];
int a[N];
int n;

void init(){
    for(int i=1;i<=n;i++){
        eg[i].clear();
        cnt[i]=0;
        for(int j=1;j<=n;j++)
            dp[i][j][0]=0;
    }
}

void dfs(int u,int fa){
    dp[u][0][0]=1;
    cnt[u]=1;
    for(auto v:eg[u]){
        if(v==fa)
            continue;
        dfs(v,u);
        for(int i=cnt[u];i>=0;i--)
            for(int j=cnt[v];j>=0;j--)
                dp[u][i+j][1]=(dp[u][i+j][1]+dp[u][i][0]*dp[v][j][0]%mod)%mod;
        cnt[u]+=cnt[v];
        for(int i=0;i<=cnt[u];i++){
            dp[u][i][0]=dp[u][i][1];
            dp[u][i][1]=0;
        }      
    }
    dp[u][a[u]][0]=0;
    if(a[u])
        dp[u][a[u]][0]=dp[u][a[u]-1][0];
}

void solve(){
    cin>>n;
    init();
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        eg[u].push_back(v);
        eg[v].push_back(u);
    }
    dfs(1,-1);
    ll ans=0;
    for(int i=0;i<=n;i++)
        ans=(ans+dp[1][i][0])%mod;
    cout<<ans<<'\n';
}   

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

M. 魔法使考核

题意：

  有 \(n\) 个初始魔力值为 \(0\) 的魔法球，目标是通过若干次魔法操作，让第 \(i\) 个魔法球最终达到指定魔力值 \(a_i\)，求完成目标所需的最小体力消耗，可以进行以下两种操作：

1. 单点加 1：给任意一个魔法球的魔力值 \(+1\)，消耗 \(x\) 点体力。
2. 区间翻倍：选择任意区间 \([l, r]\)，将该区间内所有魔法球的魔力值翻倍，消耗 \(y\) 点体力（与区间长度无关）。

思路+代码：

  首先，区间翻倍操作本质上就是对区间内每个数的二进制形式进行 \(<<\) 操作，而单点加1本质上就是对某个数的二进制形式进行进位操作。我们可以从贪心的角度出发，将目标数组的每个数都看成二进制形式，然后从二进制的高位到低位处理二进制形式的每一位即可。

  具体操作上就是对于当前已处理的前 \(j\) 位构成的数组 \(b_{i}\) 而言，若想处理从高到低的第 \(j+1\) 位的二进制，就需要先让数组 \(b_{i}\) 整体翻倍，答案加上翻倍的最小代价（可以直接进行区间翻倍操作，也可以进行\(\sum_{i=1}^{n} b_i\) 次单点加1操作），然后对于第 \(j+1\) 位的二进制，若是 \(a_{i}\) 这一位为 1 ，则对应 \(a_{i}\) 这一位也得补上 1 ，最后求出最小代价即可。

AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+100;
ll a[N],b[N];
signed main(){
    int n;
    ll x,y,ans=0;
    cin>>n>>x>>y;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int j=30;j>=0;j--){
        ll sum=0;
        for(int i=1;i<=n;i++){
            sum+=b[i];
            b[i]=b[i]*2;
        }
        if(sum>=y&&x>0)
            ans+=y;
        else
            ans+=min(sum*x,y);
        for(int i=1;i<=n;i++){
            if((a[i]>>j)&1){
                b[i]++;
                ans+=x;
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}