专栏文章

abc418 赤石寄

CClay_L
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioez58w
此快照首次捕获于
2025/12/02 18:07
3 个月前
此快照最后确认于
2025/12/02 18:07
3 个月前
查看原文

abc418赛后总结

A

题意

问字符串后缀是否为 tea。

解法

sb题不需要解法

B

题意

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

算法

暴力。

C

题意

有 nn 种物品，每种 aia_i 个。qq 次询问，问取最少多少物品必定可以拿到 bb 个相同物品。

算法

官方题解什么 shi？看不懂。说说我自己对这题的理解。
抽屉原理，想取到 bb 个就必须先取所有物品各 b−1b-1 个（若物品数量小于 bb 就取物品数量个）。
我们可以对 aa 排序，这样更好处理。
因为 ai≤106a_i\le10^6，我们可以预处理每一个 bb。
设 rr 为 aa 中大于等于这个 bb 的元素个数，则 ansb+1=ansb+n−r+1ans_{b+1}=ans_b+n-r+1。

D

题意

给定长度为 nn 的 0101 串 ss。现有操作：对于一个 0101 串 aa，选定一个 i(1≤i<n,i∈Z)i\left(1\le i<n,i\in\Z\right)，若 ai=ai+1a_i=a_{i+1}，则将 aia_i 和 ai+1a_{i+1} 替换为 11，否则替换为 00。
对于 aa 串是否合规，当且仅当任意操作后 ∣a∣=1|a|=1 且 aa 中只有一个 11 存在。
问 ss 中有多少个合规的子串。

算法

一眼 dpdp。
设 dpi,1dp_{i,1} 为以第 ii 个元素结尾的子串中合规的子串个数，dpi,0dp_{i,0} 为以第 ii 个元素结尾的子串中不合规的子串个数。
合规的子串处理后会变为 11，不合规的会变为 00。
若第 ii 位为 11，则它与以第 i−1i-1 位结尾的任何一个合规子串结合都是合规的，反之则不合规。
同理，若第 ii 位为 00，则它与以第 i−1i-1 位结尾的任何一个合规子串结合都是不合规的，反之则合规。
综上所述：
dpi,1={dpi−1,1+1(si=1)dpi−1,0(si=0),dpi,0={dpi−1,1(si=1)dpi−1,0+1(si=0).dp_{i,1}=\begin{cases}dp_{i-1,1}+1\left(s_i=1\right) \\ dp_{i-1,0}\left(s_i=0\right) \end{cases} , dp_{i,0}=\begin{cases}dp_{i-1,1}\left(s_i=1\right) \\ dp_{i-1,0}+1\left(s_i=0\right) \end{cases} .
此时答案为：
∑i=1ndpi,1\sum^n_{i=1}dp_{i,1}
对应代码：
CPP
#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;
}
还能再优化一小点。
因为以第 ii 个元素结尾的子串共 ii 个，则有 dpi,0+dpi,1=idp_{i,0}+dp_{i,1}=i。
可推出 dpi,0=i−dpi,1dp_{i,0}=i-dp_{i,1}。
由此可省去一维。
所以 dpdp 方程可化为：
dpi={dpi−1+1(si=1)i−1−dpi−1(si=0)dp_i=\begin{cases}dp_{i-1}+1\left(s_i=1\right) \\ i-1-dp_{i-1}\left(s_i=0\right) \end{cases}
此时答案为：
∑i=1ndpi\sum^n_{i=1}dp_i
对应代码：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...