Blue Bridge Cup ruler method

Palindrome determination

 Title Description 
 Given a length of  n  String  S. Please judge the string  S  Whether palindrome .

 Input description 
 Input only  1  The line contains a string  S.

1≤∣S∣≤10^6, Guarantee  S  Case only 、 Letter .

 Output description 
 If the string  S  Palindrome string , The output  Y, Otherwise output  N.

 I/o sample 
 Example  1
 Input 

abcba

 Output 

Y

 Example  2
 Input 

abcbb

 Output 

N

 Operation limit 
 Maximum operation time ：1s
 Maximum running memory : 128M

analysis

• Before this leetcode I did , Belongs to the template （ Must remember ）

Code

def judge(s):
  left = 0
  right = len(s)-1
  while left < right:
    if s[left] != s[right]:
      return 0
    left+=1
    right-=1
  return 1

s = input()
if judge(s):
  print("Y")
else:
  print("N")

Through screenshots

subject 2279: Blue Bridge Cup 2018 The ninth real topic in - Log statistics

 The time limit : 1Sec  Memory limit : 128MB  Submit : 2271  solve : 512
 Title Description 
 Xiaoming maintains a programmer Forum . Now he has a collection of " give the thumbs-up " journal , The logs share N That's ok . The format of each line is ：

ts id  

 It means that ts Time number id 's post received a " Fabulous ".  

 Now Xiaoming wants to count which posts have been " Hot post ". If a post has been in any length of D Receive no less than within the time period of K A great , Xiao Ming thinks this post was " Hot post ".  

 say concretely , If there is a moment T Satisfy the post in [T, T+D) In this period of time ( Notice that it's left closed right open ) Received no less than K A great , The post was once " Hot post ".  

 Given the log , Please help Xiao Ming count out all the things that used to be " Hot post " The post number of . 
 Input 
 The first line contains three integers N、D and K.  
 following N Each line has a log , Contains two integers ts and id.  

 about 50% The data of ,1 <= K <= N <= 1000  
 about 100% The data of ,1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000
 Output 
 Output hot posts from small to large id. Every id a line .
 The sample input 
7 10 2  
0 1  
0 10    
10 10  
10 1  
9 1
100 3  
100 3 
 Sample output 
1  
3 

analysis

• The first idea is to speed the pointer , Make sliding window . Sort the time , Quick pointer to the number of likes to add , The slow pointer is used to cancel the number of likes , If the time difference between the fast pointer and the slow pointer is greater than or equal to the specified time , Then the slow pointer needs to move , If the number of likes is greater than or equal to the specified value , Then use flag The array tag specifies the location .
• flag Arrays are pretty fast in my opinion , Because if you use lists to collect results , According to the requirements of the topic duplicate removal and Sort （ These operations take a lot of time ）, It would be better to trade space for time .
• Very helpless , This method uses python It's overtime , In terms of score , It should be right .python and c++ Much slower than it really is , hope python Group and other groups can have more time to run on the same topic

Code

N,D,K = map(int,input().split())
path = []
res = []
nums= [0]* 100001
flag = [0] * 100001
for i in range(N):
    path.append(list(map(int,input().split())))

path.sort(key = lambda x :x[0])

slow = 0
for fast in range(N):
    nums[path[fast][1]]+=1 #  give the thumbs-up ++
    while path[fast][0]-path[slow][0] >= D: #  The time difference is greater than the specified time 
        nums[path[slow][1]]-=1 #  Like Cancel 
        slow+=1
    if nums[path[fast][1]] >= K: #  The number of likes reached the standard 
        flag[path[fast][1]] = 1
for i in range(len(flag)):
    if flag[i]:
        print(i)

Time out screenshot