A. Yet Another Tetris Problem

  • time limit per test: 2 seconds
  • memory limit per test: 256 megabytes

You are given some Tetris field consisting of $n$ columns. The initial height of the $i$-th column of the field is $a_i$ blocks. On top of these columns you can place $only$ figures of size $2×1$ (i.e. the height of this figure is $2$ blocks and the width of this figure is $1$ 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 $a_i$ is greater than $0$:

You place one figure $2×1$ (choose some $i$ from $1$ to $n$ and replace $a_i$ with $a_i+2$);
then, while all $a_i$ are greater than zero, replace each $a_i$ with $a_i?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 $t$ independent test cases.

Input

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

The next $2t$ lines describe test cases. The first line of the test case contains one integer $n (1≤n≤100)$ — the number of columns in the Tetris field. The second line of the test case contains $n$ integers $a_1,a_2,…,a_n (1≤a_i≤100)$, where $a_i$ is the initial height of the $i$-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

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

output

YES
NO
YES
YES

Note

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

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]$. Then place the figure in the second column and after the second step of the process, the field becomes $[0,0,0]$.

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

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]$. Then place the figure in the first column and after the second step of the process, the field becomes $[0,0]$.

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

Code

题意:俄罗斯方块,现在只会落下高度为$2$,宽度为$1$的方块,你可以控制落下的列,问是否能消除所有的方块。
显然,高度为$2$的方块不会改变任何一列的奇偶,当所有的列不是同奇或同偶的时候,无法消除。

#include <bits/stdc++.h>
using namespace std;

int main() {
    // freopen("in.txt", "r", stdin);
    int T; scanf("%d", &T);
    for(int t=1; t<=T; t++) {
        int n; scanf("%d", &n);
        int odd = 0, even = 0;
        for(int i=0; i<n; i++) {
            int x; scanf("%d", &x);
            if(x & 1) odd++;
            else even++;
        }
        if(odd == 0 || even == 0) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

B. Yet Another Palindrome Problem

  • time limit per test: 2 seconds
  • memory limit per test: 256 megabytes

You are given an array $a$ consisting of $n$ integers.

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

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

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

You have to answer $t$ independent test cases.

Input

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

Next $2t$ lines describe test cases. The first line of the test case contains one integer $n (3≤n≤5000)$ — the length of $a$. The second line of the test case contains $n$ integers $a_1,a_2,…,a_n (1≤a_i≤n)$, where $a_i$ is the $i$-th element of $a$.

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

Output

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

Example

input

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

YES
YES
NO
YES
NO

Note

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

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

In the third test case of the example, the array $a$ has no subsequences of length at least $3$ which are palindromes.

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

In the fifth test case of the example, the array $a$ has no subsequences of length at least $3$ which are palindromes.

Code

题意:给定一个字符串,求字符串中是否有长度至少为$3$的回文子序列。
回文会让人联想起长度为奇数和偶数的两种,但考虑到这道题是子序列所以长度为偶数的子序列必然包含长度为奇数的子序列,或者更进一步,必然包含长度为$3$的回文子序列。
所以问题的重点在于是否有长度为$3$的回文子序列。记录每个数字第一次出现的位置,初始化为$-1$,一旦存在这个数字再次出现且不与第一次出现相邻,则必定可以构成一个回文子序列。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e3 + 5;
int main() {
    // freopen("in.txt", "r", stdin);
    int T; scanf("%d", &T);
    for(int t=1; t<=T; t++) {
        int n; scanf("%d", &n);
        int mp[MAXN];
        for(int i=1; i<=n; i++) mp[i] = -1;
        bool flag = false;
        for(int i=1; i<=n; i++) {
            int x; scanf("%d", &x);
            if(mp[x] == -1) mp[x] = i;
            else if(mp[x] != i-1) flag = true;
        }
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

C. Frog Jumps

  • *time limit per test: 2 seconds
  • *memory limit per test: 256 megabytes
    There is a frog staying to the left of the string $s=s_1s_2…s_n$ consisting of $n$ characters (to be more precise, the frog initially stays at the cell $0$). Each character of $s$ is either 'L' or 'R'. It means that if the frog is staying at the $i$-th cell and the $i$-th character is 'L', the frog can jump only to the left. If the frog is staying at the $i$-th cell and the $i$-th character is 'R', the frog can jump only to the right. The frog can jump only to the right from the cell $0$.

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+1$-th cell. The frog chooses some positive integer value $d$ before the first jump (and cannot change it later) and jumps by no more than $d$ cells at once. I.e. if the $i$-th character is 'L' then the frog can jump to any cell in a range $[max(0,i?d);i?1]$, and if the $i$-th character is 'R' then the frog can jump to any cell in a range $[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 $d$ such that the frog can reach the cell $n+1$ from the cell $0$ if it can jump by no more than $d$ cells at once. It is guaranteed that it is always possible to reach $n+1$ from $0$.

You have to answer $t$ independent test cases.

Input

The first line of the input contains one integer $t (1≤t≤10^4)$ — the number of test cases.

The next $t$ lines describe test cases. The $i$-th test case is described as a string $s$ consisting of at least $1$ and at most $2?10^5$ characters 'L' and 'R'.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed $2?10^5$ $(∑|s|≤2?10^5)$.

Output

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

Example

input

6
LRLRRLL
L
LLR
RRRR
LLLLLL
R

output

3
2
3
1
7
1

Note

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

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

In the third test case of the example, the frog can choose $d=3$, jump to the cell $3$ from the cell $0$ and then to the cell $4$ from the cell $3$.

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

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

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

Code

题意:有一只青蛙站在起点$0$位置,最终要跳到$n+1$位置,$0$位置只能向右跳。有一个由L、R组成的长度为$n$的字符串决定了位置$[1,n]$青蛙可以跳的方向。求一个最小的数字$d$,$d$是青蛙每次可以跳跃距离的最大值,使青蛙能够跳到终点。
字符串中有用的只有R,向左跳不会有任何贡献。所以我们只需要计算相邻的R之间距离的最大值即可,当然包括起点与第一个R的距离和重点与最后一个R的距离。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
char s[MAXN];

int main() {
    // freopen("in.txt", "r", stdin);
    int T; scanf("%d", &T);
    for(int t=1; t<=T; t++) {
        scanf("%s", s);
        int n = strlen(s);
        int pre = -1, ans = 0;
        for(int i=0; i<n; i++) {
            if(s[i] == 'L') continue;
            ans = max(ans, i - pre);
            pre = i;
        }
        ans = max(ans, n - pre);
        printf("%d\n", ans);
    }
    return 0;
}

D. Pair of Topics

  • time limit per test: 2 seconds
  • memory limit per test: 256 megabytes

The next lecture in a high school requires two topics to be discussed. The $i$-th topic is interesting by $a_i$ units for the teacher and by $b_i$ units for the students.

The pair of topics $i$ and $j$ $(i<j)$ is called good if $a_i+a_j>b_i+b_j$ (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 $n$ $(2≤n≤2?10^5)$ — the number of topics.

The second line of the input contains $n$ integers $a_1,a_2,…,a_n$ $(1≤a_i≤10^9)$, where $a_i$ is the interestingness of the $i$-th topic for the teacher.

The third line of the input contains $n$ integers $b_1,b_2,…,b_n$ $(1≤b_i≤10^9)$, where $b_i$ is the interestingness of the $i$-th topic for the students.

Output

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

Examples

input 1

5
4 8 2 6 2
4 5 4 1 3

output 1

7

input 2

4
1 3 2 4
1 3 2 4

output 2

0

Code

题意:给出两个数组$a$和$b$,求满足$i<j$且$a_i+a_j>b_i+b_j$的数对个数。
将公式变换,可得到$(a_i-b_i)+(a_j-b_j)>0$。所以我们将数组做差,将差数组排序。
遍历差数组,对于每一个数字$d_i$,二分查找它后面第一个大于$-d_i$的数字位置,并统计入$ans$。
昨晚写的时候,一心想着还要满足$i<j$这个条件,不知道怎么下手。后来才意识到这个条件无非就是告诉你每一个数对不要算两遍,排完序之后不用管下标,我是猪……
记得开long long。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int MAXN = 2e5 + 5;
int a[MAXN], d[MAXN];

int main() {
    // freopen("in.txt", "r", stdin);
    int n; scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &a[i]);
    for(int i=0; i<n; i++) {
        int x; scanf("%d", &x);
        d[i] = a[i] - x;
    }
    sort(d, d+n); 
    LL ans = 0;
    for(int i=0; i<n-1; i++) {
        int x = -d[i], now = n;
        int left = i + 1, right = n - 1;
        while(left <= right) {
            int mid = (left + right) >> 1;
            if(d[mid] > x) {
                now = min(now, mid);
                right = mid - 1;
            }
            else left = mid + 1;
        }
        ans += 1LL * (n - now);
    }
    printf("%lld\n", ans);
    return 0;
}

E. Sleeping Schedule

  • time limit per test: 2 seconds
  • memory limit per test: 256 megabytes

Vova had a pretty weird sleeping schedule. There are $h$ hours in a day. Vova will sleep exactly $n$ times. The $i$-th time he will sleep exactly after $a_i$ 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 $0$). Each time Vova sleeps exactly one day (in other words, $h$ hours).

Vova thinks that the $i$-th sleeping time is good if he starts to sleep between hours $l$ and $r$ inclusive.

Vova can control himself and before the $i$-th time can choose between two options: go to sleep after $a_i$ hours or after $a_i?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,l$ and $r$ $(1≤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 $n$ integers $a_1,a_2,…,a_n$ $(1≤a_i<h)$, where $a_i$ is the number of hours after which Vova goes to sleep the $i$-th time.

Output

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

Example

input

7 24 21 23
16 17 14 20 20 11 22

output

3

Note

The maximum number of good times in the example is $3$.

The story starts from $t=0$. Then Vova goes to sleep after $a_1?1$ hours, now the time is $15$. This time is not good. Then Vova goes to sleep after $a_2?1$ hours, now the time is $15+16=7$. This time is also not good. Then Vova goes to sleep after $a_3$ hours, now the time is $7+14=21$. This time is good. Then Vova goes to sleep after $a_4?1$ hours, now the time is $21+19=16$. This time is not good. Then Vova goes to sleep after $a_5$ hours, now the time is $16+20=12$. This time is not good. Then Vova goes to sleep after $a_6$ hours, now the time is $12+11=23$. This time is good. Then Vova goes to sleep after $a_7$ hours, now the time is $23+22=21$. This time is also good.

Code

题意:给出$n$段睡觉时间和一天的长度$h$。假设现在是$0$点,你从$1$点开始连续睡完这$n$段时间,每次可以睡当前这段睡眠的时间或者当前这段睡眠时间$-1$。给出一段时间称为“好时间”,求有几次睡醒时落在这段“好时间”里。
一道比较简单的DP,居然一次就写对了,开心。
$dp[i][j]$表示第$i$段睡眠,并且前$i$段睡眠里一共使用了$j$次时长$-1$。计算出当前的时间,如果落在“好时间”范围内,$dp[i][j]=max(dp[i-1][j], dp[i-1][j-1])+1$,否则$dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])$。
为了能够快速的得到时长,用前缀和处理睡眠时间。为了不用判断边界,$j$采用后移一位处理。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e3 + 5;
int dp[MAXN][MAXN], sleep[MAXN], sum[MAXN];

int main() {
    // freopen("in.txt", "r", stdin);
    int n, h, l, r; scanf("%d %d %d %d", &n, &h, &l, &r);
    for(int i=0; i<n; i++) scanf("%d", &sleep[i]);
    sum[0] = 0;
    for(int i=0; i<n; i++) sum[i+1] = sum[i] + sleep[i];

    memset(dp, -1, sizeof(dp)); dp[0][9] = 0;
     int ans = 0;
    for(int i=1; i<=n; i++) {
        for(int j=0; j<=i; j++) {
            int now = (sum[i] - j) % h;
            if(l <= now && now <= r) dp[i][j+1] = max(dp[i-1][j], dp[i-1][j+1]) + 1;
            else dp[i][j+1] = max(dp[i-1][j], dp[i-1][j+1]);
            ans = max(ans, dp[i][j+1]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

F. Maximum White Subtree

  • time limit per test: 2 seconds
  • memory limit per test: 256 megabytes

You are given a tree consisting of $n$ vertices. A tree is a connected undirected graph with $n?1$ edges. Each vertex $v$ of this tree has a color assigned to it ($a_v=1$ if the vertex $v$ is white and $0$ if the vertex $v$ is black).

You have to solve the following problem for each vertex v: what is the maximum difference between the number of white and the number of black vertices you can obtain if you choose some subtree of the given tree that contains the vertex v? The subtree of the tree is the connected subgraph of the given tree. More formally, if you choose the subtree that contains $cnt_w$ white vertices and $cnt_b$ black vertices, you have to maximize $cnt_w?cnt_b$.

Input

The first line of the input contains one integer $n$ $(2≤n≤2?10^5)$ — the number of vertices in the tree.

The second line of the input contains $n$ integers $a_1,a_2,…,a_n$ $(0≤a_i≤1)$, where $a_i$ is the color of the $i$-th vertex.

Each of the next $n?1$ lines describes an edge of the tree. Edge $i$ is denoted by two integers $u_i$ and $v_i$, the labels of vertices it connects $(1≤u_i,v_i≤n,u_i≠v_i)$.

It is guaranteed that the given edges form a tree.

Output

Print $n$ integers $res_1,res_2,…,res_n$, where $res_i$ is the maximum possible difference between the number of white and black vertices in some subtree that contains the vertex $i$.

Examples

input 1

9
0 1 1 1 0 0 0 0 1
1 2
1 3
3 4
3 5
2 6
4 7
6 8
5 9

output 1

2 2 2 2 2 1 1 0 2

input 2

4
0 0 1 0
1 2
1 3
1 4

output 2

0 -1 1 -1

Note

The first example is shown below:

The black vertices have bold borders.

In the second example, the best subtree for vertices $2$,$3$ and $4$ are vertices $2$,$3$ and $4$ correspondingly. And the best subtree for the vertex $1$ is the subtree consisting of vertices $1$ and $3$.

Code

题意:给出一棵树,树上的每个结点是黑色或白色。对于每一个节点,求出包含该节点的子树中,白色节点与黑色节点数量之差的最大值。
我不会做啦,看的zz的视频,哼!
将问题分解成两部分。首先,如何求包含指定节点的子树的答案;其次,如何将这个答案推广到整个树上。
第一个问题soeasy啦,以这个节点为根在树上进行dfs,在回溯的时候更新答案。
对于第二个问题嘛,学到了zz的换根DP。毕竟如果暴力求的话,对于每个节点都作为根dfs一遍,复杂度是$O(n^2)$的。假设要更换把根$x$换为根$y$,其实很简单啦,首先把$y$对于$x$答案的贡献清掉,然后再把$x$的贡献加在$y$上。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
int color[MAXN], mx[MAXN], ans[MAXN];
vector<int> edge[MAXN];

void dfs(int x, int fa) {
    mx[x] = (color[x] == 1 ? 1 : -1);
    for(auto v: edge[x]) {
        if(v == fa) continue;
        dfs(v, x);
        if(mx[v] >= 0) mx[x] += mx[v];
    }
}

void changeRoot(int x, int fa) {
    for(auto v: edge[x]) {
        if(v == fa) continue;
        int sv = mx[v], sx = mx[x];
        if(mx[v] >= 0) mx[x] -= mx[v];
        if(mx[x] >= 0) mx[v] += mx[x];
        ans[v] = mx[v];
        changeRoot(v, x);
        mx[v] = sv, mx[x] = sx;
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    int n; scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &color[i]);
    for(int i=1; i<n; i++) {
        int x, y; scanf("%d %d", &x, &y);
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs(1, 0); ans[1] = mx[1];
    changeRoot(1, 0);
    for(int i=1; i<=n; i++) printf("%d%c", ans[i], i == n ? '\n' : ' ');
     return 0;
}
最后修改:2020 年 03 月 20 日 12 : 38 PM
如果觉得我的文章对你有用,请随意赞赏