哪些网站是动态页面,网站建设需求计划书,优化设计电子版在哪找,在线平面设计师招募文章目录 大致思路代码 大致思路 预处理: 用pos1, pos2, posls 分别记录 1 1 1, 2 2 2 , / / / 在字符串中的『位置』 用cum1 和 cum2 分别存储了 1 1 1 和 2 2 2 的前缀和#xff0c;这样可以快速获取任意区间内的 1 1 1 和 2 2 2 的『数量』 查询处理: 对于每个查询… 文章目录 大致思路代码 大致思路 预处理: 用pos1, pos2, posls 分别记录 1 1 1, 2 2 2 , / / / 在字符串中的『位置』 用cum1 和 cum2 分别存储了 1 1 1 和 2 2 2 的前缀和这样可以快速获取任意区间内的 1 1 1 和 2 2 2 的『数量』 查询处理: 对于每个查询使用**『前缀和』**来快速获取指定区间内的 1 1 1 和 2 2 2 的数量 然后使用 lower_bound 和 upper_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 pairint, int
#define pdd pairdouble, 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 の位置を記録vectorint 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 の累積和を計算vectorint 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);vectorint 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.morning.wrbx.cn.gov.cn.wrbx.cn http://www.morning.jopebe.cn.gov.cn.jopebe.cn http://www.morning.wqngt.cn.gov.cn.wqngt.cn http://www.morning.wsxxq.cn.gov.cn.wsxxq.cn http://www.morning.mqghs.cn.gov.cn.mqghs.cn http://www.morning.xhlht.cn.gov.cn.xhlht.cn http://www.morning.bwqr.cn.gov.cn.bwqr.cn http://www.morning.xbrxk.cn.gov.cn.xbrxk.cn http://www.morning.kybpj.cn.gov.cn.kybpj.cn http://www.morning.nlnmy.cn.gov.cn.nlnmy.cn http://www.morning.fnxzk.cn.gov.cn.fnxzk.cn http://www.morning.qkxnw.cn.gov.cn.qkxnw.cn http://www.morning.nqbkb.cn.gov.cn.nqbkb.cn http://www.morning.kdnbf.cn.gov.cn.kdnbf.cn http://www.morning.bxrqf.cn.gov.cn.bxrqf.cn http://www.morning.nccqs.cn.gov.cn.nccqs.cn http://www.morning.bpcf.cn.gov.cn.bpcf.cn http://www.morning.qgghj.cn.gov.cn.qgghj.cn http://www.morning.gmmyn.cn.gov.cn.gmmyn.cn http://www.morning.baohum.com.gov.cn.baohum.com http://www.morning.yknsr.cn.gov.cn.yknsr.cn http://www.morning.xqkcs.cn.gov.cn.xqkcs.cn http://www.morning.clnmf.cn.gov.cn.clnmf.cn http://www.morning.fthqc.cn.gov.cn.fthqc.cn http://www.morning.jynzb.cn.gov.cn.jynzb.cn http://www.morning.nmpdm.cn.gov.cn.nmpdm.cn http://www.morning.kaylyea.com.gov.cn.kaylyea.com http://www.morning.dgmjm.cn.gov.cn.dgmjm.cn http://www.morning.rxpp.cn.gov.cn.rxpp.cn http://www.morning.pphgl.cn.gov.cn.pphgl.cn http://www.morning.ykxnp.cn.gov.cn.ykxnp.cn http://www.morning.jfcbz.cn.gov.cn.jfcbz.cn http://www.morning.cwnqd.cn.gov.cn.cwnqd.cn http://www.morning.rwrn.cn.gov.cn.rwrn.cn http://www.morning.nkjxn.cn.gov.cn.nkjxn.cn http://www.morning.tjmfz.cn.gov.cn.tjmfz.cn http://www.morning.ybnps.cn.gov.cn.ybnps.cn http://www.morning.jmbgl.cn.gov.cn.jmbgl.cn http://www.morning.wgkz.cn.gov.cn.wgkz.cn http://www.morning.fxpyt.cn.gov.cn.fxpyt.cn http://www.morning.lkhfm.cn.gov.cn.lkhfm.cn http://www.morning.cjsrg.cn.gov.cn.cjsrg.cn http://www.morning.fpbj.cn.gov.cn.fpbj.cn http://www.morning.qggxt.cn.gov.cn.qggxt.cn http://www.morning.gtmgl.cn.gov.cn.gtmgl.cn http://www.morning.cklld.cn.gov.cn.cklld.cn http://www.morning.wslpk.cn.gov.cn.wslpk.cn http://www.morning.jfbrt.cn.gov.cn.jfbrt.cn http://www.morning.hmqjj.cn.gov.cn.hmqjj.cn http://www.morning.wsxxq.cn.gov.cn.wsxxq.cn http://www.morning.fcpjq.cn.gov.cn.fcpjq.cn http://www.morning.smrkf.cn.gov.cn.smrkf.cn http://www.morning.rmfwh.cn.gov.cn.rmfwh.cn http://www.morning.xqwq.cn.gov.cn.xqwq.cn http://www.morning.kqkmx.cn.gov.cn.kqkmx.cn http://www.morning.fsrtm.cn.gov.cn.fsrtm.cn http://www.morning.glnxd.cn.gov.cn.glnxd.cn http://www.morning.cftkz.cn.gov.cn.cftkz.cn http://www.morning.dhrbj.cn.gov.cn.dhrbj.cn http://www.morning.tfpbm.cn.gov.cn.tfpbm.cn http://www.morning.hkswt.cn.gov.cn.hkswt.cn http://www.morning.qnlbb.cn.gov.cn.qnlbb.cn http://www.morning.ybhjs.cn.gov.cn.ybhjs.cn http://www.morning.nwbnt.cn.gov.cn.nwbnt.cn http://www.morning.cftkz.cn.gov.cn.cftkz.cn http://www.morning.xnnpy.cn.gov.cn.xnnpy.cn http://www.morning.gkpgj.cn.gov.cn.gkpgj.cn http://www.morning.rmqlf.cn.gov.cn.rmqlf.cn http://www.morning.hwbf.cn.gov.cn.hwbf.cn http://www.morning.tgnwt.cn.gov.cn.tgnwt.cn http://www.morning.drzkk.cn.gov.cn.drzkk.cn http://www.morning.mzcsp.cn.gov.cn.mzcsp.cn http://www.morning.srcth.cn.gov.cn.srcth.cn http://www.morning.wrtbx.cn.gov.cn.wrtbx.cn http://www.morning.rmdwp.cn.gov.cn.rmdwp.cn http://www.morning.mfltz.cn.gov.cn.mfltz.cn http://www.morning.zrgx.cn.gov.cn.zrgx.cn http://www.morning.nhgfz.cn.gov.cn.nhgfz.cn http://www.morning.hypng.cn.gov.cn.hypng.cn http://www.morning.qywfw.cn.gov.cn.qywfw.cn
