首页 > 其他分享 >P2882 题解

P2882 题解

时间:2024-04-24 18:55:35浏览次数:24  
标签:int 题解 查询 P2882 枚举 MAXN 端点 区间

思想

一眼看上去,没什么思路。

看一下标签

枚举!

于是枚举 \(K\)。

然后变成了求最少次数。

由于枚举放在第一个,我们还是考虑一下枚举。

我们枚举反转区间的左端点,我们惊奇地发现,由于从左往右扫,如果左端点是朝后的,那这次不转就没机会了。

所以最最简单的暴力:从左往右扫,遇到左端点朝后就翻转。

然后 T 了。

考虑一下,我们要查询左端点,翻转一个区间。

区间修改,单点查询!

在 Gold 赛场上我们应该想到 Fenwick,尽管正解是异或。

我们区间修改就给这个区间加一,单点查询就查询这个点的奇偶。

树状数组常数小再加上洛谷少爷机跑得嘎嘎地快。

Code

#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 5005;
constexpr int INF = 0x3f3f3f3f;

int n;

struct Fenwick {
    int c[MAXN];
    int a[MAXN];
    int lowbit(int x) {
        return (-x) & x;
    }
    void add(int l, int r, int v) {
        for (int i = l; i <= n + 1; i += lowbit(i)) {
            c[i] += v;
        }
        for (int i = r + 1; i <= n + 1; i += lowbit(i)) {
            c[i] -= v;
        }
    }
    int sum(int x) {
        int s = 0;
        for (int i = x; i >= 1; i -= lowbit(i)) {
            s += c[i];
        }
        return s;
    }
} fw, fenwick;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        if (s == "B")
            fw.add(i, i, 1);
    }

    int ans = INF, ans2;
    for (int i = 1; i <= n; i++) {
        fenwick = fw;
        int cnt = 0;
        for (int j = 1; j <= n - i + 1; j++) {
            if (fenwick.sum(j) & 1) {
                fenwick.add(j, j + i - 1, 1);
                cnt++;
            }
        }
        bool flag = true;
        for (int j = n - i + 2; j <= n; j++) {
            if (fenwick.sum(j) & 1) {
                flag = false;
                break;
            }
        }
        if (flag && cnt < ans) {
            ans = cnt;
            ans2 = i;
        }
    }

    cout << ans2 << " " << ans << endl;

    return 0;
}

标签:int,题解,查询,P2882,枚举,MAXN,端点,区间
From: https://www.cnblogs.com/LightningCreeper/p/18156101

相关文章

  • 「洛谷」题解:P1217 回文质数
    题目传送门看着题目好像很简单的样子,实际上做起来才会发现,这么多函数他奶奶的是普及-难度?在这道题目当中,我们最少需要写两个函数,如果需要优化可以再多写一个,待会儿的代码我们就直接放最简单版本的了。有人说这道题可以暴力对拍之后再输出,这完全可以,但是这么简单的题目不至于使用......
  • 2022ccpc题解
    2023年第五届河南省CCPC大学生程序设计竞赛ProblemA.Mocha上小班啦思路:求n个数位的最小值,条件:每一位数字都不同切不含前导零。只需要把0放到第二位,其他按从小到大输出,大于10以后输出-1即可。#include<bits/stdc++.h>usingnamespacestd;intmain(){//预处......
  • P5900 无标号无根树计数 题解
    不懂为啥都要对原式神秘转化之后再牛顿迭代,直接对原式牛顿迭代即可!完全不用转化!设无标号有根树的组合类是\(\mathcalT\),则有\(\mathcalT=\mathcalZ\times\mathrm{MSET}(\mathcalT)\),即\(T(x)=x\exp\sum\limits_{j\ge1}\dfrac{T(x^j)}j\),设\(G(F(x))=F(x)-x\exp\sum\lim......
  • abc340E题解
    题目描述样例input:5312345240output:04272算法1(树状数组)$O(nlogn)$本题我们可以看作对于每一个查询位置x我们都需要先把该位置上的所有球拿出来,然后再一个一个的放到对应位置上去。假设x位置上面有y个球,那么对于这y个球,如果大于n,那么就对所有的位置放y......
  • P3667 Bovine Genomics Hash+二分题解
    砂金听说了你在学字符串,于是在CLOI里出了道题给你P3667BovineGenomics题链:洛谷hzoi提高\(hash\)基础题。思路是二分答案,\(check\)中比较每一个区间字串的\(hash\)值是否相等。比较的时候可以用\(set\)或\(map\)。\(set\)的好处在于无重元素,判断时先将\(a\)串中区间子串......
  • 抢先看!美团、京东、360等大厂面试题解析,技术面试必备。
    技术面试必备!美团、京东、360等大厂面试题详解,让你轻松应对各大公司面试挑战!往期硬核面经哦耶!冲进腾讯了!牛逼!上岸腾讯互娱和腾讯TEG!腾讯的面试,强度拉满!前几篇文章分享了上岸腾讯的最新面经。不少粉丝股东留言说别只发腾讯的啦,其他大厂的也安排一些吧,比如美团、360、京东的......
  • [ABC329C] Count xxx 题解
    [ABC329C]Countxxx题解题目分析目的:统计本质不同而不是位置不同的所有字符都相同的字串。需要理解一下什么是本质不同而不是位置不同。结合样例1去理解这句话。列举样例1中的所有所有组成字符相同的字串。aaabaa编号字串位置\(1\)a\([1,1]\)\(2\)aa\([1......
  • [题解]ARC176 A~B
    赛时心态崩了,0pts遗憾离场……今天在学校冷静思考了下。发现B题思路其实很简单,不过A题怎么也没有想到,回来看了题解,其实思路也很简单,不过是自己思考方向错了。看来打比赛心态很重要,如果能冷静下来思考结果会好很多。果然算法竞赛不能被常理所束缚(笑)A-01MatrixAgain行列从\(0......
  • 题解 UOJ577【[ULR #1] 打击复读】
    题解UOJ577【[ULR#1]打击复读referencehttps://www.cnblogs.com/crashed/p/17382894.htmlhttps://www.cnblogs.com/sizeof127/articles/17579027.html字符串——黄建恒,广东实验中学题目描述为了提升搜索引擎的关键词匹配度以加大访问量,某些网站可能在网页中无意义复读大......
  • 编译用于Qt的opencv问题解决
    CMakewasunabletofindabuildprogramcorrespondingto"MinGWMakefiles"解释:这个错误表明CMake无法找到用于生成Makefiles的构建程序。在使用CMake生成项目文件时,如果指定了"MinGWMakefiles",CMake需要一个Make工具来构建项目,而这个工具通常是由MinGW提供的。如......