[POI2011]LIZ-Lollipop

摘要

题意:给一个只有 1 和 2 的序列,每次询问有没有一个子串的和为 x. .

一道很考人的思维题。暴力的思路就是直接预处理前缀和,然后每次 查询前缀和的差.

注意到这个序列只有 0 和 1 啊!所以我们尝试从奇偶性的角度考虑这个问题. 我们发现,如果在序列中有某个子串的和为 ,那么所有小于 且奇偶性与 相同的数都能被找到。构造的方法就是逐步从子串头尾去掉一个 2 或者两个 1.

因此我们只需要找到这个序列子串和中最大的奇数和偶数即可. 整个序列的和是其中之一,另一个的话前缀后缀减一减就能找到啦

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
int n,m;

int a[N],s1,pre,suf,pi,si;
char s[N];
int ans[N][2];
void calc(int sum,int l,int r){// 构造答案
    if(sum<=0)return;
    ans[sum][0]=l,ans[sum][1]=r;
    if(a[l]==2)calc(sum-2,l+1,r);
    else if(a[r]==2)calc(sum-2,l,r-1);
    else calc(sum-2,l+1,r-1);
}
int main(){scanf("%d%d%s",&n,&m,s+1);
    for(int i=1;i<=n;i++)a[i]=s[i]=='W'?1:2,s1+=a[i];
    for(int i=1;i<=n;i++){// 寻找奇数前缀
        pre+=a[i],pi=i;
        if(a[i]%2)break;
    }
    for(int i=n;i>=1;i--){// 后缀
        suf+=a[i],si=i;
        if(a[i]%2)break;
    }
    calc(s1,1,n);
    if(pre<suf)calc(s1-pre,pi+1,n);
    else calc(s1-suf,1,si-1);
    for(int i=1;i<=m;i++){
        int k;
        scanf("%d",&k);
        if(ans[k][0])printf("%d %d\n",ans[k][0],ans[k][1]);
        else puts("NIE");
    }
    return 0;
}

  转载请注明: Sshwy's Blog [POI2011]LIZ-Lollipop

 上一篇
[POI2007]TET-Tetris Attack [POI2007]TET-Tetris Attack
摘要 题意:给定一个长度为 的序列, 各出现两次,可以交换相邻两项,两个同样的数相邻会消失,求把所有数对消的最小交换次数,输出方案。 . 一看就是一个树状数组的问题,关键是
2019.04.05
下一篇 
高斯消元 高斯消元
摘要 Gaussian Elimination,一种求解线性方程组的算法 概述高斯消元是一种求解线性方程组的方法。 线性方程组与増广矩阵我们把 \left\{\begin{matrix} a_{1,1}x_1+a_{1,2}x_2+\c
2019.04.04
  目录