ZhouChuang Coding CSP-J 仿真模拟 题解

Sktic · 2025-10-19 00:07:13 · 题解

ZhouChuang Coding CSP-J 仿真模拟 题解

T1 Retribution ∼ Cycle of Redemption ∼

按照题意模拟即可。可以采用递推减少代码编写难度。

注意不开long long的话会获得 60 分的高分。

这里涉及到一个知识点，int类型最多支持算到12!，而long long 最多支持算到20!也就是刚好题目的数据范围，而我们通过简单估算可以发现20!*2仍然在long long的数据范围内所以不用写高精度。

::::info[AC code]

#include<bits/stdc++.h>
using namespace std;
const int maxn=21;
typedef long long ll;
int a[maxn];
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    a[0]=1;
    for(int i=1;i<=n;i++)
        a[i]=a[i-1]*i;
    cout<<(a[n]-n)*2<<" "<<(a[n]-2*n)*2<<" "<<2<<endl; 
    return 0;
}

::::

T2 Givemeygg lose his unique coin

首先此题旨在考查阅读理解能力。

翻译过来就是一个无向图，每条边有边权，删去一些边使得这个图变成一个二分图，使得花费价值最少。

然后可以发现这个题的 n 是非常小的，于是可以直接暴力枚举每个点所在的集合（A 或 B），不同集合的点之间的边都要删去，判断每条边是否删去需要O(m)次运算，对枚举的状态进行分解需要O(n)次计算，期望复杂度 O(\text{max}(n,m)\times2^n) ，可以通过。

不过也需要注意到这个题的边权是 10^8 次的，考虑极限数据的估算，最多情况下可以超过2.1亿也就是会爆int，所以ans也要开long long。

不开long long 会获得 80 分的高分。 ::::info[AC Code]

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
typedef long long ll;
int a[maxn],b[maxn],c[maxn];
ll k[maxn],num=10000000000; 
int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>a[i]>>b[i]>>k[i];
    for(int i=0;i<=(1<<n)-1;i++)
    {
        int x=i,tot=1;
        memset(c,0,sizeof(c));
        while(x)
            c[tot++]=x%2,x/=2;
        ll ans=0;
        for(int j=1;j<=m;j++)
            if(c[a[j]]==c[b[j]])
                ans+=k[j];
        num=min(num,ans); 
    }
    cout<<num<<endl;
    return 0;
}

::::

T3 Alice vs Bob Ⅰ

考虑 DP 求解。

记状态 dp[i][k] 表示一共剩下 k 次操作，此时走到第 i 个点的胜负情况，dp[i][k]=A 表示 Al 必胜，dp[i][k]=B 表示 Bob 必胜，我们认为初始状态的字符串 s 就表示所有的 dp[i][0]，于是可以发现 dp[i][k] 只由 dp[j][k-1] 决定，其中 j 是从 i 出发可以直接到达的点，即存在边 i->j 。

具体的，如果 k 是偶数，那么是 Al 操作，也就是只要 dp[j][k-1] 中存在一个点是 A，那么 Al 就可以这步操作走到这个点，然后必胜。所以 dp[i][k]=A 当且仅当存在 dp[j][k-1]=A，若所有的 dp[j][k-1]=B,则 dp[i][k]=B 。

同样的，如果 k 是奇数，那么是 Bob 操作，也就是只要 dp[j][k-1] 中存在一个点是 B，那么 Bob 就可以这步操作走到这个点，然后必胜。所以 dp[i][k]=B 当且仅当存在 dp[j][k-1]=B，若所有的 dp[j][k-1]=A,则 dp[i][k]=A 。

然后就可以 DP递推 或者 记忆化搜搜求解了。时间复杂度 O(\text{max}(n,m)\times 2k) ，可以通过本题。

如果想要进一步优化，可以发现上面两种转移本质上都一模一样，考虑把 A / B 必胜的意义改成先手/后手必胜，那么两部分的转移就可以完全统一到一起，也就是 std 的写法。

最后有一个小细节，注意题目中开头的冷笑话写的是Alice 中的 ice 化掉了，因此我们应该输出 Al 而不是谐音的 AI 。（注意前一个是L的小写后一个是i的大写）

::::info[AC Code]

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
typedef long long ll;
vector<int>e[maxn];
int pos[maxn][20],t,n,m,k;
void upd(int x,int k)
{
    for(int i=0;i<e[x].size();i++)
        if(pos[e[x][i]][k-1]==2)
        {
            pos[x][k]=1;
            return;
        }
    pos[x][k]=2;
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>k;
        string s;
        cin>>s;
        for(int i=1;i<=n;i++)
            e[i].clear();
        for(int i=1;i<=m;i++)
        {
            int x,y;
            cin>>x>>y;
            e[x].push_back(y);
        }
        for(int i=1;i<=n;i++)
            if(s[i-1]=='A')
                pos[i][0]=1;
            else
                pos[i][0]=2;
        for(int i=1;i<=2*k;i++)
            for(int x=1;x<=n;x++)
                upd(x,i);
        if(pos[1][2*k]==1)
            cout<<"Al"<<endl;
        else
            cout<<"Bob"<<endl;
    }
    return 0;
}

::::

T4 完蛋了这么简单的题目放T4肯定被切穿了吧

如题，结论题。

第一步翻译题目意思。

有 n 个硬币构成一个环，每个硬币有一个正反面（正面为 v_i=1 ，反面为 v_i=0）且写着一个面额（a_i），每次可以选择拿走一个硬币，若这个硬币的左边或者右边有任意一个的正反面和自己相同，那么拿走这个硬币就不算分。否则这次拿走加上这个硬币上面写着的面额。

定义环中只剩一枚硬币时它的左边与右边都是自己。

首先可以发现，对于连续一段状态相同的硬币，其中必定有且只有一个硬币对答案有贡献，也就是一直取一直取取到这一段只剩一个硬币，且两端都异面，此时再取这个硬币才会对答案有贡献。于是这部分考虑贪心求最大。

于是这个时候我们的硬币形如 0101010101 这样的一个环，设共有 2\times k 个。

首先显然可以发现，这 2k 个硬币里面最多有且只有 k 个会对答案造成贡献。

于是来到了本题最为诈骗的地方，我们考虑证明对于取环中任意 k 个硬币，这样的方案总是存在。

如下：

于是代码实现就很简单了，我们先对原来的环断环为链，然后去重，然后对于新序列排序，取最大的 n 个求和。

注意不要忘记对状态全部相等的情况特判，这个时候答案为 0 。

总复杂度 O(nlogn)，可以通过本题。

::::info[AC Code]

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
typedef long long ll;
int vis[maxn<<1];
ll a[maxn<<1],b[maxn];
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>vis[i];
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        vis[i+n]=vis[i],a[i+n]=a[i];
    int pos=1;
    while(vis[pos]==vis[pos+1]&&pos<n)
        pos++;
    if(pos==n)
    {
        cout<<0<<endl;
        return 0;
    } 
    if(pos!=n) 
        pos++;
    else
        pos=1;
    ll mx=a[pos],num=0,ans=0;
    for(int i=pos;i<pos+n;i++)
        if(vis[i]!=vis[i+1]||i==pos+n-1)
            b[++num]=mx,mx=a[i+1];
        else
            mx=max(mx,a[i+1]);
    sort(b+1,b+1+num);
    for(int i=num/2+1;i<=num;i++)
        ans+=b[i];
    cout<<ans<<endl;
    return 0;
}

:::: T5 Alice vs Bob Ⅱ

决策构造的结论题。由于我们要将这颗树标记合法的边，我们可以想一下这个游戏的性质。

• 1.首先可以发现一个简单的结论，不可能有两个相邻的节点使得它们都为 1 。

很容易发现，因为如果有一个节点为 1 已经确认，那么另一个节点先手下完后，后手必定会下在这个为 1 的节点，因为在这里后手的意义等同于先手，那么是后手必胜的。

• 2.其次，两个相邻节点都为 2 是可能的。

因为两个后手必胜的路径可能有所不同，当两个路径不经过同一个点时就可以存在两个相邻的 2 ，而这两个节点之间可以任意连边。

• 3.当一个节点没有出边时，它必定为 1 。

自己手玩可知。

通过上面三条结论我们可以发现一个简单的构造方法：当一个点为 1 时，将目前所有未被标记的边联向自己，并且将周围所有未标记的点标为 2 并进行二次编号.当其为 2 时，将所有的未被标记的边联向他人。这样就可以满足上述三条性质。

然后考虑怎么将询问次数再次降低，使其必小于 \lfloor\frac{n}{2}\rfloor 。我们可以处理好每个点未被标记的边数，每次暴力取出边数最多的点进行询问，最差情况是树退化成一条链，每次最多询问出两条边且都为 2 无法进行二次编号，因此刚好能做到 \lfloor\frac{n}{2}\rfloor 。

总复杂度 O(n^2) ，可以通过本题。

::::info[AC Code]

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
struct node
{
    int u,v,i;
};
node tr[maxn];
vector<node>s[maxn];
vector<int>q[maxn];
int du[maxn];
int f[maxn];
int win[maxn];
int m;
extern "C"
{
    int ask(int x); 
    void init(int n,vector<node>e)
    {
        m=n;
        for(int i=1;i<=n-1;i++)
        {
            tr[i]=e[i-1];
            s[tr[i].u].push_back(node{tr[i].u,tr[i].v,i});
            s[tr[i].v].push_back(node{tr[i].u,tr[i].v,i});  
            q[tr[i].u].push_back(tr[i].v);
            q[tr[i].v].push_back(tr[i].u);
            f[tr[i].u]++;f[tr[i].v]++;
        }
    }
    string que()
    {
        while(1)
        {
            int fl=1;
            for(int i=1;i<=m-1;i++)
                if(du[i]==0)
                    fl=0;
            if(fl==1)
                break;
            int md=0,mi=0;
            for(int i=1;i<=m;i++)
                if(f[i]>md)
                    md=f[i],mi=i;
            int tmp=ask(mi);
            win[mi]=tmp;
            for(int i=0;i<s[mi].size();i++)
                if(du[s[mi][i].i]==0)
                {
                    du[s[mi][i].i]=((s[mi][i].u==mi)?tmp%2+1:tmp);
                    f[s[mi][i].u]--;
                    f[s[mi][i].v]--;
                }
            if(tmp==1)
                for(int i=0;i<q[mi].size();i++)
                    if(win[q[mi][i]]==0)
                    {
                        win[q[mi][i]]=1;
                        for(int x=0;x<s[q[mi][i]].size();x++)
                            if(du[s[q[mi][i]][x].i]==0)
                            {
                                du[s[q[mi][i]][x].i]=((s[q[mi][i]][x].u==q[mi][i])?2:1);
                                f[s[q[mi][i]][x].u]--;
                                f[s[q[mi][i]][x].v]--;
                            }
                    }
        }
        string sk;
        for(int i=1;i<=m-1;i++)
            sk+=char(du[i]+'0');
        return sk;
    }
}

::::