当前位置: 首页 > article >正文

E - 11/22 Subsequence题解

文章目录

      • 大致思路
      • 代码

大致思路

  1. 预处理:

    • pos1, pos2, posls 分别记录 1 1 1, 2 2 2 , / / / 在字符串中的『位置』

    • cum1cum2 分别存储了 1 1 1 2 2 2 的前缀和,这样可以快速获取任意区间内的 1 1 1 2 2 2 的『数量』

  2. 查询处理:

    • 对于每个查询,使用**『前缀和』**来快速获取指定区间内的 1 1 1 2 2 2 的数量

    • 然后使用 lower_boundupper_bound 查找指定区间内的 / / / 的位置

    • 我们对于每个 / 的位置,需要计算左侧的 1 1 1 的数量和右侧的 2 2 2 的数量,取小的那个值乘以 2 2 2 再加 1 1 1,接着就可以可以形成的最长的 11 / 22 11/22 11/22 字符串部分序列的『长度』啦

    • 最后输出答案就可以了

代码

#include <iostream>		// 基本输入输出流
#include <algorithm>	// 通用算法(排序、查找、去重、二分查找等)
#include <vector>		// 动态数组(空间不够会自动扩容)
#include <queue>		// 队列(先进先出)
#include <stack>		// 栈(先进后出)
#include <set>			// 集合(有序不重复)
#include <map>			// 键值对容器(映射)
#include <list>			// 双向链表
#include <math.h>		// 数学函数
#include <functional>	// 通用的函数绑定和调用机制

#define endl '\n'
#define pii pair<int, int>
#define pdd pair<double, double>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define int long long
using namespace std;

const int inf = 1e9 + 7;
const int mod = 998244353;
const int N = 2e5 + 10, M = N << 1;

void solve(){
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    // 前処理: 1, /, 2 の位置を記録
    vector<int> pos1, pos2, posls;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') pos1.push_back(i);
        else if (s[i] == '2') pos2.push_back(i);
        else if (s[i] == '/') posls.push_back(i);
    }

    // 1, 2 の累積和を計算
    vector<int> cum1(n + 1, 0), cum2(n + 1, 0);
    for (int i = 0; i < n; i++) {
        cum1[i + 1] = cum1[i] + (s[i] == '1');
        cum2[i + 1] = cum2[i] + (s[i] == '2');
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        --l; // 0-indexed に変換

        // 指定範囲内の 1, 2 の数を取得
        int count1 = cum1[r] - cum1[l];
        int count2 = cum2[r] - cum2[l];

        // 指定範囲内の / の位置を取得
        auto it1 = lower_bound(posls.begin(), posls.end(), l);
        auto it2 = upper_bound(posls.begin(), posls.end(), r - 1);
    	vector<int> sah(it1, it2);
        int maxlen = 0;
        for (int mid : sah) {
            if (mid < l || mid >= r) continue;

            // 左側の 1 の数
            int l1 = cum1[mid] - cum1[l];
            // 右側の 2 の数
            int r2 = cum2[r] - cum2[mid + 1];

            // 11/22 文字列の部分列の長さを計算
            int len = min(l1, r2) * 2 + 1;
            maxlen = max(maxlen, len);
        }

        cout << maxlen << endl;
    }
}

signed main(){
	//重定向输入输出
//    freopen("pow.in", "r", stdin);
//    freopen("pow.out", "w", stdout);

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int _ = 1;
//	cin >> _;	// 非多组测试数据请注释该行
    while(_--) solve();
    return 0;
}


http://www.kler.cn/a/405872.html

相关文章:

  • ROS机器视觉入门:从基础到人脸识别与目标检测
  • 【LeetCode热题100】栈
  • 深度解析神经网络中的最大池化层:工作原理、参数配置与应用示例
  • 七、电机三环控制
  • Kafka 工作流程解析:从 Broker 工作原理、节点的服役、退役、副本的生成到数据存储与读写优化
  • 在应用启动时,使用 UniApp 提供的 API 检查和请求权限。
  • nvm安装node遇到的若干问题(vscode找不到npm文件、环境变量配置混乱、npm安装包到D盘)
  • 图像预处理之图像滤波
  • React-useEffect的使用
  • 任务通知的本质(任务通知车辆运行) 软件定时器的本质(增加游戏音效)
  • MybatisPlus编写join查询
  • 记录下jekins新建个前端部署配置项
  • 单片机学习笔记 9. 8×8LED点阵屏
  • ffmpeg区域颜色覆盖
  • Echarts中柱状图完成横向布局
  • 【MySQL】数据库的隔离级
  • 使用 vscode 调试 nodejs 代码
  • 数据分析-51-时间序列分解之局部均值分解LMD
  • 【Three.js基础学习】28.Coffee Smoke
  • 鸿蒙进阶篇-TextInputTextArea和Checkbox
  • E. Counting Arrays
  • 设计模式-创建型-工厂模式
  • 深度学习笔记24_天气预测
  • 51单片机--- 矩阵按键仿真
  • Mac M4苹果电脑M4上支持的AE/PR/PS/AI/ID/LrC/AU/DC/ME有哪些?
  • 【大模型】docker部署glm-4-9b-chat,并部署到服务器上