abc418 赤石寄

Clay_L · 2025-08-10 16:44:27 · 个人记录

abc418赛后总结

A

题意

问字符串后缀是否为 tea。

解法

sb题不需要解法

B

题意

计字符 s 中 t 开头 t 结尾的子串 t 中 t 个数为 x，问 \max\left\{\frac{x-2}{\left|t\right|-2}\right\}。

算法

暴力。

C

题意

有 n 种物品，每种 a_i 个。q 次询问，问取最少多少物品必定可以拿到 b 个相同物品。

算法

官方题解什么 shi？看不懂。说说我自己对这题的理解。

抽屉原理，想取到 b 个就必须先取所有物品各 b-1 个（若物品数量小于 b 就取物品数量个）。

我们可以对 a 排序，这样更好处理。

因为 a_i\le10^6，我们可以预处理每一个 b。

设 r 为 a 中大于等于这个 b 的元素个数，则 ans_{b+1}=ans_b+n-r+1。

D

题意

给定长度为 n 的 01 串 s。现有操作：对于一个 01 串 a，选定一个 i\left(1\le i<n,i\in\Z\right)，若 a_i=a_{i+1}，则将 a_i 和 a_{i+1} 替换为 1，否则替换为 0。

对于 a 串是否合规，当且仅当任意操作后 |a|=1 且 a 中只有一个 1 存在。

问 s 中有多少个合规的子串。

算法

一眼 dp。

设 dp_{i,1} 为以第 i 个元素结尾的子串中合规的子串个数，dp_{i,0} 为以第 i 个元素结尾的子串中不合规的子串个数。

合规的子串处理后会变为 1，不合规的会变为 0。

若第 i 位为 1，则它与以第 i-1 位结尾的任何一个合规子串结合都是合规的，反之则不合规。

同理，若第 i 位为 0，则它与以第 i-1 位结尾的任何一个合规子串结合都是不合规的，反之则合规。

综上所述：

此时答案为：

对应代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;
int n,dp1[N],dp0[N];
string s;
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>s;
    s=' '+s;
    for(int i=1;i<=n;i++){
        if(s[i]=='1'){
            dp1[i]=dp1[i-1]+1;
            dp0[i]=dp0[i-1];
        }
        else{
            dp1[i]=dp0[i-1];
            dp0[i]=dp1[i-1]+1;
        }
        dp1[n+1]+=dp1[i];
    }
    cout<<dp1[n+1];
    return 0;
}

还能再优化一小点。

因为以第 i 个元素结尾的子串共 i 个，则有 dp_{i,0}+dp_{i,1}=i。

可推出 dp_{i,0}=i-dp_{i,1}。

由此可省去一维。

所以 dp 方程可化为：

此时答案为：

对应代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;
int n,dp[N];
string s;
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>s;
    s=' '+s;
    for(int i=1;i<=n;i++){
        if(s[i]=='1')dp[i]=dp[i-1]+1;
        else dp[i]=i-dp[i-1]-1;
        dp[n+1]+=dp[i];
    }
    cout<<dp[n+1];
    return 0;
}