A. Maxim and Biology
Today in the scientific lyceum of the Kingdom of Kremland, there was a biology lesson. The topic of the lesson was the genomes. Let's call the genome the string "ACTG".
Maxim was very boring to sit in class, so the teacher came up with a task for him: on a given string operations that you need to apply, so that the genome appears in it as a substring. For one operation, you can replace any letter in the string with the next or previous in the alphabet. For example, for the letter "D" the previous one will be "C", and the next — "E". In this problem, we assume that for the letter "A", the previous one will be the letter "Z", and the next one will be "B", and for the letter "Z", the previous one is the letter "Y", and the next one is the letter "A".consisting of uppercase letters and length of at least , you need to find the minimum number of
Help Maxim solve the problem that the teacher gave him.
A stringis a substring of a string if can be obtained from by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
只不过一个字母想要变成另一个字母能得到的贡献为 min(abs(a - b),26 - abs(a - b) );
当然在比赛中没有想起来该这样写，不过因为要变化的有一个A所以所以处理起来比较简单min(26 - i, i)这样处理就行 i就是第i个字母
B. Dima and a Bad XOR
Student Dima from Kremland has a matrixof size filled with non-negative integers.
He wants to select exactly one integer from each row of the matrix so that the bitwise exclusive OR of the selected integers is strictly greater than zero. Help him!
Formally, he wants to choose an integers sequence( ) so that the inequality holds, where is the matrix element from the -th row and the -th column.
Here bitwise XOR operation of integers and .denotes the
C. Problem for Nazar
Nazar, a student of the scientific lyceum of the Kingdom of Kremland, is known for his outstanding mathematical abilities. Today a math teacher gave him a very difficult task.
Consider two infinite sets of numbers. The first set consists of odd positive numbers (two times more numbers than at the previous one, and also changes the set from which these numbers are written out to another.), and the second set consists of even positive numbers ( ). At the first stage, the teacher writes the first number on the endless blackboard from the first set, in the second stage — the first two numbers from the second set, on the third stage — the next four numbers from the first set, on the fourth — the next eight numbers from the second set and so on. In other words, at each stage, starting from the second, he writes out
The ten first written numbers: with one.. Let's number the numbers written, starting
The task is to find the sum of numbers with numbers fromto for given integers and . The answer may be big, so you need to find the remainder of the division by ( ).
Nazar thought about this problem for a long time, but didn't come up with a solution. Help him solve this problem.
这道题思路有是很简单,就是可把sum(l, r) 化成 sum(1, r) - sum(1, l - 1);也就是最后需后需要注意一下l,r最大取1e18也就是可能会有爆掉long long的时候
最初我是直接换成__int128 不过不知道为什么会CE，求sum(1,r)需要用到倍增的思想，不过后半段发现 (1ll << i)(i := 0 to 62) 大于的时候就可以直接返回,然后如果i是偶数就加到奇数出现的次数，如果i是奇数那就加到偶数出现的次数，然后用前n项和公式代入求
D. Stas and the Queue at the Buffet
During a break in the buffet of the scientific lyceum of the Kingdom of Kremland, there was formed a queue of Dissatisfaction of the person equals the product of by the number of people standing to the left of his position, add the product by the number of people standing to the right of his position. Formally, the dissatisfaction of the student , which is on the position , equals .high school students numbered from to . Initially, each student is on position . Each student is characterized by two numbers — and .
The director entrusted Stas with the task: rearrange the people in the queue so that minimize the total dissatisfaction.
Although Stas is able to solve such problems, this was not given to him. He turned for help to you.
x = a - b;
a - b的基础上，
b - a 的就反一下就好，接下来是按照x的顺序降序排列
res = ∑(i = 1,n) (p[i].a * (i - 1) + p[i].b * (n - i)) ; 然后输出一下res就好