Codeforces Round #769 (Div. 2) ABCD
A. ABC
签到，不解释
#include
#include
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
string s;
int n;
cin >> n;
cin >> s;
if(s.size() <= 2) {
if(s.size() == 1 || s[0] != s[1]) puts("YES");
else puts("NO");
}
else puts("NO");
}
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 00 to ???1n?1, where ????pi is the height of the ??i-th pillar from the left (1≤??≤??)(1≤i≤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 max1≤??≤???1????⊕????+1max1≤i≤n?1pi⊕pi+1, where ⊕⊕ denotes the bitwise XOR 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 00 to ???1n?1 in arbitrary order. For example, [2,3,1,0,4][2,3,1,0,4] is a permutation, but [1,0,1][1,0,1] is not a permutation (11 appears twice in the array) and [1,0,3][1,0,3] is also not a permutation (??=3n=3, but 33 is in the array).
Input
Each test contains multiple test cases. The first line contains the number of test cases ??t (1≤??≤1041≤t≤104). Description of the test cases follows.
The only line for each test case contains a single integer ??n (2≤??≤2?1052≤n≤2?105) — 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?1052?105.
Output
For each test case print ??n integers ??1p1, ??2p2, ……, ????pn — the sequence of pillar heights with the smallest construction cost.
If there are multiple answers, print any of them.
Example
input
Copy
4
2
3
5
10
output
Copy
0 1
2 0 1
3 2 1 0 4
4 6 3 2 0 8 9 1 7 5
巧妙的思维题，首先按照题目的意思找到一个排列使得排列中相邻两数异或的最大值最小，那么自然想到分析1出现到的最高位，这时候会发现，不论在这一位为1的数有多少个/怎么排列，至少有一个数会接触到这一位为0的数，因此最终答案的这一位必然是1。既然这样，就把这一部分数排到最后面，然后让这一部分最靠左的数与把这个数最高位1取反的数相邻，就是满足题目要求的排列了。
距离来说，比如序列为[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，那么8、9，10这个三个数的第三位都为1，就把它们放在最后面，此时如果8在这三个数的最左边，就让它与0相邻；如果是9就让其与1相邻，如果是10就让其与2相邻；这样得到的最大异或值一定是8（如果任意排列，最终这个异或值不可能比8小）。
#include
#include
using namespace std;
int n, a[200005];
int count(int x) {
int ans = 0;
while(x) {
ans += (x & 1);
x >>= 1;
}
return ans;
}
vector cnt[32];
int main() {
int t;
cin >> t;
while(t--) {
cin >> n;
memset(cnt, 0, sizeof(cnt));
int hi = 0;
for(int i = 0; i <= n - 1; i++) {
for(int j = 0; j < 32; j++) {
if((i >> j) & 1) {
cnt[j].push_back(i);
hi = max(hi, j);
}
}
}
for(int i = 0; i < n; i++) {
a[i] = i;
}
swap(a[(1 << hi) ^ cnt[hi][0]], a[cnt[hi][0] - 1]);
for(int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;
}
return 0;
}
C. Strange Test
Igor is in 11th 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 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 (1≤??≤1041≤t≤104). Description of the test cases follows. The only line for each test case contains two integers ??a and ??b (1≤??<??≤1061≤a It is guaranteed that the sum of ??b over all test cases does not exceed 106106. Output For each test case print one integer — the minimum required number of operations to make ??a and ??b equal. Example input Copy output Copy 乍一看是数学，其实是暴力。首先注意到如果用了一次｜以后a一定大于等于b，此时b只能通过不断+1追上来，因此OR最多只用一次。然后分两种情况：a先+、再进行OR、b再+以及b先+、再进行OR、b再+；分别计算答案取最小即可。 注意第二种情况加法次数上界的问题，因为b范围1e6，所以最多进行b次加法（此时相当于b进行了左移，之后再操作一定不如先OR再b++更优），这个上界取得比较宽～ 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 11 to ??n, the ??i-th class has prepared a scene of length ????ai minutes. As the main one responsible for holding the concert, Idnar knows that if a concert has ??k scenes of lengths ??1b1, ??2b2, ……, ????bk minutes, then the audience will get bored if there exist two integers ??l and ??r such that 1≤??≤??≤??1≤l≤r≤k and gcd(????,????+1,…,?????1,????)=?????+1gcd(bl,bl+1,…,br?1,br)=r?l+1, where gcd(????,????+1,…,?????1,????)gcd(bl,bl+1,…,br?1,br) is equal to the greatest common divisor (GCD) of the numbers ????bl, ????+1bl+1, ……, ?????1br?1, ????br. To avoid boring the audience, Idnar can ask any number of times (possibly zero) for the ??t-th class (1≤??≤??1≤t≤k) to make a new scene ??dminutes in length, where ??d can be any positive integer. Thus, after this operation, ????bt is equal to ??d. Note that ??t and ??d can be different for each operation. For a sequence of scene lengths ??1b1, ??2b2, ……, ????bk, 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 ??(??1)f(a1), ??(??1f(a1,??2)a2), ……, ??(??1f(a1,??2a2,……,????)an). Input The first line contains a single integer ??n (1≤??≤2?1051≤n≤2?105) — the number of classes in the school. The second line contains ??n positive integers ??1a1, ??2a2, ……, ????an (1≤????≤1091≤ai≤109) — the lengths of the class scenes. Output Print a sequence of ??n integers in a single line — ??(??1)f(a1), ??(??1f(a1,??2)a2), ……, ??(??1f(a1,??2a2,……,????)an). Examples input Copy output Copy input Copy output Copy input Copy output Copy 题意是给一个序列a，如果其中有一个区间[l, r]满足\(gcd(a_l, a_{l+1}...a_r)=r - l + 1\)则认为这个区间不好。同时，可以改变序列a的任意个数为任意值，求f(1), f(2)...f(n)。f(x)表示1到x这段a的子列最少需要改变的数的个数。 注意到，a个数的GCD一定不小于a+1个数的GCD，因此其具有单调性（满足二分条件）。且每次操作的那个数可以替换为任意值，那么就可以取一个大素数。且f值具有承袭性。那么考虑这样一个做法： 遍历1到n，设当前为i，lst为上一次进行操作的位置+1。如果当前a[i] = 1，必然要进行更改；否则基于上面提到的n个数GCD的性质，二分找[lst, i]这段区间是否存在某个字区间[x, i]满足\(gcd(a_x, a_{x+1}...a_i) = i-x+1\)。如果有的话则让f[i] = f[i - 1] + 1，同时lst更新为i + 1；如果没有则让f[i] = f[i - 1]即可。二分check可以用线段树查询区间GCD。
5
1 3
5 8
2 5
3 19
56678 164422
1
3
2
1
23329
#include D. New Year Concert
1
1
1
3
1 4 2
1 1 2
7
2 12 4 8 18 3 6
0 1 1 1 2 2 2
#include