UESTC_One Step Two Steps CDOJ 1027

As we all know,the handsome boy, Zcat, has a fever of flat shoes. He sings it on the class, in the dormitory and the way he come back from the machinery room to his dorm.One day , he sing it on the way, just like

　　"MY skating shoes are the most fashion one 
　　At the way back to home I couldn't stop 
　　rubbing rubbing
　　rubbing at such smooth floor
　　With the moonlight ,I was able to see my shadow was either very close or far 
　　I felt that my step was forced by a kind of strength
　　With the skating shoes ,I will not afraid anything around the world 
　　One step two steps,every one was just like zhuaya
　　The motion which was like a ghost was rubbing and rubbing 
　　I beat to beat for myself
　　It's the best moment of my life
　　I'd got to finish my favorite dancing
　　At the terrfic street where moonlight fall
　　I told myself that it really wasn't dream
　　One step two steps ,every one was just like zhuaya 
　　The gost step was rubbing and rubbing
　　rubbing at such smooth floor
　　The motion which was like a ghost was rubbing and rubbing　
　　One step two steps,every one was just like zhuaya 
　　One step two steps,every one was just like zhuaya
        ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯“

On he sings this,he sees a pretty girl standing on by the roadside. Zcat wants to see the pretty girl's face. Zcat knows the distance between he and her is

Input

The first line contains a single number

The second line contains

The third line contains a single number

The next line contains

Output

To every question, if Zcat can see the girl clearly, print Yes, else print No.

Sample input and output

Sample Input	Sample Output
8 2 1 1 1 1 2 2 2 6 1 3 5 7 9 11	Yes Yes Yes Yes Yes No

解题报告

令 L = min ( s1 , s2 )

s1 为从左边开始扫，连续2的个数

s2 为从右边开始扫，连续2的个数

那么无法到达的距离为:

Len = 所有数之和 - 1

for(int i = 0 ; i < L; ++ i)
   {
   	  arrive[Len-i*2] = false;
   }
这样，对于所有询问，就可以在O(1)的时间内做出回答

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000000 + 50;
int A[maxn];
bool arrive[1000000*2+500];

int main(int argc,char *argv[])
{
  int n;
  scanf("%d",&n);
  int sum = 0;
  memset(arrive,true,sizeof(arrive));
  for(int i = 0 ; i < n ; ++ i)
   {
         scanf("%d",&A[i]);
         sum += A[i];
   }
  int q;
  int host = sum-1;
  int q1 = 0, q2 = 0;
  for(int i = 0 ; i < n ; ++ i)
   if (A[i] == 1)
    break;
   else
    q1++;
  for(int i = n-1 ; i >= 0 ; --i)
   if (A[i] == 1)
    break;
   else
    q2++;
  int thisq = min(q1,q2);
  for(int i = 0 ; i < thisq; ++ i)
   {
         arrive[host-i*2] = false;
   }
  scanf("%d",&q);
  while(q--)
   {
         int a;
         scanf("%d",&a);
         if (a > sum)
          {
                printf("No
");
                continue;
       }
      if(!arrive[a])
       printf("No
");
      else
       printf("Yes
");
   }
  return 0;
}

No Pain , No Gain.