div 2 c Binary String Copying

这篇具有很好参考价值的文章主要介绍了div 2 c Binary String Copying。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

#include<bits/stdc++.h>
using namespace std ;
using ll = long long;
using PII = pair<int,int>;
string s;
void solve(){
    int n,m;
    cin >> n >> m;
    //vector<int>s(n+1);
    vector<int>ne1(n+2,n+1);
    vector<int>pre0(n+2,0);
    cin>>s;
    s = " " + s;
    for(int i=1;i<=n;i++){
        pre0[i] = pre0[i-1];
        if(s[i] == '0'){
            pre0[i] = i;
        }
    }
    for(int i=n;i>=1;i--){
        ne1[i] = ne1[i+1];
        if(s[i] == '1'){
            ne1[i] = i;
        }
    }
    set<PII> s;
    while(m--){
        int l,r;
        cin>>l>>r;
        //cout<<ne1[l]<<" "<<pre0[r]<<endl;
        if(ne1[l] > pre0[r]){
            s.emplace(-1,-1);
        }else{
            s.emplace(ne1[l],pre0[r]);
        }
    }
    cout<<s.size();

}



int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
        puts("");
    }
}

用最小的变换区间代表整个大区间

找到L右边最近的1   R左边最近的0   变换区间就在这两个之间文章来源地址https://www.toymoban.com/news/detail-613451.html

到了这里,关于div 2 c Binary String Copying的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Codeforces Round 911 (Div. 2) C. Anji‘s Binary Tree (DFS + 树)

    题目 思路:         dfs树的每一条到叶子的路径, 并计算路径中需要修改的个数, 在这些个数中取最小值 注意:         本题中的树是以每个结点的左右孩子是什么的形式给出的, 所以可以不用建树, 只需保存每个结点的左右孩子是什么即可。 代码:

    2024年01月16日
    浏览(41)
  • 【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :首先我们要知道后序遍历数组的最后一个元素必然是根节点,然后根据根节点在中序遍历数组中的位置进行划分,得到根节点的左右子树遍历数组,以此递归。当然这里有一个前提

    2024年02月10日
    浏览(39)
  • arc163 C 思维构造

    题意:https://atcoder.jp/contests/arc163/tasks/arc163_c 思路:本题构造主要就是围绕                                 初始放入2,3,6,然后一直将一个拆解直到满足大小。

    2024年02月12日
    浏览(21)
  • Educational Codeforces Round 135 (Rated for Div. 2)C. Digital Logarithm(思维)

    C. Digital Logarithm 给两个长度位 n n n 的数组 a a a 、 b b b ,一个操作 f f f 定义操作 f f f 为, a [ i ] = f ( a [ i ] ) = a [ i ] a[i]=f(a[i])=a[i] a [ i ] = f ( a [ i ]) = a [ i ] 的位数 求最少多少次操作可以使 a 、 b a、b a 、 b 两个数组变得完全相同 性质: 对于任何数,经过两次操作我们一定可以

    2024年02月20日
    浏览(37)
  • Codeforces Round 768 (Div. 1) D. Flipping Range(思维题 等价类性质 dp)

    题目 思路来源 官方题解 洛谷题解 题解 可操作的最短区间长度肯定是gcd,记为g,然后考虑如何dp 考虑g个等价类,每个等价类i,i+g,i+2*g,... 每次翻转长度为g的区间,会同时影响到g个等价类总的翻转的奇偶性, 性质一:只有每个等价类翻的次数奇偶性相同才合法  性质二:此

    2024年01月19日
    浏览(34)
  • Codeforces Round 816 (Div. 2)(D拆位图论构造 E斜率优化)

    C:直接单独算每个位置的贡献,如果当前位置和前面位置重复了,那么前面就没选的位置了 修改的时候只要重新算i和i+1位置即可 D: 拆位,考虑字典序最小,让开头的数能等于0就等于0 要先把一定是0的数和u==v这种确定的数先填了,后面根据字典序填即可 E: 直接斜率优化

    2024年04月27日
    浏览(38)
  • string类构造函数与析构函数

    构造函数 作用 string s 构造一个空字符串 string s(s1) 生成一个和s1相同的空字符串s string s(s1,5) 将s1[5]以后的部分作为s的初始部分 string s(s1,5,5) 将始于s1[5],长度为5的部分作为s的初始值 string s(cstr) 以C_string类型的cstr作为字符串s的初始值 string s(sctr,char_len) 以C_string类型的cstr的前

    2024年02月08日
    浏览(45)
  • Java 【数据结构】 二叉树(Binary_Tree)【神装】

        登神长阶  第五神装 二叉树 Binary-Tree 目录  🎷一.树形结构 🪗1.概念 🎸2.具体应用 🎹 二.二叉树(Binary Tree) 🎺1.概念  🎻2.表现形式 🪕3.特殊类型 🥁3.1完全二叉树(Complete Binary Tree) 🪘3.2满二叉树(Full Binary Tree) 🔋4.性质  🪫5.二叉树的遍历 💿5.1前中后序遍历

    2024年04月27日
    浏览(44)
  • 【每日一题】—— B. Ternary String (Educational Codeforces Round 87 (Rated for Div. 2))

    🌏博客主页: PH_modest的博客主页 🚩当前专栏: 每日一题 💌其他专栏: 🔴 每日反刍 🟡 C++跬步积累 🟢 C语言跬步积累 🌈座右铭: 广积粮,缓称王! 题目大意:给你一串由1、2、3组成的数组,让你求一个最短的子串,要求这个子串包含1、2、3 题目链接:B. Ternary String

    2024年02月16日
    浏览(35)
  • 数据结构英文习题解析-第五章 二叉搜索树Binary Search Tree

    前言:最近快到FDS考试了,po重刷了一下学校的题目,自己整理了一些解析orz 因为po在自己找解析和学习的过程中非常痛苦,所以在此共享一下我的题目和自己写的解题思路,欢迎各位指出错误~全章节预计会陆续更新,可在专栏查看~ HW5 1.In a binary search tree, the keys on the same

    2024年04月09日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包