题目：C-小美的01串翻转_牛客周赛 Round 9
链接：https://ac.nowcoder.com/acm/contest/63869/C
思路：
01字符串s .....,s[i-1],s[i],.....
首先我们定义f[n][2]，其中[2]表示状态位，也就是当前第i位变与不变（0表示
展开全文
枚举每个子串，算它变成“相邻都不同”最少要改几位，然后全部加起来。
void solve(){
string s;cin>>s;
int n=s.size();
vi pre(n+1,0);
for(int i=0;i<n;++i){
展开全文
问题分析
该问题的核心在于计算所有子串的“权值”之和。给定一个 串，权值的定义是将其转换为“相邻字符均不相等”的字符串所需的最小翻转次数。
1. 目标状态分析
对于任意长度为 的字符串，满足“相邻字符都不相等”的目标状态仅有两种：
模式 A：010101...（以 '0' 开头）
模式 B：1
展开全文
注意到, 最终的状态一定是下面的两种
因此预处理出每个字符变成对应字符的代价, 取最小值累计答案即可, 算法时间复杂度
#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begi
展开全文
很明显的树形dp问题，定义代表了当前节点选或者不选。
如果不选，那么：
如果选，在满足权值和条件的情况下，。其中d为选了其中一个孩子后的最大取值，不明白的话可以见代码。
import sys
from bisect import bisect_left
from math import inf
展开全文
思路对于这种相邻字符不同的01串，一个很经典的思想，就是这种串只有两种形式 或者 , 所以,只需要求得原字符串转换到他们的较小值就行了 ，发现枚举是 的，我们采取前缀和进行优化，提前算出 来代表前 个字符与标准串的不同个数，优化到 。Code
void solve()
{
ci
展开全文
思路
01 串相邻字符都不相等只有两种情况：
以0开头：010101....
以1开头：101010....
因此可以遍历字符串S的所有连续子串，模拟子串变换到情况1和情况2的操作次数，取两者中的最小值，就是该字串的权值。
保存 010101...&preview=true">操作次
展开全文
题意
求使得所有子串相邻字符都不同的情况下，修改的最小操作次数。
思路
对于任意一个 01 串，最终变成的是 01010101… 或 10101010…。
是否可以枚举改变的位，然后求包含它子串的个数，然后把这个个数加入到对答案的贡献呢？
答案是不行的。
例如 1110000111，可以变成 101
展开全文
题解一（枚举）
枚举所有起点开始的子串，求出以 0 开头或以 1 开头的最小权值，并累加到结果中。
写法 1：
fun main(args: Array<String>) {
val str = nextString()
var ret = 0
for (i in
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
