111qqz的小窝

老年咸鱼冲锋!

codeforces edu #29 E. Turn Off The TV (思维,乱搞)

题目链接

题意:有若干线段,给出起点和终点,问是否有一个线段是冗余的。冗余的意思是说,对于该线段所覆盖的所有整数点,没有该线段,也能被其他一个或者多个线段覆盖到。如果有,输出任意一个冗余线段即可。

思路:画画图? 显然可以按照第一关键字左端点升序,第二关键字右端点降序(降序是为了处理 n=2,[1,2],[1,3] 这样的case容易一些),先考虑2种最简单的情况。

第一种是a[i+1]完全被a[i]包裹在里面,准确得说不一定是a[i],而是之前所有线段的最大右端点的那条线段,此时a[i+1]就是冗余的线段。

第二种是a[i+1]的左端点在之前所有线段的最大右端点右边,此时没有冗余,继续进行。

接下来考虑比较复杂的相交情况,我们画图发现,当前线段是否冗余,只与a[i-1]和a[i+1]有关。

如果第i条线段的左端点,不超过第i-2条线段的右端点的右边一个位置,此时第i-1条线段就是冗余的。

wa了2次。。原因是没认真看题,l,r的范围的最小值是从0开始而不是1。所以总体来说是道水题(调教场的题这么水了么。。。

 

 

 

 

BZOJ 1303: [CQOI2009]中位数图(前缀/后缀和乱搞)

1303: [CQOI2009]中位数图

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 2480  Solved: 1529
[Submit][Status][Discuss]

Description

给出1~n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后,位于中间的数。

Input

第一行为两个正整数n和b ,第二行为1~n 的排列。

Output

输出一个整数,即中位数为b的连续子序列个数。

Sample Input

7 4
5 7 2 4 3 1 6

Sample Output

4

HINT

第三个样例解释:{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}
N<=100000

思路:这道题的思路还是比较经典的…把大于b的数看成1,小于b的数看成-1..于是一段以b为中位数的连续的长度为奇数的数列的和为0.

那么从b往前做一个后缀和,往后做一个前缀和…然后统计每个前缀和/后缀和的值的个数..

然后枚举前缀和/后缀和可能的值(-n..n,由于负数不好处理,整体+n,变成0..2n)

具体见代码

 

 

BZOJ 1637: [Usaco2007 Mar]Balanced Lineup (前缀和乱搞)

1637: [Usaco2007 Mar]Balanced Lineup

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 503  Solved: 336
[Submit][Status][Discuss]

Description

Farmer John 决定给他的奶牛们照一张合影,他让 N (1 ≤ N ≤ 50,000) 头奶牛站成一条直线,每头牛都有它的坐标(范围: 0..1,000,000,000)和种族(0或1)。 一直以来 Farmer John 总是喜欢做一些非凡的事,当然这次照相也不例外。他只给一部分牛照相,并且这一组牛的阵容必须是“平衡的”。平衡的阵容,指的是在一组牛中,种族0和种族1的牛的数量相等。 请算出最广阔的区间,使这个区间内的牛阵容平衡。区间的大小为区间内最右边的牛的坐标减去最做边的牛的坐标。 输入中,每个种族至少有一头牛,没有两头牛的坐标相同。

Input

行 1: 一个整数: N 行 2..N + 1: 每行两个整数,为种族 ID 和 x 坐标。

Output

行 1: 一个整数,阵容平衡的最大的区间的大小。

Sample Input

7
0 11
1 10
1 25
1 12
1 4
0 13
1 22

Sample Output

11
输入说明

有7头牛,像这样在数轴上。

1 1 0 1 0 1 1
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
0 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
输出说明

牛 #1 (at 11), #4 (at 12), #6 (at 13), #7 (at 22) 组成一个平衡的最大的区间,大小为 22-11=11 个单位长度。

<——– 平衡的 ——–>
1 1 0 1 0 1 1
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
0 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

题意:有n头牛,在一个数轴上,没头牛有一个坐标x和性别(0或者1)
现在要选一段最长的连续区间使得区间内公牛和母牛的个数相等(区间的端点必须有牛存在才可以选),问最长区间是多少。
思路:乱搞。先按照x排序。把性别为0的换成-1,这样比较好处理平衡。然后分三种情况,包含左端点,包含右端点,两个端点都不包含。前两种情况随便搞。最后一种情况,我的做法是正反扫两遍预处理出了sum1[i]和sum2[i],sum1[i]表示正向性别和为i的最左端的点的id,sum2[i]表示反向性别和为i的最右端的点的id。
如果所有奶牛的性别和为total,那么对于正向扫的时候,设当前性别的前缀和为X,中间选的奶牛的前缀和为Z,最后不选的奶牛的性别和为Y,那么就有X+Y+Z=total.
我们要使得Z为0,所以Y=total-x. 说白了就是对于从左往右的每个i,找到最右端的某个点使得这两个点中间的奶牛(不包含这两个点)的性别和为0.
注意下标可能为负,所以整体平移一下就好。
然后三种情况取最大值。
时间复杂度O(n)

codeforces #346 div 2 C. Tanya and Toys (暴力乱搞)

题目链接
题意:有1E9个礼物,第i个礼物价钱是i,然后现在已经有n个不重复的礼物,a[i],m元钱,想尽可能多得买不同种类的礼物,还能买多少个。
思路:先不考虑已经买的,从1连续买到k,然后考虑子啊这个区间内已经买的,等于实际上没有花钱。
反正就是暴力搞啊搞啊。。我也不知道怎么搞。。
结果最后。。方案数为0的时候。。。最后一个答案我是单独输出的。。忘了判断了。。。所以会输出两个0.宝宝心里苦啊。。。。。。。。

codeforces 484 B Maximum Value (暴力乱搞)

题目链接
题意:给出n个元素的序列,求出最大的a[i]%a[j] (i>=j)
思路:没思路。。。。

Let us iterate over all different aj. Since we need to maximize , then iterate all integer x (suchx divisible by aj) in range from 2aj to M, where M — doubled maximum value of the sequence. For each such x we need to find maximum ai, such ai < x. Limits for numbers allow to do this in time O(1) with an array. After that, update answer by value . Total time complexity is O(nlogn + MlogM)

题解也没有特别懂。。。感觉和筛法有点类似。

不过学到了一个o(1)时间得到小于x的最大数是多少的做法。

Sort the array and just maintain another array A of 10^6 elements where index i stores element just smaller than i

For example consider sorted array [2,4,7,11], then

A(0 indexed) will be [-1,-1,-1,2,2,4,4,4,7,7,7,7,11...]

-1 means no element is smaller than i.

见代码中的b数组。

 

 

 

 

codeforces #322 div 2 C. Developing Skills(乱搞)

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Petya loves computer games. Finally a game that he’s been waiting for so long came out!

The main character of this game has n different skills, each of which is characterized by an integer ai from 0 to 100. The higher the numberai is, the higher is the i-th skill of the character. The total rating of the character is calculated as the sum of the values ​​of  for all i from 1 to n. The expression ⌊ x⌋ denotes the result of rounding the number x down to the nearest integer.

At the beginning of the game Petya got k improvement units as a bonus that he can use to increase the skills of his character and his total rating. One improvement unit can increase any skill of Petya’s character by exactly one. For example, if a4 = 46, after using one imporvement unit to this skill, it becomes equal to 47. A hero’s skill cannot rise higher more than 100. Thus, it is permissible that some of the units will remain unused.

Your task is to determine the optimal way of using the improvement units so as to maximize the overall rating of the character. It is not necessary to use all the improvement units.

Input

The first line of the input contains two positive integers n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 107) — the number of skills of the character and the number of units of improvements at Petya’s disposal.

The second line of the input contains a sequence of n integers ai (0 ≤ ai ≤ 100), where ai characterizes the level of the i-th skill of the character.

Output

The first line of the output should contain a single non-negative integer — the maximum total rating of the character that Petya can get using k or less improvement units.

Sample test(s)
input

output

input

output

input

output

Note

In the first test case the optimal strategy is as follows. Petya has to improve the first skill to 10 by spending 3 improvement units, and the second skill to 10, by spending one improvement unit. Thus, Petya spends all his improvement units and the total rating of the character becomes equal to lfloor frac{100}{10} rfloor +  lfloor frac{100}{10} rfloor = 10 + 10 =  20.

In the second test the optimal strategy for Petya is to improve the first skill to 20 (by spending 3 improvement units) and to improve the third skill to 20 (in this case by spending 1 improvement units). Thus, Petya is left with 4 improvement units and he will be able to increase the second skill to 19 (which does not change the overall rating, so Petya does not necessarily have to do it). Therefore, the highest possible total rating in this example is .

In the third test case the optimal strategy for Petya is to increase the first skill to 100 by spending 1 improvement unit. Thereafter, both skills of the character will be equal to 100, so Petya will not be able to spend the remaining improvement unit. So the answer is equal to .

 

不能超过100没看到…

贡献若干次wa…蠢哭了.

然后写蠢了…

最后觉得这样写比较好:

开一个结构体数组… a,b

a用来记录原始值,b用来记录mod10的余数与10的差..

整个填充过程分两步骤

第一步是把余数不为0的填充到10..

这部分要先填充…显然比先填充余数为0的更优.而且先填充余数大的..也就是b小的…

以b为关键字…从小到达排序..

然后填充的时候记得更新 a的值到整十  

同时用一个sum累加更新后的a[i] 到100的距离…

sum/10是一个限制条件

而k/10是第二个限制条件

所以答案最后加上 min(k,sum)/10;