Sereja and Algorithm

简介: Sereja and Algorithm


E - Sereja and Algorithm

Time Limit:1000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

Submit Status

Description

Sereja loves all sorts of algorithms. He has recently come up with a new algorithm, which receives a string as an input. Let's represent the input string of the algorithm as q = q1q2... qk. The algorithm consists of two steps:

  1. Find any continuous subsequence (substring) of three characters of string q, which doesn't equal to either string "zyx", "xzy", "yxz". If q doesn't contain any such subsequence, terminate the algorithm, otherwise go to step 2.
  2. Rearrange the letters of the found subsequence randomly and go to step 1.

Sereja thinks that the algorithm works correctly on string q if there is a non-zero probability that the algorithm will be terminated. But if the algorithm anyway will work for infinitely long on a string, then we consider the algorithm to work incorrectly on this string.

Sereja wants to test his algorithm. For that, he has string s = s1s2... sn, consisting of n characters. The boy conducts a series of m tests. As the i-th test, he sends substring slisli + 1... sri(1 ≤ li ≤ ri ≤ n) to the algorithm input. Unfortunately, the implementation of his algorithm works too long, so Sereja asked you to help. For each test (li, ri) determine if the algorithm works correctly on this test or not.

Input

The first line contains non-empty string s, its length (n) doesn't exceed 105. It is guaranteed that string s only contains characters: 'x', 'y', 'z'.

The second line contains integer m(1 ≤ m ≤ 105) — the number of tests. Next m lines contain the tests. The i-th line contains a pair of integers li, ri(1 ≤ li ≤ ri ≤ n).

Output

For each test, print "YES" (without the quotes) if the algorithm works correctly on the corresponding test and "NO" (without the quotes) otherwise.

Sample Input

Input

zyxxxxxxyyz
5
5 5
1 3
1 11
1 4
3 6

Output

YES
YES
NO
YES
NO

Hint

In the first example, in test one and two the algorithm will always be terminated in one step. In the fourth test you can get string "xzyx" on which the algorithm will terminate. In all other tests the algorithm doesn't work correctly.

 

 

 

 

题目分析:

 

5组测试数据

5 5 是第五个开始第五个结束,也就是 x

1 3 是第一个开始第3个结束 ,也就是zyx

1 11是第一个开始第11个结束,也就是 zyxxxxxxyyz

1   4是第1个开始第4个结束,也就是zyxx

3  6 是第3个开始第6个结束,也就是xxxx

目的是:如果被截取出来的字符串找一下有没有 这三种zyx  xzy  yxz 子串, 如果有这些组合出现就重新排列再找,也就是只要有一种排列是找不出这三种zyx  xzy  yxz 子串

中任意一种的就输出NO,否则就是YES。但是如果字符数少于3个的都是输出YES

其实就是如果截取的字符串中  x    y     z各自的总个数    分别做差如果差有大于1那么肯定能通过重新排列出现一种排列是找不出这三种zyx  xzy  yxz 子串中任意一种的。不信你自己举些例子试一下。

 

 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define maxn 100010
using namespace std;
char str[maxn];
int a[maxn],b[maxn],c[maxn];
int len;
void fun()
{
  memset(a,0,sizeof(a));
  memset(b,0,sizeof(b));
  memset(c,0,sizeof(c));
  int x=0,y=0,z=0;
  for(int i=0;i<len;i++)
  {
    if(str[i]=='z')
      ++z;
    if(str[i]=='x')
      ++x;
    if(str[i]=='y')
      ++y;
    a[i+1]=x;
    b[i+1]=y;
    c[i+1]=z;
  }
}
int main()
{
  
  while(cin>>str)
  {
    int s,e,m;
    len=strlen(str);
    fun();
    cin>>m;
    while(m--)
    {
      cin>>s>>e;
      if(e-s<2) printf("YES\n");
      else
      {
        int as,bs,cs;
            as=a[e]-a[s-1];
            bs=b[e]-b[s-1];
            cs=c[e]-c[s-1];
          //printf("%d %d %d \n",as,bs,cs);
          if(abs(as-bs)<=1&&abs(as-cs)<=1&&abs(bs-cs)<=1)
            printf("YES\n");
          else printf("NO\n");
      }
    }
  }
  return 0;
 } 

 

 

 

 

 

 

 


目录
相关文章
|
机器学习/深度学习 算法 搜索推荐
精确率(Precision)和召回率(Recall)
精确率(Precision)和召回率(Recall)是用于评估分类模型性能的指标。它们通常用于二分类问题,例如判断一个样本是正例(Positive)还是负例(Negative)。
7324 0
|
SQL 存储 人工智能
MyCat-架构剖析-核心技术之跨库 join 实现 | 学习笔记
快速学习 MyCat-架构剖析-核心技术之跨库 join 实现
MyCat-架构剖析-核心技术之跨库 join 实现 | 学习笔记
|
SQL 资源调度 数据库
数仓学习---14、大数据技术之DolphinScheduler
数仓学习---14、大数据技术之DolphinScheduler
|
Linux iOS开发 MacOS
pnpm全局安装报错:Run “pnpm setup“ to create it automatically, or set the global-bin-dir setting, or the PN
pnpm全局安装报错:Run “pnpm setup“ to create it automatically, or set the global-bin-dir setting, or the PN
3519 0
|
机器学习/深度学习 缓存 监控
Pytorch学习笔记(7):优化器、学习率及调整策略、动量
Pytorch学习笔记(7):优化器、学习率及调整策略、动量
1736 0
Pytorch学习笔记(7):优化器、学习率及调整策略、动量
|
9月前
|
Windows
Office Tool Plus 永恒经典,让每个人都能轻松使用上免费的办公神器!
本文介绍如何使用Office Tool Plus在Windows 11系统上快速、免费安装和激活Office。首先,下载并解压Office Tool Plus,启动后选择“Microsoft 365企业应用版”并设置为简体中文,点击“开始部署”。安装完成后,可通过两种方法激活Office:一是使用命令框输入特定指令,二是通过KMS激活。推荐使用KMS服务器(如kms.loli.beer)进行激活。此外,若之前安装过Office,需先清除激活信息和旧版本残留文件,以确保新安装顺利进行。
4490 9
|
Ubuntu Docker 容器
Ubuntu 22.04.3 LTS_安装Docker
Ubuntu 22.04.3 LTS_安装Docker
1279 2
|
Java Spring
快速解决Spring Boot跨域困扰:使用CORS实现无缝跨域支持
这是一个简单的配置示例,用于在Spring Boot应用程序中实现CORS支持。根据你的项目需求,你可能需要更详细的配置来限制允许的来源、方法和标头。
1271 3
|
机器学习/深度学习 程序员 Python
Python装逼指南——五行代码实现批量抠图
Python装逼指南——五行代码实现批量抠图
592 0
Python装逼指南——五行代码实现批量抠图
|
算法 Java
JVM垃圾回收算法,解析新生代为什么要有两个survivor区域
复制算法将可用内存按容量划分为大小相等的两块,每次只使用其中的一块。当这一块的内存用完了,就将还存活着的对象复制到另外一块上面,然后再把已使用过的内存空间一次清理掉。
340 0