二維碼
企資網(wǎng)

掃一掃關(guān)注

當(dāng)前位置: 首頁 » 企業(yè)資訊 » 熱點 » 正文

Tokitsukaze_and_Good_01

放大字體  縮小字體 發(fā)布日期:2022-06-23 21:24:19    作者:葉麓菲    瀏覽次數(shù):103
導(dǎo)讀

題目:codeforces/contest/1678/problem/B2題意:給定長度為偶數(shù)得一個01串,通過修改它得某些位置,使得它最終每個字符相同得連續(xù)段,得長度都為偶數(shù)。現(xiàn)在可以將字符上任意位置得字符修改為

題目:
codeforces/contest/1678/problem/B2

題意:給定長度為偶數(shù)得一個01串,通過修改它得某些位置,使得它最終每個字符相同得連續(xù)段,得長度都為偶數(shù)。

現(xiàn)在可以將字符上任意位置得字符修改為0或1.

1、求最小需要改變得位置,才能滿足上述條件。

2、同時,在保證最小改變數(shù)量得前提下,求最終能得到得最小得連續(xù)段個數(shù)。

參考:
codeforces/blog/entry/102631

思路:

要使每個字符相同得連續(xù)段,長度都為偶數(shù),則要求每兩個相鄰得字符需要相等,即

對于相鄰字符相同得位置,我們無需改動;對于相鄰字符不同得位置,我們考慮變?yōu)?,1對于最終得到得最小連續(xù)段得影響。我們用

表示第個位置,以0/1結(jié)尾得最小得連續(xù)段,從前往后計算即可。

#include<bits/stdc++.h> using namespace std;const int maxn = 200010;const int mod = 1e9 + 7;int n;char s[maxn];int dp[maxn][2];void solve() {scanf("%d", &n);scanf("%s", s);for (int i = 0; i <= n; ++i) {dp[i][0] = dp[i][1] = maxn;// 用maxn標(biāo)記不可達(dá) }int ans = 0;if (s[1] != s[0]) {++ans;dp[1][0] = dp[1][1] = 1;} else {int val = s[1] - '0';dp[1][val] = 1;}for (int i = 3; i < n; i += 2) {if (s[i-1] != s[i]) {++ans;// 對于需要改變得位置,它可以選擇取0和1做為結(jié)尾 dp[i][0] = min(dp[i-2][0], dp[i-2][1] + 1);dp[i][1] = min(dp[i-2][0] + 1, dp[i-2][1]);}else {int val = s[i] - '0';// 對于不能改變得位置,默認(rèn)取它原來得0/1字符 dp[i][val] = min(dp[i-2][val], dp[i-2][1-val] + 1);}}printf("%d %d\n", ans, min(dp[n-1][0], dp[n-1][1]));}int main() {int t;scanf("%d", &t);while (t--) {solve();}return 0;}

 
(文/葉麓菲)
免責(zé)聲明
本文僅代表作發(fā)布者:葉麓菲個人觀點,本站未對其內(nèi)容進(jìn)行核實,請讀者僅做參考,如若文中涉及有違公德、觸犯法律的內(nèi)容,一經(jīng)發(fā)現(xiàn),立即刪除,需自行承擔(dān)相應(yīng)責(zé)任。涉及到版權(quán)或其他問題,請及時聯(lián)系我們刪除處理郵件:weilaitui@qq.com。
 

Copyright ? 2016 - 2025 - 企資網(wǎng) 48903.COM All Rights Reserved 粵公網(wǎng)安備 44030702000589號

粵ICP備16078936號

微信

關(guān)注
微信

微信二維碼

WAP二維碼

客服

聯(lián)系
客服

聯(lián)系客服:

在線QQ: 303377504

客服電話: 020-82301567

E_mail郵箱: weilaitui@qq.com

微信公眾號: weishitui

客服001 客服002 客服003

工作時間:

周一至周五: 09:00 - 18:00

反饋

用戶
反饋

主站蜘蛛池模板: 野外三级国产在线观看| 丰满人体bbw| caoporn成人| 欧美午夜免费观看福利片| 国产精品无码电影在线观看 | 成人无码嫩草影院| 四虎在线观看一区二区| 中文字幕无码乱人伦| 绝世名器np嗯嗯哦哦粗| 小明发布永久在线成人免费| 加勒比精品久久一区二区三区| 三上悠亚ssni_229在线播放| 精品伊人久久久久网站| 女仆的味道hd中字在线观看| 人妖系列免费网站观看| 97色在线视频观看香蕉| 欧美精品18videosex性欧美| 国产精品另类激情久久久免费| 亚洲va乱码一区二区三区| 黄色小说网站在线观看| 日本三级高清电影全部| 午夜视频在线观看按摩女| а√天堂中文最新版地址| 男女午夜性刺激| 国产高清一区二区三区视频| 亚洲午夜在线一区| 黄网视频在线观看| 成人综合在线视频免费观看完整版 | 视频一区视频二区制服丝袜| 无翼乌全彩绅士知可子无遮挡| 午夜a级理论片在线播放| a级日本高清免费看| 欧美性色黄在线视| 国产在线精品观看一区| 中文字幕66页| 淫444kkk| 国产日韩在线观看视频| 中文字幕理伦午夜福利片| 男朋友想吻我腿中间部位 | 又粗又大又长又爽免费视频| a视频在线观看免费|