二維碼
        企資網

        掃一掃關注

        當前位置: 首頁 » 企業資訊 » 熱點 » 正文

        Tokitsukaze_and_Good_01

        放大字體  縮小字體 發布日期:2022-06-23 21:24:19    作者:葉麓菲    瀏覽次數:95
        導讀

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

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

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

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

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

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

        參考:
        codeforces/blog/entry/102631

        思路:

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

        對于相鄰字符相同得位置,我們無需改動;對于相鄰字符不同得位置,我們考慮變為0,1對于最終得到得最小連續段得影響。我們用

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

        #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標記不可達 }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做為結尾 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';// 對于不能改變得位置,默認取它原來得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;}

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

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

        粵ICP備16078936號

        微信

        關注
        微信

        微信二維碼

        WAP二維碼

        客服

        聯系
        客服

        聯系客服:

        在線QQ: 303377504

        客服電話: 020-82301567

        E_mail郵箱: weilaitui@qq.com

        微信公眾號: weishitui

        客服001 客服002 客服003

        工作時間:

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

        反饋

        用戶
        反饋

        主站蜘蛛池模板: 精品一区二区三区影院在线午夜 | 无码人妻一区二区三区在线 | 亚洲综合一区二区国产精品| 风间由美性色一区二区三区 | www一区二区www免费| 日韩视频在线观看一区二区 | 国模少妇一区二区三区| 加勒比无码一区二区三区| 国产成人精品一区在线| 久久se精品动漫一区二区三区| 无码人妻精品一区二区三区蜜桃 | 精品亚洲一区二区| 亚洲AV永久无码精品一区二区国产 | 国产亚洲一区二区手机在线观看| 日本一区二区三区在线网| 日本精品一区二区在线播放 | 中文字幕视频一区| 久久婷婷色综合一区二区| 天天看高清无码一区二区三区| 国产一区二区三区韩国女主播| 亚欧成人中文字幕一区| 国产av成人一区二区三区| 中文字幕一区二区三区四区| 国产福利电影一区二区三区,亚洲国模精品一区 | 精品乱码一区二区三区四区| 精品性影院一区二区三区内射| 国产一区二区三区在线看| 无码精品人妻一区二区三区人妻斩| 久久亚洲综合色一区二区三区 | 国产一区中文字幕| 国产成人一区二区动漫精品| 美女视频一区二区| 天堂Aⅴ无码一区二区三区| 久久精品一区二区免费看| 无码人妻视频一区二区三区 | 国产精品日本一区二区不卡视频| 三上悠亚日韩精品一区在线| 无码精品人妻一区二区三区免费看| 在线视频一区二区| 色婷婷亚洲一区二区三区| 爆乳熟妇一区二区三区|