2019-4-19-div2 cf ,又是一次显示我的愚蠢的比赛

地址: cf(点前面的cf)

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 s consisting of uppercase letters and length of at least 4, you need to find the minimum number of 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 s 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".

Help Maxim solve the problem that the teacher gave him.

A string a is a substring of a string b if 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题是一很简单的暴力然而我就是在预处理的时候处理不出来我想要的结果

然后写完A题发现已经过了半个小时了,A题的意思就是处理一个字符串序列使其中的一段长度为4的序列变成"ACTG"

只不过一个字母想要变成另一个字母能得到的贡献为 min(abs(a - b),26 - abs(a - b) );

因为一个字母只能一次一次的向左或向右变,不存在一会左一会右的情况,那样贡献的值肯定会特别大,而且是无缘无故的大,不过本题求的是最小值。

当然在比赛中没有想起来该这样写,不过因为要变化的有一个A所以所以处理起来比较简单min(26 - i, i)这样处理就行 i就是第i个字母

比赛过程中想这样去变形,但是推不出来 :heixian:

所以我就通过A数组直接去处理T,C,G的数组了这样只需要通过A平移得到就行

然后就暴力遍历每相邻的四个字符最后求出一个最小贡献的值输出就行

B. Dima and a Bad XOR

Student Dima from Kremland has a matrix a of size n×m 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 c1,c2,,cn (1cjm) so that the inequality a(1,c1)a(2,c2)a(n,cn)>0holds, where a(i,j) is the matrix element from the i-th row and the j-th column.

Here xy denotes the bitwise XOR operation of integers xx and yy.

b题的话我我明显发现我的智商偏低了

我想的是用深搜去搜,当然这个题我算是理解错了,这个和我的英语水平,和sb翻译器的同时作用的结果

因为他让求的是在每一行中选择一个元素使其Xor和不为0,既然如此那一我直接让第一列的所以元素都异或一下,如果发现,第一列元素的异或和不为0那样这个就是一个正解,否则的话那就在遍历一遍n行2~m列找到一个元素使其异或行首元素和异或这个元素不为0则将其输出即可

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 (1,3,5,7,), and the second set consists of even positive numbers (2,4,6,8,). 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 two times more numbers than at the previous one, and also changes the set from which these numbers are written out to another.

The ten first written numbers: 1,2,4,3,5,7,9,6,8,10. Let's number the numbers written, starting with one.

The task is to find the sum of numbers with numbers from ll to r for given integers ll and r. The answer may be big, so you need to find the remainder of the division by 1000000007 (109+7).

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 n high school students numbered from 1 to n. Initially, each student i is on position i. Each student i is characterized by two numbers — ai and biDissatisfaction of the person i equals the product of ai by the number of people standing to the left of his position, add the product bi by the number of people standing to the right of his position. Formally, the dissatisfaction of the student i, which is on the position j, equals ai⋅(j−1)+bi⋅(n−j).

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.

d题的话因为b题消耗时间太多,在加上没有读懂题,所以最后16分钟开的D题,虽说最后还是没有写出来吧 :leng:

d题的思路也很简单定义一个含有三个元素的结构体,a,b,x。a是储存在a数里相应的值,b是储存在b数组里相应的值,令  x = a - b;

这个是一个差值,谁减谁是无所谓的,下面的思路都会建立在a - b的基础上,b - a 的就反一下就好,接下来是按照x的顺序降序排列

因为如果差值大的话代表a大所以应该放在前面,否则就是b大那样尽可能的靠后放,这算是一个小贪心吧。

所以最后排序的是和  res = ∑(i = 1,n) (p[i].a  *  (i - 1) + p[i].b * (n - i)) ; 然后输出一下res就好

总结:

1.自己真菜,

2.死磕在了b题上

3.写代码的速度还是有点慢

4.写题的第一想法是暴力,应该在多想想,比如b题如果能想出来第一列异或和为0只需要在i(1~n)行中找一个能替换的输出就好,而不是下意识的直接想起来一个n^m的暴力

5.还没想好,等我补完剩下的三道题在来看看还有没有补充的吧

5.还没想好,不过剩下的那两题超出了我的实力范围之内,果断跳过。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注