您现在的位置是:首页 > 正文

Codeforces Round #627 (Div. 3)题解

2024-02-01 01:22:42阅读 3

A. Yet Another Tetris Problem

题目

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given some Tetris field consisting of nn columns. The initial height of the ii-th column of the field is aiai blocks. On top of these columns you can place only figures of size 2×12×1 (i.e. the height of this figure is 22 blocks and the width of this figure is 11 block). Note that you cannot rotate these figures.

Your task is to say if you can clear the whole field by placing such figures.

More formally, the problem can be described like this:

The following process occurs while at least one aiai is greater than 00:

  1. You place one figure 2×12×1 (choose some ii from 11 to nn and replace aiai with ai+2ai+2);
  2. then, while all aiai are greater than zero, replace each aiai with ai−1ai−1.

And your task is to determine if it is possible to clear the whole field (i.e. finish the described process), choosing the places for new figures properly.

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤1001≤t≤100) — the number of test cases.

The next 2t2t lines describe test cases. The first line of the test case contains one integer nn (1≤n≤1001≤n≤100) — the number of columns in the Tetris field. The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1001≤ai≤100), where aiai is the initial height of the ii-th column of the Tetris field.

Output

For each test case, print the answer — “YES” (without quotes) if you can clear the whole Tetris field and “NO” otherwise.

Example

input

Copy

4
3
1 1 3
4
1 1 2 1
2
11 11
1
100

output

Copy

YES
NO
YES
YES

Note

The first test case of the example field is shown below:

img

Gray lines are bounds of the Tetris field. Note that the field has no upper bound.

One of the correct answers is to first place the figure in the first column. Then after the second step of the process, the field becomes [2,0,2][2,0,2]. Then place the figure in the second column and after the second step of the process, the field becomes [0,0,0][0,0,0].

And the second test case of the example field is shown below:

img

It can be shown that you cannot do anything to end the process.

In the third test case of the example, you first place the figure in the second column after the second step of the process, the field becomes [0,2][0,2]. Then place the figure in the first column and after the second step of the process, the field becomes [0,0][0,0].

In the fourth test case of the example, place the figure in the first column, then the field becomes [102][102] after the first step of the process, and then the field becomes [0][0] after the second step of the process.

题意

俄罗斯方块:给你每一列的高度 每次只能竖着放尺寸2*1的长方形,问是否能全部消

分析

一眼题,消除的必定是相连奇偶性相同的

代码

import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict




IA = lambda: map(int,input().split())

T=int(input())

for i in range(0,T):

    n=int(input())
    vis=[int(-1) for i in range(0,n+1)]
    a=list(IA())
    le=len(a)
    flag=1
    t=a[0]&1
    for i in range(1,le):
        if (a[i]&1)!=t:
            flag=0
            break
        
        
    if flag==1:
        print("YES")
    else:
        print("NO")
    
#a = [int(0) for i in range(1,n+1)]

B. Yet Another Palindrome Problem

B. Yet Another Palindrome Problem

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array aa consisting of nn integers.

Your task is to determine if aa has some subsequence of length at least 33 that is a palindrome.

Recall that an array bb is called a subsequence of the array aa if bb can be obtained by removing some (possibly, zero) elements from aa (not necessarily consecutive) without changing the order of remaining elements. For example, [2][2], [1,2,1,3][1,2,1,3] and [2,3][2,3] are subsequences of [1,2,1,3][1,2,1,3], but [1,1,2][1,1,2] and [4][4] are not.

Also, recall that a palindrome is an array that reads the same backward as forward. In other words, the array aa of length nn is the palindrome if ai=an−i−1ai=an−i−1 for all ii from 11 to nn. For example, arrays [1234][1234], [1,2,1][1,2,1], [1,3,2,2,3,1][1,3,2,2,3,1] and [10,100,10][10,100,10] are palindromes, but arrays [1,2][1,2] and [1,2,3,1][1,2,3,1] are not.

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤1001≤t≤100) — the number of test cases.

Next 2t2t lines describe test cases. The first line of the test case contains one integer nn (3≤n≤50003≤n≤5000) — the length of aa. The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n), where aiai is the ii-th element of aa.

It is guaranteed that the sum of nn over all test cases does not exceed 50005000 (∑n≤5000∑n≤5000).

Output

For each test case, print the answer — “YES” (without quotes) if aa has some subsequence of length at least 33 that is a palindrome and “NO” otherwise.

Example

input

Copy

5
3
1 2 1
5
1 2 2 3 2
3
1 1 2
4
1 2 2 1
10
1 1 2 2 3 3 4 4 5 5

output

Copy

YES
YES
NO
YES
NO

Note

In the first test case of the example, the array aa has a subsequence [1,2,1][1,2,1] which is a palindrome.

In the second test case of the example, the array aa has two subsequences of length 33 which are palindromes: [2,3,2][2,3,2] and [2,2,2][2,2,2].

In the third test case of the example, the array aa has no subsequences of length at least 33 which are palindromes.

In the fourth test case of the example, the array aa has one subsequence of length 44 which is a palindrome: [1,2,2,1][1,2,2,1] (and has two subsequences of length 33 which are palindromes: both are [1,2,1][1,2,1]).

In the fifth test case of the example, the array aa has no subsequences of length at least 33 which are palindromes.

题意

是否可以找至少长度为3的回文串

分析

只要找到两个不相邻的数相等就满足题意

代码

import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict




IA = lambda: map(int,input().split())

T=int(input())

for i in range(0,T):

    n=int(input())
    vis=[int(-1) for i in range(0,n+1)]
    a=list(IA())
    le=len(a)
    flag=0
    for i in range(0,le):
        if vis[a[i]]!=-1:
            if i-vis[a[i]]>1:
                flag=1
                break
            
        else:
            vis[a[i]]=i
        
    if flag==1:
        print("YES")
    else:
        print("NO")
    
#a = [int(0) for i in range(1,n+1)]

C. Frog Jumps

C. Frog Jumps

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There is a frog staying to the left of the string s=s1s2…sns=s1s2…sn consisting of nn characters (to be more precise, the frog initially stays at the cell 00). Each character of ss is either ‘L’ or ‘R’. It means that if the frog is staying at the ii-th cell and the ii-th character is ‘L’, the frog can jump only to the left. If the frog is staying at the ii-th cell and the ii-th character is ‘R’, the frog can jump only to the right. The frog can jump only to the right from the cell 00.

Note that the frog can jump into the same cell twice and can perform as many jumps as it needs.

The frog wants to reach the n+1n+1-th cell. The frog chooses some positive integer value dd before the first jump (and cannot change it later) and jumps by no more than dd cells at once. I.e. if the ii-th character is ‘L’ then the frog can jump to any cell in a range [max(0,i−d);i−1][max(0,i−d);i−1], and if the ii-th character is ‘R’ then the frog can jump to any cell in a range [i+1;min(n+1;i+d)][i+1;min(n+1;i+d)].

The frog doesn’t want to jump far, so your task is to find the minimum possible value of dd such that the frog can reach the cell n+1n+1 from the cell 00 if it can jump by no more than dd cells at once. It is guaranteed that it is always possible to reach n+1n+1 from 00.

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases.

The next tt lines describe test cases. The ii-th test case is described as a string ss consisting of at least 11 and at most 2⋅1052⋅105 characters ‘L’ and ‘R’.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed 2⋅1052⋅105 (∑|s|≤2⋅105∑|s|≤2⋅105).

Output

For each test case, print the answer — the minimum possible value of dd such that the frog can reach the cell n+1n+1 from the cell 00 if it jumps by no more than dd at once.

Example

input

Copy

6
LRLRRLL
L
LLR
RRRR
LLLLLL
R

output

Copy

3
2
3
1
7
1

Note

The picture describing the first test case of the example and one of the possible answers:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UbbjjlpM-1584117518441)(https://espresso.codeforces.com/de84e2ea205b39d12a73b422b7f6b0229de451ba.png)]

In the second test case of the example, the frog can only jump directly from 00 to n+1n+1.

In the third test case of the example, the frog can choose d=3d=3, jump to the cell 33 from the cell 00 and then to the cell 44 from the cell 33.

In the fourth test case of the example, the frog can choose d=1d=1 and jump 55 times to the right.

In the fifth test case of the example, the frog can only jump directly from 00 to n+1n+1.

In the sixth test case of the example, the frog can choose d=1d=1 and jump 22 times to the right.

题意:

给一个长度为n里面有’L’ ‘R’ 的字符串,表示向左或者向右移动最大d长度, 在可以跳到终点n+1的情况下,问d最小是多长。

分析:

因为我们根本不需要往左跳,左跳只会降低我们的位置,起点终点当作两个R,然后判断两个RR之间的最大距离即可。(证明咳咳)

代码:

from collections import defaultdict




IA = lambda: map(int,input().split())

T=int(input())

for i in range(0,T):

    n=input()
    le=len(n)
    l=int(0)

    pre=0
    i=0
    ans=0
    for it in n:
        i+=1 
        if it=='R':
            ans=max(ans,i-pre)
            pre=i
          
    ans=max(ans,le+1-pre)
    print(ans)
    
#a = [int(0) for i in range(1,n+1)]

D. Pair of Topics

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

The next lecture in a high school requires two topics to be discussed. The ii-th topic is interesting by aiai units for the teacher and by bibi units for the students.

The pair of topics ii and jj (i<ji<j) is called good if ai+aj>bi+bjai+aj>bi+bj (i.e. it is more interesting for the teacher).

Your task is to find the number of good pairs of topics.

Input

The first line of the input contains one integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the number of topics.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109), where aiai is the interestingness of the ii-th topic for the teacher.

The third line of the input contains nn integers b1,b2,…,bnb1,b2,…,bn (1≤bi≤1091≤bi≤109), where bibi is the interestingness of the ii-th topic for the students.

Output

Print one integer — the number of good pairs of topic.

Examples

input

Copy

5
4 8 2 6 2
4 5 4 1 3

output

Copy

7

input

Copy

4
1 3 2 4
1 3 2 4

output

Copy

0

题意:

给你两个长度均为n的数列a和b,找到满足a[i]+a[j]>b[i]+b[j]的对数(i<j).

分析:

a[i]-b[i]>-(a[j]-b[j])

c[i]>-c[j]

两种思想,三种方法:

  1. 树状数组类似逆序对做法
  2. c[i]+c[j]>0,双指针或者二分

代码:

from collections import defaultdict




IA = lambda: map(int,input().split())

n=int(input())

a=list(IA())
b=list(IA())

for i in range(0,n):
    a[i]=a[i]-b[i]

a=sorted(a)
l=0
r=n-1
ans=0
#print(a)
while r>l:
    if a[l]+a[r]>0:
        ans+=r-l
        r-=1
    else:l+=1
print(ans)
#a = [int(0) for i in range(1,n+1)]


from collections import defaultdict



def solve(x,pos):
    l=0
    r=pos
    while l<r:
        mid=(l+r)>>1
        if a[mid]+x>0:
            r=mid
        else:
            l=mid+1
  
    return pos-l

IA = lambda: map(int,input().split())

n=int(input())

a=list(IA())
b=list(IA())

for i in range(0,n):
    a[i]=a[i]-b[i]

a=sorted(a)
l=0
r=n-1
ans=0
#print(a)

for i in range(0,n):
    ans+=solve(a[i],i)
    
print(ans)


#a = [int(0) for i in range(1,n+1)]

E. Sleeping Schedule

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Vova had a pretty weird sleeping schedule. There are hh hours in a day. Vova will sleep exactly nn times. The ii-th time he will sleep exactly after aiai hours from the time he woke up. You can assume that Vova woke up exactly at the beginning of this story (the initial time is 00). Each time Vova sleeps exactly one day (in other words, hh hours).

Vova thinks that the ii-th sleeping time is good if he starts to sleep between hours ll and rr inclusive.

Vova can control himself and before the ii-th time can choose between two options: go to sleep after aiai hours or after ai−1ai−1 hours.

Your task is to say the maximum number of good sleeping times Vova can obtain if he acts optimally.

Input

The first line of the input contains four integers n,h,ln,h,l and rr (1≤n≤2000,3≤h≤2000,0≤l≤r<h1≤n≤2000,3≤h≤2000,0≤l≤r<h) — the number of times Vova goes to sleep, the number of hours in a day and the segment of the good sleeping time.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai<h1≤ai<h), where aiai is the number of hours after which Vova goes to sleep the ii-th time.

Output

Print one integer — the maximum number of good sleeping times Vova can obtain if he acts optimally.

Example

input

Copy

7 24 21 23
16 17 14 20 20 11 22

output

Copy

3

Note

The maximum number of good times in the example is 33.

The story starts from t=0t=0. Then Vova goes to sleep after a1−1a1−1 hours, now the time is 1515. This time is not good. Then Vova goes to sleep after a2−1a2−1 hours, now the time is 15+16=715+16=7. This time is also not good. Then Vova goes to sleep after a3a3 hours, now the time is 7+14=217+14=21. This time is good. Then Vova goes to sleep after a4−1a4−1 hours, now the time is 21+19=1621+19=16. This time is not good. Then Vova goes to sleep after a5a5 hours, now the time is 16+20=1216+20=12. This time is not good. Then Vova goes to sleep after a6a6 hours, now the time is 12+11=2312+11=23. This time is good. Then Vova goes to sleep after a7a7 hours, now the time is 23+22=2123+22=21. This time is also good.

题意

一天有h小时,主人公要睡n次觉,一次可以睡a[i]小时或者a[i]-1个小时,醒了马上就要睡下一觉直到睡完n次,如果睡觉起来的时候时间(如果时间大于一天就要对h取模)在l到r之间,那么这一觉就是good,加一分,问你睡完这n次,最多得多少分?

分析

t挺简单的一个DP,当时忘记了二维还能取模,算错了空间复杂度,背包的思想完全能搞。

代码

from collections import defaultdict

IA = lambda: map(int,input().split())

n,h,l,r=IA()
a=list(IA())


def judge(x):
    if x<=r and x>=l:
        return 1
    return 0



dp=[[int(-1) for _ in range(h)] for _ in range(n+1)]

dp[0][0]=0
for i in range(0,n):
    for j in range(0,h):
        if dp[i][j]>=0:
            
            dp[i+1][(j+a[i])%h]=max(dp[i][j]+int(l<=(j+a[i])%h<=r),dp[i+1][(j+a[i])%h])
            dp[i+1][(j+a[i]-1)%h]=max(dp[i][j]+int(l<=(j+a[i]-1)%h<=r),dp[i+1][(j+a[i]-1)%h])
        
        

ans=max(dp[-1])
print(ans)


#a = [int(0) for i in range(1,n+1)]

网站文章

  • (11)web安全|渗透测试|网络安全 漏洞挖掘的重点环节及基础知识

    (11)web安全|渗透测试|网络安全 漏洞挖掘的重点环节及基础知识

    (11)web安全|渗透测试|网络安全 漏洞挖掘的重点环节及基础知识

    2024-02-01 01:22:36
  • vCenter 服务器漏洞可导致代码执行和认证绕过

    vCenter 服务器漏洞可导致代码执行和认证绕过

    聚焦源代码安全,网罗国内外最新资讯!编译:代码卫士VMware 修复了位于 vCenter Server 中的多个高危漏洞,可导致攻击者获得代码执行权限并绕过未修复系统上的认证。vCenter Ser...

    2024-02-01 01:22:07
  • 解决实现虚拟机win10与主机文件的共享问题

    解决实现虚拟机win10与主机文件的共享问题

    2024-02-01 01:21:59
  • class二进制文件解析(一)

    class二进制文件解析(一)

    class文件创建及解析创建项目结构:#项目名称testclassmkdir testClass#进入相应目录cd testClass#源码目录mkdir src#输出目录mkdir out#进入源码...

    2024-02-01 01:21:51
  • SSM医疗管理系统 热门推荐

    SSM医疗管理系统 热门推荐

    《SSM医疗管理系统》该项目采用技术jsp、SpringMVC、Spring、Mybatis、tomcat服务器、mysql数据库 开发工具eclipse,项目含有源码、文档、配套开发软件、软件安装教...

    2024-02-01 01:21:44
  • 112.求解非线性方程

    #include "math.h"#include "stdio.h"int BinSearchRoot(a,b,h,eps,x,m) /*用二法计算非线性方程的实根*/int m;/*参数意义:a ...

    2024-02-01 01:21:06
  • Spring-AOP深度学习

    AOP是一种编程范式,旨在将不同关注点(如日志记录、事务管理、性能监视等)与应用程序的核心业务逻辑分离开来。它通过在关注点与业务逻辑之间的交叉点(称为切点)上插入代码来实现这一目标。切点(Pointcut):切点是您选择在哪里插入额外代码的规则或条件。通常,它是一个方法的签名或一个特定的类。通知(Advice):通知是在切点上执行的额外代码块。

    2024-02-01 01:21:01
  • 【SQL基础】查询数据 —— 排序

    【SQL基础】查询数据 —— 排序

    排序 查询结果集通常是按照id排序的,也就是根据主键排序。如果要根据其他条件排序,可以使用ORDER BY子句 -- 按score从低到高排序 SELECT id, name, gender, score FROM students ORDER BY score; 查询结果 如果想从高到低排序,加上DESC -- 按score从高到低排序 SELECT id, name, gender, ...

    2024-02-01 01:20:55
  • 在Ubuntu下,从零开始写操作系统(0)-笔记

    1.安装Ubuntu 16.04操作系统 32位,因为16.04版本是最稳定的版本。安装方法请百度。2.安装bochs; 命令:sudo apt-get install bochs3.安装gcc;可能系统没有自带gcc, 命令:sudo apt-get install gcc编写如下代码//16位的代码段.code16//代码起始.text mov %cs,%...

    2024-02-01 01:20:17
  • 第十三周总结

    这周重点了解水王的题目,去借鉴别人的代码去修改这一周在代码上花费的时间加起来差不多16个小时。共写了1000行代码。转载于:https://www.cnblogs.com/lishengming00/p/11071283.html...

    2024-02-01 01:20:11