有问题请评论区聊喵！！！

A.Kato_Shoko

问题回顾

给定长度为 $N$ （ $1\le N\le10^5$ ）的字符串 $S$ 。
从 $S$ 中选取一些字符，对其进行任意重排求能否组成目标字符串 Kato_Shoko，
如果可以，输出 YES 以及需要删除的最少字符数
若无解输出 NO。

核心思路

最终字符串要变成 Kato_Shoko，也就是说最终字符串长度只能是 $10$ ；

统计字符数量
如果有字符串 Kato_Shoko 对应的数量的字符，那么就可以，否则就输出 NO。
输出 YES 以及 $n-10$ 。

代码展示

#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128=__int128_t;

const ll N = 1e6 + 5, mod = 1e9+7, inf = 2e18;
const double esp=1e-9;
double PI=3.1415926;

il void solve(){
    ll n;
    string s;
    cin>>n>>s;
    map<char,int>mp;
    for(auto ch:s)mp[ch]++;
    string t="Kato_Shoko";
    for(auto ch:t){
        if(--mp[ch]<0){
            cout<<"NO";
            return ;
        }
    }
    cout<<"YES "<<n-10;
}

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

B.白绝大军

题解

核心思路

贪心最优解是：每次选取当前最大的可用项，即把按降序排序，依次累加总活跃度直到达到或超过 $\text{T}$ 。理由直观：若希望用最少的项达到一定和，必然优先使用大的项（换位交换证明也很容易写出）。

证明

要最小化选取项数使得和 $\ge \text{need}$ ，任何最优解中若存在两项 $x < y$ ，而我们选了 $x$ 但没有选 $y$ （且 $y$ 可选），将 $x$ 换为 $y$ 能使总和增加或不变，项数不变，因此不会变差。

总结

关键在于把每个 $a_i$ 按 $b_i$ 次展开为一个“可选项”集合，然后按降序贪心取数直到满足目标。（特别是 $\sum b_i \le 2\times 10^5$ ）。

代码展示

#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll N = 1e5 + 5, mod = 998244353, inf = 2e18;
const double esp=1e-9;
double PI=3.1415926;

il void solve(){
    ll n,t,sum=0;
    cin>>n>>t;
    vector<ll>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }

    if(sum>=t){
        cout<<0;
        return ;
    }

    vector<ll>all;
    for(int i=1;i<=n;i++){
        ll b;cin>>b;
        while(b--){
            all.push_back(a[i]);
        }
    }
    sort(all.rbegin(),all.rend());
    ll ans=0;
    for(auto v:all){
        sum+=v;
        ans++;
        if(sum>=t){
            cout<<ans;
            return ;
        }
    }
    cout<<-1;
}

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

C.重组猎魔团

问题回顾

给定长度为 $N$ （ $1\le N\le8$ ）的符文字符串 $S$ 和咒语力量值 $D$ （ $1\le D\le100$ ）。
从 $S$ 中选取一个非空子集，对其中数字进行任意重排（允许前导零）得到一个整数，要求该整数能被 $D$ 整除。
求所有可行结果中的最小值，若无解输出 $-1$ 。

核心思路

由于 $N\le8$ ，可以直接枚举：

子集枚举：用位掩码 mask 从 $1$ 到 $(1\ll N)-1$ ，筛选数字。
排列枚举：对当前子集排序后，使用 next_permutation 枚举所有排列。
验证整除：将排列拼成整数 res，若 res % D == 0，则更新最小值。

代码展示

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 1e5 + 5, mod = 998244353, inf = 1e18;

void solve(){
    int n,d;
    cin>>n>>d;
    string s;
    cin>>s;
    vector<int>a;
    for(auto c:s){
        a.push_back(c-'0');
    }
    ll ans=inf;
    for(ll mask=1;mask<(1ll<<n);mask++){
        vector<int>num;
        for(int i=0;i<n;i++){
            if((mask>>i)&1){
                num.push_back(a[i]);
            }
        }
        sort(num.begin(),num.end());
        do{
            ll res=0;
            for(auto v:num)res=res*10+v;
            if(res%d==0)ans=min(ans,res);
        }while(next_permutation(num.begin(),num.end()));
    }
    cout<<(ans==inf?-1:ans);
}

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

    }
    return 0;
}

D.谁敢动资本的蛋糕

问题分析

给定一个长度为 $N$ 的数组 $A=[a_1,\dots,a_N]$ 。每次可以选取两个数 $x, y$ ，将它们删除并插入 $z = x\oplus y$ ，同时支付代价经过 $N-1$ 次操作后，数组归约为单个数，要求计算出总代价的最小值。

解题思路

这个题有很多种解法，我说一下出这个题的时候的解法，

方法一

利用恒等式

x + y = (x \oplus y) + 2(x \& y).

对一次合并（把两个数 $x, y$ 合并为 $x \oplus y$ ）的代价定义为
$\text{cost} = 2(x \& y) = x + y - (x \oplus y).$
合并后数组中元素和 $S$ 会减少该 $\text{cost}$ 。
反复合并直到只剩下一个数时，最终留下的数恰好是整体异或
$X = a_1 \oplus a_2 \oplus \cdots \oplus a_n.$
因此所有合并造成的总成本为初始数组和与最终剩余值之差：
$\text{总成本} = sum - xor,$
并且该值与合并顺序无关。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve(){
    ll n;
    cin>>n;
    ll sum=0,XOR=0;
    while(n--){
        ll a;cin>>a;
        sum+=a;
        XOR^=a;
    }
    cout<<sum-XOR;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);   
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

方法二

一开始想利用利用恒等式 $x + y = (x \oplus y) + 2(x \& y).$ 来出这个题的，出完后过了几天突然想到这个丑陋的解法了，那就是利用二进制位独立性的特性：

对每个二进制位 $b$ （ $0\le b\le 60$ ），统计数组中该位为 1 的元素个数 $c_b$ 。

在第 $b$ 位上，每合并一对在该位均为 1 的数，会消除两个 1，成本为 $2^{b}*2$ 。

最多可以配对合并 $\lfloor c_b/2\rfloor$ 次，因此第 $b$ 位的最小总成本为

2^{b}*2*\left\lfloor \frac{c_b}{2}\right\rfloor

将所有位的成本累加，即得到全局最优成本。

整体时间复杂度为 $O(N\times L)$ ，其中 $L=61$ ，空间复杂度为 $O(L)$ 。

实现步骤

读入整数 n；
初始化长度 61 的计数数组 cnt，初值为 0；
对数组中每个元素 x，遍历位 $b=0\ldots 60$ ，若当前位的二进制位 1，则 cnt[b]++。
对每个位 $b$ ，令 pairs = cnt[b]/2，将 ans += pairs * (1LL<<b)；
输出 ans*2。

代码展示

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve(){
    int n;
    cin>>n;
    vector<ll>cont(70);
    for(int i=1;i<=n;i++){
        ll x;
        cin>>x;
        for(int mask=0;mask<=60;mask++){
            if((x>>mask)&1){
                cont[mask]++;
            }
        }
    }
    ll ans=0;
    for(int mask=0;mask<=60;mask++){
        ans+=(1ll<<mask)*(cont[mask]>>1);
    }
    cout<<(ans<<1)<<'\n';
}

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

E.构造序列

思路

把一个合法序列看作有 $k$ 个 R，R 长度为 $\ell_i$ 正整数且严格递增：

\ell_1 < \ell_2 < \dots < \ell_k,\qquad \sum_{i=1}^k \ell_i = n.

因此问题可拆成两部分：

计数有多少种严格递增的长度序列 $(\ell_1,\dots,\ell_k)$ （即把 $n$ 分成 $k$ 个互不相等的正整数且按升序排列）。设该计数为 $P(n,k)$ 。
对于固定的某个长度序列，取值有多少选择？第一个 R 有 $m$ 种选择，之后每个 R 必须与前一 R 不同，因此总数为 $m\cdot (m-1)^{\,k-1}$ 。

把两部分相乘并对所有合法的 $k$ 求和即可：

\text{ans}=\sum_{k\ge1} P(n,k)\cdot m\cdot (m-1)^{k-1}\pmod{10^9+7},

其中只考虑满足最小和约束的 $k$ ： $\displaystyle \frac{k(k+1)}{2}\le n$ 。

$P(n,k)$ 的计算

在 OI-Wiki的相关章节-互异分拆数亦有记载

我们用 DP 计数把整数 $i$ 划分为 $j$ 个 严格递增 的正整数的方案数，记

dp[i][j]=P(i,j).

初始 $dp[0][0]=1$ ，其余为 $0$ 。

递推：

dp[i][j]=dp[i-j][\,j-1\,] + dp[i-j][\,j\,].

递推的证明

我们把所有把 $i$ 拆成 $j$ 个严格递增正整数的方案，按照最小项的值分成两类来计数。

情况 A：最小项等于 $1$ .
假设某一拆分为

\ell_1=1<\ell_2<\dots<\ell_j,\qquad \sum_{t=1}^j\ell_t=i.

去掉这一个 $1$ ，剩下 $j-1$ 个部分 $\ell_2,\dots,\ell_j$ 。由于原序列严格递增且 $\ell_2\ge2$ ，对剩余的每个部分减去 $1$ 得到

\ell_2-1<\ell_3-1<\dots<\ell_j-1,

这是一组严格递增的正整数，共 $j-1$ 项，且其和为

(\ell_2+\dots+\ell_j)-(j-1)=(i-1)-(j-1)=i-j.

因此，“最小项为 $1$ ” 的所有拆分与把 $i-j$ 拆成 $j-1$ 个严格递增正整数的一一对应，方案数为 $dp[i-j][\,j-1\,]$ 。

情况 B：最小项至少为 $2$ .
如果拆分中每一项都 $\ge2$ ，令 $\ell'_t=\ell_t-1$ （对所有 $t$ ）。则每个 $\ell'_t\ge1$ ，且仍保持严格递增，项数为 $j$ ，并且和为

\sum_t \ell'_t = \sum_t \ell_t - j = i-j.

所以“最小项 $\ge2$ ” 的拆分集合与把 $i-j$ 拆成 $j$ 个严格递增正整数的一一对应，方案数为 $dp[i-j][\,j\,]$ 。

合并。 由于两类互不相交并覆盖所有可能，故

dp[i][j]=dp[i-j][\,j-1\,] + dp[i-j][\,j\,],

从而得到所述递推。

边界注意。 若 $i<j$ 则 $dp[i][j]=0$ 。若最小可能和 $1+2+\dots+j=\tfrac{j(j+1)}{2}>i$ 也可直接剪枝为 0。

复杂度

DP 的规模为 $O(n\cdot K)$ ，其中 $K$ 为满足 $\tfrac{K(K+1)}{2}\le n$ 的最大 $K$ 。
当 $n\le 10^5$ 时 $K\le 450$ ，总体复杂度 $O(nK)$ 。

代码展示

#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll N = 2e5 + 5, mod = 1e9+7, inf = 2e18;
const double esp=1e-9;
double PI=3.1415926;

il ll quikc_mi(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1){
            ans=ans*a%mod;
        }
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}

il void solve(){
    ll n,m;
    cin>>n>>m;
    const ll J=450;
    vector<vector<ll>>dp(n+1,vector<ll>(J+1));
    dp[0][0]=1;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=min(i,J);j++){
            dp[i][j]=(dp[i-j][j-1]+dp[i-j][j])%mod;
        }
    }

    ll ans=0;
    for(ll k=1;k<=J;k++){
        if(n<k*(k+1)/2)break;
        ll p=quikc_mi(m-1,k-1);
        ll res=dp[n][k];
        res=res*m%mod*p%mod;
        ans=(ans+res)%mod;
    }
    cout<<ans;
}

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

F.区间或与与再异或之和最大值

问题回顾

给定长度为 $N$ 的正整数序列 $a_1,\dots,a_N$ ，需要将序列划分成若干连续子区间，最大化（原题式子在此省略，可按题面补充）

其中 $O(l,r)=a_l\lor\cdots\lor a_r$ , $A(l,r)=a_l\land\cdots\land a_r$ 。

核心思路

固定右端点 $i$ ，从 $j=i-1$ 向左扩展，区间 OR 值 $O(j+1,i)$ 单调不减、AND 值 $A(j+1,i)$ 单调不增，
每种 $(O,A)$ 组合在向左扩时只会变化 $\le30+30$ 次，总共 $O(60)$ 个不同区间块。

用一个结构体 Block 存储每段相同值块：其中该块覆盖所有 $j+1\in[L..R]$ 。

定义 $\text{dp}[i]$ 为前 $i$ 个元素的最优值，转移：

（原转移公式请按题面补充）

为高效取区间最大值，引入线段树支持 $O(\log N)$ 的点更新与区间最大查询。

整体复杂度 $O(N\times60\times\log N)$ 。

算法流程

初始化：令 $dp[0]=0$ ，构造大小为 $N+1$ 的线段树 st，并执行 st.update(0,0)。
对每个 $i=1,2,\dots,N$ ：
1. 构造新块列表 nxt：
  - 首先插入单元素块 $(o=a_i,\ a=a_i,\ L=i)$ ；
  - 遍历旧块 $(o,a,L)$ ，计算新值 $(o\!\lor\!a_i,\ a\!\land\!a_i)$ ，并将相同 $(o,a)$ 的块合并。
2. 确定每块的右端：对第 $k$ 块设置 $R_k \;=\; \begin{cases} i, & k=0,\\ L_{k-1}-1, & k>0. \end{cases}$
3. DP 转移：对每块 $(o,a,L,R)$ ， $val = o \oplus a,$ 查询 $mx = \texttt{st.query}(L-1,\,R-1),$ 并更新 $dp[i] = \max\bigl(dp[i],\,mx + val\bigr).$
4. 更新线段树：st.update(i, dp[i])，然后将 blocks 替换为 nxt。
最终输出 $dp[N]$ 。

复杂度分析

每个 $i$ 生成 $O(60)$ 个块，
每个块做一次 $O(\log N)$ 的线段树查询，
更新一次点值。
总计 $O(N\times60\times\log N)$ ，满足 $N\le2\times10^5$ 。

代码展示

#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128=__int128_t;

const ll N = 2e5 + 5, mod = 998244353, inf = 1e18;
const double esp=1e-3;
double PI=3.1415926;

ll tree[N<<2];
il int lson(int i){
    return i<<1;
}
il int rson(int i){
    return i<<1|1;
}

il void up(int i){
    tree[i]=max(tree[lson(i)],tree[rson(i)]);
}

il void updata(int i,int pl,int pr,int L,int R,ll val){
    if(L<=pl&&pr<=R){
        tree[i]=val;
        return ;
    }
    int mid=pl+pr>>1;
    if(L<=mid){
        updata(lson(i),pl,mid,L,R,val);
    }else{
        updata(rson(i),mid+1,pr,L,R,val);
    }
    
    up(i);
}

il ll query(int i,int pl,int pr,int L,int R){
    if(L<=pl&&pr<=R){
        return tree[i];
    }
    ll ans=-inf;
    int mid=pl+pr>>1;
    if(L<=mid){
        ans=max(ans,query(lson(i),pl,mid,L,R));
    }
    if(R>mid){
        ans=max(ans,query(rson(i),mid+1,pr,L,R));
    }
    return ans;
}

il void solve(){
    int n;
    cin>>n;
    vector<ll>a(n+1),dp(n+1,-inf);
    //dp[i]:前i个元素的最优值
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dp[0]=0;
    //下标从1开始，但是1点存的是dp[0],2点存的是dp[1]...
    updata(1,1,n+1,1,1,dp[0]);
    struct Block {
        ll or_v, and_v;
        int L, R;
    };
    vector<Block>blocks;   // 上一轮的块列表
    vector<Block>nxt;      // 用于构建新一轮的块

    for(int i=1;i<=n;i++){
        nxt.clear();
        //新区间[i,i]
        nxt.push_back({a[i], a[i], i, 0});

        //拓展旧块
        for(auto &[or_v,and_v,L,R]:blocks){
            ll new_or=or_v|a[i],new_and=and_v&a[i];

            if(nxt.back().or_v==new_or&&nxt.back().and_v==new_and){
                //合并：只要更新最小的 L
                nxt.back().L = min(nxt.back().L, L);
            }else{
                //新开一个块
                nxt.push_back({new_or,new_and,L,0});
            }
        }

        //填充R，按下标0..sz-1顺序，块0的R=i，之后R=前一个块的L-1
        int sz=nxt.size();
        for(int k=0;k<sz;k++){
            nxt[k].R=(k==0?i:nxt[k-1].L-1);
        }

        ll res=-inf;
        for(auto [o,a,L,R]:nxt){
            ll val=o^a;
            //因为线段树偏移，所以查询区间刚好是L,R
            ll max_dp=query(1,1,n+1,L,R);
            res=max(res,max_dp+val);
        }
        dp[i]=res;
        //开点
        updata(1,1,n+1,i+1,i+1,dp[i]);
        blocks.swap(nxt);
    }
    cout<<dp[n];
}

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

题解 | #Round 99#

有问题请评论区聊喵！！！

A.Kato_Shoko

问题回顾

核心思路

代码展示

B.白绝大军

题解

核心思路

证明

总结

代码展示

C.重组猎魔团

问题回顾

核心思路

代码展示

D.谁敢动资本的蛋糕

问题分析

解题思路

方法一

方法二

实现步骤

代码展示

E.构造序列

思路

$P(n,k)$ 的计算

递推的证明

复杂度

代码展示

F.区间或与与再异或之和最大值

问题回顾

核心思路

算法流程

复杂度分析

代码展示

最后有什么疑问可以在评论区指出来喵！！！

题解 | #Round 99#

有问题请评论区聊喵！！！

A.Kato_Shoko

问题回顾

核心思路

代码展示

B.白绝大军

题解

核心思路

证明

总结

代码展示

C.重组猎魔团

问题回顾

核心思路

代码展示

D.谁敢动资本的蛋糕

问题分析

解题思路

方法一

方法二

实现步骤

代码展示

E.构造序列

思路

的计算

递推的证明

复杂度

代码展示

F.区间 或 与 与 再 异或 之和最大值

问题回顾

核心思路

算法流程

复杂度分析

代码展示

最后有什么疑问可以在评论区指出来喵！！！

$P(n,k)$ 的计算

F.区间或与与再异或之和最大值