2026.8.25(COCI 2023/2024# 5题解)

2026年8月25日 · 阅读需 10 分钟

A. Bitovi

一个数要变为另一个数最多修改15位，即操作步数一定 $<2^{15}*15$ ，所以最终操作步数是 $<2^{19}$ 的，符合题目限制。

现在需要考虑的是，如何设计一种修改流程，使得所有情况都满足题目限制，也都保证正确。

首先，先将题目限制放松一点思考，若没有“结果数不能是改变前集合 $A$ 中的元素”这句话的限制，那么对每个数都直接暴力修改，而且无需考虑顺序（最劣情况不会超过题目限制）。那么加上这个限制呢，可以想到，一个数的变化如果固定了是从低位开始修改，那么它的修改路径是一定的，如 $3$ 修改到 $15$ 时，路径是 $3\to 7\to 15$ ，如果中途碰到了“阻碍”，即某个数已经存在，就先搁置这一步操作，让这一步上的数代替原来的数进行修改，后续遇到阻碍时同样这样处理，那些被搁置的操作在修改完后逆向回溯时再操作，因为原来阻碍的数已经被移走了，那么现在的操作一定是可以进行的，而最后的结果等价于将原本的数改为目标数，类似于“华容道”。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;

const int N=(1<<15)+5;
int n;
int a[N],b[N];
bool visa[N],visb[N];
int c1[N],c2[N],cnt1,cnt2;
vector<int> nums;
vector<pii> ans;

void change(int a,int b)
{
    if(a==b) return;
    int t=(a^b)&(-(a^b));
    if(!visa[a^t]) ans.push_back({a,a^t});
    change(a^t,b);
    if(visa[a^t]) ans.push_back({a,a^t});
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],visa[a[i]]=1;
    for(int i=1;i<=n;i++) cin>>b[i],visb[b[i]]=1;
    for(int i=1;i<=n;i++){
        if(visb[a[i]]) continue;
        nums.push_back(a[i]);
    }
    for(int i=1;i<=n;i++){
        if(visa[b[i]]) continue;
        int t=nums.back();
        nums.pop_back();
        change(t,b[i]);
        visa[t]=0;
        visa[b[i]]=1;
    }
    cout<<ans.size()<<"\n";
    for(auto i:ans) cout<<i.x<<" "<<i.y<<"\n";

    return 0;
}

B. Piratski kod

容易看出应该是道 dp 题，难在状态设计。

根据题目中“将其分割为尽可能多的部分”这一句话，可以知道划分是从左往右时，在上一次划分后，第一次遇到 $“11”$ 时就进行，将这个划分点称作“划分结尾”。

定义一段结尾为划分结尾的二进制数列为“整块”，没有连续的 $1$ 的一段二进制数列称为“散块”，注意没有定义结尾不是划分结尾但有连续 $1$ 的数列，因为这样的数列可以被前面的两种数列拼出，而且没有什么特殊的性质，也不好转移。

注意到一段长度为 $i$ 的海盗代码的形式一定如下：

长为\,j\,的整块+长为\,(i-j)\,的散块

产生贡献的是前面的整块，而且只需考虑长度，我们要考虑如何求一段长度固定的整块的价值。一段整块长为 $len$ 又一定是如下形式：

一段长为\,j\,的整块+一段长为\,(len-j-1)\,的结尾是\,1\,的散块+1

整块的价值是由整块的价值与散块的价值拼接的，所以还要计算散块价值，定义其价值为可能向以它开头的整块贡献的价值。那么设 $f[i][0/1]$ 表示长为 $i$ ，最后一位为 $0$ 或 $1$ 的散块的价值，显然还需要用到这样的散块的数量来求解，那么再定义 $num[i][0/1]$ 表示长为 $i$ ，最后一位为 $0$ 或 $1$ 的散块的数量，转移就是：

\begin{array}{l} f_{i,0}=f_{i-1,1}+f_{i-1,0}\\ f_{i,1}=f_{i-1,0}+num_{i-1,0}*fib_{i+1}\\ num_{i,0}=num_{i-1,1}+num_{i-1,0}\\ num_{i,1}=num_{i-1,0} \end{array}

$num_{0,0}$ 初始化为 $1$ 。

再定义 $dp[i]$ 为长度为 $i$ 的整块的贡献， $s[i]$ 为长度为 $i$ 的整块的数量，转移是：

\begin{array}{l} dp_i=\sum_j dp_j*num_{i-j-1,1}+f_{i-j-1,1}*s_j\\ s_i=\sum_j s_j*num_{i-j-1,1} \end{array}

这个转移因为整块与散块之间的组合，使用了乘法原理与加法原理， $s_0$ 初始化为 $1$ 。

最后，答案的统计，根据我们最初写出的海盗代码基本形式，我们加答案时，只需要加每个固定的长度的整块的价值与剩下散块的数量即可，形式化的说，对于每个 $k$ ，统计答案 $ans$ 时，公式为：

ans=\sum_{i=2}^{k}dp_i*(num_{k-i,0}+num_{k-i,1})

最后需要注意的是取模问题。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;

const int N=5005;
const ll mod=1e9+7;
int n;
ll fib[N],f[N][2],num[N][2],dp[N],s[N];

int main()
{
    cin>>n;
    fib[1]=fib[2]=1;
    for(int i=3;i<=n+1;i++) fib[i]=(fib[i-1]+fib[i-2])%mod;
    num[0][0]=1;
    for(int i=1;i<=n;i++){
        f[i][0]=(f[i-1][1]+f[i-1][0])%mod;
        num[i][0]=(num[i-1][1]+num[i-1][0])%mod;
        f[i][1]=(f[i-1][0]+num[i-1][0]*fib[i+1])%mod;
        num[i][1]=num[i-1][0];
    }
    s[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            dp[i]=(dp[i]+dp[i-j-1]*num[j][1])%mod;
            dp[i]=(dp[i]+f[j][1]*s[i-j-1]%mod)%mod;
            s[i]=(s[i]+s[i-j-1]*num[j][1]%mod)%mod;
        }
    }
    for(int i=1;i<=n;i++){
        ll ans=0;
        for(int j=2;j<=i;j++){
            ans=(ans+dp[j]*(num[i-j][0]+num[i-j][1])%mod)%mod;
        }
        cout<<ans<<" ";
    }

    return 0;
}

C. Rolete

因为自动拉窗帘在某窗帘到顶后会额外产生开销，所以先使用自动再使用手动一定不劣于先使用手动再使用自动。

对于每个 $h$ ，我们记录 $f_h(x)$ 表示高度为 $h$ 时，我们先用自动拉窗帘拉 $x$ 厘米时所用的时间。根据题意可知：

f_h(x)=s\cdot x+t\cdot \sum_{i,a_i>h+x}(a_i-h-x)+k\cdot \sum_{i,a_i<x}(x-a_i)

直觉告诉我们，决策是有单调性的，考虑证明，计算一下 $f_h(x+1)$ 与 $f_h(x)$ 的差为：

\Delta(x)=s-t\cdot \left|\{i|a_i>h+x\}\right|+k\cdot \left|\{i|a_i\le x\}\right|

随着 $x$ 的增大， $\left|\{i|a_i>h+x\}\right|$ 不增，所以第二项不降， $\left|\{i|a_i\le x\}\right|$ 不降，所以第三项不降，所以整体是不降的，所以当我们找到第一个 $\Delta x\ge 0$ 时，就找到了最有决策点，可以用二分来求解。

点击展开代码

#include<iostream>
#include<algorithm>
#include<string.h>
#define int long long
using namespace std;
typedef long long ll;

const int N=1e5+5;
int n,t,s,k,q,h;
ll ma;
ll a[N];
ll cnt[N],sum[N];

int cle(int x)
{
    if(x>ma) return n;
    if(x<0) return 0;
    return cnt[x];
}

int cge(int x)
{
    if(x>ma) return 0;
    if(x<0) return n;
    return cnt[ma]-cnt[x-1];
}

bool check(int x)
{
    ll wx=cge(h+x+1),wy=cle(x);
    return s-wx*t+wy*k>=0;
}

ll calc(int h,int x)
{
    int wh=h+x;
    int wx=cge(wh+1);
    ll wxy=0;
    if(ma>wh) wxy=sum[ma]-sum[wh];
    wxy=(wxy-wx*wh)*t;
    int wy=cle(x-1);
    ll wyx=0;
    if(x-1>=0) wyx=sum[x-1];
    wyx=(x*wy-wyx)*k;
    return (ll)s*x+wxy+wyx;
}

signed main()
{
    cin>>n>>t>>s>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        cnt[a[i]]++,sum[a[i]]+=a[i];
        ma=max(ma,a[i]);
    }
    for(int i=1;i<N;i++) cnt[i]+=cnt[i-1],sum[i]+=sum[i-1];
    cin>>q;
    while(q--){
        cin>>h;
        int l=0,r=ma,res;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)) r=mid-1,res=mid;
            else l=mid+1;
        }
        cout<<calc(h,res)<<" ";
    }

    return 0;
}

D. Trokut

首先理一下题目信息，三角形的构成条件是已经有一个点连了两条边，所以除非别无选择，否则不会有人去选已经用过的点，所以已用的点可以视作删除。还有一个重要的点就是不能有两条线段相交，我们称可以互相连边的点集称为一个“块”，转化一下即，每选择两个点，就会将原本两点所在的块分割为两个块。

推博弈转化，设当前有一段连续的、尚未被分割的顶点，长度为 $n$ ，记它的 SG 值为 $sg[n]$ 。

在这段中连接两个顶点后：

这两个端点不能再作为普通操作端点使用，否则会形成必败结构；
这条弦把当前区域分成左右两个互不影响的区域；
如果两侧分别有 $i$ 和 $n-2-i$ 个可用顶点，那么新状态的 SG 值为

sg[i]\, \^\ \,sg[n-2-i]

因此：

\begin{array}{l} sg[0]=0\\ sg[1]=0\\ sg[n]=mex{sg[i]\, \^\ \,sg[n-2-i]|0<=i<=n-2} \end{array}

其中 $mex$ 是集合中没有出现的最小非负整数。当 $sg[n]!=0$ 时，先手必胜，即 Lucija 获胜；否则后手必胜，即 Ivan 获胜。

然后根据打表观察，可以得出一个结论：

sg[n+34]=sg[n](n\ge 70)

然后就完了。

点击展开代码

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const bool f[]={0,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1};
int n;
int main(){
	int t;
    cin>>t;
	while(t--){
        cin>>n;
		if(n<=69) puts(f[n]?"Lucija":"Ivan");
		else puts(f[(n-70)%34+70]?"Lucija":"Ivan");
	}
    return 0;
}

A. Bitovi​

B. Piratski kod​

C. Rolete​

D. Trokut​

A. Bitovi

B. Piratski kod

C. Rolete

D. Trokut