首页 > 其他分享 >POI2011/洛谷P3514 LIZ-Lollipop

POI2011/洛谷P3514 LIZ-Lollipop

时间:2024-10-31 09:31:21浏览次数:4  
标签:maxx 洛谷 int sum POI2011 -- 区间 co LIZ

前言

典中典思维蓝题难度薄纱模板水紫捏。

\(1\) \(2\) 序列这种也不是第一次见了,感觉多多少少都沾点 Ad-hoc。

话说这种考法真的好吗,一上来就是一个门槛很高的性质,推出来就满分,推不出来就 \(0\) 分,正推和反推的难度完全不是一个思维量级。

题意

Link

给一个只有 \(1\) 和 \(2\) 的序列,每次询问有没有一个子串的和为 \(x\),序列长与询问次数均为 \(10^6\) 级。

思路

发挥惊人的观察力得到,假如一段区间的和为 \(sum\),则如果 \(sum>2\),那么这个区间一定有一个子区间的区间和为 \(sum-2\)。考虑两种情况,区间的左右端点有 \(2\) 和没有 \(2\),前者直接在原区间中减去 \(2\) 即可得到 \(sum-2\) 的子区间,后者说明区间左右端点都是 \(1\),那么原区间减去两个端点即可得到 \(sum-2\) 的子区间。

于是我们找到最大的奇数 \(sum\) 和偶数 \(sum\) 区间,再不断按照上述方法缩小两端点即可求出每个数对应的区间。

代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=1000005,MAXK=2000005;
int n,m,maxx[2]={0};
int a[MAXN],q=0,sum=0;
pii co[MAXK];
int main(){
    cin>>n>>m;
    string inp;
    cin>>inp;

    for(int i=1;i<=n;i++){
        a[i]=(inp[i-1]=='T'?2:1);
        sum+=a[i];
        maxx[sum%2]=max(maxx[sum%2],sum);
        co[sum].first=1;co[sum].second=i;
    }
    sum=0;
    for(int i=n;i>=1;i--){
        sum+=a[i];
        maxx[sum%2]=max(maxx[sum%2],sum);
        co[sum].first=i;co[sum].second=n;
    }
    for(int i=0;i<2;i++){
        int l=co[maxx[i]].first,r=co[maxx[i]].second,con=maxx[i];
        while(l<=r && con>0){
            co[con]=make_pair(l,r);
            if(a[l]==1 && a[r]==1) l++,r--;
            else if(a[l]==2) l++;
            else r--;
            con-=2;
        }
    }
    for(int i=1;i<=m;i++){
        cin>>q;
        if(q>maxx[q%2]) cout<<"NIE";
        else{
            cout<<co[q].first<<' '<<co[q].second;
        }
        if(i!=m) cout<<endl;
    }
    return 0;
}

标签:maxx,洛谷,int,sum,POI2011,--,区间,co,LIZ
From: https://www.cnblogs.com/SkyNet-PKN/p/18517005

相关文章

  • Normalized Mutual Information(NMI, 归一化互信息)
    NormalizedMutualInformation(NMI,归一化互信息)值域是$[0,1]$,值越高表示两个聚类结果越相似。归一化是指将两个聚类结果的相似性值定量到$0\sim1$之间。$$\text{NMI}=\frac{2\sum_i\sum_jn_{ij}ln\frac{n_{ij}N}{n_in_j}}{-\sum_in_iln\frac{n_i}{N}-\sum_jn_jln\fra......
  • 易优cms系统报错unserialize(): Error at offset 0 of 1571 bytes_Eyoucms系统报错问
    解决方案清除缓存通过FTP访问服务器。导航至 /data/runtime 目录。删除该目录下的所有文件和文件夹。升级系统登录后台。检查是否有可用的更新。升级到最新版本,以确保已知的问题已被修复。检查代码如果问题仍然存在,可以检查 \corelibrary\think\cache\dri......
  • [NISACTF 2022]babyserialize
    1.题目2.exp两种第一种:<?phpheader("Content-Type:text/html;charset=utf-8");classNISA{public$fun;public$txw4ever='SYSTEM("tac/f*");';}classTianXiWei{public$ext;publi......
  • DRF-Serializers序列化器组件源码分析及改编su
    1.源码分析注意:以下代码片段为方便理解已进行简化,只保留了与序列化功能相关的代码序列化的源码中涉及到了元类的概念,我在这里简单说明一下:元类(metaclass)是一个高级概念,用于定义类的创建行为。简单来说,元类是创建类的类,它决定了类的创建方式和行为。在Python中一切皆为对象,包......
  • 洛谷 语言月赛 202401
    B3913[语言月赛202401]装满葡萄汁的酒杯[语言月赛202401]装满葡萄汁的酒杯-洛谷B3914[语言月赛202401]分饼干I[语言月赛202401]分饼干I-洛谷B3915[语言月赛202401]跳房子[语言月赛202401]跳房子-洛谷B3916[语言月赛202401]区间函数......
  • 洛谷P1045 [NOIP2003 普及组] 麦森数
    形如 2P−12P−1 的素数称为麦森数,这时 PP 一定也是个素数。但反过来不一定,即如果 PP 是个素数,2P−12P−1 不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是 P=3021377P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。任务:输......
  • DRF-Serializers序列化器组件源码分析及改编
    1.源码分析注意:以下代码片段为方便理解已进行简化,只保留了与序列化功能相关的代码序列化的源码中涉及到了元类的概念,我在这里简单说明一下:元类(metaclass)是一个高级概念,用于定义类的创建行为。简单来说,元类是创建类的类,它决定了类的创建方式和行为。在Python中一切皆为对象,包......
  • Error in eval(family$initialize): y值必需满足0 <= y <= 1解决
    今天在使用R语言对Weekly进行交叉验证时,发生如下报错:错误于eval(family$initialize):y值必需满足0<=y<=1错误代码为:Weekly<-read.csv("Weekly.csv")set.seed(1)attach(Weekly)glm.fit1=glm(Direction~Lag1+Lag2,data=Weekly,family=binomial)summary(glm.fit1)......
  • 深度优先算法(DFS)洛谷P1683-入门
    虽然洛谷是有题解的,但是你如果直接看得懂题解,你也不会来看这篇文章..这些代码均是我记录自身成长的记录,有写的不好的地方请谅解!先上代码:#include<iostream>#include<vector>#include<iomanip>#include<cstdio>usingnamespacestd;constintN=30;charg[N......
  • CSP/信奥赛C++刷题训练:经典二分例题(2):洛谷P1678:烦恼的高考志愿
    CSP/信奥赛C++刷题训练:经典二分例题(2)烦恼的高考志愿题目背景计算机竞赛小组的神牛V神终于结束了高考,然而作为班长的他还不能闲下来,班主任老t给了他一个艰巨的任务:帮同学找出最合理的大学填报方案。可是v神太忙了,身后还有一群小姑娘等着和他约会,于是他想到了同为计......