上午看大话数据结构，了解了线索二叉树。

下午测试（两题）

晚上补题 （一题）

题目描述

Imp likes his plush toy a lot.

Recently, he found a machine that can clone plush toys. Imp knows that if he applies the machine to an original toy, he additionally gets one more original toy and one copy, and if he applies the machine to a copied toy, he gets two additional copies.

Initially, Imp has only one original toy. He wants to know if it is possible to use machine to get exactly xx copied toys and yy original toys? He can't throw toys away, and he can't apply the machine to a copy if he doesn't currently have any copies.

输入格式

The only line contains two integers xx and yy ( 0<=x,y<=10^{9}0<=x,y<=109 ) — the number of copies and the number of original toys Imp wants to get (including the initial one).

输出格式

Print "Yes", if the desired configuration is possible, and "No" otherwise.

You can print each letter in arbitrary case (upper or lower).

题意翻译

题目描述

Imp非常喜欢他的毛绒玩具。

最近，他发现了一个可以克隆毛绒玩具的机器。Imp知道如果他将一个玩具本体进行克隆，他将会得到两个本体（新增一个）和一个克隆体；而如果将一个克隆体进行克隆，他将会得到三个克隆体（新增两个）。

一开始，Imp只有一个毛绒玩具本体。他想要知道他能否使用这个机器得到恰好xx 个克隆体和yy 个本体。他不能把玩具扔掉，也不能在没有克隆体的时候对一个克隆体进行克隆。 输入格式

一行两个整数x,y(0 \le x,y \le 10^9)x,y(0≤x,y≤109) ，分别表示Imp想要得到的玩具克隆体数量和本体数量（包括一开始的一个本体）。 输出格式

如果能够满足题意，输出"Yes"，否则输出"No"。大小写不敏感。 说明

在样例一中，Imp可以对本体进行两次克隆，再对克隆体进行两次克隆。 翻译贡献者：浮尘ii

输入输出样例

输入 #1复制

6 3

输出 #1复制

Yes

输入 #2复制

4 2

输出 #2复制

No

输入 #3复制

1000 1001

输出 #3复制

Yes

说明/提示

In the first example, Imp has to apply the machine twice to original toys and then twice to copies.

错了好几次，细节地方没搞好 

1、本体数量不可能为 0 。

2、如果本体只需要一个，那么克隆体就只能为 0 ，反之亦然 。否则如果本体为 1 或克隆体为 0 就不可能满足需要 。

3、本体可以克隆出一个本体和一个克隆体，所以克隆体的数量必须大于等于本体数量 - 1(一开始的本体) 才可能满足需要 。 当本体达到了数量要求，此时克隆体的数量为 y-1 ，一个克隆体可以克隆出两个克隆体，所以只需再判断 x - ( y-1 ) 是否为 2 的倍数就能知道能不能满足。

#include<stdio.h>

int main()
{
    long long x,y;
    scanf("%lld%lld",&x,&y);
    if(y==1&&x==0) printf("Yes\n");
    else if(y==1||y==0||x==0) printf("No\n");
    else if((x-(y-1))%2==0&&x>=y-1) printf("Yes\n");
    else printf("No\n");
}

题目描述

In this problem, we define a sequence of ( and ) as a "bracket sequence".

The definition of Regular Bracket Sequence is as follows:

1. () is a Regular Bracket Sequence.
2. If A is a Regular Bracket Sequence, then (A) is also a Regular Bracket Sequence.
3. If A and B are Regular Bracket Sequences, then AB is also a Regular Bracket Sequence.

For example: (), (()), and ()() are all Regular Bracket Sequences, but )(, ()( are not.

In particular, an empty sequence is not a Regular Bracket Sequence sequence in this problem.

Now cute Ran gives you a bracket sequence ss of length nn. She wants you to construct 2\cdot m2⋅m strictly increasing arrays. Let us denote them as p_1,p_2,\cdots,p_{2 m}p1​,p2​,⋯,p2m​ (you can leave any of them empty). You need to ensure that all integers between 1\sim n1∼n appear exactly once in these arrays.

An array p_i=\{r_1,r_2,\cdots,r_k\}pi​={r1​,r2​,⋯,rk​} is Beautiful if \{s_{r_1},s_{r_2},\cdots,s_{r_k}\}{sr1​​,sr2​​,⋯,srk​​} is a Regular Bracket Sequence.

Ran wonders whether it is possible to construct these arrays so that at least mm of the 2\cdot m2⋅m arrays are "beautiful arrays".

输入格式

Each test contains multiple test cases.

The first line contains an integer TT, the number of test cases.

For each test case, the first line contains two integers nn and mm, and the second line contains a bracket sequence ss.

输出格式

For each test case, print one line.

If it is possible to construct these arrays, print 11. Otherwise print 00.

题意翻译

定义一个字符串为括号串当且仅当其仅由 ( 和 ) 组成。

试将一个长度为 nn 的括号串分为 2m2m 个子序列，子序列可以为空，且每个字符都必须分到恰好一个子序列中，使得至少 mm 个子序列为匹配的括号串。空序列不算匹配的括号序列。无解请输出 00，否则输出 11。本题多组数据，其中数据组数为 TT。

定义 AA 为 BB 的子序列当且仅当 AA 能由 BB 在顺序不改变的前提下删除若干元素后得到。

*样例 11 解释：你可以将第一个和第二个字符分入第一个子序列，让第二个子序列为空子序列。此时第一个子序列为 ()，第二个为空，总计有一个匹配的括号序列，满足要求。

输入输出样例

输入 #1复制

2
2 1
()
2 99
()

输出 #1复制

1
0

说明/提示

Explanation

For the first test case, we can construct p_1=\{1,2\}p1​={1,2} and p_2=\{\}p2​={}. So p_1p1​ is a "beautiful array".

For the second test case, it is obvious that we cannot use two numbers to construct 9999 beautiful arrays.

Constraints

1\le T,n,m\le 2001≤T,n,m≤200.

 

这题是括号匹配问题。

如果是左括号就入栈，是右括号并且栈不为空就出栈，每这样子出一次栈就+1，最后判断是否大于等于 m 。

#include<stdio.h>
#include<math.h>
int main()
{
    int n,m,T;
    char s[1000],a[1000];
    scanf("%d",&T);
    while(T--){
    scanf("%d%d",&n,&m);
    scanf("%s",s);
    int i,top=0,sum=0;
    for(i=0;s[i];i++){
        if(s[i]=='(') a[++top]=s[i];
        else{
            if(top==0) continue;
            else if(s[i]==')'){
                sum++;
                top--;
            }
        }
    }
    if(sum>=m) printf("1\n");
    else printf("0\n");
    }
}

 

题目描述

The difference between the versions is the limit of operations.

Alice is a cute girl who has a lot of dolls.

There are 4\cdot n4⋅n dolls playing rock-paper-scissors. They are divided into two teams: Team A and Team B. Each team contains 2\cdot n2⋅n dolls.

A total of 2\cdot n2⋅n rounds of the game will be played. In the ii-th round, the ii-th doll in Team A will play against the ii-th doll in Team B. If the doll in Team A wins, Team A will get 11 point. If it loses, Team A will lose 11 point. If it ties, Team A will not get points.

Alice knows all the dolls' choices in this game. To be precise, she uses two arrays aa and bb to represent the choices of the dolls in the two teams. a_iai​ means the choice of the ii-th doll in Team A, and b_ibi​ means the choice of the ii-th doll in Team B. In this question, we use 11 for rock, 22 for scissors, and 33 for paper.

Now for each team, Alice wants to change the choices of at most nn dolls to make the score of Team A as high as possible.

Find the maximum score of Team A and its construction method. If there are multiple answers print any of them (you still have to maximize the score of Team A).

输入格式

Each test contains multiple testcases. The first line contains an integer TT, the number of test cases.

For each test case, the first line contains one integer nn.

Then two lines follow, containing an array aa of length 2\cdot n2⋅n and an array bb of length 2\cdot n2⋅n, respectively.

输出格式

For each test case, print three lines.

The first line contains one integer, the maximum score of Team A.

The second line contains an array a'a′ of length 2\cdot n2⋅n, which represents the aa array after Alice's modification. For integers 11 to 2\cdot n2⋅n, if a_i \ne a'_iai​=ai′​, then it means you have modified the choice of one player in Team A.

The third line contains an array b'b′ of length 2\cdot n2⋅n, which represents the bb array after Alice's modification. For integers 11 to 2\cdot n2⋅n, if b_i \ne b'_ibi​=bi′​, then it means you have modified the choice of one player in Team B.

题意翻译

AB 每队 2n2n 人正在玩石头剪刀布。A 队第 ii 个人出 a_iai​，B 队第 ii 个人出 b_ibi​。编号相同的人会对战。若 A 队赢则加一分，平不得分，输扣一分。你可以至多改变每队 nn 个人的出拳方案，使得 A 队的得分最高。输出得分的最大值和任意一组构造方案。

本题中，我们用 11 代表石头，22 代表剪刀，33 代表布。

输入输出样例

输入 #1复制

2
1
1 2
1 2
2
2 3 1 3
1 2 2 1

输出 #1复制

2
1 1
2 2
4
3 1 1 3
1 2 2 1

说明/提示

Explanation

For the first test case, we can change a_2a2​ to 11 and b_1b1​ to 22. Then Team A can get 22 points. It can be proved that this is the maximum score that Team A can get.

For the second test case, we can change a_1a1​ to 33 and a_2a2​ to 11.

Constraints

1\le T,n \le 10^5;\ 1\le a_i,b_i \le 31≤T,n≤105; 1≤ai​,bi​≤3. The sum of nn over all test cases \le 10^5≤105.

思路：碰到 A 平局或者是输了，就将改成 A 队赢 B 队的 ，当 A 队改的数量达到了n ,就开始改B 队的。

#include<stdio.h>

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int t=0;
        int n,a[200000],b[200000];
        scanf("%d",&n);
        for(int i=0;i<2*n;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<2*n;i++)
            scanf("%d",&b[i]);
        for(int i=0;i<2*n;i++)
            if((a[i]==1&&b[i]==2)||(a[i]==2&&b[i]==3)||(a[i]==3&&b[i]==1)) continue;
            else{
                if(t<n){
                if(b[i]==1) a[i]=3;
                if(b[i]==2||b[i]==3) a[i]=b[i]-1;
                t++;
                }
                else{
                    if(a[i]==3) b[i]=1;
                    if(a[i]==2||a[i]==1) b[i]=a[i]+1;
                    t++;
                }
            }
            printf("%d\n",2*n);
            for(int i=0;i<2*n;i++)
                printf("%d ",a[i]);
            printf("\n");
            for(int i=0;i<2*n;i++)
                printf("%d ",b[i]);
            printf("\n");
    }
}