Codeforces Round 857 div.2

admin管理员组

文章数量:1593955

目录

A. Likes（贪心）

题面翻译

思路

代码实现

B. Settlement of Guinea Pigs

题面翻译

思路

代码实现 

C. The Very Beautiful Blanket

题面翻译

思路

代码实现

D. Buying gifts

题面翻译

思路

代码实现

---

这场太失败了， 40分钟A了两道签到，然后两个多小时全程梦游，相继开了C、D、E三道题，一道也写不出来，现来补个题

A. Likes（贪心）

Nikita recently held a very controversial round, after which his contribution changed very quickly.

The announcement hung on the main page for n seconds. In the i th second |ai||th person either liked or removed the like (Nikita was lucky in this task and there are no dislikes). If ai>0, then the aith person put a like. If ai<0 then the person −ai− removed the like. Each person put and removed the like no more than once. A person could not remove a like if he had not put it before.

Since Nikita's contribution became very bad after the round, he wanted to analyze how his contribution changed while the announcement was on the main page. He turned to the creator of the platform with a request to give him the sequence a1,a2,…,an. But due to the imperfection of the platform, the sequence a was shuffled.

You are given a shuffled sequence of a that describes user activity. You need to tell for each moment from 11 to n what the maximum and minimum number of likes could be on the post at that moment.

Input

The first line of input data contains one number t (1⩽t⩽1000) — the number of test cases.

In the first line of test case, one number is given n (1⩽n⩽100) — the number of seconds during which Nikita's announcement hung on the main page.

The next line contains n numbers b1,b2,b3,…,bn (1⩽|bi|⩽n) — mixed array a. It is guaranteed that there exists such a permutation of b that it is a correct sequence of events described in the condition.

It is guaranteed that the sum of n for all input test cases does not exceed 104104.

Output

For each test case, output two lines, each of which contains n numbers.

In the first line, for each test case, output the maximum number of likes that Nikita could have at the announcement at the i th second.

In the second line, for each test case, output the minimum number of likes that Nikita could have at the announcement at the i th second.

Example

input

5

3

1 2 -2

2

1 -1

6

4 3 -1 2 1 -2

5

4 2 -2 1 3

7

-1 6 -4 3 2 4 1

output

1 2 1 
1 0 1 
1 0 
1 0 
1 2 3 4 3 2 
1 0 1 0 1 2 
1 2 3 4 3 
1 0 1 2 3 
1 2 3 4 5 4 3 
1 0 1 0 1 2 3 

Note

In the first test case, the maximum values are reached with the following permutation: 1,2,−21,2,−2. And the minimum values for such: 2,−2,12,−2,1.

In the third test case, all maximal values are reached with the following permutation: 4,2,3,1,−1,−24,2,3,1,−1,−2. And the minimum values for the next permutation: 2,−2,1,−1,3,42,−2,1,−1,3,4.

题面翻译

小明，有n天，每天要么有人给他点赞，要么取消他的赞，没有点赞的人不能取消赞

现在知道所有点赞和取消赞的情况，但不知道顺序，a[i]>0表示a[i]点赞，a[i]<0表示取消赞

输出：2行，每行n个数，第 i 个数表示第 i 天可能获得的最多和最少的赞数

思路

贪心即可
所有人先给他点赞，全部点完再取消赞，此时为最大值
每个人先点赞，然后立刻取消，此刻为最小值

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int num1=0,num2=0;
        int a;
        for(int i=0;i<n;i++){
            cin>>a;
            if(a>0)num1++;  //点赞总数
            else num2++;    //取消赞总数
        }
        int ans=0;
        for(int i=0;i<num1;i++){    //每一秒都点赞
            cout<<++ans<<' ';
        }
        for(int i=num1;i<n;i++){ //所有赞点完之后逐个取消
            cout<<--ans<<' ';
        }
        cout<<endl;
        for(int i=1;i<=2*num2;i++){ //先点赞然后取消，赞数为1,0,1,0循环
            cout<<(i%2)<<' ';
        }
        ans=0;
        for(int i=0;i<n-2*num2;i++){
            cout<<++ans<<' ';       //全部取消后，再点完剩下的赞
        }
        cout<<endl;
    }
    return 0;
}

---

B. Settlement of Guinea Pigs

Dasha loves guinea pigs very much. In this regard, she decided to settle as many guinea pigs at home as possible and developed a plan for the next n days. Every day, she will either buy a new guinea pig or call a doctor to examine all her pets.

Unfortunately, the store where she was going to buy guinea pigs does not understand them. Therefore, it cannot determine their gender. Dasha can't do it either. The only one who can help is a doctor.

To keep guinea pigs, aviaries are needed. Dasha plans to buy them in the same store. Unfortunately, only one species is sold there — a double aviary. No more than two guinea pigs can live in it.

Since Dasha does not want to cause moral injury to her pets — she will not settle two guinea pigs of different genders in one aviary.

Help Dasha calculate how many aviaries in the worst case you need to buy so that you can be sure that at no moment of time do two guinea pigs of different genders live in the same aviary.

As part of this task, we believe that guinea pigs have only two genders — male and female.

Input

The first line of input data contains one number t (1⩽t⩽10^5) — the number of input data sets.

The first line of each input data set contains one number n (1⩽n⩽10^5) — the number of days Dasha has a plan for.

The next line contains n numbers b1,b2,b3,…,bn= (1⩽bi⩽2) — Dasha's plan. If bi=1, then on the ith day, Dasha will buy a new guinea pig. If bi=2, then on the i th day, a doctor will come to Dasha and help determine the sex of all guinea pigs that Dasha already has.

It is guaranteed that the sum of n for all input data sets does not exceed 105105.

Output

For each set of input data, output one number — the minimum number of aviaries Dasha needs to buy so that no matter what the genders of the pigs turn out to be, we can settle them so that at no point in time do two guinea pigs of different genders live together.

Example

input

6

3

1 1 1

3

2 2 2

5

1 1 1 2 1

10

1 2 1 2 1 2 1 2 1 2

20

1 2 1 1 1 1 1 2 1 2 1 2 2 1 1 1 1 1 1 1

20

2 1 1 2 1 1 2 1 2 2 1 1 1 2 2 1 1 1 1 2

output

3
0
3
4
12
9

Note

In the first set of input data, Dasha needs to put each guinea pig in a separate enclosure, since she does not know their gender.

In the second set of input data, Dasha will buy 0 guinea pigs, which means she will need 0 aviaries.

In the third set of input data, you even need 3 aviaries to put each guinea pig in a separate aviary before the doctor arrives at the 4th day. When she finds out their gender, at least two guinea pigs will be of the same gender and they can be placed in one aviary, and the third in another aviary. Thus, she will have one free aviary in which she can settle a new guinea pig. So answer is 3.

In the fourth set of input data, we show that 4 is the optimal answer.

To begin with, we note that the first four guinea pigs can be placed one at a time in an aviary. Then a doctor will come and determine their gender. Among these four guinea pigs there will be at least one pair of the same gender, because: either male guinea pigs are at least 2, or they are not more than 1, which means that the female is at least 3. Now we can put this couple in one aviary, and the other two in separate ones. We will have one more empty aviary where we can put a new pig.

Now let's show that the answer is at least 4. Let's say that among the first 4 guinea pigs, 3 are female and 1 is male. We need at least 3 aviaries to settle them. Then, when we buy a new guinea pig, we will need another aviary in which we will put it, since we do not know its gender.

题面翻译

在n天里，每天进行一次操作，1为买鸟，2为判断所有鸟的性别

鸟有雌雄两种，每个笼子最多放两只鸟，不同性别的鸟不能放在一个笼子，新买的鸟在判断性别前不知道它的性别

输出：n个值，第 i 个数字表示前 i 天最多需要的笼子数

思路

模拟，一步一步按照条件走，也是很签
医生检查的时候，发现最少需要的笼子为 (n/2)+1 个
雌雄不能放在一个笼子，5只鸟时，若2雌3雄需要3个笼子，6只鸟时，若3雌3雄，需要4个笼子

代码实现 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int flag;
        int num=0,longzi=0;
        int ans=-1;
        while(n--){
            cin>>flag;
            if(flag==1){
                num++;     //鸟个数加一
                longzi++;       //由于未知个数，单独把鸟放在一个笼子
                ans=max(longzi,ans);    //记录过程中最多需要的笼子数
            }
            if(flag==2){
                if(num==0){     //特判没有鸟的情况
                    longzi=0;
                    ans=0;
                }
                else{
                    longzi=(num/2)+1;   //找规律发现n只鸟的情况下，最少需要的笼子个数
                    ans=max(longzi,ans);    //记录过程中最多需要的笼子数
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

---

C. The Very Beautiful Blanket

Kirill wants to weave the very beautiful blanket consisting of n×m of the same size square patches of some colors. He matched some non-negative integer to each color. Thus, in our problem, the blanket can be considered a B matrix of size n×m consisting of non-negative integers.

Kirill considers that the blanket is very beautiful, if for each submatrix A of size 4×4 of the matrix B is true:

• A11⊕A12⊕A21⊕A22=A33⊕A34⊕A43⊕A44,
• A13⊕A14⊕A23⊕A24=A31⊕A32⊕A41⊕A42,

where ⊕⊕ means bitwise exclusive OR

Kirill asks you to help her weave a very beautiful blanket, and as colorful as possible!

He gives you two integers n and m.

Your task is to generate a matrix B of size n×m which corresponds to a very beautiful blanket and in which the number of different numbers maximized.

Input

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

The single line of each test case contains two integers n and m (4≤n,m≤200) — the size of matrix B.

It is guaranteed that the sum of n⋅m does not exceed 2⋅10^5.

Output

For each test case, in first line output one integer cnt (1≤cnt≤n⋅m) — the maximum number of different numbers in the matrix.

Then output the matrix B(0≤Bij<263) of size n×m. If there are several correct matrices, it is allowed to output any one.

It can be shown that if there exists a matrix with an optimal number of distinct numbers, then there exists among suitable matrices such a B that (0≤Bij<263)

Example

input

4

5 5

4 4

4 6

6 6

output

25
9740 1549 9744 1553 9748
1550 1551 1554 1555 1558
10252 2061 10256 2065 10260
2062 2063 2066 2067 2070
10764 2573 10768 2577 10772
16
3108 3109 3112 3113
3110 3111 3114 3115
3620 3621 3624 3625
3622 3623 3626 3627
24
548 549 552 553 556 557
550 551 554 555 558 559
1060 1061 1064 1065 1068 1069
1062 1063 1066 1067 1070 1071
36
25800 25801 25804 25805 25808 25809
25802 4294993099 25806 4294993103 25810 4294993107
26312 26313 26316 26317 26320 26321
26314 4294993611 26318 4294993615 26322 4294993619
26824 26825 26828 26829 26832 26833
26826 4294994123 26830 4294994127 26834 4294994131

Note

In the first test case, there is only 4 submatrix of size 4×4. Consider a submatrix whose upper-left corner coincides with the upper-left corner of the matrix B

9740⊕1549⊕1550⊕1551== 10256⊕2065⊕2066⊕2067 == 8192;

10252⊕2061⊕2062⊕2063 == 9744⊕1553⊕1554⊕1555 == 8192

So, chosen submatrix fits the condition. Similarly, you can make sure that the other three submatrices also fit the condition.

题面翻译

给你两个数n，m，找到一个n*m的矩阵，其所有4*4的子阵都满足以下条件，并使矩阵内不同的元素最多

• A11⊕A12⊕A21⊕A22=A33⊕A34⊕A43⊕A44,
• A13⊕A14⊕A23⊕A24=A31⊕A32⊕A41⊕A42,

 每一组数据，先输出最多含有的不同元素的个数，再输出任意一个合法的矩阵

思路

这题的数据一看就是专门吓人的，意思应该是让矩阵所有的2*2子阵的异或值相等（可这玩意该怎么算啊）

看了看题解，竟然可以利用随机数，随机生成第一行第一列的数据，然后利用异或值相等来算出整个矩阵，如果符合题意就找到了解（好神奇）

随机数生成链接：随机数（mt19937 , distribution）_

麻了，一道题补了三四个小时，随机数和异或都好难学

这里用到了异或运算的性质：

    a^b^c^d = target    //异或性质
——--> d = a^b^c^target  //由上式可以推出


    int a=9,b=11;       //补充异或的性质
    a^=b;       //实现两个数的交换
    b^=a;
    a^=b;       //此时a=11，b=9

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    
    mt19937_64 Rnd(random_device{}());      //随机数生成器
    uniform_int_distribution<ll>dist(0,LLONG_MAX);  //定义随机数dist(Rnd)

    int T;
    cin>>T;
    while(T--){
        int n,m;
        cin>>n>>m;
        vector<vector<ll> >a(n,vector<ll>(m));      //开n*m的二维数组
        while(1){   //不断生成数据，直到找到答案
            
            for(int i=0;i<n;i++) a[i][0]=dist(Rnd);     //随机生成第一行第一列
            for(int i=0;i<m;i++) a[0][i]=dist(Rnd);
            
            ll target=dist(Rnd);        //随机生成一个数，作为四个数的异或值
            for(int i=1;i<n;i++){
                for(int j=1;j<m;j++){       //利用异或的性质，算出这个n*m矩阵
                    a[i][j]=target^a[i-1][j-1]^a[i][j-1]^a[i-1][j];
                }
            }
            
            set<ll>s;       //去重，判断是否合法（即全部不重复）
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    s.insert(a[i][j]);
                }
            }
        
            if(s.size()==n*m){      //合法，输出并结束循环
                cout<<n*m<<endl;
                for(int i=0;i<n;i++){
                    for(int j=0;j<m;j++){
                        cout<<a[i][j]<<" \n"[j==m-1];   //膜拜大佬的华丽输出
                    }
                }
                break;
            }
        }
    }
    return 0;
}

---

D. Buying gifts

Little Sasha has two friends, whom he wants to please with gifts on the Eighth of March. To do this, he went to the largest shopping center in the city.

There are n departments in the mall, each of which has exactly two stores. For convenience, we number the departments with integers from 11 to n. It is known that gifts in the first store of the i department cost ai rubles, and in the second store of the i department — bi rubles.

Entering the mall, Sasha will visit each of the n departments of the mall, and in each department, he will enter exactly one store. When Sasha gets into the i-th department, he will perform exactly one of two actions:

1. Buy a gift for the first friend, spending ai rubles on it.
2. Buy a gift for the second friend, spending bi rubles on it.

Sasha is going to buy at least one gift for each friend. Moreover, he wants to pick up gifts in such a way that the price difference of the most expensive gifts bought for friends is as small as possible so that no one is offended.

More formally: let m1  be the maximum price of a gift bought to the first friend, and m2  be the maximum price of a gift bought to the second friend. Sasha wants to choose gifts in such a way as to minimize the value of |m1−m2|.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤1000. The description of the test cases follows.

The first line of each test case contains a single integer n (2≤n≤500000) — the number of departments in the mall.

Each of the following n lines of each test case contains two integers ai and bi (0≤ai,bi≤10^9) — the prices of gifts in the first and second store of the i department, respectively.

It is guaranteed that the sum of n over all test cases does not exceed 500000.

Output

Print one integer — the minimum price difference of the most expensive gifts bought to friends.

Example

input

2

2

1 2

2 1

5

1 5

2 7

3 3

4 10

2 5

output

0
1

Note

In the first test case, Sasha has two possible options: buy a gift for the first friend in the first department, and the second friend  — in the second department, or vice versa. In the first case, m1=m2=1, and in the second case — m1=m2=2. In both cases, the answer is 00. In the second test case, you can buy gifts for the first friend in the 2, 4 and 5 departments, and for the second friend  — in the 11 and 33 departments.So m1=max(2,4,2)=4, m2=max(5,3)=5. The answer is |4−5|=1.

题面翻译

小明有两个朋友，进了n家商店，每家商店有价格为a[i]，b[i] 的两个商品，小明要么给1号朋友买a[i]，要么给2号朋友买b[i]，怎么买能使给1号朋友和给2号朋友买的最贵的礼物差值最小

每家商店都要买礼物，每个朋友至少有一个礼物

输出：两个最贵的礼物的差值

思路

没有思路

代码实现

先贴个别人代码，学习完了回来补

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        vector<pair<int,int> >a(n);
        multiset<int>s1,s2;
        for(int i=0;i<n;i++){
            cin>>a[i].first>>a[i].second;
            s2.insert(a[i].second);
        }
        sort(a.begin(),a.end());
        int ans=1e9;
        for(int i=0;i<n;i++){
            int x=a[i].first,y=a[i].second;
            //auto [x,y]=a[i];      //结构化绑定
            s2.erase(s2.lower_bound(y));
            if(!s2.empty()){
                int mx=*prev(s2.end());
                if(mx>=x)ans=min(ans,mx-x);
                else{
                    ans=min(ans,x-mx);
                    auto it=s1.lower_bound(x);
                    if(it!=s1.end()){
                        ans=min(ans,*it-x);
                    }
                    if(it!=s1.begin()){
                        ans=min(ans,x-*prev(it));
                    }
                }
            }
            else{
                auto it=s1.lower_bound(x);
                if(it!=s1.end()){
                    ans=min(ans,*it -x);
                }
                if(it!=s1.begin()){
                    ans=min(ans,x-*prev(it));
                }
            }
            s1.insert(y);
        }
        cout<<ans<<'\n';
    }
}

本文标签： codeforcesDiv