标签归档:题解

洛谷 P1582 倒水 题解

题目描述
一天,CC买了N个容量可以认为是无限大的瓶子,开始时每个瓶子里有1升水。接着~~CC发现瓶子实在太多了,于是他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子,把一个瓶子的水全部倒进另一个里,然后把空瓶丢弃。(不能丢弃有水的瓶子)

显然在某些情况下CC无法达到目标,比如N=3,K=1。此时CC会重新买一些新的瓶子(新瓶子容量无限,开始时有1升水),以到达目标。

现在CC想知道,最少需要买多少新瓶子才能达到目标呢?

输入输出格式
输入格式:
一行两个正整数, N,K。

输出格式:
一个非负整数,表示最少需要买多少新瓶子。

这道题很有意思,所以要在这里好好的写一下题解。

由“开始时每个瓶子里有1升水”和“新瓶子容量无限,开始时有1升水”、“他选择两个当前含水量相同的瓶子,把一个瓶子的水全部倒进另一个里”,很容易联想到但凡不是空瓶子,每个瓶子里水的数量一定都是以2为底的幂,如1、2、4、8、16、32、64……等等。由此我们可以将这些数字放到二进制视角下来思考。

由题中说“他决定保留不超过K个瓶子”,可将其转化为“CC最终所具有的瓶子总数 $n_f$ 在二进制表示形式下有总计不超过K个1”。
(下面说的所有东西可能都不太好想,请认真思考。)

然而我们需要买空瓶子……所以结果的数字只能大不能小,因此我们需要通过去除数字末尾的1,保留数字前面的1来使数字达到要求。

除了Lowbit之外,我还有一种做法(这个做法其实就是Lowbit和加综合起来的底层实现)。这个做法分为三步:
1、找到数字中倒数第一个1.
2、把接下来从后向前连续的所有1变成0.
3、再把接下来不是1的第一个0变成1.
举例:原数:001011
第二步完成后:001000
第三步完成后:001100
重复进行这一操作,直到满足要求“瓶子总数 $n_f$ 在二进制表示形式下有总计不超过K个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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<deque>
#include<map>
#include<cstring>
using namespace std;
inline int & setBit(int & v, int sv, int p) {
    if (sv) {
        v |= 1 << p;
    }
    else {
        v &= ~(1 << p);
    }
    return v;
}
inline int getBit(int v, int p) {
    return (v >> p) & 1;
}
bool checkBits(int value, int num) {
    int cnt = 0;
    for (int i = 0; i < 32; i++) {
        cnt += getBit(value, i);
    }
    return cnt <= num;
}
int main() {
    int n, k;
    cin >> n >> k;
    int no = n;
    while (!checkBits(n, k)) {
        int ptr = 0;
        while (!getBit(n, ptr))ptr++;
        while (getBit(n, ptr)) {
            setBit(n, 0, ptr);
            ptr++;
        }
        setBit(n, 1, ptr);
    }
    cout << n-no;
}

数据结构 邓俊辉 PA#4 循环移位(Cycle) 题解

循环移位(Cycle)


Description

Cycle shifting refers to following operation on the sting. Moving first letter to the end and keeping rest part of the string. For example, apply cycle shifting on ABCD will generate BCDA. Given any two strings, to judge if arbitrary times of cycle shifting on one string can generate the other one.

Input

There m lines in the input, while each one consists of two strings separated by space. Each string only contains uppercase letter ‘A’~’Z’.

Output

For each line in input, output YES in case one string can be transformed into the other by cycle shifting, otherwise output NO.

Example

Input

1
2
3
4
AACD CDAA
ABCDEFG EFGABCD
ABCD ACBD
ABCDEFEG ABCDEE

Output

1
2
3
4
YES
YES
NO
NO

Restrictions

0 <= m <= 5000

1 <= |S1|, |S2| <= 10^5

Time: 2 sec

Memory: 256 MB

描述

所谓循环移位是指。一个字符串的首字母移到末尾, 其他字符的次序保持不变。比如ABCD经过一次循环移位后变成BCDA

给定两个字符串,判断它们是不是可以通过若干次循环移位得到彼此

输入

由m行组成,每行包含两个由大写字母’A’~’Z’组成的字符串,中间由空格隔开

输出

对于每行输入,输出这两个字符串是否可以通过循环移位得到彼此:YES表示是,NO表示否

样例

见英文题面

限制

0 ≤ m ≤ 5000

1 ≤ |S1|, |S2| ≤ 10^5

时间:2 sec

内存:256 MB

开心死啦!本来就觉得这道题必须写KMP来着,结果搞了个c++stl糊弄过去了……还好THUOJ没有删掉头文件 /笑,倒是其他的map list queue还有什么 algorithm 都删啦! /偷笑 /捂脸
继续阅读

Openjudge 画家问题

画家问题

总时间限制:
1000ms
内存限制:
65536kB
描述
有一个正方形的墙,由N*N个正方形的砖组成,其中一些砖是白色的,另外一些砖是黄色的。Bob是个画家,想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i, j)个位置的砖时, 位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖,才能使所有砖的颜色都变成黄色。

输入
第一行是一个整数n (1≤n ≤15),表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖,“y”表示黄砖。
输出
一行,如果Bob能够将所有的砖都涂成黄色,则输出最少需要涂画的砖数,否则输出“inf”。
样例输入
5
wwwww
wwwww
wwwww
wwwww
wwwww
样例输出
15
来源
1681

继续阅读

Openjudge Calling Extraterrestrial Intelligence Again 题解

Calling Extraterrestrial Intelligence Again

总时间限制:
1000ms
内存限制:
65536kB
描述
A message from humans to extraterrestrial intelligence was sent through the Arecibo radio telescope in Puerto Rico on the afternoon of Saturday November 16, 1974. The message consisted of 1679 bits and was meant to be translated to a rectangular picture with 23 x 73 pixels. Since both 23 and 73 are prime numbers, 23 x 73 is the unique possible size of the translated rectangular picture each edge of which is longer than 1 pixel. Of course, there was no guarantee that the receivers would try to translate the message to a rectangular picture. Even if they would, they might put the pixels into the rectangle incorrectly. The senders of the Arecibo message were optimistic.

We are planning a similar project. Your task in the project is to find the most suitable width and height of the translated rectangular picture. The term “most suitable” is defined as follows. An integer m greater than 4 is given. A positive fraction a/b less than or equal to 1 is also given. The area of the picture should not be greater than m. Both of the width and the height of the translated picture should be prime numbers. The ratio of the width to the height should not be less than a/b nor greater than 1. You should maximize the area of the picture under these constraints.

In other words, you will receive an integer m and a fraction a/b. It holds that m > 4 and 0 < a/b <= 1. You should find the pair of prime numbers p, q such that pq <= m and a/b <= p/q <= 1, and furthermore, the product pq takes the maximum value among such pairs of two prime numbers. You should report p and q as the “most suitable” width and height of the translated picture.

输入
The input is a sequence of at most 2000 triplets of positive integers, delimited by a space character in between. Each line contains a single triplet. The sequence is followed by a triplet of zeros, 0 0 0, which indicates the end of the input and should not be treated as data to be processed.

The integers of each input triplet are the integer m, the numerator a, and the denominator b described above, in this order. You may assume 4 < m <= 100000 and 1 <= a <= b <= 1000.

输出
The output is a sequence of pairs of positive integers. The i-th output pair corresponds to the i-th input triplet. The integers of each output pair are the width p and the height q described above, in this order.

Each output line contains a single pair. A space character is put between the integers as a delimiter. No other characters should appear in the output.

样例输入
5 1 2
99999 999 999
1680 5 16
1970 1 1
2002 4 11
0 0 0
样例输出
2 2
313 313
23 73
43 43
37 53
来源
Japan 2002 Kanazawa

继续阅读

Openjudge Sudoku 题解

2982:Sudoku

总时间限制:
2000ms
内存限制:
65536kB
描述
Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3×3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3×3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task.
输入
The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.
输出
For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.
样例输入
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
样例输出
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
来源
Southeastern Europe 2005

继续阅读

数据结构 邓俊辉 PA#3 重名剔除(Deduplicate)题解

重名剔除(Deduplicate)


Description

Mr. Epicure is compiling an encyclopedia of food. He had collected a long list of candidates nominated by several belly-gods. As candidates in list are nominated by several people, duplication of name is inevitable. Mr. Epicure pay you a visit for help. He request you to remove all duplication, which is thought an easy task for you. So please hold this opportunity to be famous to all belly-gods.

Input

1 integer in fist line to denote the length of nomination list. In following n lines, each nomination is given in each line.

Output

All the duplicated nomination (only output once if duplication appears more multiple times), which is sorted in the order that duplication appears firstly.

Example

Input

1
2
3
4
5
6
7
8
9
10
11
10
brioche
camembert
cappelletti
savarin
cheddar
cappelletti
tortellni
croissant
brioche
mapotoufu

Output

1
2
cappelletti
brioche

Restrictions

1 < n < 6 * 10^5

All nominations are only in lowercase. No other character is included. Length of each item is not greater than 40.

Time: 2 sec

Memory: 256 MB

Hints

Hash

描述

Epicure先生正在编撰一本美食百科全书。为此,他已从众多的同好者那里搜集到了一份冗长的美食提名清单。既然源自多人之手,其中自然不乏重复的提名,故必须予以筛除。Epicure先生因此登门求助,并认定此事对你而言不过是“一碟小菜”,相信你不会错过在美食界扬名立万的这一良机

输入

第1行为1个整数n,表示提名清单的长度。以下n行各为一项提名

输出

所有出现重复的提名(多次重复的仅输出一次),且以其在原清单中首次出现重复(即第二次出现)的位置为序

样例

见英文题面

限制

1 < n < 6 * 10^5

提名均由小写字母组成,不含其它字符,且每项长度不超过40

时间:2 sec

空间:256 MB

提示

散列

继续阅读

数据结构 邓俊辉 PA#4 任务调度(Schedule)题解

任务调度(Schedule)


Description

A HPS cluster is equipped with a unique task scheduler. To be simple, it is assumed that this cluster doesn’t support multiple tasks running at the same time, such that only one task is allowed to be in running state at any moment. Initially, the priority of ever task is denoted by an integer which is called priority number. The smaller priority number stands for high priority. If two tasks have same task number, the priority is decided in the ASCII order of task name. Following this policy, resources, such as CPU, are always occupied by the task with minimum priority number. When one task is finished, the one with minimum priority number in the rest tasks is picked to execute. The finished task won’t quit immediately. The priority number is doubled and put back to the task set. Once the priority number is greater or equal to 2^32, this task is deleted from the task set.

Given initial priority setting of every task, your job is to predict the running order of a batch of tasks.

Input

First line contains two integers, says n and m. n stands for the number of tasks in initial state. m stands for the length of predicted sequence. Every line is ended by a line break symbol. In each one of the following n lines, an integer and a string are included. This string is shorter than 8, which only contains lowercase letters and numbers. The integer is priority number and the string is the task name. The integer and string is separated by space.

Output

At most m lines, each one contains a string. Output the name of tasks according to the order that tasks are executed. If the number of executed tasks is less than m, then output all the executed tasks.

Example

Input

1
2
3
4
3 3
1 hello
2 world
10 test

Output

1
2
3
hello
hello
world

Restrictions

0 <= n <= 4,000,000

0 <= m <= 2,000,000

0 < Priority number < 2^32

No tasks have same name

Time: 2 sec

Memory: 512 MB

Hints

Priority queue

描述

某高性能计算集群(HPC cluster)采用的任务调度器与众不同。为简化起见,假定该集群不支持多任务同时执行,故同一时刻只有单个任务处于执行状态。初始状态下,每个任务都由称作优先级数的一个整数指定优先级,该数值越小优先级越高若优先级数相等,则任务名ASCII字典顺序低者优先。此后,CPU等资源总是被优先级数最小的任务占用;每一任务计算完毕,再选取优先级数最小下一任务。不过,这里的任务在计算结束后通常并不立即退出,而是将优先级数加倍(加倍计算所需的时间可以忽略)并继续参与调度;只有在优先级数不小于2^32时,才真正退出

你的任务是,根据初始优先级设置,按照上述调度原则,预测一批计算任务的执行序列。

输入

第一行为以空格分隔的两个整数n和m,n为初始时的任务总数,m为所预测的任务执行序列长度,每行末尾有一个换行符

以下n行分别包含一个整数和一个由不超过8个小写字母和数字组成的字符串。前者为任务的初始优先级数,后者为任务名。数字和字符串之间以空格分隔

输出

最多m行,各含一个字符串。按执行次序分别给出执行序列中前m个任务的名称,若执行序列少于m,那么输出调度器的任务处理完毕前的所有任务即可。

样例

见英文题面

限制

0 ≤ n ≤ 4,000,000

0 ≤ m ≤ 2,000,000

0 < 每个任务的初始优先级 < 2^32

不会有重名的任务

时间:2 sec

内存:512 MB

提示

优先级队列

必须要用坑爹的setvbuf:
继续阅读

Openjudge 百练 最大子矩阵 题解

描述

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。

比如,如下4 * 4的矩阵

0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

的最大子矩阵是

9 2
-4 1
-1 8

这个子矩阵的大小是15。输入输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。再后面的若干行中,依次(首先从左到右给出第一行的N个整数,再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数,整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[-127, 127]。输出输出最大子矩阵的大小。

样例输入

4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1

8  0 -2

样例输出

15

 

继续阅读

Vijos 数的划分 题解

描述

将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。

例如:n=7,k=3,下面三种分法被认为是相同的。

1,1,5; 1,5,1; 5,1,1;
问有多少种不同的分法。

格式

输入格式

输入n,k (6<n<=200,2<=k<=6)

输出格式

一个整数,即不同的分法。

样例1

样例输入1

1
7 3

样例输出1

1
4

限制

每个测试点1s

来源

NOIP2001第二题
继续阅读

洛谷 [SCOI2005] 繁忙的都市 题解

题目描述

城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市C的道路是这样分布的:城市中有n个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连接。这些道路是双向的,且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值,分值越小表示这个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的要求:

1.改造的那些道路能够把所有的交叉路口直接或间接的连通起来。

2.在满足要求1的情况下,改造的道路尽量少。

3.在满足要求1、2的情况下,改造的那些道路中分值最大的道路分值尽量小。

任务:作为市规划局的你,应当作出最佳的决策,选择那些道路应当被修建。

输入输出格式

输入格式:
第一行有两个整数n,m表示城市有n个交叉路口,m条道路。接下来m行是对每条道路的描述,u, v, c表示交叉路口u和v之间有道路相连,分值为c。(1≤n≤300,1≤c≤10000)

输出格式:
两个整数s, max,表示你选出了几条道路,分值最大的那条道路的分值是多少。

输入输出样例

输入样例#1:

4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8
输出样例#1:

3 6

写了两种方法:
一种邻接表,一种邻接矩阵,都是Prim算法.
继续阅读