虽然翻车了TwT，但还是补一下题吧~~

A.ABC

题目

Recently, the students of School 179 have developed a unique algorithm, which takes in a binary string $s$ as input. However, they soon found out that if some substring $t$ of $s$ is a palindrome of length greater than 1 , the algorithm will work incorrectly. Can the students somehow reorder the characters of $s$ so that the algorithm will work correctly on the string?
A binary string is a string where each character is either 0 or 1 .
A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
A palindrome is a string that reads the same backwards as forwards.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t(1 \leq t \leq 100)$. Description of the test cases follows.
The first line of each test case contains a single integer $n(1 \leq n \leq 100)-$ the length of the string $s$.
The second line of each test case contains the string $s$ of length $n$ consisting only of the characters 0 and 1 .

Output

For each test case, print YES (case-insensitive) if it is possible to reorder the characters of $s$ so that there are no substrings that are a palindrome of length greater than 1, or NO (case-insensitive) otherwise.

Example input

1
2
3
4
5
6
7
8
9
4
1
1
2
10
2
01
4
1010

Example output

1
2
3
4
YES
YES
YES
NO

题意

给定一个长度为n的01序列，可以对他进行任意排序，问是否存在一种排序方法，使得任意长度大于1的子串不为回文串。存在输出YES，不存在输出NO

思路

显然，如果1或0的个数>=2，必然是NO，其他情况为YES

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <deque>
using namespace std;
typedef pair<int,int> PII;
 
int main(){
    int t;
    cin>>t;
    string str;
    while(t--){
        int len;
        cin>>len;
        cin>>str;
        if(len==2){
            if(str[1]==str[0]){
                cout<<"NO"<<endl;
            }else{
                cout<<"YES"<<endl;
            }
        }else if(len==1){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

B. Roof Construction

题目

It has finally been decided to build a roof over the football field in School 179 . Its construction will require placing $n$ consecutive vertical pillars. Furthermore, the headmaster wants the heights of all the pillars to form a permutation $p$ of integers from 0 to $n-1$, where $p_{i}$ is the height of the $i$-th pillar from the left $(1 \leq i \leq n)$.

As the chief, you know that the cost of construction of consecutive pillars is equal to the maximum value of the bitwise XOR of heights of all pairs of adjacent pillars. In other words, the cost of construction is equal to $\max _{1 \leq i \leq n-1} p_{i} \oplus p_{i+1}$, where $\oplus$ denotes the bitwise $X O R$ operation.
Find any sequence of pillar heights $p$ of length $n$ with the smallest construction cost.
In this problem, a permutation is an array consisting of $n$ distinct integers from 0 to $n-1$ in arbitrary order. For example, $[2,3,1,0,4]$ is a permutation, but $[1,0,1]$ is not a permutation ( 1 appears twice in the array) and $[1,0,3]$ is also not a permutation $(n=3$, but 3 is in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $t\left(1 \leq t \leq 10^{4}\right) .$ Description of the test cases follows.

The only line for each test case contains a single integer $n\left(2 \leq n \leq 2 \cdot 10^{5}\right)-$ the number of pillars for the construction of the roof.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$.

Output

For each test case print $n$ integers $p_{1}, p_{2}, \ldots, p_{n}-$ the sequence of pillar heights with the smallest construction cost.
If there are multiple answers, print any of them.

Example input

1
2
3
4
5
4
2
3
5
10

Example output

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

题意

给定n，表示有一个长度n的序列，元素为0，1，2，……，n-1 。

让我们给出一个排列方式使得$\max _{1 \leq i \leq n-1} p_{i} \oplus p_{i+1}$最小

思路

$2^a<=n-1<2^{a+1}$，那么$\max _{1 \leq i \leq n-1} p_{i} \oplus p_{i+1}$一定小于等于$2^a$。因为不管怎么排序，始终会存在一个异或结果，保留了最高位的1。

我们按一下方式构造可以保证结果为$2^a$：

前面依次为：n-1，n-2,……,$2^a$，0

后面：填0 ~ $2^a-1$，顺序任意。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <deque>
using namespace std;
typedef pair<int,int> PII;
int b[1000];
bool st[200010];
int main(){
    int t;
    cin>>t;
    b[0]=1;
    for(int i=1;b[i-1]<1e7;i++){
        b[i]=b[i-1]*2;
    }
    int n;
    while(t--){
        scanf("%d",&n);
        n--;
        int w=0;
        for(;;w++){
            if(b[w]>=n) break;
        }
        if(b[w]==n){
            printf("%d %d ",n,0);
            st[n]=st[0]= true;
        }else{
            for(int j=b[w-1];j<=n;j++){
                printf("%d ",j);
                st[j]= true;
            }
            printf("%d ",n-b[w-1]);
            st[n-b[w-1]]= true;
        }
        for(int i=0;i<=n;i++){
            if(st[i]== false) printf("%d ",i);
        }
        printf("\n");
        for(int i=0;i<=n;i++) st[i]= false;
    }
    return 0;
}

C. Strange Test

题目

Igor is in 11 th grade. Tomorrow he will have to write an informatics test by the strictest teacher in the school, Pavel Denisovich.
Igor knows how the test will be conducted: first of all, the teacher will give each student two positive integers $a$ and $b(a<b)$. After that,
the student can apply any of the following operations any number of times:

  • $a:=a+1$ (increase $a$ by 1 ),

  • $b:=b+1$ (increase $b$ by 1 ),

  • $a:=a \mid b$ (replace $a$ with the bitwise OR of $a$ and $b$ ).

To get full marks on the test, the student has to tell the teacher the minimum required number of operations to make $a$ and $b$ equal.
Igor already knows which numbers the teacher will give him. Help him figure out what is the minimum number of operations needed to
make $a$ equal to $b$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t\left(1 \leq t \leq 10^{4}\right)$. Description of the test cases
follows.
The only line for each test case contains two integers $a$ and $b\left(1 \leq a<b \leq 10^{6}\right)$.
It is guaranteed that the sum of $b$ over all test cases does not exceed $10^{6}$.

Output

For each test case print one integer - the minimum required number of operations to make $a$ and $b$ equal.

Example input

1
2
3
4
5
6
5
1 3
5 8
2 5
3 19
56678 164422

Example output

1
2
3
4
5
1
3
2
1
23329

题意

给定两个数,a,b。每次可以进行以下三种运算的一种：

  • $a:=a+1$
  • $b:=b+1$
  • $a:=a \mid b$

求最少经过几次运算，让a==b。

思路

  • 1和2不能同时使用，否则就不是最佳方案了
  • 如果用3，只能用一次。如果不用3，那么答案为b-a
  • 注意到 It is guaranteed that the sum of b over all test cases does not exceed 1e6， 直接暴力枚举即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <deque>
using namespace std;
typedef pair<int,int> PII;
const int mx=0x3f3f3f3f;
int main(){
    int t,a,b;
    cin>>t;
    while(t--){
        scanf("%d%d",&a,&b);
        int ans=b-a,nw=0;
        for(int x=a;x<=b;x++){
            if((x|b)==b){
                ans=min(ans,x-a+1);
            }
        }
        for(int x=b;x<=b+a;x++){
            if((x|a)==x){
                ans=min(ans,x-b+1);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

D. New Year Concert

题目

New Year is just around the corner, which means that in School 179, preparations for the concert are in full swing.
There are $n$ classes in the school, numbered from 1 to $n$, the $i$-th class has prepared a scene of length $a_{i}$ minutes.
As the main one responsible for holding the concert, Idnar knows that if a concert has $k$ scenes of lengths $b_{1}, b_{2}, \ldots, b_{k}$ minutes, then the audience will get bored if there exist two integers $l$ and $r$ such that $1 \leq l \leq r \leq k$ and $\operatorname{gcd}\left(b_{l}, b_{l+1}, \ldots, b_{r-1}, b_{r}\right)=r-l+1$, where $\operatorname{gcd}\left(b_{l}, b_{l+1}, \ldots, b_{r-1}, b_{r}\right)$ is equal to the greatest common divisor (GCD) of the numbers $b_{l}, b_{l+1}, \ldots, b_{r-1}, b_{r}$.

To avoid boring the audience, Idnar can ask any number of times (possibly zero) for the $t$-th class $(1 \leq t \leq k)$ to make a new scene $d$ minutes in length, where $d$ can be any positive integer. Thus, after this operation, $b_{t}$ is equal to $d$. Note that $t$ and $d$ can be different for each operation.

For a sequence of scene lengths $b_{1}, b_{2}, \ldots, b_{k}$, let $f(b)$ be the minimum number of classes Idnar has to ask to change their scene if he wants to avoid boring the audience.

Idnar hasn’t decided which scenes will be allowed for the concert, so he wants to know the value of $f$ for each non-empty prefix of $a$. In other words, Idnar wants to know the values of $f\left(a_{1}\right), f\left(a_{1}, a_{2}\right), \ldots, f\left(a_{1}, a_{2}, \ldots, a_{n}\right)$.

Input

The first line contains a single integer $n\left(1 \leq n \leq 2 \cdot 10^{5}\right)-$ the number of classes in the school.
The second line contains $n$ positive integers $a_{1}, a_{2}, \ldots, a_{n}\left(1 \leq a_{i} \leq 10^{9}\right)-$ the lengths of the class scenes.

Output

Print a sequence of $n$ integers in a single line $-f\left(a_{1}\right), f\left(a_{1}, a_{2}\right), \ldots, f\left(a_{1}, a_{2}, \ldots, a_{n}\right) .$

Example input

1
2
7
2 12 4 8 18 3 6

Example output

1
0 1 1 1 2 2 2

题意

题意: 给定一个长度为 $\mathrm{n}$ 的数组 $\mathrm{a}$, 我们定义一个数组是bad, 当且仅当存在这么一对$[l, r]$ 使得
$g c d\left(a_{l}, a_{l+1}, \ldots, a_{r}\right)=r-l+1$ 。
我们可以通过改变数组中的数来避免这一现象。
定义 $f(a)$ 为对于长度为k的数组中, 至少要改变多少的数使得不存在bad数组。
对于一个长度为 $\mathrm{n}$ 的数组 $\mathrm{a}$, 求出 $f\left(a_{1}\right), f\left(a_{1}, a_{2}\right), \ldots, f\left(a_{1}, a_{2}, \ldots, a_{n}\right)$

思路

st表

对于一段连续的数来说，gcd是单调递减的，数组长度是单调递增的，所以最多只存在n个bad数组。

我们对于每个左边界 l，最多能找到一个 r 满足bad数组的定义。

那么查到以后，我们的想法是直接修改成一个大质数即可，由于原数组值域只有1e9，我们修改为1e9 + 7，就相当于是添了一堵墙。

区间gcd查询用st表实现。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <deque>
using namespace std;
typedef pair<int,int> PII;
int f[200010][21],Log2[200010];
int n;
int res=0;
int gcd(int a,int b){
    if(b>a) return gcd(b,a);
    return b>0 ? gcd(b,a%b):a;
}
int getGcd(int l, int r) {
    int st = Log2[r - l + 1];
    return gcd(f[l][st], f[r + 1 - (1 << st)][st]);
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d",&f[i][0]);
    }
    for (int i = 1 ;i <= 20; ++i)
        for (int j = 0; j  <= n-(1<<i); ++j)
            f[j][i] = gcd(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);

    for (int i = 2; i <= n; ++i)
        Log2[i] = Log2[i / 2] + 1;

    int ans = 0;
    int maxr = -1;
    int pt = 0;
    for(int i=0;i<n;i++){
        while(pt < i && getGcd(pt, i) < i - pt + 1) ++pt;
        if(getGcd(pt, i) == i - pt + 1) {
            if(pt > maxr) {
                ++ans;
                maxr = i;
            }
        }
        cout << ans << ' ';
    }
    return 0;
}