二維碼
企資網(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

反饋

用戶
反饋

主站蜘蛛池模板: 橘子没熟svk| 黄色三级在线播放| 欧美疯狂xxxx乱大交视频| 天天插在线视频| 免费看国产一级特黄aa大片| 一级看片免费视频| 精品久久亚洲中文无码| 好硬啊进得太深了h动态图120秒| 嗨动漫在线观看| 一级美国乱色毛片| 男女啪啪免费体验区| 天堂а√在线地址| 亚洲视频综合网| 777777农村一级毛片| 欧美一级做一a做片性视频| 国产白袜脚足j棉袜在线观看 | 久久黄色免费网站| 91香蕉视频导航| 日本免费人成黄页在线观看视频| 国产二级一片内射视频播放| 久久99精品久久久久久国产| 综合五月天婷婷丁香| 女人与大拘交口述| 亚洲第一精品福利| 18禁强伦姧人妻又大又| 极品人体西西44f大尺度| 国产在线视频www色| 中文字幕日韩一区二区三区不| 精品国产欧美一区二区| 夏夏和三个老头第二部| 亚洲国产欧美在线人成北岛玲| 日本人强jizz多人| 日本三级韩国三级三级a级播放 | 国产一卡2卡3卡4卡无卡免费视频| 中文字幕亚洲综合久久| 百合h肉动漫无打码在线观看| 国产高清精品入口91| 乱中年女人伦av三区| 羞羞漫画喷水漫画yy视| 天天视频官网天天视频在线| 亚洲婷婷综合色高清在线|