杭电 OJ2060-2069
写在前面
本文记录了刷杭电 OJ2060-2069 的过程和一些想法，代码仅供参考！
2060 Snooker
Problem Description
background: Philip likes to play the QQ game of Snooker when he wants a relax, though he was just a little vegetable-bird. Maybe you hadn’t played that game yet, no matter, I’ll introduce the rule for you first. There are 21 object balls on board, including 15 red balls and 6 color balls: yellow, green, brown, blue, pink, black. The player should use a white main ball to make the object balls roll into the hole, the sum of the ball’s fixed value he made in the hole is the player’s score. The player should firstly made a red ball into the hole, after that he gains red-ball’s value(1 points), then he gets the chance to make a color ball, then alternately. The color ball should be took out until all the red-ball are in the hole. In other word, if there are only color balls left on board, the player should hit the object balls in this order: yellow(2 point), green(3 point), brown(4 point), blue(5 point), pink(6 point), black(7 point), after the ball being hit into the hole, they are not get out of the hole, after no ball left on board, the game ends, the player who has the higher score wins the game. PS: red object balls never get out of the hole. I just illustrate the rules that maybe used, if you want to contact more details, visit http://sports.tom.com/snooker/ after the contest. for example, if there are 12 red balls on board(if there are still red ball left on board, it can be sure that all the color balls must be on board either). So suppose Philp can continuesly hit the ball into the hole, he can get the maximun score is 12 × 1 (12 red-ball in one shoot) 7 × 12(after hit a red ball, a black ball which was the most valuable ball should be the target) 2 3 4 5 6 7(when no red ball left, make all the color ball in hole). Now, your task is to judge whether Philip should make the decision to give up when telling you the condition on board(How many object balls still left not in the hole and the other player’s score). If Philp still gets the chance to win, just print “Yes”, otherwise print “No”. (PS: if the max score he could get on board add his current score is equal to the opponent’s current score, still output “Yes”)
Input
The first line contains a numble N indicating the total conditions. Then followed by N lines, each line is made of three integers: Ball_Left P_Score O_Score represeting the ball number left on board, Philp’s current score, and the opponent’s current score. All the input value are in 32 bit integer value range.
Output
You should caculate the max score left Philp can gain, and judge whether he has the possiblity to win.
Sample Input
2 12 1 1 1 30 39
Sample Output
Yes No
解题思路
题目大意：斯诺克 当菲利普要放松一下自己的时候，他喜欢去玩 QQ 里的斯诺克游戏，虽然他还只是个小菜鸟。也许你还不知道这个游戏的规则，没关系，我会先为你介绍。一共有 21 个球在台面上，其中包括 15 个红球和 6 个彩球:黄、绿、褐、蓝、粉、黑。选手需要用一个白球来使这些球滚进洞里，那些球所代表的值的和就是他的得分。选手必须先把一个红球打进洞里，然后它得到红球相应的分值(1 分)，然后他就有一次机会去选择打一个彩球。在红球还未全部打进洞里之前，打进去的彩球需要重新拿出来。换句话说，也就是最后桌上将会只留下彩球。选手按下面的顺序来击球:黄(2 分)、绿(3 分)、褐(4 分)、蓝(5 分)、粉(6 分)、黑(7 分)。这时候把彩球打进洞里，它们不会被拿出来。当桌面上没有球留下的时候，比赛结束。分数高的选手获胜。PS:红球不会重新拿出。 例如，桌台上还有 12 个红球(如果还有红球留在台面上，表示所有的彩球一定也都留在台面上)。我假设菲利普能继续击球，他能得到的最大分数是： 12 × 1(一次性打掉 12 个红球) 7 × 12(每打完一个红球就打黑球) 2 3 4 5 6 7(没有红球剩下时，就打所有的彩球)。现在，你的任务就是在菲利普告诉你现在台面上的情况(有多少个球还留在台面上)后判断一下他是否需要放弃这局比赛。如果他还有获胜的机会，就输出“Yes”，否则输出“No”。(PS:如果他最大可能的得分加上现在的分数等于对手的分数，依然输出“Yes”)
直接计算，考虑有无红球
参考源码
代码语言：javascript复制#include <iostream>
using namespace std;
int main() {
int n, ball, s1, s2;
cin >> n;
while (n--) {
cin >> ball >> s1 >> s2;
if (ball > 6) {
s1 = (ball - 6) * 8 27; //还有红球
} else
s1 = (6 - ball 2 7) * ball / 2; //没有红球
if (s1 >= s2)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}2061 Treasure the new start, freshmen!
Problem Description
background: A new semester comes , and the HDU also meets its 50th birthday. No matter what’s your major, the only thing I want to tell you is:“Treasure the college life and seize the time.” Most people thought that the college life should be colorful, less presure.But in actual, the college life is also busy and rough. If you want to master the knowledge learned from the book, a great deal of leisure time should be spend on individual study and practise, especially on the latter one. I think the every one of you should take the learning attitude just as you have in senior school. “No pain, No Gain”, HDU also has scholarship, who can win it? That’s mainly rely on the GPA(grade-point average) of the student had got. Now, I gonna tell you the rule, and your task is to program to caculate the GPA. If there are K(K > 0) courses, the i-th course has the credit Ci, your score Si, then the result GPA is GPA = (C1 _ S1 C2 _ S2 …… Ci * Si……) / (C1 C2 …… Ci……) (1 <= i <= K, Ci != 0) If there is a 0 <= Si < 60, The GPA is always not existed.
Input
The first number N indicate that there are N test cases(N <= 50). In each case, there is a number K (the total courses number), then K lines followed, each line would obey the format: Course-Name (Length <= 30) , Credits(<= 10), Score(<= 100). Notice: There is no blank in the Course Name. All the Inputs are legal
Output
Output the GPA of each case as discribed above, if the GPA is not existed, ouput:“Sorry!”, else just output the GPA value which is rounded to the 2 digits after the decimal point. There is a blank line between two test cases.
Sample Input
2 3 Algorithm 3 97 DataStruct 3 90 softwareProject 4 85 2 Database 4 59 English 4 81
Sample Output
90.10
Sorry!
解题思路
题目大意，计算 GPA，假如有 K 门课程，第 i 门课的学分为 Ci，你的成绩为为 Si，则 GPA 为：GPA = (C1 × S1 C2 × S2 …… Ci × Si……) / (C1 C2 …… Ci……) (1 <= i <= K, Ci != 0)如果有一门课程成绩在 0 到 60 之间，则 GPA 将不存在。
直接按计算公式计算即可
参考源码
代码语言：javascript复制#include <cstring>
#include <iostream>
using namespace std;
int main() {
int n, k;
string name;
double c, s;
cin >> n;
while (n--) {
cin >> k;
int flag = 1;
double sumcs = 0, sumc = 0;
while (k--) {
cin >> name >> c >> s;
if (s < 60 && s >= 0) //有课程不及格
flag = 0;
else {
sumcs = c * s;
sumc = c;
}
}
if (flag)
printf("%.2fn", sumcs / sumc);
else
cout << "Sorry!" << endl;
if (n) cout << endl;
}
return 0;
}2062 Subset sequence
Problem Description
Consider the aggregate An= { 1, 2, …, n }. For example, A1={1}, A3={1,2,3}. A subset sequence is defined as a array of a non-empty subset. Sort all the subset sequece of An in lexicography order.Your task is to find the m-th one.
Input
The input contains several test cases. Each test case consists of two numbers n and m ( 0< n<= 20, 0< m<= the total number of the subset sequence of An ).
Output
For each test case, you should output the m-th subset sequence of An in one line.
Sample Input
1 1 2 1 2 2 2 3 2 4 3 10
Sample Output
1 1 1 2 2 2 1 2 3 1
解题思路
f(n) = n × (f(n - 1) 1) ，f(n)为子集总个数 g(n) = f(n) / n ，g(n)为每组个数 可以得到 g(n) = (n-1) × g(n - 1) 1
参考源码
代码语言：javascript复制#include <iostream>
using namespace std;
int main() {
int i, n, s[21];
__int64 m, group, g[21] = {0};
for (i = 1; i < 21; i ) { //计算每组个数
g[i] = (i - 1) * g[i - 1] 1;
}
while (cin >> n >> m) {
for (i = 0; i < 21; i ) { //计算首元素
s[i] = i;
}
while (n-- && m) {
group = m / g[n 1] ((m % g[n 1]) ? 1 : 0); //计算组数
if (group) {
cout << s[group]; //输出首个数字
for (i = group; i <= n; i ) s[i] = s[i 1];
m -= (group - 1) * g[i] 1; //更新m，在第n-1时的位置
if (m)
cout << " ";
else
cout << endl;
}
}
}
return 0;
}2063 过山车
Problem Description
RPG girls 今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做 partner 和她同坐。但是，每个女孩都有各自的想法，举个例子把，Rabbit 只愿意和 XHD 或 PQK 做 partner，Grass 只愿意和 linle 或 LL 做 partner，PrincessSnow 愿意和水域浪子或伪酷儿做 partner。考虑到经费问题，boss 刘决定只让找到 partner 的人去坐过山车，其他的人，嘿嘿，就站在下面看着吧。聪明的 Acmer，你可以帮忙算算最多有多少对组合可以坐上过山车吗？
Input
输入数据的第一行是三个整数 K , M , N，分别表示可能的组合数目，女生的人数，男生的人数。0<K<=10001<=N 和 M<=500.接下来的 K 行，每行有两个数，分别表示女生 Ai 愿意和男生 Bj 做 partner。最后一个 0 结束输入。
Output
对于每组数据，输出一个整数，表示可以坐上过山车的最多组合数。
Sample Input
6 3 3 1 1 1 2 1 3 2 1 2 3 3 1 0
Sample Output
3
解题思路
二分图匹配的题目，匈牙利算法
参考源码
代码语言：javascript复制#include <cstring>
#include <iostream>
using namespace std;
int line[501][501];
int visit[501];
int boy[501];
int k, m, n;
bool find(int x) { //为女生寻找男生
for (int i = 1; i <= n; i ) { //遍历每个男生
if (line[x][i] && !visit[i]) { //如果两个人之间有意向并且男生未被询问
visit[i] = 1;
if (!boy[i] || find(boy[i])) { //如果男生没有对象或者男生的那个对象还能找到其他男生
boy[i] = x; //处上对象了(但可能后面被其他人赶走)
return true;
}
}
}
return false;
}
int main() {
int a, b, count;
while (cin >> k && k) {
cin >> m >> n;
memset(line, 0, sizeof(line));
memset(boy, 0, sizeof(boy));
while (k--) {
cin >> a >> b;
line[a][b] = 1;
}
count = 0;
for (int i = 1; i <= m; i ) { //遍历每个女生
memset(visit, 0, sizeof(visit));
if (find(i)) {
count ;
}
}
cout << count << endl;
}
return 0;
}2064 汉诺塔 III
Problem Description
约 19 世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由 64 个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。现在我们改变游戏的玩法，不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到下盘的上面。Daisy 已经做过原来的汉诺塔问题和汉诺塔 II，但碰到这个问题时，她想了很久都不能解决，现在请你帮助她。现在有 N 个圆盘，她至少多少次移动才能把这些圆盘从最左边移到最右边？
Input
包含多组数据，每次输入一个 N 值(1<=N<=35)。
Output
对于每组数据，输出移动最小的次数。
Sample Input
1 3 12
Sample Output
2 26 531440
解题思路
要想把第 n 个盘从 1 移到 3，需要先把前 n-1 个从 1 移动 3，再从 3->1 最后再 1->3 第 n 个盘要从 1->2->3 经历 2 步 得到递推公式：f(1) = 2，f(n) = 3 × f(n - 1) 2
参考源码
代码语言：javascript复制#include <iostream>
using namespace std;
int main() {
__int64 n, f[36] = {0, 2};
for (int i = 2; i < 36; i ) {
f[i] = 3 * f[i - 1] 2;
}
while (cin >> n) {
cout << f[n] << endl;
}
return 0;
}2065 "红色病毒"问题
Problem Description
医学界发现的新病毒因其蔓延速度和 Internet 上传播的"红色病毒"不相上下,被称为"红色病毒", 经研究发现,该病毒及其变种的 DNA 的一条单链中,胞嘧啶,腺嘧啶均是成对出现的。 现在有一长度为 N 的字符串,满足一下条件: (1) 字符串仅由 A,B,C,D 四个字母组成; (2) A 出现偶数次(也可以不出现); (3) C 出现偶数次(也可以不出现); 计算满足条件的字符串个数. 当 N=2 时,所有满足条件的字符串有如下 6 个:BB,BD,DB,DD,AA,CC. 由于这个数据肯能非常庞大,你只要给出最后两位数字即可.
Input
每组输入的第一行是一个整数 T,表示测试实例的个数,下面是 T 行数据,每行一个整数 N(1<=N<2^64),当 T=0 时结束.
Output
对于每个测试实例,输出字符串个数的最后两位,每组输出后跟一个空行.
Sample Input
4 1 4 20 11 3 14 24 6 0
Sample Output
Case 1: 2 Case 2: 72 Case 3: 32 Case 4: 0
Case 1: 56 Case 2: 72 Case 3: 56
解题思路
f[n][0]保存长度为 n，合法的字符串的个数。 f[n][1]保存长度为 n，仅 A 出现奇数次的字符串的个数。 f[n][2]保存长度为 n，仅 C 出现奇数次的字符串的个数。 f[n][3]保存长度为 n，A、C 出现奇数次的字符串的个数。 那么可以写出递推公式 f[n][0] = 2 × f[n-1][0] f[n-1][1] f[n-1][2]; f[n][1] = 2 × f[n-1][1] f[n-1][0] f[n-1][3]; f[n][2] = 2 × f[n-1][2] f[n-1][0] f[n-1][3]; f[n][3] = 2 × f[n-1][3] f[n-1][1] f[n-1][2]; 其中 f[1][0] = 2 f[1][1] = 1 f[1][2] = 1 f[1][3] = 0
另外注意到 f[n][1] = f[n][2] f[n][0] f[n][3] = f[n][1] f[n][2] 可以得到 f[n][0] = 2 × f[n-1][0] f[n-1][1] f[n-1][2] = 2 × f[n-1][0] 2 × 4^n-2
所以 f[n][0] = 2^n 2^(n-1) 2^n … 2^(2n-3) = 2^(2n-2) 2^(n-1)
之后可以用快速幂计算
参考源码
代码语言：javascript复制#include <iostream>
using namespace std;
int ksm(long long a, long long b) {
int res = 1;
while (b > 0) {
if (b & 1) res = res * a % 100;
a = a * a % 100;
b /= 2;
}
return res;
}
int main() {
long long t, n, sum, num;
while (cin >> t && t) {
num = 1;
while (t--) {
cin >> n;
cout << "Case " << num << ": ";
cout << (ksm(4, n - 1) ksm(2, n - 1)) % 100 << endl;
}
cout << endl;
}
return 0;
}2066 一个人的旅行
Problem Description
虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。
Input
输入数据有多组，每组的第一行是三个整数 T，S 和 D，表示有 T 条路，和草儿家相邻的城市的有 S 个，草儿想去的地方有 D 个；接着有 T 行，每行有三个整数 a，b，time,表示 a,b 城市之间的车程是 time 小时；(1=<(a,b)<=1000;a,b 之间可能有多条路) 接着的第 T 1 行有 S 个数，表示和草儿家相连的城市；接着的第 T 2 行有 D 个数，表示草儿想去地方。
Output
输出草儿能去某个喜欢的城市的最短时间。
Sample Input
6 2 3 1 3 5 1 4 7 2 8 12 3 8 4 4 9 12 9 10 2 1 2 8 9 10
Sample Output
9
解题思路
Dijkstra 算法
参考源码
代码语言：javascript复制#include <algorithm>
#include <iostream>
#define INF 0x3fffffff
using namespace std;
int mp[1001][1001];
int visit[1001];
int dp[1001];
void dj(int s, int n) {
for (int i = 0; i <= n; i ) {
dp[i] = mp[s][i];
visit[i] = 0;
}
dp[s] = 0; //到达起点的距离为0
visit[s] = 1;
for (int i = 0; i <= n; i ) { //遍历n个城市
int pos = -1, min = INF; // pos存放距离起点最短的城市，min为距离
for (int j = 0; j <= n; j ) { //未被访问的城市中，距离起点最短的
if (!visit[j] && min > dp[j]) {
pos = j;
min = dp[j];
}
}
if (pos == -1) return; //若未找到，则说明起点孤立
visit[pos] = 1; //标记为访问
for (int j = 0; j <= n; j ) { //再次遍历n个城市优化路径
//如果城市j未被访问，并且从pos可到达j，并且以pos作为中介可以优化路径
if (!visit[j] && dp[j] > dp[pos] mp[pos][j]) {
dp[j] = dp[pos] mp[pos][j];
}
}
}
}
void init() { //初始化地图
for (int i = 0; i < 1001; i )
for (int j = 0; j < 1001; j ) mp[i][j] = INF;
}
int main(void) {
int t, s, d;
int a, b, time;
int x;
while (cin >> t >> s >> d) {
init(); //初始化地图
int maxn = 0;
for (int i = 0; i < t; i ) {
cin >> a >> b >> time;
if (mp[a][b] > time) mp[a][b] = mp[b][a] = time;
maxn = max(maxn, max(a, b)); //记录最大城市编号
}
while (s--) {
cin >> x;
mp[0][x] = mp[x][0] = 0; // 0为起点,到x的距离为0
}
dj(0, maxn);
int ans = INF;
for (int i = 0; i < d; i ) {
cin >> x;
ans = min(ans, dp[x]); //到目的城市x的距离
}
cout << ans << endl;
}
return 0;
}2067 小兔的棋盘
Problem Description
小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是 C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!
Input
每次输入一个数 n(1<=n<=35)，当 n 等于－1 时结束输入。
Output
对于每个输入数据输出路径数，具体格式看 Sample。
Sample Input
1 3 12 -1
Sample Output
1 1 2 2 3 10 3 12 416024
解题思路
观察图片
f(i, j) = f(i - 1, j) f(i, j - 1); f(i, i) = f(i, j - 1); f(i, 0) = f(i - 1, 0);
参考源码
代码语言：javascript复制#include <iostream>
using namespace std;
int main() {
int n;
long long a[36][36];
for (int i = 0; i < 36; i ) {
for (int j = 0; j <= i; j ) {
if (i == 0 && j == 0)
a[i][j] = 1;
else if (i == j)
a[i][j] = a[i][j - 1];
else if (j == 0)
a[i][j] = a[i - 1][j];
else
a[i][j] = a[i - 1][j] a[i][j - 1];
}
}
int count = 1;
while (cin >> n && n != -1) {
cout << count << " " << n << " " << 2 * a[n][n] << endl;
}
return 0;
}2068 RPG 的错排
Problem Description
今年暑假杭电 ACM 集训队第一次组成女生队,其中有一队叫 RPG,但做为集训队成员之一的野骆驼竟然不知道 RPG 三个人具体是谁谁。 RPG 给他机会让他猜猜， 第一次猜：R 是公主，P 是草儿，G 是月野兔； 第二次猜：R 是草儿，P 是月野兔，G 是公主； 第三次猜：R 是草儿，P 是公主，G 是月野兔；… 可怜的野骆驼第六次终于把 RPG 分清楚了。由于 RPG 的带动，做 ACM 的女生越来越多，我们的野骆驼想都知道她们， 可现在有 N 多人，他要猜的次数可就多了，为了不为难野骆驼，女生们只要求他答对一半或以上就算过关，请问有多少组答案能使他顺利过关。
Input
输入的数据里有多个 case,每个 case 包括一个 n，代表有几个女生，（n<=25）, n = 0 输入结束。
Output
给出有多少组答案能使他顺利过关。
Sample Input
1 2 0
Sample Output
1 1
解题思路
错排问题，类似 2048、2049
参考源码
代码语言：javascript复制#include <iostream>
using namespace std;
long long res[26][26] = {0};
long long C(int n, int m) {
if (n == m || m == 0) return 1;
if (res[n][m] != 0) //避免重复计算
return res[n][m];
else
return res[n][m] = C(n - 1, m) C(n - 1, m - 1); //按递推公式计算
}
int main() {
int n;
long long s, f[26] = {0, 0, 1, 2};
for (int i = 4; i < 26; i ) {
f[i] = (i - 1) * (f[i - 1] f[i - 2]);
}
while (cin >> n && n) {
s = 0;
for (int i = n / 2; i >= 0; i--) {
s = C(n, i) * f[i];
}
s = 1;
cout << s << endl;
}
return 0;
}2069 Coin Change
Problem Description
Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money. For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent coin, or two 5-cent coins and one 1-cent coin, or one 5-cent coin and six 1-cent coins, or eleven 1-cent coins. So there are four ways of making changes for 11 cents with the above coins. Note that we count that there is one way of making change for zero cent. Write a program to find the total number of different ways of making changes for any amount of money in cents. Your program should be able to handle up to 100 cents.
Input
The input file contains any number of lines, each one consisting of a number ( ≤250 ) for the amount of money in cents.
Output
For each input line, output a line containing the number of different ways of making changes with the above 5 types of coins.
Sample Input
11 26
Sample Output
4 13
解题思路
题目大意：有 50，25，10，5，1 五种货币，将钱换成这五种货币，有几种换法 暴力破解法即可
参考源码
代码语言：javascript复制#include <iostream>
using namespace std;
int main() {
int n, c50, c25, c10, c5, c1;
while (cin >> n) {
int count = 0;
for (c50 = 0; c50 <= n; c50 ) {
for (c25 = 0; c25 * 25 <= n - c50 * 50; c25 )
for (c10 = 0; c10 * 10 <= n - c50 * 50 - c25 * 25; c10 )
for (c5 = 0; c5 * 5 <= n - c50 * 50 - c25 * 25 - c10 * 10; c5 ) {
c1 = n - c50 * 50 - c25 * 25 - c10 * 10 - c5 * 5;
if (c1 c5 c10 c25 c50 <= 100) count ;
}
}
cout << count << endl;
}
return 0;
}相关内容
- 杭电 OJ2040-2049
- 杭电 OJ2050-2059
- 杭电 OJ2070-2079
- 杭电 OJ2080-2089
- 杭电 OJ2090-2099
