当前位置:首页 >> 其它 >> 整理的-----ACM题目及答案

整理的-----ACM题目及答案


杭电: 1000 1001 1002 1005 1008 1009 1021 1089 1090 1091 1092 1093 1094 1095 1096 1176 1204 1213 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2014 2015 2016 2017 2019 2020 2021 2033 2037 2039 2040 A + B Problem.......................................................... 4 Sum Problem............................................................ 5 A + B Problem II....................................................... 6 Number Sequence........................................................ 8 Elevator............................................................... 9 FatMouse' Trade....................................................... 11 Fibonacci Again....................................................... 13 A+B for Input-Output Practice (I) ..................................... 14 A+B for Input-Output Practice (II) .................................... 15 A+B for Input-Output Practice (III) ................................... 16 A+B for Input-Output Practice (IV) .................................... 17 A+B for Input-Output Practice (V) ..................................... 18 A+B for Input-Output Practice (VI) .................................... 20 A+B for Input-Output Practice (VII) ................................... 21 A+B for Input-Output Practice (VIII) .................................. 22 免费馅饼.............................................................. 23 糖果大战.............................................................. 25 How Many Tables....................................................... 26 ASCII 码排序 .......................................................... 32 计算两点间的距离...................................................... 34 计算球体积............................................................ 35 求绝对值.............................................................. 36 成绩转换.............................................................. 37 第几天?.............................................................. 38 求奇数的乘积.......................................................... 40 平方和与立方和........................................................ 41 数值统计.............................................................. 42 求数列的和............................................................ 43 水仙花数.............................................................. 44 多项式求和............................................................ 46 素数判定.............................................................. 47 青年歌手大奖赛_评委会打分 ............................................. 49 偶数求和.............................................................. 50 数据的交换输出........................................................ 52 字符串统计............................................................ 54 数列有序!............................................................. 55 绝对值排序............................................................ 56 发工资咯:).......................................................... 58 人见人爱 A+B .......................................................... 59 今年暑假不 AC ......................................................... 61 三角形................................................................ 63 亲和数................................................................ 64

1

2045 2049 2056 2073 2084 2201 2212 2304 2309 2317 2401 2500 2501 2502 2503 2504 2519 2520 2521 2522 2523 2524 2535 2537 2539 2547 2548 2549 2550 2551 2552 2553 2554 2555 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569

不容易系列之(3)—— LELE 的 RPG 难题 ................................... 65 不容易系列之(4)——考新郎 ............................................. 66 Rectangles............................................................ 68 无限的路.............................................................. 69 数塔.................................................................. 71 熊猫阿波的故事........................................................ 72 DFS................................................................... 73 Electrical Outlets .................................................... 74 ICPC Score Totalizer Software ......................................... 75 Nasty Hacks........................................................... 77 Baskets of Gold Coins ................................................. 78 做一个正气的杭电人 .................................................... 79 Tiling_easy version ................................................... 80 月之数................................................................ 81 a/b + c/d............................................................. 82 又见 GCD .............................................................. 83 新生晚会.............................................................. 84 我是菜鸟,我怕谁...................................................... 85 反素数................................................................ 86 A simple problem...................................................... 88 SORT AGAIN............................................................ 89 矩形 A + B ............................................................ 90 Vote.................................................................. 91 8 球胜负 .............................................................. 93 点球大战.............................................................. 95 无剑无我.............................................................. 98 两军交锋.............................................................. 99 壮志难酬............................................................. 100 百步穿杨............................................................. 101 竹青遍野............................................................. 103 三足鼎立............................................................. 104 N 皇后问题 ........................................................... 105 N 对数的排列问题 ..................................................... 106 人人都能参加第 30 届校田径运动会了 .................................... 107 Buildings............................................................ 110 第二小整数........................................................... 112 奇偶位互换........................................................... 113 统计问题............................................................. 114 词组缩写............................................................. 115 放大的 X ............................................................. 117 统计硬币............................................................. 118 寻梦................................................................. 119 前进................................................................. 121 彼岸................................................................. 123

2

2700 Parity............................................................... 124 2577 How to Type.......................................................... 126 北京大学: 1035 1061 1142 1200 1811 2262 2407 2447 2503 2513 Spell checker........................................................ 青蛙的约会........................................................... Smith Numbers........................................................ Crazy Search......................................................... Prime Test........................................................... Goldbach's Conjecture ................................................ Relatives............................................................ RSA.................................................................. Babelfish............................................................ Colored Sticks....................................................... 129 133 136 139 141 146 150 152 156 159

ACM 算法: kurXX 最小生成树 ........................................................... Prim ...................................................................... 堆实现最短路............................................................... 最短路 DIJ 普通版........................................................... floyd ..................................................................... BELL_MAN................................................................... 拓扑排序................................................................... DFS 强连通分支 ............................................................. 最大匹配................................................................... 还有两个最大匹配模板....................................................... 最大权匹配,KM 算法 ......................................................... 两种欧拉路................................................................. 无向图:............................................................... 有向图:............................................................... 【最大流】Edmonds Karp..................................................... dinic ..................................................................... 【最小费用最大流】Edmonds Karp 对偶算法 .................................... ACM 题目: 【题目】排球队员站位问题 ................................................... 【题目】把自然数N分解为若干个自然数之和。 ................................. 【题目】把自然数N分解为若干个自然数之积。 ................................. 【题目】马的遍历问题。..................................................... 【题目】加法分式分解。..................................................... 【题目】地图着色问题....................................................... 182 184 185 185 186 189 163 164 166 167 168 168 169 170 172 173 175 177 177 178 178 179 181

3

【题目】放置方案........................................................... 【题目】找迷宫的最短路径。 ................................................. 【题目】火车调度问题....................................................... 【题目】农夫过河。......................................................... 【题目】七段数码管问题。 ................................................... 【题目】 求相邻的格的数不连续 .............................................. 【题目】 棋盘上放棋子...................................................... 【题目】迷宫问题........................................................... 【题目】一笔画问题......................................................... 【题目】城市遍历问题....................................................... 【题目】棋子移动问题....................................................... 【题目】求集合元素问题(1,2x+1,3X+1 类) ....................................

191 194 195 197 199 200 202 204 205 207 208 209

杭电: 1000
Problem Description
Calculate A + B.

A + B Problem

Input
Each line will contain two integers A and B. Process to end of file.

Output
For each case, output A + B in one line.

Sample Input
1 1

Sample Output
2

Author
HDOJ 代码:

#include<stdio.h> int main() { int a,b;
4

while(scanf("%d %d",&a,&b)!=EOF) printf("%d\n",a+b); }

1001
Problem Description

Sum Problem

Hey, welcome to HDOJ(Hangzhou Dianzi University Online Judge). In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + ... + n.

Input
The input will consist of a series of integers n, one integer per line.

Output
For each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer.

Sample Input
1 100

Sample Output
1 5050

Author
DOOM III

解答: #include<stdio.h> main() { int n,i,sum; sum=0; while((scanf("%d",&n)!=-1)) {
5

sum=0; for(i=0;i<=n;i++) sum+=i;

printf("%d\n\n",sum); } }

1002
Problem Description

A + B Problem II

I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B.

Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.

Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line is the an equation "A + B = Sum", Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases.

Sample Input
2 1 2 112233445566778899 998877665544332211

Sample Output
Case 1: 1 + 2 = 3 Case 2: 112233445566778899 + 998877665544332211 = 1111111111111111110
6

Author
Ignatius.L

代码: #include <stdio.h> #include <string.h> int main(){ char str1[1001], str2[1001]; int t, i, len_str1, len_str2, len_max, num = 1, k; scanf("%d", &t); getchar(); while(t--){ int a[1001] = {0}, b[1001] = {0}, c[1001] = {0}; scanf("%s", str1); len_str1 = strlen(str1); for(i = 0; i <= len_str1 - 1; ++i) a[i] = str1[len_str1 - 1 - i] - '0'; scanf("%s",str2); len_str2 = strlen(str2); for(i = 0; i <= len_str2 - 1; ++i) b[i] = str2[len_str2 - 1 - i] - '0'; if(len_str1 > len_str2) len_max = len_str1; else len_max = len_str2; k = 0; for(i = 0; i <= len_max - 1; ++i){ c[i] = (a[i] + b[i] + k) % 10; k = (a[i] + b[i] + k) / 10; } if(k != 0) c[len_max] = 1; printf("Case %d:\n", num); num++; printf("%s + %s = ", str1, str2); if(c[len_max] == 1) printf("1"); for(i = len_max - 1; i >= 0; --i){ printf("%d", c[i]); } printf("\n");
7

if(t >= 1) printf("\n"); } return 0; }

1005
Problem Description

Number Sequence

A number sequence is defined as follows: f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7. Given A, B, and n, you are to calculate the value of f(n).

Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.

Output
For each test case, print the value of f(n) on a single line.

Sample Input
1 1 3 1 2 10 0 0 0

Sample Output
2 5

Author
CHEN, Shunbao

Source
ZJCPC2004

Recommend
JGShining 代码:

#include<stdio.h>
8

int f[200]; int main() { int a,b,n,i; while(scanf("%d%d%d",&a,&b,&n)&&a&&b&&n) { if(n>=3) { f[1]=1;f[2]=1; for(i=3;i<=200;i++) { f[i]=(a*f[i-1]+b*f[i-2])%7; if(f[i-1]==1&&f[i]==1) break; } i-=2; n=n%i; if(n==0) printf("%d\n",f[i]); else printf("%d\n",f[n]); } else printf("1\n"); } return 0; }

1008
Problem Description

Elevator

The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop. For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.

9

Input
There are multiple test cases. Each case contains a positive integer N, followed by N positive numbers. All the numbers in the input are less than 100. A test case with N = 0 denotes the end of input. This test case is not to be processed.

Output
Print the total time on a single line for each test case.

Sample Input
1 2 3 2 3 1 0

Sample Output
17 41

Author
ZHENG, Jianqiang

Source
ZJCPC2004

Recommend
JGShining 代码:

#include<stdio.h> int a[110]; int main() { int sum,i,n; while(scanf("%d",&n)&&n!=0) { for(i=1;i<=n;i++) scanf("%d",&a[i]); sum=0; a[0]=0; for(i=1;i<=n;i++) { if(a[i]>a[i-1]) sum+=6*(a[i]-a[i-1]); else sum+=4*(a[i-1]-a[i]);
10

sum+=5; } printf("%d\n",sum); } return 0; }

1009
Problem Description

FatMouse' Trade

FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean. The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.

Input
The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.

Output
For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.

Sample Input
5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1

Sample Output
13.333 31.500

Author
CHEN, Yue

Source
ZJCPC2004

Recommend
JGShining

11

代码:
#include<stdio.h> #include<string.h> #define MAX 1000 int main() { int i,j,m,n,temp; int J[MAX],F[MAX]; double P[MAX]; double sum,temp1; scanf("%d%d",&m,&n); while(m!=-1&&n!=-1) { sum=0; memset(J,0,MAX*sizeof(int)); memset(F,0,MAX*sizeof(int)); memset(P,0,MAX*sizeof(double)); for(i=0;i<n;i++){ scanf("%d%d",&J[i],&F[i]); P[i]=J[i]*1.0/((double)F[i]); } for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { if(P[i]<P[j]) { temp1=P[i]; P[i]=P[j]; P[j]=temp1; temp=J[i]; J[i]=J[j]; J[j]=temp; temp=F[i]; F[i]=F[j]; F[j]=temp; } } } for(i=0;i<n;i++) { if(m<F[i]){ sum+=m/((double)F[i])*J[i]; break; } else { sum+=J[i]; m-=F[i]; } } printf("%.3lf\n",sum); scanf("%d%d",&m,&n); } return 0; }

12

1021
Problem Description

Fibonacci Again

There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).

Input
Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000).

Output
Print the word "yes" if 3 divide evenly into F(n). Print the word "no" if not.

Sample Input
0 1 2 3 4 5

Sample Output
no no yes no no no

Author
Leojay

Recommend
JGShining

#include<stdio.h> int main() { long n; while(scanf("%ld",&n) != EOF) if (n%8==2 || n%8==6) printf("yes\n"); else printf("no\n");
13

return 0; }

1089

A+B for Input-Output Practice (I)

Problem Description
Your task is to Calculate a + b. Too easy?! Of course! I specially designed the problem for acm beginners. You must have found that some problems have the same titles with this one, yes, all these problems were designed for the same aim.

Input
The input will consist of a series of pairs of integers a and b, separated by a space, one pair of integers per line.

Output
For each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input.

Sample Input
1 5 10 20

Sample Output
6 30

Author
lcy

Recommend
JGShining

解答: #include<stdio.h> main() {
14

int a,b; while(scanf("%d%d",&a,&b)!=EOF) printf("%d\n",a+b); }

1090

A+B for Input-Output Practice (II)

Problem Description
Your task is to Calculate a + b.

Input
Input contains an integer N in the first line, and then N lines follow. Each line consists of a pair of integers a and b, separated by a space, one pair of integers per line.

Output
For each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input.

Sample Input
2 1 5 10 20

Sample Output
6 30

Author
lcy

Recommend
JGShining

解答: #include<stdio.h> #define M 1000 void main()
15

{ int a ,b,n,j[M],i; //printf("please input n:\n"); scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d",&a,&b); //printf("%d %d",a,b); j[i]=a+b; } i=0; while(i<n) { printf("%d",j[i]); i++; printf("\n"); } }

1091

A+B for Input-Output Practice (III)

Problem Description
Your task is to Calculate a + b.

Input
Input contains multiple test cases. Each test case contains a pair of integers a and b, one pair of integers per line. A test case containing 0 0 terminates the input and this test case is not to be processed.

Output
For each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input.

Sample Input
1 5 10 20 0 0

Sample Output
6
16

30

Author
lcy

Recommend
JGShining

解答: #include<stdio.h> main() { int a,b; scanf("%d %d",&a,&b); while(!(a==0&&b==0)) { printf("%d\n",a+b); scanf("%d %d",&a,&b); } }

1092

A+B for Input-Output Practice (IV)

Problem Description
Your task is to Calculate the sum of some integers.

Input
Input contains multiple test cases. Each test case contains a integer N, and then N integers follow in the same line. A test case starting with 0 terminates the input and this test case is not to be processed.

Output
For each group of input integers you should output their sum in one line, and with one line of output for each line in input.

17

Sample Input
4 1 2 3 4 5 1 2 3 4 5 0

Sample Output
10 15

Author
lcy

Recommend
JGShining

解答: #include <stdio.h> int main() { int n,sum,i,t; while(scanf("%d",&n)!=EOF&&n!=0) { sum=0; for(i=0;i<n;i++) { scanf("%d",&t); sum=sum+t; } printf("%d\n",sum); } }

1093

A+B for Input-Output Practice (V)

Problem Description
Your task is to calculate the sum of some integers.

Input
18

Input contains an integer N in the first line, and then N lines follow. Each line starts with a integer M, and then M integers follow in the same line.

Output
For each group of input integers you should output their sum in one line, and with one line of output for each line in input.

Sample Input
2 4 1 2 3 4 5 1 2 3 4 5

Sample Output
10 15

Author
lcy

解答: #include<stdio.h> main() { int n,a,b,i,j,sum; sum=0; while(scanf("%d\n",&n)!=-1) { for(i=0;i<n;i++) { scanf("%d",&b); for(j=0;j<b;j++) { scanf("%d",&a); sum+=a; } printf("%d\n",sum); sum=0; } } }

19

1094

A+B for Input-Output Practice (VI)

Problem Description
Your task is to calculate the sum of some integers.

Input
Input contains multiple test cases, and one case one line. Each case starts with an integer N, and then N integers follow in the same line.

Output
For each test case you should output the sum of N integers in one line, and with one line of output for each line in input.

Sample Input
4 1 2 3 4 5 1 2 3 4 5

Sample Output
10 15

Author
lcy

Recommend
JGShining

解答: #include<stdio.h> main() { int n,a,b,i,j,sum; sum=0; while(scanf("%d\n",&n)!=-1) { for(j=0;j<n;j++) { scanf("%d",&a); sum+=a; }
20

printf("%d\n",sum); sum=0; } }
[ Copy to Clipboard ] [ Save to File]

1095

A+B for Input-Output Practice (VII)

Problem Description
Your task is to Calculate a + b.

Input
The input will consist of a series of pairs of integers a and b, separated by a space, one pair of integers per line.

Output
For each pair of input integers a and b you should output the sum of a and b, and followed by a blank line.

Sample Input
1 5 10 20

Sample Output
6 30

Author
lcy

Recommend
JGShining

解答: #include<stdio.h> main() { int a,b;
21

while(scanf("%d%d",&a,&b)!=EOF) printf("%d\n\n",a+b); }

1096

A+B for Input-Output Practice (VIII)

Problem Description
Your task is to calculate the sum of some integers.

Input
Input contains an integer N in the first line, and then N lines follow. Each line starts with a integer M, and then M integers follow in the same line.

Output
For each group of input integers you should output their sum in one line, and you must note that there is a blank line between outputs.

Sample Input
3 4 1 2 3 4 5 1 2 3 4 5 3 1 2 3

Sample Output
10 15 6

Author
lcy

Recommend
JGShining

解答: int main() { int a,b,i,j,l[1000],k; scanf("%d",&i); getchar(); for(j=1;j<=i;j++)
22

l[j]=0; for(j=1;j<=i;j++) { scanf("%d",&a); getchar(); for(k=1;k<=a;k++) { scanf("%d",&b); getchar(); l[j]+=b; } } for(j=1;j<=i-1;j++) printf("%d\n\n",l[j]); printf("%d\n",l[i]); }

1176
Problem Description

免费馅饼

都说天上不会掉馅饼,但有一天 gameboy 正走在回家的小径上,忽然天上掉下大把大把的 馅饼。说来 gameboy 的人品实在是太好了,这馅饼别处都不掉,就掉落在他身旁的10米范 围内。馅饼如果掉在了地上当然就不能吃了,所以 gameboy 马上卸下身上的背包去接。但 由于小径两侧都不能站人,所以他只能在小径上接。由于 gameboy 平时老呆在房间里玩游 戏,虽然在游戏中是个身手敏捷的高手,但在现实中运动神经特别迟钝,每秒种只有在移动 不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标:

为了使问题简化,假设在接下来的一段时间里,馅饼都掉落在0-10这11个位置。开始时 gameboy 站在5这个位置,因此在第一秒,他只能接到4,5,6这三个位置中其中一个位置上的 馅饼。问 gameboy 最多可能接到多少个馅饼?(假设他的背包可以容纳无穷多个馅饼)

Input
输入数据有多组。每组数据的第一行为以正整数 n(0<n<100000),表示有 n 个馅饼掉在这条 小径上。在结下来的 n 行中,每行有两个整数 x,T(0<T<100000),表示在第 T 秒有一个馅饼掉 在 x 点上。同一秒钟在同一点上可能掉下多个馅饼。n=0时输入结束。

Output
每一组输入数据对应一行输出。输出一个整数 m,表示 gameboy 最多可能接到 m 个馅饼。 提示:本题的输入数据量比较大,建议用 scanf 读入,用 cin 可能会超时。

Sample Input
6 5 1 4 1 6 1 7 2 7 2 8 3 0
23

Sample Output
4

Author
lwg

代码:
#include<stdio.h> #include<string.h> #define MAX 100001 int arr[MAX][13]; int Max(int n1,int n2,int n3) { int max; max=(n1>n2)?n1:n2; max=(max>n3)?max:n3; return max; } void res(int num) { int i,j; int n,m,count=-1; memset(arr,0,MAX*13*sizeof(int)); for(i=0;i<num;i++) { scanf("%d%d",&n,&m); arr[m][n+1]++; if(count<m) count=m; } for(i=count-1;i>=0;i--) for(j=1;j<=11;j++) arr[i][j]+=Max(arr[i+1][j-1],arr[i+1][j],arr[i+1][j+1]); printf("%d\n",arr[0][6]); } int main() { int num; scanf("%d",&num); while(num) { res(num); scanf("%d",&num); }

24

return 0; }

1204
Problem Description

糖果大战

生日 Party 结束的那天晚上,剩下了一些糖果,Gandon 想把所有的都统统拿走,Speakless 于是说:―可以是可以,不过我们来玩24点,你不是已经拿到了一些糖果了吗?这样,如果 谁赢一局,就拿走对方一颗糖,直到拿完对方所有的糖为止。‖如果谁能算出来而对方算不 出来,谁就赢,但是如果双方都能算出或者都不能,就算平局,不会有任何糖果的得失。 Speakless 是个喜欢提前想问题的人,既然他发起了这场糖果大战,就自然很想赢啦(不然 可就要精光了-_-) 。现在他需要你的帮忙,给你他每局赢的概率和 Gardon 每局赢的概率, 请你给出他可能获得这场大战胜利的概率。

Input
每行有四个数,Speakless 手上的糖果数 N、Gardon 手上的糖果数 M(0<=N,M<=50)、一局 Speakless 能解答出来的概率 p、一个问题 Gardon 能解答出来的概率 q(0<=p,q<=1)。

Output
每行一个数,表示 Speakless 能赢的概率(用百分比计算,保留到小数点后2位) 。

Sample Input
50 50 0.5 0.5 10 10 0.51 0.5 50 50 0.51 0.5

Sample Output
0.50 0.60 0.88

Author
Speakless

Source
Gardon-DYGG Contest 2

Recommend
JGShining

代码:
#include <stdio.h> #include <math.h> const double EPS = 1e-12; inline void solve(int n, int m, double p, double q) { if(n==0) printf("0.00\n"); else if(m==0) printf("1.00\n"); else if(p==0.0||q==1.0) printf("0.00\n"); else { double lamda = q*(1-p)/(p*(1-q));
25

if(fabs(lamda-1.0)<EPS) else {

printf("%.2lf\n", double(n)/(m+n));

double res = (1-pow(lamda, n))/(1-pow(lamda, m+n)); printf("%.2lf\n", res); } } } int main() { int n, m; double p, q; while(scanf("%d%d%lf%lf", &n, &m, &p, &q)!=EOF) { solve(n, m, p, q); } return 0; }

1213
Problem Description

How Many Tables

Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers. One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table. For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.

Input
The input starts with an integer T(1<=T<=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N,M<=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.

Output
For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.

Sample Input
2 5 3 1 2 2 3 4 5 5 1 2 5

Sample Output
2 4

Author
Ignatius.L
26

Source
杭电 ACM 省赛集训队选拔赛之热身赛

Recommend
Eddy 代码:#include <stdio.h> #define MAX 2000 int n,m; int start[MAX],end[MAX]; int res; int arr[MAX]; int len; int Mempty() { int i; for(i=0;i<m;i++) if(start[i]!=0) return 0; return 1; } int inSet(int index) { int i; for(i=0;i<res;i++) if(arr[i]==index) return 1; return 0; } void deal() { int i; int space=0; for(i=0;i<m;i++) { if(start[i]==0) space++; else { start[i-space]=start[i]; end[i-space]=end[i]; } m=m-space; } void proc() { int i; int j; while(!Mempty()) { i=0; while(i<m)

}

27

{ if(start[i]==0) { i++; continue; } if(i==0) { if(start[i]!=end[i]) { arr[res++]=start[i]; arr[res++]=end[i]; else arr[res++]=start[i]; start[i]=end[i]=0; } else { for(j=0;j<res;j++) { if(arr[j]==start[i]) { if(!inSet(end[i])) arr[res++]=end[i]; start[i]=end[i]=0; i=-1; break; } if(arr[j]==end[i]) { if(!inSet(start[i])) arr[res++]=start[i]; start[i]=end[i]=0; i=-1; break; } } } i++; } len++; deal(); } if(res==n) len--; else len+=n-res-1; } int main() { int i; int num; scanf("%d",&num); while(num--) { scanf("%d%d",&n,&m); for(i=0;i<m;i++) scanf("%d %d",&start[i],&end[i]);

}

28

res=0; len=0; proc(); printf("%d\n",len+1); } return 0; }

1231
Problem Description

最大连续子序列

给定 K 个整数的序列{ N1, N2, ..., NK },其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj },其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个, 例如给定序列{ -2, 11, -4, 13, -5, -2 },其最大连续子序列为{ 11, -4, 13 },最大和 为20。 在今年的数据结构考卷中,要求编写程序得到最大和,现在增加一个要求,即还需要输出该 子序列的第一个和最后一个元素。

Input
测试输入包含若干测试用例,每个测试用例占2行,第1行给出正整数 K( < 10000 ),第2行给 出 K 个整数,中间用空格分隔。当 K 为0时,输入结束,该用例不被处理。

Output
对每个测试用例,在1行里输出最大和、最大连续子序列的第一个和最后一个元 素,中间用空格分隔。如果最大连续子序列不唯一,则输出序号 i 和 j 最小的那个(如输入 样例的第2、3组) 。若所有 K 个元素都是负数,则定义其最大和为0,输出整个序列的首尾 元素。

Sample Input
6 -2 11 -4 13 -5 -2 10 -10 1 2 3 4 -5 -23 3 7 -21 6 5 -8 3 2 5 0 1 10 3 -1 -5 -2 3 -1 0 -2 0

Sample Output
20 11 13 10 1 4 10 3 5 10 10 10 0 -1 -2 0 0 0 Hint Hint Huge input, scanf is recommended.

Source
浙大计算机研究生复试上机考试-2005年

Recommend
JGShining

代码:
#include<stdio.h> #include<string.h> #define MAX 20000 int arr[MAX]; int main()
29

{ int num,temp,i,flage; int sum,start,end,max=-32768; scanf("%d",&num); while(num!=0) { memset(arr,0,MAX*sizeof(int)); for(i=0;i<num;i++) scanf("%d",&arr[i]); sum=0; temp=0; max=-32768; flage=0; for(i=0;i<num;i++) { if(arr[i]>=0) flage=1; sum+=arr[i]; if(max<sum) { max=sum; start=temp; end=i; if(sum<0) { sum=0; temp=i+1; } if(flage) printf("%d %d %d\n",max,arr[start],arr[end]); else printf("0 %d %d\n",arr[0],arr[num-1]); scanf("%d",&num); } return 0; }

} }

1232
Problem Description

畅通工程

某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。 省政府―畅通工程‖的目标是使全省任何两个城镇间都可以实现交通 (但不一定有直接的道路 相连,只要互相间接通过道路可达即可) 。问最少还需要建设多少条道路?

Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目 N ( < 1000 )和道路数目 M;随后的 M 行对应 M 条道路,每行给出一对正整数,分别是该条道路 直接连通的两个城镇的编号。为简单起见,城镇从1到 N 编号。 注意:两个城市之间可以有多条道路相通,也就是说 33 12 12 21 这种输入也是合法的 当 N 为0时,输入结束,该用例不被处理。

30

Output
对每个测试用例,在1行里输出最少还需要建设的道路数目。

Sample Input
4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0

Sample Output
1 0 2 998 Hint Hint Huge input, scanf is recommended.

Source
浙大计算机研究生复试上机考试-2005年

Recommend
JGShining

代码:#include <stdio.h>
#include <string.h> #define MAX 2000 int n,m; int arr[MAX][2]; int res[MAX]; int set; void proc() { int i,j; int rest; set=1; //用来统计集合个数 memset(res,0,(n+1)*sizeof(int)); res[arr[0][0]]=res[arr[0][1]]=1; for(i=1;i<=set;i++) { for(j=0;j<m;j++) { if(res[arr[j][0]]*res[arr[j][1]]) continue; //当前数据已经归类,则不进行任何 操作 if(res[arr[j][0]]==i||res[arr[j][1]]==i) { res[arr[j][0]]=res[arr[j][1]]=i; //对数据进行集合划分 j=-1; //从第一组元素开始继续遍历 } }
31

for(j=0;j<m;j++) if(res[arr[j][0]]*res[arr[j][1]]==0) break; //遇到首或尾没有归类的情况的时候跳 出 if(j<m) set++; //如果当前还有没有归类的情况新增加一个集合 else break; //如果当前数据全部归类则跳出所有循环 for(j=0;j<m;j++) { if(res[arr[j][0]]*res[arr[j][1]]==0){ res[arr[j][0]]=res[arr[j][1]]=set; break; } } } rest=0; for(i=1;i<=n;i++) if(res[i]==0) rest++; if(m==0) printf("%d\n",n-1); else if(rest==0) { if(set==1) printf("0\n"); else printf("%d\n",set-1); } else printf("%d\n",rest+set-1); } int main() { int i; scanf("%d",&n); while(n) { scanf("%d",&m); for(i=0;i<m;i++) scanf("%d %d",&arr[i][0],&arr[i][1]); proc(); scanf("%d",&n); } return 0; }

2000
Problem Description

ASCII 码排序

输入三个字符后,按各字符的 ASCII 码从小到大的顺序输出这三个字符。

Input
输入数据有多组,每组占一行,有三个字符组成,之间无空格。

Output
对于每组输入数据,输出一行,字符中间用一个空格分开。
32

Sample Input
qwe asd zxc

Sample Output
e q w a d s c x z

Author
lcy

Source
C 语言程序设计练习(一)

Recommend
JGShining

解答: #include<stdio.h> main() { char a,b,c,d; while(scanf("%c %c %c",&a,&b,&c)!=EOF) { getchar(); if(a>=b) { if(c>=a) printf("%c %c %c\n",b,a,c); else if(b>=c) printf("%c %c %c\n",c,b,a); else if(b<c) printf("%c %c %c\n",b,c,a); } else { if(c>=b) printf("%c %c %c\n",a,b,c); else if(c>=a) printf("%c %c %c\n",a,c,b); else if(a>c)
33

printf("%c %c %c\n",c,a,b); }

} }

2001
Problem Description

计算两点间的距离

输入两点坐标(X1,Y1),(X2,Y2),计算并输出两点间的距离。

Input
输入数据有多组,每组占一行,由 4 个实数组成,分别表示 x1,y1,x2,y2,数据之间用空格隔 开。

Output
对于每组输入数据,输出一行,结果保留两位小数。

Sample Input
0 0 0 1 0 1 1 0

Sample Output
1.00 1.41

Author
lcy

Source
C 语言程序设计练习(一)

Recommend
JGShining

解答: #include<stdio.h> #include<math.h> main() { double a,b,c,d,s;
34

while(scanf("%lf %lf %lf %lf",&a,&b,&c,&d)!=EOF) { s=sqrt((a-c)*(a-c)+(b-d)*(b-d)); printf("%.2lf\n",s); } }

2002
Problem Description
根据输入的半径值,计算球的体积。

计算球体积

Input
输入数据有多组,每组占一行,每行包括一个实数,表示球的半径。

Output
输出对应的球的体积,对于每组输入数据,输出一行,计算结果保留三位小数。

Sample Input
1 1.5

Sample Output
4.189 14.137 Hint #define PI 3.1415927

Author
lcy

Source
C 语言程序设计练习(一)

Recommend
JGShining

解答: #include<stdio.h> #define PI 3.1415927 main() { double a,v;
35

while(scanf("%lf",&a)!=EOF) { v=4*PI*a*a*a/3; printf("%.3lf\n",v); } }

2003
Problem Description
求实数的绝对值。

求绝对值

Input
输入数据有多组,每组占一行,每行包含一个实数。

Output
对于每组输入数据,输出它的绝对值,要求每组数据输出一行,结果保留两位小数。

Sample Input
123 -234.00

Sample Output
123.00 234.00

Author
lcy

Source
C 语言程序设计练习(一)

Recommend
JGShining

解答: #include<stdio.h> main() { double a; while(scanf("%lf",&a)!=EOF) { if(a<0) a=-a;
36

printf("%.2lf\n",a); } }

2004
Problem Description

成绩转换

输入一个百分制的成绩 t,将其转换成对应的等级,具体转换规则如下: 90~100 为 A; 80~89 为 B; 70~79 为 C; 60~69 为 D; 0~59 为 E;

Input
输入数据有多组,每组占一行,由一个整数组成。

Output
对于每组输入数据,输出一行。如果输入数据不在 0~100 范围内,请输出一行:―Score is error!‖。

Sample Input
56 67 100 123

Sample Output
E D A Score is error!

Author
lcy

Source
C 语言程序设计练习(一)

Recommend
JGShining

解答: #include <stdio.h>
37

int main() { int n; while(scanf("%d",&n)!=EOF) { if(n>100||n<0)printf("Score is error!\n"); else if(n>=90)printf("A\n"); else if(n>=80)printf("B\n"); else if(n>=70)printf("C\n"); else if(n>=60)printf("D\n"); else printf("E\n"); } return 0; }

2005
Problem Description

第几天?

给定一个日期,输出这个日期是该年的第几天。

Input
输入数据有多组,每组占一行,数据格式为 YYYY/MM/DD 组成,具体参见 sample input , 另外,可以向你确保所有的输入数据是合法的。

Output
对于每组输入数据,输出一行,表示该日期是该年的第几天。

Sample Input
1985/1/20 2006/3/12

Sample Output
20 71

Author
lcy

Source
C 语言程序设计练习(一)

Recommend
JGShining

38

解答: #include<stdio.h> main() { int a,b,c,d,e,f,g; while(scanf("%d/%d/%d",&a,&b,&c)!=EOF) { if(b==1) d=c; else if(b==2) d=31+c; else if(b==3) d=31+28+c; else if(b==4) d=31+28+31+c; else if(b==5) d=31+31+28+30+c; else if(b==6) d=31+28+31+30+31+c; else if(b==7) d=31+28+31+30+31+30+c; else if(b==8) d=31+28+31+30+31+30+31+c; else if(b==9) d=31+28+31+30+31+30+31+31+c; else if(b==10) d=31+28+31+30+31+30+31+31+30+c; else if(b==11) d=31+28+31+30+31+30+31+31+30+31+c; else if(b==12) d=31+28+31+30+31+30+31+31+30+31+c+30; e=a%100; f=a%400; g=a%4; if(e==0) { if(f==0) d=1+d; else d=d; } else if(g=0) d=d+1;
39

else d=d; printf("%d\n",d); } }

2006
Problem Description

求奇数的乘积

给你 n 个整数,求他们中所有奇数的乘积。

Input
输入数据包含多个测试实例,每个测试实例占一行,每行的第一个数为 n,表示本组数据一 共有 n 个,接着是 n 个整数,你可以假设每组数据必定至少存在一个奇数。

Output
输出每组数中的所有奇数的乘积,对于测试实例,输出一行。

Sample Input
3 1 2 3 4 2 3 4 5

Sample Output
3 15

Author
lcy

Source
C 语言程序设计练习(一)

Recommend
JGShining

解答: #include<stdio.h> main() { int n,s,i,a; while(scanf("%d",&n)!=EOF) { s=1;
40

for(i=0;i<n;i++) { scanf("%d",&a); if(a%2==1) s=s*a; else ; } printf("%d\n",s); } }

2007
Problem Description

平方和与立方和

给定一段连续的整数,求出他们中所有偶数的平方和以及所有奇数的立方和。

Input
输入数据包含多组测试实例,每组测试实例包含一行,由两个整数 m 和 n 组成。

Output
对于每组输入数据,输出一行,应包括两个整数 x 和 y,分别表示该段连续的整数中所有偶 数的平方和以及所有奇数的立方和。 你可以认为 32 位整数足以保存结果。

Sample Input
1 3 2 5

Sample Output
4 28 20 152

Author
lcy

Source
C 语言程序设计练习(一)

Recommend
JGShining

解答: #include<stdio.h> int main()
41

{ int sum1,sum2,n,i,m,t; while(scanf("%d%d",&m,&n)!=EOF) { sum1=sum2=0; if(m>n){t=m;m=n;n=t;} for(i=m;i<=n;i++) { if(i%2==0) sum1+=(i*i); else sum2+=(i*i*i); } printf("%d %d\n",sum1,sum2); } return 0; }

2008
Problem Description

数值统计

统计给定的 n 个数中,负数、零和正数的个数。

Input
输入数据有多组,每组占一行,每行的第一个数是整数 n(n<100),表示需要统计的数值 的个数,然后是 n 个实数;如果 n=0,则表示输入结束,该行不做处理。

Output
对于每组输入数据,输出一行 a,b 和 c,分别表示给定的数据中负数、零和正数的个数。

Sample Input
6 0 1 2 3 -1 0 5 1 2 3 4 0.5 0

Sample Output
1 2 3 0 0 5

Author
lcy

Source
C 语言程序设计练习(二)

42

Recommend
JGShining

解答: #include<stdio.h> int main() { int n,i,b1,b2,b3; double a[101]; while(scanf("%d",&n)!=EOF && n!=0) { for(i=0;i<n;i++) scanf("%lf",&a[i]); b1=b2=b3=0; for(i=0;i<n;i++) { if(a[i]<0) b1++; else if(a[i]==0) b2++; else b3++; } printf("%d %d %d\n",b1,b2,b3); } }

2009
Problem Description

求数列的和

数列的定义如下: 数列的第一项为 n,以后各项为前一项的平方根,求数列的前 m 项的和。

Input
输入数据有多组,每组占一行,由两个整数 n(n<10000)和 m(m<1000)组成,n 和 m 的含 义如前所述。

Output
对于每组输入数据,输出该数列的和,每个测试实例占一行,要求精度保留 2 位小数。

Sample Input
81 4 2 2

Sample Output
94.73
43

3.41

Author
lcy

Source
C 语言程序设计练习(二)

Recommend
JGShining

解答: #include<stdio.h> #include<math.h> main() { double n,m,s,w,i; while(scanf("%lf%lf",&n,&m)!=EOF) { s=n; for(i=1;i<m;i++) { n=sqrt(n); s=s+n; } printf("%.2lf\n",s); } }

2010
Problem Description

水仙花数

春天是鲜花的季节, 水仙花就是其中最迷人的代表, 数学上有个水仙花数, 他是这样定义的: ―水仙花数‖是指一个三位数,它的各位数字的立方和等于其本身,比如:153=1^3+5^3+3^3。 现在要求输出所有在 m 和 n 范围内的水仙花数。

Input
输入数据有多组,每组占一行,包括两个整数 m 和 n(100<=m<=n<=999)。

Output
对于每个测试实例,要求输出所有在给定范围内的水仙花数,就是说,输出的水仙花数必须 大于等于 m,并且小于等于 n,如果有多个,则要求从小到大排列在一行内输出,之间用一个 空格隔开;
44

如果给定的范围内不存在水仙花数,则输出 no; 每个测试实例的输出占一行。

Sample Input
100 120 300 380

Sample Output
no 370 371

Author
lcy

Source
C 语言程序设计练习(二)

Recommend
JGShining

解答: #include<stdio.h> main() { int m,n,i,w,a,b,c,j,s,d; while(scanf("%d %d",&n,&m)!=EOF) { d=0; j=1; if(m>n) { w=m; m=n; n=w; } else ; for(i=m;i<=n;i++) { a=i/100; b=i/10%10; c=i%10; s=a*a*a+b*b*b+c*c*c; if(i==s)
45

{ if(d!=0) printf(" "); printf("%d",i); d=d+1; j=j+1; } } if(j==1) printf("no\n"); else printf("\n"); } }

2011
Problem Description
多项式的描述如下: 1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + ... 现在请你求出该多项式的前 n 项的和。

多项式求和

Input
输入数据由 2 行组成,首先是一个正整数 m(m<100),表示测试实例的个数,第二行包含 m 个正整数,对于每一个整数(不妨设为 n,n<1000),求该多项式的前 n 项的和。

Output
对于每个测试实例 n,要求输出多项式前 n 项的和。每个测试实例的输出占一行,结果保留 2 位小数。

Sample Input
2 1 2

Sample Output
1.00 0.50

Author
lcy

46

Source
C 语言程序设计练习(二)

Recommend
JGShining

解答: #include<stdio.h> #include<math.h> main() { double m,n,i,s,j,k,a; while(scanf("%lf",&m)!=EOF) { for(i=0;i<m;i++) { s=0; scanf("%lf",&n); for(j=1;j<=n;j++) s=s+1/j*pow(-1,j+1); printf("%.2lf\n",s); } } }

2012
Problem Description

素数判定

对于表达式 n^2+n+41,当 n 在(x,y)范围内取整数值时(包括 x,y)(-39<=x<y<=50),判定 该表达式的值是否都为素数。

Input
输入数据有多组,每组占一行,由两个整数 x,y 组成,当 x=0,y=0 时,表示输入结束,该 行不做处理。

Output
对于每个给定范围内的取值,如果表达式的值都为素数,则输出"OK",否则请输出―Sorry‖, 每组输出占一行。

47

Sample Input
0 1 0 0

Sample Output
OK

Author
lcy

Source
C 语言程序设计练习(二)

Recommend
JGShining

解答: #include<stdio.h> main() { int x,y,i,j,s,k,w,d; while(scanf("%d%d",&x,&y)==2&&(x!=0||y!=0)) { w=0; for(i=x;i<=y;i++) { k=i*i+i+41; for(j=2;j<k;j++) { d=k%j; if(d==0) w++; } } if(w==0) printf("OK\n"); else printf("Sorry\n");

}
48

}

2014

青年歌手大奖赛_评委会打分

Problem Description
青年歌手大奖赛中, 评委会给参赛选手打分。 选手得分规则为去掉一个最高分和一个最低分, 然后计算平均得分,请编程输出某选手的得分。

Input
输入数据有多组,每组占一行,每行的第一个数是 n(2<n<100),表示评委的人数,然后是 n 个评委的打分。

Output
对于每组输入数据,输出选手的得分,结果保留 2 位小数,每组输出占一行。

Sample Input
3 99 98 97 4 100 99 98 97

Sample Output
98.00 98.50

Author
lcy

Source
C 语言程序设计练习(三)

Recommend
lcy

解答: #include<stdio.h> int main() { int n,s,a[100],i,k,b; double w; while(scanf("%d",&n)!=EOF) { k=0; w=0; s=0; for(i=0;i<n;i++)
49

{ scanf("%d",&a[i]); k++; b=a[0]; w=w+a[i]; } for(i=0;i<k;i++) { if(a[i]>s) s=a[i]; } for(i=1;i<k;i++) { if(b>a[i]) b=a[i]; } w=(w-s-b)/(k-2); printf("%.2lf\n",w); } }

2015
Problem Description

偶数求和

有一个长度为 n(n<=100)的数列,该数列定义为从 2 开始的递增有序偶数,现在要求你按照 顺序每 m 个数求出一个平均值,如果最后不足 m 个,则以实际数量求平均值。编程输出该 平均值序列。

Input
输入数据有多组,每组占一行,包含两个正整数 n 和 m,n 和 m 的含义如上所述。

Output
对于每组输入数据,输出一个平均值序列,每组输出占一行。

Sample Input
3 2 4 2

Sample Output
3 6 3 7

Author
lcy
50

Source
C 语言程序设计练习(三)

Recommend
lcy

解答: #include<stdio.h> main() { int n,m,a,b,i,j,k,w,l,e,s,d,r; while(scanf("%d%d",&n,&m)!=EOF) { s=0; e=0; l=0; if(n<=m) { for(i=0;i<n;i++) { s=s+2; e=e+s; k=e/n; } printf("%d\n",k); } else { w=n%m; r=0; for(i=1;i<=n-w;i++) { s=s+2; l=l+s; e=e+s; if(i%m==0) { k=e/m; e=0; if(r) printf(" "); printf("%d",k); r=r+1;
51

} } s=0; if(w!=0) { for(j=0;j<n;j++) { s=s+2; e=e+s; } d=e-l; k=d/w; printf(" "); printf("%d",k); } printf("\n"); } } }

2016
Problem Description

数据的交换输出

输入 n(n<100)个数,找出其中最小的数,将它与最前面的数交换后输出这些数。

Input
输入数据有多组, 每组占一行, 每行的开始是一个整数 n, 表示这个测试实例的数值的个数, 跟着就是 n 个整数。n=0 表示输入的结束,不做处理。

Output
对于每组输入数据,输出交换后的数列,每组输出占一行。

Sample Input
4 2 1 3 4 5 5 4 3 2 1 0

Sample Output
1 2 3 4 1 4 3 2 5
52

Author
lcy

Source
C 语言程序设计练习(三)

Recommend
lcy

解答: #include<stdio.h> main() { int n,a[100],i,j,k,s,w; while(scanf("%d",&n)!=EOF&&n!=0) { j=0; for(i=0;i<n;i++) { scanf("%d",&a[i]); k=a[0]; } for(i=0;i<n;i++) { if(k>a[i]) { k=a[i]; j=i; } } w=a[0]; a[0]=k; a[j]=w; for(i=0;i<n;i++) { printf("%d",a[i]); if(n-i!=1) printf(" "); } printf("\n"); }
53

}

2017
Problem Description

字符串统计

对于给定的一个字符串,统计其中数字字符出现的次数。

Input
输入数据有多行,第一行是一个整数 n,表示测试实例的个数,后面跟着 n 行,每行包括一 个由字母和数字组成的字符串。

Output
对于每个测试实例,输出该串中数值的个数,每个输出占一行。

Sample Input
2 asdfasdf123123asdfasdf asdf111111111asdfasdfasdf

Sample Output
6 9

Author
lcy

解答: #include<stdio.h> main() { int n,i,j,a; char s[1000]; while(scanf("%d",&n)!=EOF) { getchar(); for(i=0;i<n;i++) { gets(s); a=0; for(j=0;s[j]!='\0';j++) { if((s[j]<='9')&&(s[j]>='0')) a=a+1; }
54

printf("%d\n",a); } } }

2019
Problem Description

数列有序!

有 n(n<=100)个整数,已经按照从小到大顺序排列好,现在另外给一个整数 x,请将该数插 入到序列中,并使新的序列仍然有序。

Input
输入数据包含多个测试实例,每组数据由两行组成,第一行是 n 和 m,第二行是已经有序的 n 个数的数列。n 和 m 同时为 0 标示输入数据的结束,本行不做处理。

Output
对于每个测试实例,输出插入新的元素后的数列。

Sample Input
3 3 1 2 4 0 0

Sample Output
1 2 3 4

Author
lcy

Source
C 语言程序设计练习(三)

Recommend
lcy

解答: #include<stdio.h> main() { int n,m,a[100],b[100],i,j,k,s,w,d; scanf("%d%d",&n,&m); while(!(n==0&&m==0)) {
55

w=0; for(i=0;i<n;i++) scanf("%d",&a[i]); s=a[0]; if(m<s) { printf("%d",m); for(j=0;j<n;j++) { printf(" "); printf("%d",a[j]); } } else { for(j=0;j<n;j++) { if(m>a[j]) w=w+1; } for(j=0;j<w;j++) { printf("%d",a[j]); printf(" "); } printf("%d",m); for(j=w;j<n;j++) { printf(" "); printf("%d",a[j]); } } printf("\n"); scanf("%d%d",&n,&m); } }

2020
Problem Description

绝对值排序

输入 n(n<=100)个整数,按照绝对值从大到小排序后输出。题目保证对于每一个测试实例, 所有的数的绝对值都不相等。

56

Input
输入数据有多组,每组占一行,每行的第一个数字为 n,接着是 n 个整数,n=0 表示输入数据 的结束,不做处理。

Output
对于每个测试实例, 输出排序后的结果, 两个数之间用一个空格隔开。 每个测试实例占一行。

Sample Input
3 3 -4 2 4 0 1 2 -3 0

Sample Output
-4 3 2 -3 2 1 0

Author
lcy

Source
C 语言程序设计练习(三)

Recommend
lcy

解答: #include<stdio.h> main() { int n,m,a[100],b[100],c,d,e,f,i,j,k; while(scanf("%d",&n)!=EOF&&n!=0) { for(i=0;i<n;i++) scanf("%d",&a[i]); f=0; for(j=0;j<n;j++) { c=0; for(i=0;i<n;i++) { if(a[i]<0) m=-a[i]; else m=a[i]; if(c<=m)
57

{ c=m; b[j]=a[i]; k=i; } } a[k]=0; if(f) printf(" "); printf("%d",b[j]); f=f+1; } printf("\n"); } }

2021
Problem Description

发工资咯: )

作为杭电的老师,最盼望的日子就是每月的 8 号了,因为这一天是发工资的日子,养家糊口 就靠它了,呵呵 但是对于学校财务处的工作人员来说, 这一天则是很忙碌的一天, 财务处的小胡老师最近就 在考虑一个问题:如果每个老师的工资额都知道,最少需要准备多少张人民币,才能在给每 位老师发工资的时候都不用老师找零呢? 这里假设老师的工资都是正整数,单位元,人民币一共有 100 元、50 元、10 元、5 元、2 元和 1 元六种。

Input
输入数据包含多个测试实例,每个测试实例的第一行是一个整数 n(n<100),表示老师的 人数,然后是 n 个老师的工资。 n=0 表示输入的结束,不做处理。

Output
对于每个测试实例输出一个整数 x,表示至少需要准备的人民币张数。每个输出占一行。

Sample Input
3 1 2 3 0

Sample Output
4

58

Author
lcy

Source
C 语言程序设计练习(四)

Recommend
lcy

解答: #include<stdio.h> main() { int n,m,a,b,c,d,e,f,i,j,k; while(scanf("%d",&n)!=EOF&&n!=0) { k=0; for(i=0;i<n;i++) { scanf("%d",&m); a=m/100; b=m%100/50; c=m%100%50/10; d=m%100%50%10/5; e=m%100%50%10%5/2; f=m%100%50%10%5%2; k=k+a+b+c+d+e+f; } printf("%d\n",k); } }

2033
Problem Description

人见人爱 A+B

HDOJ 上面已经有 10 来道 A+B 的题目了,相信这些题目曾经是大家的最爱,希望今天的这 个 A+B 能给大家带来好运,也希望这个题目能唤起大家对 ACM 曾经的热爱。 这个题目的 A 和 B 不是简单的整数,而是两个时间,A 和 B 都是由 3 个整数组成,分别表 示时分秒,比如,假设 A 为 34 45 56,就表示 A 所表示的时间是 34 小时 45 分钟 56 秒。

Input

59

输入数据有多行组成,首先是一个整数 N,表示测试实例的个数,然后是 N 行数据,每行 有 6 个整数 AH,AM,AS,BH,BM,BS,分别表示时间 A 和 B 所对应的时分秒。题目保证所有 的数据合法。

Output
对于每个测试实例,输出 A+B,每个输出结果也是由时分秒 3 部分组成,同时也要满足时 间的规则(即:分和秒的取值范围在 0~59),每个输出占一行,并且所有的部分都可以用 32 位整数表示。

Sample Input
2 1 2 3 4 5 6 34 45 56 12 23 34

Sample Output
5 7 9 47 9 30

Author
lcy

Source
ACM 程序设计期末考试(2006/06/07)

Recommend
lcy

解答: #include<stdio.h> main() {int i,j,a,b,c,d,e,f,n,s; while(scanf("%d",&n)!=EOF) { c=0;d=0;e=0; for(i=0;i<n;i++) { a=0;b=0;c=0;d=0;e=0;f=0; scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f); a=a+d; b=b+e;c=c+f; j=0; while(c>60) { c=c-60; j=j+1; }
60

b=b+j; s=0; while(b>60) { b=b-60; s=s+1; } a=a+s; printf("%d %d %d\n",a,b,c); } } }

2037
Problem Description
―今年暑假不 AC?‖ ―是的。‖ ―那你干什么呢?‖ ―看世界杯呀,笨蛋!‖ ―@#$%^&*%...‖

今年暑假不 AC

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13407 Accepted Submission(s): 6933

确实如此,世界杯来了,球迷的节日也来了,估计很多 ACMer 也会抛开电脑,奔向电视了。 作为球迷,一定想看尽量多的完整的比赛,当然,作为新时代的好青年,你一定还会看一些 其它的节目,比如新闻联播(永远不要忘记关心国家大事) 、非常6+7、超级女生,以及王 小丫的《开心辞典》等等,假设你已经知道了所有你喜欢看的电视节目的转播时间表,你会 合理安排吗?(目标是能看尽量多的完整节目)

Input
输入数据包含多个测试实例,每个测试实例的第一行只有一个整数 n(n<=100),表示你喜欢 看的节目的总数,然后是 n 行数据,每行包括两个数据 Ti_s,Ti_e (1<=i<=n),分别表示第 i 个节目的开始和结束时间,为了简化问题,每个时间都用一个正整数表示。n=0表示输入结 束,不做处理。

Output
对于每个测试实例,输出能完整看到的电视节目的个数,每个测试实例的输出占一行。

Sample Input
12 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0

Sample Output
5

Author
lcy

61

Source
ACM 程序设计期末考试(2006/06/07)

Recommend
lcy

代码:
#include<stdio.h> #define MAX 200 int arr[MAX][2]; int num; void res() { int i,j; int start; int count=0,max=-1; for(i=num-1;i>=num/2;i--) { if(count>max) max=count; count=1; start=arr[i][0]; for(j=i-1;j>=0;j--) { if(arr[j][1]<=start){ count++; start=arr[j][0]; } } } printf("%d\n",max); } void prc() { int i,j; for(i=0;i<num;i++) scanf("%d %d",&arr[i][0],&arr[i][1]); for(i=0;i<num;i++) //排序 for(j=i+1;j<num;j++) { if(arr[i][0]>arr[j][0]) { arr[i][0]+=arr[j][0]; arr[j][0]=arr[i][0]-arr[j][0]; arr[i][0]=arr[i][0]-arr[j][0]; arr[i][1]+=arr[j][1]; arr[j][1]=arr[i][1]-arr[j][1]; arr[i][1]=arr[i][1]-arr[j][1]; } if((arr[i][0]==arr[j][0])&&(arr[i][1]>arr[j][1])) { arr[i][1]+=arr[j][1]; arr[j][1]=arr[i][1]-arr[j][1]; arr[i][1]=arr[i][1]-arr[j][1]; }

62

} res(); } int main() { scanf("%d",&num); while(num) { prc(); scanf("%d",&num); } return 0; }

2039
Problem Description

三角形

给定三条边,请你判断一下能不能组成一个三角形。

Input
输入数据第一行包含一个数 M,接下有 M 行,每行一个实例,包含三个正数 A,B,C。其中 A,B,C <1000;

Output
对于每个测试实例,如果三条边长 A,B,C 能组成三角形的话,输出 YES,否则 NO。

Sample Input
2 1 2 3 2 2 2

Sample Output
NO YES

Author
linle

Source
2005 实验班短学期考试

Recommend
lcy

63

解答: #include<stdio.h> main() { double n,a,b,c,i; while(scanf("%lf",&n)!=EOF) { for(i=0;i<n;i++) { scanf("%lf%lf%lf",&a,&b,&c); if((a+b)>c&&(b+c)>a&&(a+c)>b) printf("YES\n"); else printf("NO\n"); } } }

2040
Problem Description

亲和数

古希腊数学家毕达哥拉斯在自然数研究中发现,220 的所有真约数(即不是自身的约数)之和 为: 1+2+4+5+10+11+20+22+44+55+110=284。 而 284 的所有真约数为 1、2、4、71、 142,加起来恰好为 220。人们对这样的数感到很惊 奇,并称之为亲和数。一般地讲,如果两个数中任何一个数都是另一个数的真约数之和,则 这两个数就是亲和数。 你的任务就编写一个程序,判断给定的两个数是否是亲和数

Input
输入数据第一行包含一个数 M, 接下有 M 行, 每行一个实例,包含两个整数 A,B; 其中 0 <= A,B <= 600000 ;

Output
对于每个测试实例,如果 A 和 B 是亲和数的话输出 YES,否则输出 NO。

Sample Input
2 220 284 100 200

64

Sample Output
YES NO

Author
linle

Source
2005 实验班短学期考试

Recommend
lcy

解答: #include<stdio.h> main() { double n,a,b,c,i; while(scanf("%lf",&n)!=EOF) { for(i=0;i<n;i++) { scanf("%lf%lf%lf",&a,&b,&c); if((a+b)>c&&(b+c)>a&&(a+c)>b) printf("YES\n"); else printf("NO\n"); } } }

2045

不容易系列之(3)—— LELE 的 RPG 难题

Problem Description
人称―AC 女之杀手‖的超级偶像 LELE 最近忽然玩起了深沉,这可急坏了众多―Cole‖(LELE 的粉丝,即"可乐"),经过多方打探,某资深 Cole 终于知道了原因,原来,LELE 最近研究起 了著名的 RPG 难题: 有排成一行的n个方格,用红(Red)、粉(Pink)、绿(Green)三色涂每个格子,每格涂一色,要 求任何相邻的方格不能同色,且首尾两格也不同色.求全部的满足要求的涂法. 以上就是著名的 RPG 难题.
65

如果你是 Cole,我想你一定会想尽办法帮助 LELE 解决这个问题的;如果不是,看在众多漂亮的 痛不欲生的 Cole 女的面子上,你也不会袖手旁观吧?

Input
输入数据包含多个测试实例,每个测试实例占一行,由一个整数 N 组成,(0<n<=50)。

Output
对于每个测试实例,请输出全部的满足要求的涂法,每个实例的输出占一行。

Sample Input
1 2

Sample Output
3 6

Author
lcy

Source
递推求解专题练习(For Beginner)

Recommend
lcy

递推公式:f(n)=f(n-1)+2*f(n-2)

代码:#include<stdio.h>
int main() { __int64 i,arr[51]; __int64 num; arr[0]=0; arr[1]=3; arr[2]=6; arr[3]=6; for(i=4;i<51;i++) arr[i]=arr[i-1]+2*arr[i-2]; while(scanf("%d",&num)!=EOF) { printf("%I64d\n",arr[num]); } return 0; }

2049

不容易系列之(4)——考新郎

Problem Description
国庆期间,省城 HZ 刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想 出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的:

66

首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排; 然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个. 最后,揭开盖头,如果找错了对象就要当众跪搓衣板... 看来做新郎也不是容易的事情... 假设一共有 N 对新婚夫妇,其中有 M 个新郎找错了新娘,求发生这种情况一共有多少种可能.

Input
输入数据的第一行是一个整数 C,表示测试实例的个数,然后是 C 行数据,每行包含两个整 数 N 和 M(1<M<=N<=20)。

Output
对于每个测试实例,请输出一共有多少种发生这种情况的可能,每个实例的输出占一行。

Sample Input
2 2 2 3 2

Sample Output
1 3

Author
lcy

Source
递推求解专题练习(For Beginner)

Recommend
lcy

错排类递推公式为:f(n)=(m-1)*[f(n-1)+f(n-2)],其中 m 表示错排的个数(即错排 的新人对数) 表示全部的新人个数。 ,n

代码:
#include <stdio.h> int main(void) { int i, m, n; __int64 a[21][2] = {{1,0},{1,0},{2,1},{6,2}}; for (i = 4; i < 21; i++) { a[i][0] = i * a[i-1][0]; a[i][1] = (i-1) * (a[i-1][1] + a[i-2][1]);

67

} scanf("%d", &i); while (i-- && scanf("%d%d", &n, &m)) printf("%I64d\n", a[n][0]/a[m][0]/a[n-m][0]*a[m][1]); return 0; }

2056
Problem Description

Rectangles

Given two rectangles and the coordinates of two points on the diagonals of each rectangle,you have to calculate the area of the intersected part of two rectangles. its sides are parallel to OX and OY .

Input
Input The first line of input is 8 positive numbers which indicate the coordinates of four points that must be on each diagonal.The 8 numbers are x1,y1,x2,y2,x3,y3,x4,y4.That means the two points on the first rectangle are(x1,y1),(x2,y2);the other two points on the second rectangle are (x3,y3),(x4,y4).

Output
Output For each case output the area of their intersected part in a single line.accurate up to 2 decimal places.

Sample Input
1.00 1.00 3.00 3.00 2.00 2.00 4.00 4.00 5.00 5.00 13.00 13.00 4.00 4.00 12.50 12.50

Sample Output
1.00 56.25

Author
seeyou

Source
校庆杯 Warm Up

Recommend
linle

代码:
#include<stdio.h> void res(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4) { double tmpx1,tmpy1,tmpx2,tmpy2; double tmpx,tmpy; tmpx=x1+x2; x1=(x1>x2)?x2:x1; x2=tmpx-x1; tmpy=y1+y2; y1=(y1>y2)?y2:y1; y2=tmpy-y1; tmpx=x3+x4; x3=(x3>x4)?x4:x3; x4=tmpx-x3; tmpy=y3+y4; y3=(y3>y4)?y4:y3; y4=tmpy-y3; tmpx1=(x1>x3)?x1:x3; tmpx2=(x2>x4)?x4:x2;
68

tmpy1=(y1>y3)?y1:y3; tmpy2=(y2>y4)?y4:y2; if(tmpx1<tmpx2&&tmpy1<tmpy2) printf("%.2lf\n",(tmpx1-tmpx2)*(tmpy1-tmpy2)); else printf("0.00\n"); } int main() { double x1,y1,x2,y2; double x3,y3,x4,y4; while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4)!=EOF) { res(x1,y1,x2,y2,x3,y3,x4,y4); } return 0; }

2073
Problem Description

无限的路

甜甜从小就喜欢画图画,最近他买了一支智能画笔,由于刚刚接触,所以甜甜只会用它来画 直线,于是他就在平面直角坐标系中画出如下的图形:

甜甜的好朋友蜜蜜发现上面的图还是有点规则的,于是他问甜甜:在你画的图中,我给你两 个点,请你算一算连接两点的折线长度(即沿折线走的路线长度)吧。

Input
第一个数是正整数 N(≤100) 。代表数据的组数。
69

每组数据由四个非负整数组成 x1,y1,x2,y2;所有的数都不会大于100。

Output
对于每组数据, 输出两点(x1,y1),(x2,y2)之间的折线距离。 注意输出结果精确到小数点后3位。

Sample Input
5 0 0 0 1 0 0 1 0 2 3 3 1 99 99 9 9 5 5 5 5

Sample Output
1.000 2.414 10.646 54985.047 0.000

Author
Lily

Source
浙江工业大学网络选拔赛

Recommend
linle

代码:
#include <cmath> #include <cstdio> #include <algorithm> using namespace std; int main(void) { int n, x[3], y[3]; double s; scanf("%d", &n); while (n-- && scanf("%d%d%d%d", x, y, x+1, y+1)) { if ((x[2] = x[0]+y[0]) > (y[2] = x[1]+y[1])) { swap(x[0], x[1]); swap(y[0], y[1]); swap(x[2], y[2]); } if (x[2] == y[2]) printf("%.3f\n", sqrt(pow(x[0]-x[1], 2)+pow(y[0]-y[1], 2))); else { s = sqrt((double)2.0)*(x[2] + x[1] - x[0] + y[2]*(y[2]-1)/2.0 - x[2]*(x[2]+1)/2.0); for (; x[2] < y[2]; x[2]++) s += sqrt((double)2*x[2]*x[2]+2*x[2]+1); printf("%.3f\n", s); } } return 0; }

70

2084
Problem Description

数塔

在讲述 DP 算法的时候,一个经典的例子就是数塔问题,它是这样描述的: 有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的 数字之和最大是多少?

已经告诉你了,这是个 DP 的题目,你能 AC 吗?

Input
输入数据首先包括一个整数 C,表示测试实例的个数, 每个测试实例的第一行是一个整数 N(1 <= N <= 100),表示数塔的高度,接下来用 N 行数字表示数塔,其中第 i 行有个 i 个整数, 且所有的整数均在区间[0,99]内。

Output
对于每个测试实例,输出可能得到的最大和,每个实例的输出占一行。

Sample Input
1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

Sample Output
30

Source
2006/1/15 ACM 程序设计期末考试

Recommend
lcy

代码:#include<stdio.h>
#include<string.h> #define MAX 101

71

int arr[MAX][MAX][2]; void res() { int n; int i,j; memset(arr,0,MAX*MAX*sizeof(int)); scanf("%d",&n); for(i=0;i<n;i++) //输入数塔 for(j=0;j<=i;j++) { scanf("%d",&arr[i][j][0]); arr[i][j][1]=arr[i][j][0]; for(i=n-2;i>=0;i--) { for(j=0;j<=i;j++) { if(arr[i+1][j][1]>arr[i+1][j+1][1]) arr[i][j][1]+=arr[i+1][j][1]; else arr[i][j][1]+=arr[i+1][j+1][1]; } } printf("%d\n",arr[0][0][1]); } int main() { int num; scanf("%d",&num); while(num--) { res(); } return 0; }

}

2201
Problem Description

熊猫阿波的故事

凡看过功夫熊猫这部电影的人都会对影片中那只憨憨的熊猫阿波留下相当深的印象, 胖胖的 熊猫阿波自从打败了凶狠强悍的雪豹泰龙以后, 在和平谷的地位是越来越高, 成为谷中第一 的功夫大师。 并因此他父亲经营的面馆的生意也越来越好, 店里每天都会有许多慕名而来吃 面和想拜阿波为师的人。 一日,阿波收到了一张请柬,请柬里说在遥远的美国将召开全球比武大会,特邀请阿波过去 做嘉宾。阿波当然很高兴,因为自己长这么大都还没出过和平谷,更何况是出国去那遥远的 美国。于是他托人买了当晚的机票,阿波来到机场发现其他乘客们正准备按机票上的号码 (1,2,3,.....,n)依次排队上飞机,由于阿波是第一次坐飞机,所以他想先一步登机,因此他插队 第一个登上了飞机,并且他也不看机票,随机的选择了一个座位坐下了。乘客们都很气氛, 他们想: 既然阿波都不遵守规定, 那么我为什么要遵守呢?因此后面所有的人也都随意地找 了位置坐下来,并且坚决不让座给其他的乘客。 现在的问题是这样的:在这样的情况下,第 i 个乘客(除去熊猫阿波外)坐到原机票位置的概 率是多少?

Input
输入包含多组测试数据,每组数据占一行,包含两个整数,分别是 n 和 m(n>=m),n 表示共
72

有 n 个乘客(包括阿波),m 表示第 m 个乘客。

Output
对于每组数据,请输出第 m 个乘客(除去熊猫阿波外)坐到原机票位置的概率是多少?(结果保 留2位小数) 每组输出占一行。

Sample Input
2 1 11 3

Sample Output
0.50 0.09

Author
Eddy

Recommend
lcy 代码: #include<iostream> using namespace std; int main() { double n, m; while( cin >> n >> m) { double k = 1/ n; printf("%.2f",k); cout << endl; } return 0; }

2212
Problem Description

DFS

A DFS(digital factorial sum) number is found by summing the factorial of every digit of a positive integer. For example ,consider the positive integer 145 = 1!+4!+5!, so it's a DFS number. Now you should find out all the DFS numbers in the range of int( [1, 2147483647] ). There is no input for this problem. Output all the DFS numbers in increasing order. The first 2 lines of the output are shown below.

Input
no input
73

Output
Output all the DFS number in increasing order.

Sample Output
1 2 ......

Author
zjt

Recommend
Lcy 代码: #include<stdio.h> main() { printf("1\n2\n145\n40585\n"); }

2304
Problem Description

Electrical Outlets

Roy has just moved into a new apartment. Well, actually the apartment itself is not very new, even dating back to the days before people had electricity in their houses. Because of this, Roy's apartment has only one single wall outlet, so Roy can only power one of his electrical appliances at a time. Roy likes to watch TV as he works on his computer, and to listen to his HiFi system (on high volume) while he vacuums, so using just the single outlet is not an option. Actually, he wants to have all his appliances connected to a powered outlet, all the time. The answer, of course, is power strips, and Roy has some old ones that he used in his old apartment. However, that apartment had many more wall outlets, so he is not sure whether his power strips will provide him with enough outlets now. Your task is to help Roy compute how many appliances he can provide with electricity, given a set of power strips. Note that without any power strips, Roy can power one single appliance through the wall outlet. Also, remember that a power strip has to be powered itself to be of any use.

Input
Input will start with a single integer 1 <= N <= 20, indicating the number of test cases to follow. Then follow N lines, each describing a test case. Each test case starts with an integer 1 <= K <= 10, indicating the number of power strips in the test case. Then follow, on the same line, K integers separated by single spaces, O1 O2 . . . OK, where 2 <= Oi <= 10, indicating the number of outlets in each power strip.

Output
Output one line per test case, with the maximum number of appliances that can be powered.

Sample Input
3 3 2 3 4 10 4 4 4 4 4 4 4 4 4 4 4 10 10 10 10

Sample Output
7 31 37
74

Source
NCPC2005

Recommend
zty

代码: #include<stdio.h> int main() { int sum,num,t,n,i; scanf("%d",&t); while(t--) { scanf("%d",&n); sum=0; for(i=0;i<n;i++) { scanf("%d",&num); sum+=num; } printf("%d\n",sum-n+1); } return 0; }

2309

ICPC Score Totalizer Software

Problem Description
The International Clown and Pierrot Competition (ICPC), is one of the most distinguished and also the most popular events on earth in the show business. One of the unique features of this contest is the great number of judges that sometimes counts up to one hundred. The number of judges may differ from one contestant to another, because judges with any relationship whatsoever with a specific contestant are temporarily excluded for scoring his/her performance. Basically, scores given to a contestant's performance by the judges are averaged to decide his/her score. To avoid letting judges with eccentric viewpoints too much influence the score, the highest and the lowest scores are set aside in this calculation. If the same highest score is marked by two or more judges, only one of them is ignored. The same is with the lowest score. The average, which may contain fractions, are truncated down to obtain final score as an integer. You are asked to write a program that computes the scores of performances, given the scores of all the judges, to speed up the event to be suited for a TV program.
75

Input
The input consists of a number of datasets, each corresponding to a contestant's performance. There are no more than 20 datasets in the input. A dataset begins with a line with an integer n, the number of judges participated in scoring the performance (3 ≤ n ≤ 100). Each of the n lines following it has an integral score s (0 ≤ s ≤ 1000) marked by a judge. No other characters except for digits to express these numbers are in the input. Judges' names are kept secret. The end of the input is indicated by a line with a single zero in it.

Output
For each dataset, a line containing a single decimal integer indicating the score for the corresponding performance should be output. No other characters should be on the output line.

Sample Input
3 1000 342 0 5 2 2 9 11 932 5 300 1000 0 200 400 8 353 242 402 274 283 132 402 523 0

Sample Output
342 7 300 326

Source
Japan 2007 Domestic

Recommend
teddy

代码: #include<stdio.h> main() { int n,i,s,x,y,a; while(scanf("%d",&n)!=EOF&&n) { x=0,y=1000; for(i=1,s=0;i<=n;i++) { scanf("%d",&a); s+=a; if(a>x) x=a; if(a<y) y=a; }

76

printf("%d\n",(s-x-y)/(n-2)); } }

2317
Problem Description

Nasty Hacks

You are the CEO of Nasty Hacks Inc., a company that creates small pieces of malicious software which teenagers may use to fool their friends. The company has just finished their first product and it is time to sell it. You want to make as much money as possible and consider advertising in order to increase sales. You get an analyst to predict the expected revenue, both with and without advertising. You now want to make a decision as to whether you should advertise or not, given the expected revenues.

Input
The input consists of n cases, and the first line consists of one positive integer giving n. The next n lines each contain 3 integers, r, e and c. The first, r, is the expected revenue if you do not advertise, the second, e, is the expected revenue if you do advertise, and the third, c, is the cost of advertising. You can assume that the input will follow these restrictions: -106 ≤ r, e ≤ 106 and 0 ≤ c ≤ 106.

Output
Output one line for each test case: ―advertise‖, ―do not advertise‖ or ―does not matter‖, presenting whether it is most profitable to advertise or not, or whether it does not make any difference.

Sample Input
3 0 100 70 100 130 30 -100 -70 40

Sample Output
advertise does not matter do not advertise

Source
Nordic 2006

Recommend
zty

代码: #include<stdio.h> main() { int i; long a[3],k; scanf("%d",&i); while(i--) { scanf("%ld%ld%ld",&a[0],&a[1],&a[2]); k=a[1]-a[2];
77

if(a[0]<k) printf("advertise\n"); else if(a[0]==k) printf("does not matter\n"); else printf("do not advertise\n"); } }

2401

Baskets of Gold Coins

Problem Description
You are given N baskets of gold coins. The baskets are numbered from 1 to N. In all except one of the baskets, each gold coin weighs w grams. In the one exceptional basket, each gold coin weighs w-d grams. A wizard appears on the scene and takes 1 coin from Basket 1, 2 coins from Basket 2, and so on, up to and including N-1 coins from Basket N-1. He does not take any coins from Basket N. He weighs the selected coins and concludes which of the N baskets contains the lighter coins. Your mission is to emulate the wizard's computation.

Input
The input file will consist of one or more lines; each line will contain data for one instance of the problem. More specifically, each line will contain four positive integers, separated by one blank space. The first three integers are, respectively, the numbers N, w, and d, as described above. The fourth integer is the result of weighing the selected coins. N will be at least 2 and not more than 8000. The value of w will be at most 30. The value of d will be less than w.

Output
For each instance of the problem, your program will produce one line of output, consisting of one positive integer: the number of the basket that contains lighter coins than the other baskets.

Sample Input
10 25 8 1109 10 25 8 1045 8000 30 12 959879400

Sample Output
2 10 50

Source
ACM/ICPC 2008 Warmup(2)——测试帐号(杭州)

Recommend
lcy

代码: #include<stdio.h> int main() {
78

int a,b,c,d,sum; while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF) { sum=a*(a-1)/2*b; if(sum==d) printf("%d\n",a); else printf("%d\n",(sum-d)/c); } return 0; }

2500
Problem Description

做一个正气的杭电人

做人要有一身正气,杭电学子都应该如此。比如我们今天的考试就应该做到―诚信‖为上。 每次考试的第一个题目总是很简单, 今天也不例外, 本题是要求输出指定大小的"HDU"字符 串, 特别地, 为了体现―正气‖二字, 我们要求输出的字符串也是正方形的 (行数和列数相等) 。

Input
输入的第一行包含一个正整数 N(N<=20) ,表示一共有 N 组数据,接着是 N 行数据,每行 包含一个正整数 M(M<=50) ,表示一行内有 M 个―HDU‖相连。

Output
输出指定大小的方形字符串,输出格式参见样本数据。

Sample Input
2 1 2

Sample Output
HDU HDU HDU HDUHDU HDUHDU HDUHDU HDUHDU HDUHDU HDUHDU

Source
《ACM 程序设计》短学期考试_软件工程及其他专业

Recommend
lcy

代码: #include<stdio.h> main() { int n,m,i,j; scanf("%d",&n); while(n--) { scanf("%d",&m); for(i=0;i<m*3;i++)
79

{ for(j=0;j<m;j++) printf("HDU"); puts(""); } } }

2501
Problem Description

Tiling_easy version

有一个大小是 2 x n 的网格, 现在需要用 2 种规格的骨牌铺满, 骨牌规格分别是 2 x 1 和 2 x 2,请计算一共有多少种铺设的方法。

Input
输入的第一行包含一个正整数 T(T<=20) ,表示一共有 T 组数据,接着是 T 行数据,每行 包含一个正整数 N(N<=30) ,表示网格的大小是 2 行 N 列。

Output
输出一共有多少种铺设的方法,每组数据的输出占一行。

Sample Input
3 2 8 12

Sample Output
3 171 2731

Source
《ACM 程序设计》短学期考试_软件工程及其他专业

Recommend
lcy

代码: #include<stdio.h> main() { int t,n,i,a[31]; a[1]=1; a[2]=3; for(i=3;i<=31;i++) a[i]=2*a[i-2]+a[i-1];
80

scanf("%d",&t); while(t--) { scanf("%d",&n); printf("%d\n",a[n]); } }

2502
Problem Description

月之数

当寒月还在读大一的时候,他在一本武林秘籍中(据后来考证,估计是计算机基础,狂汗 -ing) ,发现了神奇的二进制数。 如果一个正整数 m 表示成二进制,它的位数为 n(不包含前导0) ,寒月称它为一个 n 二进制 数。所有的 n 二进制数中,1的总个数被称为 n 对应的月之数。 例如,3二进制数总共有4个,分别是4(100) 、5(101) 、6(110) 、7(111) ,他们中1的个 数一共是1+2+2+3=8,所以3对应的月之数就是8。

Input
给你一个整数 T, 表示输入数据的组数, 接下来有 T 行, 每行包含一个正整数 n 1<=n<=20) ( 。

Output
对于每个 n ,在一行内输出 n 对应的月之数。

Sample Input
3 1 2 3

Sample Output
1 3 8

Source
《ACM 程序设计》短学期考试_软件工程及其他专业

Recommend
lcy

代码: main() { int n,m; scanf("%d",&n); while(n--) { scanf("%d",&m); printf("%d\n",(m+1)*(1<<m)/4); } }

81

2503
Problem Description Input

a/b + c/d

Output
对于每组测试数据,输出两个整数 e 和 f,表示 a/b + c/d 的最简化结果是 e/f,每组输出占一 行。

Sample Input
2 1 2 1 3 4 3 2 3

Sample Output
5 6 2 1

Source
《ACM 程序设计》短学期考试_软件工程及其他专业

Recommend
lcy

代码: #include<iostream> using namespace std; int gcd(int a,int b) { int c=a%b; while(c) { a=b; b=c; c=a%b; } return b; } int main() { int n,a,b,c,d,t1,t2,t; cin>>n; while(n--) { scanf("%d%d%d%d",&a,&b,&c,&d); t1=a*d+b*c; t2=b*d;

82

t=gcd(t1,t2); printf("%d %d\n",t1/t,t2/t); } return 0; }

2504
Problem Description

又见 GCD

有三个正整数 a,b,c(0<a,b,c<10^6),其中 c 不等于 b。若 a 和 c 的最大公约数为 b,现已知 a 和 b,求满足条件的最小的 c。

Input
第一行输入一个 n,表示有 n 组测试数据,接下来的 n 行,每行输入两个正整数 a,b。

Output
输出对应的 c,每组测试数据占一行。

Sample Input
2 6 2 12 4

Sample Output
4 8

Source
《ACM 程序设计》短学期考试_软件工程及其他专业

Recommend
lcy

代码: #include<stdio.h> int gcd(int a,int b) { return a%b==0 ? b : gcd(b,a%b); } int main() { int n,a,b,c,temp,i; scanf("%d",&n); while(n--){ scanf("%d%d",&a,&b); temp=a/b; for(i=2;i<temp;i++){ if(gcd(temp,i)==1){ break; } }
83

c=b*i; printf("%d\n",c); } return 0; }

2519
Problem Description

新生晚会

开学了,杭电又迎来了好多新生。ACMer 想为新生准备一个节目。来报名要表演节目的人 很多,多达 N 个,但是只需要从这 N 个人中选 M 个就够了,一共有多少种选择方法?

Input
数据的第一行包括一个正整数 T,接下来有 T 组数据,每组数据占一行。 每组数据包含两个整数 N(来报名的人数,1<=N<=30) ,M(节目需要的人数0<=M<=30)

Output
每组数据输出一个整数,每个输出占一行

Sample Input
5 3 2 5 3 4 4 3 6 8 0

Sample Output
3 10 1 0 1

Source
ECJTU 2008 Autumn Contest

Recommend
gaojie

代码: #include<stdio.h> #include<math.h> int main() { int T, n, m, i; double num; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); num=1; for (i=1;i<=m;i++) num*=(1.0*(n-i+1)/i); printf("%.f\n",floor(num+0.5)); } return 0; }
84

方法二:
这里用到的数学公式为: c n = c n ?1 + c n ?1 (注意用一维数组来计算此式的技巧)
m m m

代码:
#include<stdio.h> #include<string.h> #define MAX 1000 int arr[MAX]; long solve(int n,int m) { int i,j; arr[0]=1; for(i=1;i<=n;i++) { for(j=i;j>-1;j--) { if(j==0||i==j) arr[j]=1; else arr[j]+=arr[j-1]; } } return arr[m]; } int main() { int num; int n,m; scanf("%d",&num); memset(arr,0,MAX*sizeof(int)); while(num--) { scanf("%d%d",&n,&m); printf("%ld\n",solve(n,m)); } return 0; }

2520
Problem Description

我是菜鸟,我怕谁

lin2144是一只小菜鸟,都是笨鸟先飞,lin2144想来个菜鸟先飞,他从0点出发 一开始的飞行速度为1m/s,每过一个单位时间 lin2144的飞行速度比上一个单位时间的飞行
85

速度快2m/s,问 n (0 < n < 10^5)个单位时间之后 lin2144飞了多远?

Input
输入一个 T 表示为有几组数据 每组数据输入一个 n,表示 lin2144飞行的时间.

Output
输出 lin2144飞行了多远,因为数字很大,所以对10000取模.

Sample Input
2 1 2

Sample Output
1 4

Source
HDU 2008-10 Programming Contest

Recommend
gaojie

代码: #include<stdio.h> int main() { int t; __int64 n,k; scanf("%d",&t); while(t--) { scanf("%I64d",&n); k=n*n; if(k>10000) printf("%I64d\n",k%10000); else printf("%I64d\n",k); } return 0; }

2521
Problem Description

反素数

反素数就是满足对于任意 i(0<i<x),都有 g(i)<g(x),(g(x)是 x 的因子个数),则 x 为一个反素数。 现在给你一个整数区间[a,b],请你求出该区间的 x 使 g(x)最大。

Input
第一行输入 n,接下来 n 行测试数据 输入包括 a,b, 1<=a<=b<=5000,表示闭区间[a,b].

86

Output
输出为一个整数,为该区间因子最多的数.如果满足条件有多个,则输出其中最小的数.

Sample Input
3 2 3 1 10 47 359

Sample Output
2 6 240 Hint 2的因子为:1 2 10的因子为:1 2 5 10

Source
HDU 2008-10 Programming Contest

Recommend
gaojie

代码: #include"stdio.h" int c[5001]; int main() { int i,n,j,a,b,t,max; for(i=2;i<5001;i++) c[i]=2; c[1]=1; for(i=2;i<=2500;i++) { for(j=i+i;j<=5000;j+=i) { c[j]++; } } scanf("%d",&n); for(i=0;i<n;i++) { max=0; scanf("%d%d",&a,&b); for(j=a;j<=b;j++) if(c[j]>max) { max=c[j];t=j; } printf("%d\n",t); }
87

return 0; }

2522
Problem Description

A simple problem

Zty 很痴迷数学问题.。一天,yifenfei 出了个数学题想难倒他,让他回答1 / n。但 Zty 却回答 不了^_^. 请大家编程帮助他.

Input
第一行整数 T,表示测试组数。后面 T 行,每行一个整数 n (1<=|n|<=10^5).

Output
输出1/n. (是循环小数的,只输出第一个循环节).

Sample Input
4 2 3 7 168

Sample Output
0.5 0.3 0.142857 0.005952380

Author
yifenfei

Source
HDU 2008-10 Programming Contest

Recommend
gaojie

代码: #include<stdio.h> #include<string.h> char b[500001]={0}; int main() { int t,i,d,n,s; scanf("%d",&t); while(t--) { memset(b,0,sizeof(b)); scanf("%d",&n); if(n<0) { printf("-"); n=-n; } if(n==1) {
88

printf("%d\n",n); continue; } else printf("0."); d=1;b[0]=1; for(i=1;;i++) { b[d]++; s=d*10/n; if(b[d]==2) break; printf("%d",s); d=d*10-s*n; } printf("\n"); } }

2523
Problem Description

SORT AGAIN

给你 N 个整数,x1,x2...xn,任取两个整数组合得到|xi-xj|,(0<i,j<=N,i!=j)。 现在请你计算第 K 大的组合数是哪个(一个组合数为第 K 大是指有 K-1个不同的组合数小 于它) 。

Input
输入数据首先包含一个正整数 C,表示包含 C 组测试用例. 每组测试数据的第一行包含两个整数 N,K。(1<N<=1000,0<K<=2000) 接下去一行包含 N 个整数,代表 x1,x2..xn。(0<=xi<=2000)

Output
对于每组测试数据,请输出第 K 大的组合数,每个输出实例占一行。

Sample Input
3 3 2 4 0 7 4 2 1 2 3 4 2 1 2 9

Sample Output
4 2 7

Source
HDU 2008-10 Programming Contest

Recommend
gaojie

代码: #include<iostream> #include<math.h>
89

using namespace std; int main() { int n,m,t,a[1001],b[2002],w,i,j; scanf("%d",&n); while(n--) { scanf("%d%d",&m,&t); memset(b,-1,sizeof(b)); w=0; for(i=0;i<m;i++) scanf("%d",&a[i]); for(i=m-1;i>=0;i--) for(j=0;j<i;j++) b[abs(a[i]-a[j])]=abs(a[i]-a[j]); for(i=0;i<2002;i++) { if(b[i]!=-1) { w++; if(w==t) { printf("%d\n",b[i]); break; } } } } return 0; }

2524
Problem Description

矩形 A + B

给你一个高为 n ,宽为 m 列的网格,计算出这个网格中有多少个矩形,下图为高为2,宽为 4的网格.

90

Input
第一行输入一个 t, 表示有 t 组数据, 然后每行输入 n,m,分别表示网格的高和宽 ( n < 100 , m < 100).

Output
每行输出网格中有多少个矩形.

Sample Input
2 1 2 2 4

Sample Output
3 30

Source
HDU 2008-10 Programming Contest

Recommend
gaojie

代码: #include<stdio.h> int main() { int t, n, m; scanf("%d", &t); while (t--) { scanf("%d%d",&n,&m); printf("%d\n",n*(n+1)/2*m*(m+1)/2); } return 0; }

2535
Problem Description

Vote

美国大选是按各州的投票结果来确定最终的结果的, 如果得到超过一半的州的支持就可以当 选, 而每个州的投票结果又是由该州选民投票产生的, 如果某个州超过一半的选民支持希拉 里,则她将赢得该州的支持。现在给出每个州的选民人数,请问希拉里至少需要赢得多少选
91

民的支持才能当选?

Input
多组输入数据 每组数据的第一行包括一个整数 N(1<=N<=101),表示美国的州数,N=0表示输入结束 接下来一行包括 N 个正整数,分别表示每个州的选民数,每个州的选民数不超过100

Output
对于每组数据输出一行,表示希拉里至少需要赢得支持的选民数

Sample Input
3 5 7 5 0

Sample Output
6

Source
The 6th UESTC Programming Contest

Recommend
lcy

代码: #include <stdio.h> int main() { int n, t, c,f[102], i, j, k; while(scanf("%d",&n) != EOF && n != 0) { for(i = 0; i < n; i ++) { scanf("%d",&f[i]); } for(i = 0; i < n; i ++) {

92

for(j = 0; j < n - i - 1; j ++) { if(f[j] > f[j + 1]) { t = f[j]; f[j] = f[j + 1]; f[j + 1] = t; } } } c = 0; if(n % 2 != 0) k = (n + 1) / 2; else k = n / 2 + 1; for(i = 0; i < k; i ++) { if(f[i] % 2 != 0) c += (f[i] + 1) / 2; else c += f[i] / 2 + 1; } printf("%d\n",c); } return 0; }

2537
Problem Description

8 球胜负

8球是一种台球竞赛的规则。台面上有7个红球、7个黄球以及一个黑球,当然还有一个白球。 对于本题,我们使用如下的简化规则:红、黄两名选手轮流用白球击打各自颜色的球,如果 将该颜色的7个球全部打进,则这名选手可以打黑球,如果打进则算他胜。如果在打进自己 颜色的所有球之前就把黑球打进,则算输。如果选手不慎打进了对手的球,入球依然有效。 现在给出打进的球 (白球除外) 的顺序, 以及黑球由哪方打进, 你的任务是判定哪方是胜者。 假设不会有一杆同时打进一颗黑球和其他彩球。

93

Input
输入包含多组数据。每组数据第一行是一个整数 N(1<=N<=15),表示打进的球的个数,N=0 表示结束。随后有一行,包含 N 个字符,依序表示打进的是何种球。如果是’B’,表示是红 方打进的黑球, 如果是’L’, 表示是黄方打进的黑球。 如果是’Y’则表示是黄球, ’R’表示红球。 字符间没有空格。 所有输入都满足如下条件: 最后一颗球打进时这局比赛正好结束, 而且打进的红球和黑球都 不超过7个。

Output
对每组数据,输出一行。如果红方胜,输出’Red’;黄方胜,输出’Yellow’。

Sample Input
5 RYRRB 9 RRRRYRRRB 0

Sample Output
Yellow Red

Source
UESTC 6th Programming Contest Online

Recommend
lcy

代码:

94

#include <iostream> using namespace std; char dig[20]; int main() { int n; while(cin>>n&&n) { int sum1=0,sum2=0; for(int i=0;i<n;i++) { cin>>dig[i]; if(dig[i]=='R') if(dig[i]=='Y') }

sum1++; sum2++;

if(sum1<7&&sum2<7&&dig[n-1]=='L'||sum1==7&&sum2<7||sum1==7&&sum2==7&&dig[n-1] =='B') cout<<"Red"<<endl; else cout<<"Yellow"<<endl; } return 0; }

2539
Problem Description

点球大战

在足球比赛中,有不少赛事,例如世界杯淘汰赛和欧洲冠军联赛淘汰赛中,当比赛双方经过 正规比赛和加时赛之后仍然不分胜负时,需要进行点球大战来决定谁能够获得最终的胜利。 点球大战的规则非常简单,两方轮流派出球员罚点球,每方各罚5个。当5轮点球结束以后如 果仍然不分胜负,则进入一轮定胜负的阶段。两方各派一名球员罚点球,直到有一方罚进而 另一方没有进为止。 在北美职业冰球联赛中,也有点球大战。与足球的规则不同的是,它只先罚3轮点球,随后 就进入一轮定胜负的阶段,而其他的规则完全一样。 在本题中,输入将给出每次点球是否罚进,而你的任务则是输出一个―比分板‖。

95

Input
输入包含多组数据。每组数据的第一行包含一个整数 N(1<=N<=18),表示双方总共罚了多 少个点球,N=0表示输入结束。随后有 N 行,每行是一个如下形式的字符串: XXXX good:表示这个点球罚进 或者 XXXX no good:表示这个点球没有罚进 其中 XXXX 表示球员名字(全部由字母和空格组成,保证不会出现歧义) 每一行保证不超过100个字符。 XXXX 和 good 以及 XXXX 和 no、no 和 good 之间保证有且只有1个空格。 good、no good 都是小写。本题是大小写相关的。 数据不保证点球大战一定结束,也不保证在结束以后立即结束这组数据(即:不用判断点球 大战是否结束,只用把罚进的点球往比分上加即可) 。

Output
对每组数据,输出一个比分板。一个点球如果罚进,则在对应的地方标上’O’,如果没有进 则标上’X’。先罚球的队伍的信息在上面,后罚的在下面。最右边标上两队的比分。具体格 式参考样例输出。注意如果一轮点球只罚了一个,则后面那个点球对应的地方写上’-’。

Sample Input
6 Riise good Ballack good Gerrard no good Lampard no good Fernando Torres good Malouda good 9 Christiano Ronaldo no good Messi no good Giggs good Abidal no good Carrick good Ronaldinho good Rooney good Henry no good Tevez good 0

Sample Output
1 2 3 Score O X O 2 O X O 2 1 2 3 4 5 Score X O O O O 4 X X O X - 1 提示: 空格数要和样例输出一样,否则很可能会被判为―格式错误‖(Presentation Error)。

Source
UESTC 6th Programming Contest Online

Recommend
lcy

96

代码: #include<stdio.h> #include<string.h> int main() { int T,a[9],b[9],t,i,j,k,len,sum1,sum2; char s[100]; while(scanf("%d",&T)!=EOF&&T) { getchar(); j=k=0; for(t=0;t<T;t++) { gets(s); len=strlen(s); for(i=len-1;i>=0;i--) if(s[i]==' ') { if(t%2==0) { if(s[i-1]=='o'&&s[i-2]=='n'&&s[i-3]==' ') a[j]=0; else a[j]=1; j++; } else { if(s[i-1]=='o'&&s[i-2]=='n'&&s[i-3]==' ') b[k]=0; else b[k]=1; k++; } break; } } sum1=sum2=0; for(i=1;i<=j;i++) printf("%d ",i); printf("Score\n"); for(i=0;i<j;i++)

97

{ if(a[i]==0) printf("X "); else printf("O "); sum1+=a[i]; } printf("%d\n",sum1); for(i=0;i<k;i++) { if(b[i]==0) printf("X "); else printf("O "); sum2+=b[i]; } if(k<j) printf("- "); printf("%d\n",sum2); } }

2547
Problem Description

无剑无我

北宋末年,奸臣当道,宦官掌权,外侮日亟,辽军再犯。时下战火连连,烽烟四起,哀鸿遍 野,民不聊生,又有众多能人异士群起而反,天下志士云集响应,景粮影从。 值此危急存亡之秋,在一个与世隔绝的地方---MCA 山上一位江湖人称<英雄哪里出来>的人 正在为抗击辽贼研究剑法,终于于一雷电交加之夜精确计算出了荡剑回锋的剑气伤害公式。 定义 f(x, y, m, n) = sqrt(x*x + y*y + m*m + n*n - 2*m*x - 2*n*y); hint : sqrt 表示开方,即 sqrt(4) = 2; sqrt(16) = 4; (其中 x,y 为位置变量,m,n 为属性常量) 剑气伤害 = f(x, y, a, b) + f(x, y, c, d); 剑气威力巨大无比,实难控制,现在他想知道剑气伤害的最小伤害值。

Input
首先输入一个 t,表示有 t 组数据,跟着 t 行: 输入四个实数 a,b,c,d 均小于等于100

Output
输出剑气的最小伤害值 M,保留小数点后一位 (可以使用.1lf)

Sample Input
2 0 0 3 4 4 0 0 3

98

Sample Output
5.0 5.0

Author
英雄哪里出来

Source
2008―缤纷下沙校园文化活动月‖之大学生程序设计竞赛暨新生专场

Recommend
lcy

代码: #include<stdio.h> #include<math.h> int main() { int t; double a,b,c,d,ans; scanf("%d",&t); while(t--) { scanf("%lf%lf%lf%lf",&a,&b,&c,&d); ans = sqrt(((a-c)*(a-c)+(b-d)*(b-d))*1.0); printf("%.1lf\n",ans); } }

2548
Problem Description

两军交锋

话说辽军与 MCA 相峙多年,终于在一个秋日的早晨爆发了一次大规模的冲突.情况是这样子 的,当天上午,由耶律-Pacision 领军的辽军忽然带领数万人马浩浩荡荡向 MCA 山杀来,而这时 候驻扎在 MCA 防守前线的是久经沙场的老将纪哥.纪哥得知这个消息,立刻召集手下精英,前 往阻击辽军.现已知辽军前进速度 U 米/秒 ,纪哥 速度 V 米 /秒 ,两军一开始相距 L 米,战 地记者从两军刚开始进军就立刻开始以 W 米/秒的速度马不停蹄地往返于两军之间作第一 时间的报道,即一到达一方,立刻返回前往另一方.问,当两军交锋之时,战地记者总共走的路程.

Input
首先输入一个 t,表示有 t 组数据,跟着 t 行: 每行有四个实数 u ,v , w , l 分别表示辽军速度,纪哥速度,记者速度,以及起始的距离.

Output
输出一行实数表示总的路程.精确到小数点后3位.

Sample Input
1 10 20 30 100

Sample Output
100.000
99

Author
Teddy

Source
2008―缤纷下沙校园文化活动月‖之大学生程序设计竞赛暨新生专场

Recommend
lcy

代码: #include<stdio.h> int main() { int t; double u,v,w,l,ans; scanf("%d",&t); while(t--) { scanf("%lf%lf%lf%lf",&u,&v,&w,&l); ans = w*l/(u+v); printf("%.3lf\n",ans); } }

2549
Problem Description

壮志难酬

话说 MCA 山上各路豪杰均出山抗敌,去年曾在江湖威名显赫的,江湖人称<万军中取上将 首级舍我其谁>的甘露也不甘示弱,―天将降大任于斯人也,必先劳其筋骨,饿其体肤,空乏 其身‖他说。可惜,由于去年取上将首级时不慎右手右关节第七次骨折,养伤达一年之久, 空有一腔抱负却壮志难酬,如今天下危亡,习武之人又怎能袖手旁观,于是他决定出山协助 威士忌共抗辽贼,这时他的对头枫冰叶子出现,两人都是水属性,但由于十年前的一场恩怨 (这是后话)势成水火。 枫冰叶子要求甘露回答一个问题,否则不让他离开,可惜甘露绞尽脑汁未果,希望你来帮他 解决,助他完成大业。 问题是这样的:给你一个小数 x,让你算出小数点后第 n 位是什么,(1 <= n <= 6)

Input
首先输入一个 t,表示有 t 组数据,跟着 t 行: 每行输入一个小数 (输入数据保证一定是 a.b 的形式,为了简单化问题, 没有循环小数的情况) 然后跟一个 n,表示小数点后第几位

Output
输出一个数表示小数点后第 n 位的数

100

Sample Input
3 1.234 1 2.345 2 3.456 3

Sample Output
2 4 6

Author
英雄哪里出来

Source
2008―缤纷下沙校园文化活动月‖之大学生程序设计竞赛暨新生专场

Recommend
lcy

代码: #include<stdio.h> #include<string.h> char x[99]; int main() { int i,n,t,len,ans; scanf("%d",&t); while(t--&&scanf("%s %d",x,&n)) { len = strlen(x); for(i=0; i<len; i++) if(x[i]=='.') break; if(len-i-1<n) ans = 0; else ans = x[i+n]-'0'; printf("%d\n",ans); } }

2550
Problem Description

百步穿杨

时维九月,序属三秋,辽军大举进攻 MCA 山,战场上两军正交锋.辽军统帅是名噪一时的耶律 -James,而 MCA 方则是派出了传统武将中草药123.双方经过协商,约定在十一月八日正午十 分进行射箭对攻战.中草药123早早就开始准备,但是他是武将而不是铁匠,造弓箭的活就交给 聪明能干的你了,现在告诉你每种弓箭规格,即箭身的长度,以及每种规格弓箭所需要的数目, 要求你把需要的弓箭都输出. 弓箭的基本样子为 ">+---+>",其中"+---+"为箭身,数据保证箭身长度 > 2

Input
首先输入一个 t,表示有 t 组数据,跟着 t 行: 每行一个 N (N < 50 ),接下去有 N 行,第 i 行两个整数 Ai , Bi,分别代表需要箭身长度为 Ai 的 弓箭 Bi 枝. (Ai < 30 , Bi < 10 )
101

输入数据保证每一个 Ai 都是不同的.

Output
按照箭身的长度从小到大的顺序依次输出所有需要的弓箭,"每一种"弓箭后输出一个空行.

Sample Input
1 4 3 4 4 5 5 6 6 7

Sample Output
>+-+> >+-+> >+-+> >+-+> >+--+> >+--+> >+--+> >+--+> >+--+> >+---+ > >+---+> >+---+> >+---+> >+---+> >+---+> >+----+> >+----+> >+---+> >+----+> >+----+> >+----+> >+----+>

Author
Teddy

Source
2008―缤纷下沙校园文化活动月‖之大学生程序设计竞赛暨新生专场

Recommend
lcy

代码: #include<iostream> using namespace std; char a[40]=">+"; int b[2][51]; int main() { int i,j,n,t; scanf("%d",&t); while(t--&&scanf("%d",&n)) { for(i=0; i<n; i++) scanf("%d%d",&b[0][i],&b[1][i]); for(i=0; i<n-1; i++) for(j=i+1; j<n; j++) if(b[0][i]>b[0][j]) { swap(b[0][i],b[0][j]); swap(b[1][i],b[1][j]); } for(i=0; i<n; i++) { for(j=2; j<b[0][i]; j++) a[j] = '-'; a[j] = '+'; a[j+1] = '>'; a[j+2] = '\0';

102

for(j=0; j<b[1][i]; j++) printf("%s\n",a); puts(""); } } }

2551
Problem Description

竹青遍野

"临流揽镜曳双魂 落红逐青裙 依稀往梦幻如真 泪湿千里云" 在 MCA 山上,除了住着众多武林豪侠之外,还生活着一个低调的世外高人,他本名逐青裙,因为 经常被人叫做"竹蜻蜓",终改名逐青,常年隐居于山中,不再见外人.根据山上附近居民所流传 的说法,逐青有一个很奇怪的癖好,从他住进来那天开始,他就开始在他的院子周围种竹子,第1 个月种1根竹子,第2个月种8根竹子,第3个月种27根竹子...第 N 个月就种(N^3)根竹子.他说当 他种下第 X 根竹子那一刻,就是他重出江湖之时!告诉你 X 的值,你能算出逐青的复出会是在 第几个月吗?

Input
首先输入一个 t,表示有 t 组数据,跟着 t 行.每行是一个整数 X,X < 1000000000

Output
输出一个整数 n,表示在第 n 个月复出

Sample Input
3 1 2 10

Sample Output
1 2 3

Author
Teddy

Source
2008―缤纷下沙校园文化活动月‖之大学生程序设计竞赛暨新生专场

Recommend
lcy

代码:
#include<stdio.h> int num[1001]={0}; int main() { int n,i,m; for(i=1;i<1001;i++) //这里先把每个月逐青种的竹子总数计算出来

103

num[i]=num[i-1]+i*i*i; scanf("%d",&n); while(n--) { scanf("%d",&m); for(i=0;;i++)

//以后的数据处理就可以直接找这的计算结果

if(m>num[i]&&m<=num[i+1]) break; printf("%d\n",i+1); } }

//i 遍历找到符合条件的数

2552
Problem Description

三足鼎立

MCA 山中人才辈出,洞悉外界战火纷纷,山中各路豪杰决定出山拯救百姓于水火,曾以题 数扫全场的威士忌,曾经高数九十九的天外来客,曾以一剑铸十年的亦纷菲,歃血为盟,盘 踞全国各个要塞(简称全国赛)遇敌杀敌,遇佛杀佛,终于击退辽军,暂时平定外患,三人 位置也处于稳态。 可惜辽誓不甘心,辽国征南大将军<耶律 javac++>欲找出三人所在逐个击破,现在他发现威 士忌的位置 s,天外来客的位置 u,不过很难探查到亦纷菲 v 所在何处,只能知道三人满足关 系: arctan(1/s) = arctan(1/u)+arctan(1/v)

注:

(其中0 <= x <= 1)

定义 f(s, u, v) = v*u-s*u-s*v 的值 为<三足鼎立> <耶律 javac++>想计算<三足鼎立>的值

Input
首先输入一个 t,表示有 t 组数据,跟着 t 行: 输入 s, u (s <= 12^3, u <= 2^20 且 s, u, v > 0) 且 s,u,v 均为实数

Output
输出 v*u-s*u-s*v 的值,为了简单起见,如果是小数,直接取整 比如:答案是1.7 则输出 1
104

Sample Input
1 1 2

Sample Output
1

Author
英雄哪里出来

Source
2008―缤纷下沙校园文化活动月‖之大学生程序设计竞赛暨新生专场

Recommend
lcy

代码: #include<stdio.h> #include<math.h> int main() { int t; double s,u,v,ans; scanf("%d",&t); while(t--&&scanf("%lf%lf",&s,&u)) { v = atan(1.0/s)-atan(1.0/u); v = 1.0/tan(v); ans = v*u-s*u-s*v; printf("%.0lf\n",ans); } }

2553
Problem Description

N 皇后问题

在 N*N 的方格棋盘放置了 N 个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同 一排,同一列,也不允许处在与棋盘边框成45角的斜线上。 你的任务是,对于给定的 N,求出有多少种合法的放置方法。

Input
共有若干行,每行一个正整数 N≤10,表示棋盘和皇后的数量;如果 N=0,表示结束。

Output
共有若干行,每行一个正整数,表示对应输入行的皇后的不同放置数量。

Sample Input
1 8 5 0

Sample Output
1 92 10
105

Author
cgf

Source
2008 HZNU Programming Contest

Recommend
lcy

代码: #include<stdio.h> int a[11]={0,1,0,0,2,10,4,40,92,352,724}; int main() { int n; while(scanf("%d",&n)&&n) printf("%d\n",a[n]); }

2554
Problem Description

N 对数的排列问题

有 N 对双胞胎,他们的年龄分别是1,2,3,……,N 岁,他们手拉手排成一队到野外去玩, 要经过一根独木桥,为了安全起见,要求年龄大的和年龄小的排在一起,好让年龄大的保护 年龄小的,然后从头到尾,每个人报告自己的年龄,就得到了一个年龄的序列。比如有4对 双胞胎,他们报出来的年龄序列是:41312432。突然,他们中间最聪明的小明发现了一个有 趣的现象,原来,这个年龄序列有一个规律,两个1中间有1个数,两个2中间有2个数,两个 3中间有3个数,两个4中间有4个数。但是,如果是2对双胞胎,那么无论他们怎么排年龄序 列,都不能满足这个规律。 你的任务是,对于给定的 N 对双胞胎,是否有一个年龄序列,满足这一规律,如果是,就 输出 Y,如果没有,输出 N。

Input
共有若干行,每行一个正整数 N<100000,表示双胞胎的数量;如果 N=0,表示结束。

Output
共有若干行,每行一个正整数,表示对应输入行是否有一个年龄序列,满足这一规律,如果 是,就输出 Y,如果没有,输出 N

Sample Input
4 2 1309 0

Sample Output
Y N N

Author
cgf

Source
2008 HZNU Programming Contest

106

Recommend
lcy

代码: #include<stdio.h> int main() { int n; while(scanf("%d",&n),n) puts((n+1)/2%2?"N":"Y"); }

2555

人人都能参加第 30 届校田径运 动会了

Problem Description
杭州师范大学第29届田径运动会圆满的闭幕了, 本届运动会是我校规模最大, 参赛人数最多 的一次运动会。在两天半时间里,由学生、教工组成的61支代表队共2664名运动员参加了比 赛。比赛期间,运动健儿赛出了风格、赛出了水平,共有9人次打破6项校纪录。 我们寝室的4名同学是我班最卖力的啦啦队员,每天都在看台上为班级里的运动员们加油助 威,为我班获得精神文明奖立下了汗马功劳。可是遗憾的是,与我校的其他近2万名同学一 样,我们自己不能上场表演 :( 于是,我们4名同学为下一届校运会发明了一种人人都能参加的比赛项目: 在地面上有 N 个大小不等的长方形陷阱,每个陷阱的周长各不相同,每个参赛者都有一个 沙包,闭上眼睛把它扔向地面,如果沙包掉到了某个陷阱里,那么这个参赛者根据这个陷阱 的周长长度(如50米) ,绕跑道跑陷阱的周长长度(如50米) ,如果沙包没有掉到任何一个陷 阱里,那么恭喜你,你跑0米。 有 m<20000个同学参加了比赛,为了给跑步跑得最多的三位同学(冠军、亚军、季军)颁发安 慰奖,必须给这 m 个同学的跑的长度按从多到少排序。 如下图一样的坐标系与长方形,这些长方形(陷阱)的四条边都与 X 轴或 Y 轴平行,它们 之间互不相交, 它们的左上角顶点的坐标与右下角顶点的坐标已知, 给定一个你扔出去的沙 包(看作是一个点)的坐标,可以得到你要跑的距离。 (注意, 这里的坐标值都不超过10000)

107

Input
第一行是两个正整数 m<20000,n<100,它表示有 m 个同学参加了扔沙包比赛,有 n 个陷 阱。 接下去 m 行是 m 个同学扔出去的沙包的坐标,每一行都是两个正整数。 接下去的 n 行是陷阱的坐标,每行有4个正整数,它们从左到右分别是:陷阱左下角顶点的 横坐标的值、陷阱左下角顶点的纵坐标的值,陷阱右上角顶点的横坐标的值、陷阱右上角顶 点的纵坐标的值。

Output
m 个同学按跑的距离的多少,从多到少输出,一个数字一行。

Sample Input
5 3 15 27 32 93 22 3 98 4 65 23 22 65 100 76 2 5 7 9 54 6 94 24

Sample Output
116 0 0 0 0

Author
cgf

Source
2008 HZNU Programming Contest

Recommend
lcy

108

代码: #include<cstdio> #include<algorithm> using namespace std; typedef struct { int x; int y; int len; }PLAYER; typedef struct { int x1; int y1; int x2; int y2; int len; }RECTANGLE; void meters(PLAYER *p[],int m,RECTANGLE rec[],int n); void mysort(PLAYER *p[],int m); int main() { PLAYER player[20000],*p[20000]; RECTANGLE rec[100]; int m,mi,n,ni; while(scanf("%d%d",&m,&n)!=EOF){ for(mi=0;mi<m;mi++) { p[mi]=&player[mi]; scanf("%d%d",&p[mi]->x,&p[mi]->y); p[mi]->len=0; } for(ni=0;ni<n;ni++) { scanf("%d%d%d%d",&rec[ni].x1,&rec[ni].y1,&rec[ni].x2,&rec[ni].y2); rec[ni].len=2*(rec[ni].y2-rec[ni].y1+rec[ni].x2-rec[ni].x1); } meters(p,m,rec,n); mysort(p,m); for(mi=0;mi<m;mi++) printf("%d\n",p[mi]->len); }

109

return 0; } void meters(PLAYER *p[],int m,RECTANGLE rec[],int n) { int ni,mi; for(mi=0;mi<m;mi++) for(ni=0;ni<n;ni++) if(p[mi]->x>=rec[ni].x1&&p[mi]->x<=rec[ni].x2&&p[mi]->y>=rec[ni].y1&&p[mi]->y<=rec[ni]. y2) { p[mi]->len+=rec[ni].len; break; } } void mysort(PLAYER *p[],int m) { int i,j,k; PLAYER *t; for(i=0;i<m-1;i++) { k=i; for(j=i+1;j<m;j++) if(p[k]->len<p[j]->len) k=j; t=p[i];p[i]=p[k];p[k]=t; } }

2560
Problem Description

Buildings

We divide the HZNU Campus into N*M grids. As you can see from the picture below, the green grids represent the buidings. Given the size of the HZNU Campus, and the color of each grid, you should count how many green grids in the N*M grids.

110

Input
Standard input will contain multiple test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow. The first line of each test case contains two integers n and m(1<=n,m<=100), the size of the campus. Then follow n lines, each line containing m integers. The j-th integer in the i-th line is the color of that grid, 0 stands for white color, while 1 stands for green.

Output
Results should be directed to standard output. For each case, output an integers T, the total green grids in the N*M size campus.

Sample Input
2 2 2 1 1 0 0 3 3 1 0 1 0 0 1 1 1 0

Sample Output
2 5

Source
2008 HZNU Programming Contest

Recommend
lcy

代码: #include<stdio.h> int main()

111

{ int n,a,b,m,t,sum=0; scanf("%d",&n); while(n--) { scanf("%d%d",&a,&b); t=a*b; sum=0; while(t--) { scanf("%d",&m); if(m==1) sum++; } printf("%d\n",sum); } }

2561
Problem Description

第二小整数

求 n 个整数中倒数第二小的数。 每一个整数都独立看成一个数,比如,有三个数分别是1,1,3,那么,第二小的数就是1。

Input
输入包含多组测试数据。 输入的第一行是一个整数 C,表示有 C 测试数据; 每组测试数据的第一行是一个整数 n,表示本组测试数据有 n 个整数(2<=n<=10) ,接着一 行是 n 个整数 (每个数均小于100);

Output
请为每组测试数据输出第二小的整数,每组输出占一行。

Sample Input
2 2 1 2 3 1 1 3

Sample Output
2 1

Author
yifenfei

Source
绍兴托普信息技术职业技术学院——第二届电脑文化节程序设计竞赛

Recommend
yifenfei

代码: #include<stdio.h> main()
112

{ int T,i,n,a,f,s,m; for(scanf("%d",&T);T>0;T--) { scanf("%d",&n); f=100; s=100; for(i=0;i<n;i++) { scanf("%d",&a); if(a<=s) s=a; if(s<=f) {m=s;s=f;f=m;} } printf("%d\n",s); } }

2562
Problem Description Input

奇偶位互换

给定一个长度为偶数位的0,1字符串,请编程实现串的奇偶位互换。 输入包含多组测试数据; 输入的第一行是一个整数 C,表示有 C 测试数据; 接下来是 C 组测试数据,每组数据输入均为0,1字符串,保证串长为偶数位(串长<=50)。

Output
请为每组测试数据输出奇偶位互换后的结果; 每组输出占一行。

Sample Input
2 0110 1100

Sample Output
1001 1100

Author
yifenfei

Source
绍兴托普信息技术职业技术学院——第二届电脑文化节程序设计竞赛

Recommend
yifenfei

代码: #include<string.h> #include<stdio.h> int main()
113

{ int n,i; char s[100],temp; scanf("%d",&n); while(n--) { scanf("%s",s); for(i=0;i<strlen(s);i+=2) { temp=s[i]; s[i]=s[i+1]; s[i+1]=temp; } for(i=0;i<strlen(s);i++) printf("%c",s[i]); printf("\n"); } return 0; }

2563
Problem Description

统计问题

在一无限大的二维平面中,我们做如下假设: 1、 每次只能移动一格; 2、 不能向后走(假设你的目的地是―向上‖,那么你可以向左走,可以向右走,也可以向上 走,但是不可以向下走) ; 3、 走过的格子立即塌陷无法再走第二次; 求走 n 步不同的方案数(2种走法只要有一步不一样,即被认为是不同的方案) 。

Input
首先给出一个正整数 C,表示有 C 组测试数据 接下来的 C 行,每行包含一个整数 n (n<=20),表示要走 n 步。

Output
请编程输出走 n 步的不同方案总数; 每组的输出占一行。

Sample Input
2 1 2

Sample Output
3 7

Author
yifenfei

Source
绍兴托普信息技术职业技术学院——第二届电脑文化节程序设计竞赛
114

Recommend
yifenfei

代码: #include<iostream> using namespace std; int main() { int n,m,i; int a[40]={0,1},b[40]={0,2},c[40]={1,3}; for(i=2;i<40;i++) { a[i]=c[i-1]; b[i]=a[i-1]*2+b[i-1]; c[i]=a[i]+b[i]; } cin>>n; while(n--) { cin>>m; printf("%d\n",c[m]); } return 0; }

2564
Problem Description

词组缩写

定义:一个词组中每个单词的首字母的大写组合称为该词组的缩写。 比如,C 语言里常用的 EOF 就是 end of file 的缩写。

Input
输入的第一行是一个整数 T,表示一共有 T 组测试数据; 接下来有 T 行,每组测试数据占一行,每行有一个词组,每个词组由一个或多个单词组成; 每组的单词个数不超过10个,每个单词有一个或多个大写或小写字母组成; 单词长度不超过10,由一个或多个空格分隔这些单词。

Output
请为每组测试数据输出规定的缩写,每组输出占一行。

Sample Input
1 end of file

Sample Output
EOF

Author
lemon
115

Source
绍兴托普信息技术职业技术学院——第二届电脑文化节程序设计竞赛

Recommend
yifenfei

代码: #include"stdio.h" int main() { int t,i,n; char str[120],a[13]; scanf("%d",&n); getchar(); while(n--) { gets(str); if(str[0]!=' ') { a[0]=str[0]; t=1; for(i=0;str[i]!='\0';i++) { if(str[i]==' '&&str[i+1]!=' ') a[t++]=str[i+1]; if(a[t-1]>=97 && a[t-1]<=122) a[t-1]-=32; } a[t]='\0'; puts(a); } else { t=0; for(i=0;str[i]!='\0';i++) { if(str[i]==' '&&str[i+1]!=' ') a[t++]=str[i+1]; if(a[t-1]>=97 && a[t-1]<=122) a[t-1]-=32; } a[t]='\0'; puts(a); }

116

} return 0; }

2565
Problem Description
请你编程画一个放大的’X’。 如3*3的’X’应如下所示: XX X XX 5*5的’X’如下所示: X X XX X XX X X

放大的 X

Input
输入数据第一行是一个整数 T,表示有 T 组测试数据; 接下来有 T 行,每行有一个正奇数 n(3 <= n <= 79) ,表示放大的规格。

Output
对于每一个 n 打印一个规格为 n * n 放大的’X’;每组输出后面空一行。

Sample Input
2 3 5

Sample Output
X X X X X X X X X X X X X X

Author
lemon

Source
绍兴托普信息技术职业技术学院——第二届电脑文化节程序设计竞赛

Recommend
yifenfei

代码: #include <cstdlib> #include <iostream> using namespace std; int main(int argc, char *argv[]) { int a,n,t;
117

int i,j,k,i1; cin>>t; for(i1=0;i1<t;i1++) { cin>>n; a=n/2+1; for(i=1;i<=a;i++) { for(k=1;k<=(i-1);k++) cout<<" "; for(j=1;j<=(2*a+1-2*i);j++) { if(j==1 || j==2*a+1-2*i)cout<<"X"; else cout<<" "; } cout<<'\n'; } for(i=2;i<=a;i++) { for(k=1;k<=(a-i);k++) cout<<" "; for(j=1;j<=(2*i-1);j++) { if(j==1 || j==2*i-1)cout<<"X"; else cout<<" "; } cout<<endl; } cout<<endl; } return EXIT_SUCCESS; }

2566
Problem Description

统计硬币

假设一堆由1分、2分、5分组成的 n 个硬币总面值为 m 分,求一共有多少种可能的组合方式 (某种面值的硬币可以数量可以为0) 。

Input
输入数据第一行有一个正整数 T,表示有 T 组测试数据; 接下来的 T 行,每行有两个数 n,m,n 和 m 的含义同上。

Output
对于每组测试数据,请输出可能的组合方式数; 每组输出占一行。
118

Sample Input
2 3 5 4 8

Sample Output
1 2

Author
lemon

Source
绍兴托普信息技术职业技术学院——第二届电脑文化节程序设计竞赛

Recommend
yifenfei

代码: #include <stdio.h> void main() { int n,m,i,j,k,num,T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); num=0; for(i=0;i<=n;++i) { for(j=0;j<=n;j++) { for(k=0;k<=n;k++) { if(i+j*2+k*5==m&&i+j+k==n) {num++;} } } } printf("%d\n",num); } }

2567
Problem Description

寻梦

每个人的童年都可能梦想过自己成为一个英雄,尤其是喜欢武侠的男生,Yifenfei 也不 例外 童年的他常常梦想自己能成为一个绝世英雄, 手拿一把灿灿发亮的宝剑, 手挽一位长发 飘逸的秀丽气质 MM ^_^ ,散步于清幽的泉边小道,微风吹过,飘落两片枫叶。。。 。。。
119

正由于成天陶醉于这种脱世的意境之中, 导致此人老大不小依旧形单影只, 每天只能在 人潮中孤单上路。。。 。。。 现在就让我们为这个可怜的人创造一个机会,权当假设 yifenfei 现在已经捕获一位 MM 的芳心,但该 MM 被邪恶并且极其可恶的大魔头(AC 女之杀手 lemon)抓走。为了正义, 为了 MM,燃烧吧。。。 。。。 好了,现在就正式开始我们的行程,接下来将有6关等待着 yifenfei,让我们帮助他战胜 邪恶的 lemon 大魔王吧。 来到大魔王居住的千年古墓前,呈现在 yifenfei 眼前的是墓碑上神秘的字符,经过仔细 研究,发现原来这是开启古墓入口的方法。 墓碑上有2行字符串, 其中第一个串的长度为偶数, 现在要求把第2个串插入到第一个串 的正中央,如此便能开启墓碑进入墓中。

Input
输入数据首先给出一个整数 n,表示测试数据的组数。 然后是 n 组数据,每组数据2行,每行一个字符串,长度大于0,小于50,并且第一个串的长 度必为偶数。

Output
请为每组数据输出一个能开启古墓的字符串,每组输出占一行。

Sample Input
2 HDCM UA Aw CFlo

Sample Output
HDUACM ACFlow

Author
yifenfei

Source
120

ACM 程序设计期末考试081230

Recommend
yifenfei

代码: #include<stdio.h> #include<string.h> main() { int n,l1,l2,i,j; char a[100],b[50]; scanf("%d",&n); while(n--) { for(i=0;i<50;i++) {a[i]=0;b[i]=0;} j=0; scanf("%s %s",a,b); l1=strlen(a); l2=strlen(b); for(i=l1/2;i<l1;i++) a[i+l2]=a[i]; for(i=l1/2;i<l1/2+l2;i++) a[i]=b[j++]; puts(a); } }

2568
Problem Description

前进

轻松通过墓碑,进入古墓后,才发现里面别有洞天。 突然, Yifenfei 发现自己周围是黑压压的一群蝙蝠, 个个扇动翅膀正准备一起向他发起进攻! 形势十分危急! 好在此时的 yifenfei 已经不是以前那个经常被 lemon 抢走 MM 的菜鸟了! 面对众多蝙蝠的嗜 血狂攻,只见 yifenfei 使出轻灵的剑法,刷,刷,刷,瞬间搞定…… 现已知 yifenfei 使用了2招(剑招 A 和剑招 B) :剑招 A,一招能杀死一半的蝙蝠。但是如果 当前的蝙蝠数为奇数,那么就必须先出一招剑招 B 杀死其中任意一个,使蝙蝠数为偶数, 再出剑招 A。 现在请问:杀死 n 只蝙蝠需要使出多少招剑招 B?

121

Input
输入数据首先给出一个整数 C,表示测试组数。 然后是 C 组数据,每组包含一个正整数 n (n<2^31)。

Output
对应每组数据,请输出一个整数,表示 yifenfei 使用的剑招 B 的数目,每组输出占一行。

Sample Input
2 1 5

Sample Output
1 2

Author
yifenfei

Source
ACM 程序设计期末考试081230

Recommend
yifenfei

代码: #include<stdio.h> main() { int n,a,t; scanf("%d",&n); while(n--) { t=0; scanf("%d",&a); while(a&&a%2==0) a/=2;

122

while(a&&a%2) { t++; a-=1; while(a&&a%2==0) a/=2; } printf("%d\n",t); } }

2569
Problem Description

彼岸

突破蝙蝠的包围, yifenfei 来到一处悬崖面前, 悬崖彼岸就是前进的方向, 好在现在的 yifenfei 已经学过御剑术,可御剑轻松飞过悬崖。 现在的问题是:悬崖中间飞着很多红,黄,蓝三种颜色的珠子,假设我们把悬崖看成一条长 度为 n 的线段,线段上的每一单位长度空间都可能飞过红,黄,蓝三种珠子,而 yifenfei 必 定会在该空间上碰到一种颜色的珠子。如果在连续3段单位空间碰到的珠子颜色都不一样, 则 yifenfei 就会坠落。 比如经过长度为3的悬崖,碰到的珠子先后为 ―红黄蓝‖,或者 ―蓝红黄‖ 等类似情况就会坠 落,而如果是 ―红黄红‖ 或者 ―红黄黄‖等情况则可以安全到达。 现在请问:yifenfei 安然抵达彼岸的方法有多少种?

123

Input
输入数据首先给出一个整数 C,表示测试组数。 然后是 C 组数据,每组包含一个正整数 n (n<40)。

Output
对应每组输入数据,请输出一个整数,表示 yifenfei 安然抵达彼岸的方法数。 每组输出占一行。

Sample Input
2 2 3

Sample Output
9 21

Author
yifenfei

Source
ACM 程序设计期末考试081230

Recommend
yifenfei

代码: #include <cstdlib> #include <iostream> using namespace std; int result[40]; int main() { int C, n; result[1] = 3; result[2] = 9; for (int i=3; i<40; ++i) result[i] = 2*result[i-1] + result[i-2]; cin >> C; while (C--) { cin >> n; cout << result[n]<< endl; } }

2700
Problem Description

Parity

A bit string has odd parity if the number of 1's is odd. A bit string has even parity if the number of 1's is even.Zero is considered to be an even number, so a bit string with no 1's has even parity. Note that the number of
124

0's does not affect the parity of a bit string.

Input
The input consists of one or more strings, each on a line by itself, followed by a line containing only "#" that signals the end of the input. Each string contains 1–31 bits followed by either a lowercase letter 'e' or a lowercase letter 'o'.

Output
Each line of output must look just like the corresponding line of input, except that the letter at the end is replaced by the correct bit so that the entire bit string has even parity (if the letter was 'e') or odd parity (if the letter was 'o').

Sample Input
101e 010010o 1e 000e 110100101o #

Sample Output
1010 0100101 11 0000 1101001010

Source
2008 Mid-Central USA

Recommend
zty

代码: #include<iostream> using namespace std; #include<string> int main() { int i,flag,count,size; char a[100000],c; while(scanf("%s",a)!=EOF) { if(a[0]=='#')break; count=0; size=strlen(a); for(i=0;a[i];i++) { if(a[i]=='1')count++; } if(a[size-1]=='e')flag=1; else if(a[size-1]=='o')flag=0; if(!flag) { if(count%2==1)c='0'; else c='1'; } else

125

{ if(count%2==1)c='1'; else c='0'; } for(i=0;i<size-1;i++) printf("%c",a[i]); printf("%c\n",c); } return 0; }

2577
Problem Description

How to Type

Pirates have finished developing the typing software. He called Cathy to test his typing software. She is good at thinking. After testing for several days, she finds that if she types a string by some ways, she will type the key at least. But she has a bad habit that if the caps lock is on, she must turn off it, after she finishes typing. Now she wants to know the smallest times of typing the key to finish typing a string.

Input
The first line is an integer t (t<=100), which is the number of test case in the input file. For each test case, there is only one string which consists of lowercase letter and upper case letter. The length of the string is at most 100.

Output
For each test case, you must output the smallest times of typing the key to finish typing this string.

Sample Input
3 Pirates HDUacm HDUACM

Sample Output
8 8 8 Hint The string ―Pirates‖, can type this way, Shift, p, i, r, a, t, e, s, the answer is 8. The string ―HDUacm‖, can type this way, Caps lock, h, d, u, Caps lock, a, c, m, the answer is 8 The string "HDUACM", can type this way Caps lock h, d, u, a, c, m, Caps lock, the answer is 8

Author
Dellenge

Source
HDU 2009-5 Programming Contest

Recommend
lcy

126

代码:#include <stdio.h>
#include <string.h> #define MAX 200 int arr[MAX][4]; char str[MAX]; int letter(char ch) { if(ch>='A'&&ch<='Z') return 1; return 0; } void proc() { int i; int tmp,min; int len=strlen(str); for(i=0;i<len;i++) { if(i==0) { if(letter(str[i])) { arr[i][1]=2; arr[i][2]=2; } else { arr[i][0]=1; arr[i][3]=3; } } else { if(letter(str[i])==letter(str[i-1])) { if(arr[i-1][0]){ arr[i][0]=arr[i-1][0]+1;arr[i][3]=arr[i-1][0]+3;} if(arr[i-1][1]) { arr[i][1]=arr[i-1][1]+2; arr[i][2]=arr[i-1][1]+2;} if(arr[i-1][2]) { if(arr[i][0]>arr[i-1][2]+1||!arr[i][0]) arr[i][0]=arr[i-1][2]+1; if(arr[i][3]>arr[i-1][2]+3||!arr[i][3]) arr[i][3]=arr[i-1][2]+3; } if(arr[i-1][3]) { if(arr[i][1]>arr[i-1][3]+2||!arr[i][1]) arr[i][1]=arr[i-1][3]+2; if(arr[i][2]>arr[i-1][3]+2||!arr[i][2]) arr[i][2]=arr[i-1][3]+2; } } else { if(arr[i-1][0]){ arr[i][1]=arr[i-1][0]+2; arr[i][2]=arr[i-1][0]+2;} if(arr[i-1][1]){ arr[i][0]=arr[i-1][1]+1; arr[i][3]=arr[i-1][1]+3;}

127

if(arr[i-1][2]) { if(arr[i][1]>arr[i-1][2]+2||!arr[i][1]) arr[i][1]=arr[i-1][2]+2; if(arr[i][2]>arr[i-1][2]+2||!arr[i][2]) arr[i][2]=arr[i-1][2]+2; } if(arr[i-1][3]) { if(arr[i][0]>arr[i-1][3]+1||!arr[i][0]) arr[i][0]=arr[i-1][3]+1; if(arr[i][3]>arr[i-1][3]+3||!arr[i][3]) arr[i][3]=arr[i-1][3]+3; } } } } min=3*MAX; if(letter(str[len-1])) { if(arr[len-1][0]){ if(arr[len-1][1]){ if(arr[len-1][2]){ if(arr[len-1][3]){ } else { if(arr[len-1][0]) { if(arr[len-1][1]) { if(arr[len-1][2]) { if(arr[len-1][3]) { } printf("%d\n",min);

tmp=arr[len-1][0]+1; if(tmp<min) min=tmp;} tmp=arr[len-1][1]; if(tmp<min) min=tmp; } tmp=arr[len-1][2]+1; if(tmp<min) min=tmp;} tmp=arr[len-1][3]; if(tmp<min) min=tmp; }

tmp=arr[len-1][0]; tmp=arr[len-1][1]+1; tmp=arr[len-1][2]; tmp=arr[len-1][3]+1;

if(tmp<min) min=tmp; } if(tmp<min) min=tmp;} if(tmp<min) min=tmp; } if(tmp<min) min=tmp;}

} //Caps Shift:0-00;1-01;2-10;3-11 int main() { int num; scanf("%d",&num); while(num--) { scanf("%s",str); memset(arr,0,strlen(str)*4*sizeof(int)); proc(); } return 0; }

128

北京大学: 1035
Description
You, as a member of a development team for a new spell checking program, are to write a module that will check the correctness of given words using a known dictionary of all correct words in all their forms. If the word is absent in the dictionary then it can be replaced by correct words (from the dictionary) that can be obtained by one of the following operations: ?deleting of one letter from the word; ?replacing of one letter in the word with an arbitrary letter; ?inserting of one arbitrary letter into the word. Your task is to write the program that will find all possible replacements from the dictionary for every given word.

Spell checker

Input
The first part of the input file contains all words from the dictionary. Each word occupies its own line. This part is finished by the single character '#' on a separate line. All words are different. There will be at most 10000 words in the dictionary. The next part of the file contains all words that are to be checked. Each word occupies its own line. This part is also finished by the single character '#' on a separate line. There will be at most 50 words that are to be checked. All words in the input file (words from the dictionary and words to be checked) consist only of small alphabetic characters and each one contains 15 characters at most.

Output
Write to the output file exactly one line for every checked word in the order of their appearance in the second part of the input file. If the word is correct (i.e. it exists in the dictionary) write the message: "is correct". If the word is not correct then write this word first, then write the character ':' (colon), and after a single space write all its possible replacements, separated by spaces. The replacements should be written in the order of their appearance in the dictionary (in the first part of the input file). If there are no replacements for this word then the line feed should immediately follow the colon.

Sample Input
i is
129

has have be my more contest me too if award # me aware m contest hav oo or i fi mre #

Sample Output
me is correct aware: award m: i my me contest is correct hav: has have oo: too or: i is correct fi: i mre: more me

Source
Northeastern Europe 1998

开始做字符串的题目,本人觉得最头痛噶野,好鬼唔锺意处理字符串噶野。不过唯有硬住头 皮上啦。 呢条题有个奇怪噶地方,就系用 STL 做的话,点都系 TLE,后来改翻用 C 语言甘样慢慢搞先 过,重要用左将近 1s.

130

注意: (1)用另一个字符数组记录字典,然后排序,用于二分查找的。 (2)先处理与被检查数组相同长度的,然后系,比距长的,最后系比距短的。 (3)数组开得足够大啦

#include<iostream> #include<stdio.h> #include<cstring> using namespace std; int cmp(const void *p, const void *q) { return strcmp((char *) p, (char *) q); } struct s { char word[20]; int len; } str1[10005]; char str2[10005][20], bc[20], ch[20], *p; int bcl, n; void input() { int i = 0; while (strcmp(gets(str1[++i].word), "#")) { str1[i].len = strlen(str1[i].word); strcpy(str2[i], str1[i].word); } n = i; qsort(str2 + 1, n, sizeof (str2[0]), cmp); } void solve() { int i, j, k; while (strcmp(gets(bc), "#")) { bcl = strlen(bc); p = (char *) bsearch(&bc, str2 + 1, n, sizeof (str2[0]), cmp); if (p) cout << bc << " is correct" << endl; else { cout << bc << ":"; for (i = 1; i <= n; i++) {

131

if (str1[i].len == bcl) { int flag = 0; for (j = 0; j < str1[i].len; j++) { if (str1[i].word[j] != bc[j]) flag++; } if (flag < 2) cout << " " << str1[i].word; } else if (bcl == str1[i].len + 1) { for (j = 0; j < bcl; j++) { strcpy(ch, bc); for (k = j; k < bcl; k++) ch[k] = ch[k + 1]; //cout<<bc<<" "<<str1[i].word<<" "<<ch<<endl; if (strcmp(ch, str1[i].word) == 0) { printf(" %s", str1[i].word); break; } } } else if (bcl == str1[i].len - 1) { for (j = 0; j < str1[i].len; j++) { strcpy(ch, str1[i].word); for (k = j; k < str1[i].len; k++) ch[k] = ch[k + 1]; //cout<<bc<<" "<<str1[i].word<<" "<<ch<<endl; if (strcmp(ch, bc) == 0) { printf(" %s", str1[i].word); break; } } } } cout << endl; } } } int main() { input(); solve(); return 0; }

132

1061
Description

青蛙的约会

两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高 兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。 可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有 约定见面的具体位置。 不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方 向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不 然是永远都不可能碰面的。 为了帮助这两只乐观的青蛙,你被要求写一个程序来 判断这两只青蛙是否能够碰面,会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙 A 和青蛙 B,并且规定纬度线上东经0度处为原 点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。 设青蛙 A 的出发点坐标是 x,青蛙 B 的出发点坐标是 y。青蛙 A 一次能跳 m 米, 青蛙 B 一次能跳 n 米,两只青蛙跳一次所花费的时间相同。纬度线总长 L 米。 现在要你求出它们跳了几次以后才会碰面。

Input
输入只包括一行5个整数 x,y,m,n,L,其中 x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。

Output
输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行"Impossible"

Sample Input
1 2 3 4 5

Sample Output
4

Source
浙江

这题用的是解线性同余方程的方法, 之前没接触到过, 搜索资料后看到一个人的博客里面讲 的很好就拷贝过来了。内容如下: 对于方程:ax≡b(mod m),a,b,m 都是整数,求解 x 的值,这个就是线性同余方程。 符号说明: mod 表示:取模运算 ax≡b(mod m)表示:(ax - b) mod m = 0,即同余 gcd(a,b)表示:a 和 b 的最大公约数 求解 ax≡b(mod n)的原理:对于方程 ax≡b(mod n),存在 ax + by = gcd(a,b),x,y 是整 数。而 ax≡b(mod n)的解可以由 x,y 来堆砌。具体做法如下:

133

第一个问题:求解 gcd(a,b) 定理一:gcd(a,b) = gcd(b,a mod b) 欧几里德算法 int Euclid(int a,int b) { if(b == 0) return a; else return Euclid(b,mod(a,b)); } 附:取模运算 int mod(int a,int b) { if(a >= 0) return a % b; else return a % b + b; } 第二个问题:求解 ax + by = gcd(a,b) 定理二:ax + by = gcd(a,b)= gcd(b,a mod b) = = = = 则:x = y' y = x' - a / b * y' 以上内容转自 hi.baidu.com/redcastle/blog/item/934b232dbc40d336349bf7e4.html

b b a a

* * * *

x' + (a mod b) * y' x' + (a - a / b * b) * y' y' + b * (x' - a / b * y') x + b * y

由这个可以得出扩展的欧几里德算法: int exGcd(int a, int b, int &x, int &y) { if(b == 0) { x = 1; y = 0; return a;

134

} int int x = y = }

r = exGcd(b, a % b, x, y); t = x; y; t - a / b * y; return r;

代码:
#include<iostream> #include<cstdlib> #include<cstring> #include<cmath> using namespace std; __int64 mm,nn,xx,yy,l; __int64 c,d,x,y; __int64 modd(__int64 a, __int64 b) { if(a>=0) return a%b; else return a%b+b; } __int64 exGcd(__int64 a, __int64 b) { if(b==0) { x=1; y=0; return a; } __int64 r=exGcd(b, a%b); __int64 t=x; x=y; y=t-a/b*y; return r; } int main() {

135

scanf("%I64d %I64d %I64d %I64d %I64d",&xx,&yy,&mm,&nn,&l); if(mm>nn) //分情况 { d=exGcd(mm-nn,l); c=yy-xx; } else { d=exGcd(nn-mm,l); c=xx-yy; } if(c%d != 0) { printf("Impossible\n"); return 0; } l=l/d; x=modd(x*c/d,l); ///取模函数要注意 printf("%I64d\n",x); system("pause"); return 0; }

1142
Description

Smith Numbers

While skimming his phone directory in 1982, Albert Wilansky, a mathematician of Lehigh University,noticed that the telephone number of his brother-in-law H. Smith had the following peculiar property: The sum of the digits of that number was equal to the sum of the digits of the prime factors of that number. Got it? Smith's telephone number was 493-7775. This number can be written as the product of its prime factors in the following way: 4937775= 3*5*5*65837 The sum of all digits of the telephone number is 4+9+3+7+7+7+5= 42,and the sum of the digits of its prime factors is equally 3+5+5+6+5+8+3+7=42. Wilansky was so amazed by his discovery that he named this kind of numbers after his brother-in-law: Smith numbers. As this observation is also true for every prime number, Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number, so he excluded them from the definition. Wilansky published an article about Smith numbers in the Two Year College
136

Mathematics Journal and was able to present a whole collection of different Smith numbers: For example, 9985 is a Smith number and so is 6036. However,Wilansky was not able to find a Smith number that was larger than the telephone number of his brother-in-law. It is your task to find Smith numbers that are larger than 4937775!

Input
The input file consists of a sequence of positive integers, one integer per line. Each integer will have at most 8 digits. The input is terminated by a line containing the number 0.

Output
For every number n > 0 in the input, you are to compute the smallest Smith number which is larger than n,and print it on a line by itself. You can assume that such a number exists.

Sample Input
4937774 0

Sample Output
4937775

Source
Mid-Central European Regional Contest 2000

题意:寻找最接近而且大于给定的数字的 SmithNumber 什么是 SmithNumber? 用 sum(int)表示一个 int 的各位的和,那一个数 i 如果是 SmithNumber,则 sum(i) = sigma( sum(Pj )),Pj 表示 i 的第 j 个质因数。例如 4937775= 3*5*5*65837,4+9+3+7+7+7+5 = 42,3+5+5+(6+5+8+3+7) = 42,所以 4937775 是 SmithNumber。 思路: 要寻找大于给定数字且最接近给定数字的 SmithNumber, 只要将给定数字不断的加 1, 判断它是否是 SmithNumber 就行了,如果是 SmithNumber 就立即输出。 但是如何判断是否是 SmithNumber 呢?首先就是要对数字进行质因数分解。 质因数分解要保 证因子都是质数。 这里先介绍一个如何判断一个数 int 是否是质数呢, 如果对于这个数, = i 2.....sqrt(int)都不是它的约数,那 int 就是一个质数。所以我们可以将 i 初始化为 2, 然后不断递增 i,看 i 是否是 int 的一个约数,如果是的话那 i 就是 int 的一个质因数(因 为这个数是从 2 开始第一个可以整除 int 的数,它不可能是一个可以分解的合数,否则,它 的约数在它之前就整除 int) ,然后将 int 除以该质因数,重置 i 为 2,重新对 int 判断它是 否是质数。这样最后剩下的 int 一定是一个质数,从而对 int 进行了质因数分解

137

然后就很简单的将数字各质因数的各位加起来, 看和是否等于该数字的各位和, 如果相等那 它可能就是 SmithNumber,为什么说只是可能呢,因为这个数可能是质数,但是质数不是 SmithNumber。

#include <stdio.h> #include <math.h> int Sum( int number ) { int sum = 0; while( number != 0 ) { sum += number % 10; number /= 10; } return sum; } bool SmithNumber( int number ) { int i = 2; int temp = number; int sumOfNumber = Sum( number ); int sum = 0; while( i <= (int)sqrt( (double)number ) ) { if ( number % i ==0 ) { sum += Sum( i ); number /= i; i = 2; } else { ++i; } //以上的代码做了无谓的计算,可用下面的代码,更新于 20090904 //while( number % i == 0 ) //{ // sum += sum(i); // number /= i; //}

138

// ++i; } sum += Sum( number ); if ( sum == sumOfNumber && number != temp ) { return true; } else { return false; } }

int main() { while( true ) { int num; scanf("%d",&num ); if ( num == 0 ) { break; } while( true ) { if ( SmithNumber(++num)) { printf("%d\n", num); break; } } } return 0; }

1200
Description

Crazy Search

Many people like to solve hard puzzles some of which may lead them to madness. One such puzzle could be finding a hidden prime number in a given text. Such number could be the number of different substrings of a given size that exist in the text. As you soon will discover, you really need the help of a computer and a good
139

algorithm to solve such a puzzle. Your task is to write a program that given the size, N, of the substring, the number of different characters that may occur in the text, NC, and the text itself, determines the number of different substrings of size N that appear in the text. As an example, consider N=3, NC=4 and the text "daababac". The different substrings of size 3 that can be found in this text are: "daa"; "aab"; "aba"; "bab"; "bac". Therefore, the answer should be 5.

Input
The first line of input consists of two numbers, N and NC, separated by exactly one space. This is followed by the text where the search takes place. You may assume that the maximum number of substrings formed by the possible set of characters does not exceed 16 Millions.

Output
The program should output just an integer corresponding to the number of different substrings of size N found in the given text.

Sample Input
3 4 daababac

Sample Output
5

Hint
Huge input,scanf is recommended.

Source
Southwestern Europe 2002
这个是说一段字符串 有 nc 种字符组成 问长度为 n 的不同的字符串有多少个 非常关键的一条信息是 nc^n 最多只有 16 000 000 so 我们用 nc 进制的 HASH 来做

#include <stdio.h> #include <string.h> int n,nc; char str[20000000]; char asca[128]; int hash[16000005];

140

int main() { while(scanf("%d%d\n",&n,&nc)!=EOF) { scanf("%s",str); int i=0; int j; int key=0; while(str[i]) { if(asca[str[i]]==0) asca[str[i]]=++key; i++; if(key==nc) break; } int len=strlen(str); int sum; int cnt=0; for(i=0;i+n-1<len;i++) { sum=0; for(j=i;j<=i+n-1;j++) { sum=sum*nc+asca[str[j]]-1; } if(hash[sum]==0) { hash[sum]=1; cnt++; } } printf("%d\n",cnt); } }

1811
Description

Prime Test

Given a big integer number, you are required to find out whether it's a prime number.
141

Input
The first line contains the number of test cases T (1 <= T <= 20 ), then the following T lines each contains an integer number N (2 <= N < 254).

Output
For each test case, if N is a prime number, output a line containing the word "Prime", otherwise, output a line containing the smallest prime factor of N.

Sample Input
2 5 10

Sample Output
Prime 2

Source
POJ Monthly
Miller Robin 素性测试 + Pollard rho 寻找素因子 Miller Robin 和 Pollard rho 的理论想非常强,细节这里就不说了,可以参考 算法导论第 31 章 #include <iostream> #include <ctime> #include <cmath> #define MAX_L 64 //最长位数 #define TIMES 8 //miller robin 素性测试的测试次数 #define MAX_VAL (pow(2.0, 60)) //定义最大值 #define CVAL 200 using namespace std; //最小的素因子 __int64 minFactor; //(1)计算 a * b mod n, 思路: 利用 b 的二进制表示进行拆分计算 //(2)例如: b = 1011101 那么 a * b mod n = (a * 1000000 mod n + a * 10000 mod n + a * 1000 mod n + a * 100 mod n + a * 1 mod n) mod n //(3)思路就是上面描述的那样, 那么可以用从低位往高位遍历 b, 并用 a 来记录当前位为 1 的值,每次遇到 b 当前位为 //1 就将结果值加上 a 并 mod n,然后 a 要乘以 2 __int64 multAndMod(__int64 a, __int64 b, __int64 n) {

142

a = a % n; __int64 res = 0; while(b) { //当前位为 1 if(b & 1) { //加上当前权位值 res += a; //相当于 mod n if(res >= n) res -= n; } //乘以 2,提高一位 a = a<<1; //mod n if(a >= n) a -= n; b = b >> 1; } return res; } //(1)计算 a ^ b mod n, 思路: 和上面类似,也是利用 b 的二进制表示进行拆分计算 //(2)例如: b = 1011101 那么 a ^ b mod n = [(a ^ 1000000 mod n) * (a ^ 10000 mod n) * (a ^ 1000 mod n) * (a ^ 100 mod n) * (a ^ 1 mod n)] mod n //(3)思路就是上面描述的那样, 那么可以用从低位往高位遍历 b, 并用 a 来记录当前位为 1 的值,每次遇到 b 当前位为 //1 就将结果乘上 a 并 mod n,然后 a 要乘以 a 以提升一位 __int64 modAndExp(__int64 a, __int64 b, __int64 n) { a = a % n; __int64 res = 1; while(b >= 1) { //遇到当前位为 1,则让 res * 当前 a 并 mod n if(b & 1) res = multAndMod(res, a, n); //a * a 以提升一位 a = multAndMod(a, a, n); b = b >> 1; } return res; } //MillerRobin 素性测试,true:素数,flase:合数 bool millerRobin(__int64 a, __int64 n)

143

{ __int64 u = 0, cur = n - 1; int t = 0; bool find1 = false; while(cur != 0) { if(!find1) { int pb = cur % 2; if(pb == 0) t++; else find1 = true; } if(find1) break; cur = cur / 2; } u = cur; cur = modAndExp(a, u, n); __int64 now; for(int p = 1; p <= t; p++) { now = modAndExp(cur, 2, n); if(cur != 1 && now == 1 && cur != n - 1) { //printf("%d %d\n", cur, now); return false; } cur = now; } if(cur != 1) { //printf("a:%I64d u:%I64d n:%I64d val:%I64d\n", a, u, n, start); return false; } //printf("a:%I64d u:%I64d n:%I64d val:%I64d\n", a, u, n, start); return true; } //利用 Miller Robin 对 n 进行 n 次素性测试 bool testPrime(int times, __int64 n) { if(n == 2) return true; if(n % 2 == 0) return false; __int64 a; int t;

144

srand(time(NULL)); for(t = 1; t <= times; t++) { a = rand() % (n - 1) + 1; if(!millerRobin(a, n)) return false; } return true; } __int64 gcd(__int64 a, __int64 b) { if(b == 0) return (a); return gcd(b, a % b); } __int64 PollardRho(__int64 n, int c) { int i = 1; srand(time(NULL)); __int64 x = rand() % n; __int64 y = x; int k = 2; while(true) { i = i + 1; x = (modAndExp(x, 2, n) + c) % n; __int64 d = gcd(y - x, n); if(1 < d && d < n) return d; if(y == x) return n; //重复了, 说明当前 x 下无解,需要重新启动 PollardRho if(i == k) { y = x; k = k * 2; } } } void getSmallest(__int64 n, int c) { if(n == 1) return; //判断当前因子是否为素数 if(testPrime(TIMES, n)) { if(n < minFactor) minFactor = n; return; } __int64 val = n;

145

//循环,知道找到一个因子 while(val == n) val = PollardRho(n, c--); //二分 getSmallest(val, c); getSmallest(n / val, c); } int main() { int caseN; __int64 n; scanf("%d", &caseN); while(caseN--) { scanf("%I64d", &n); minFactor = MAX_VAL; if(testPrime(TIMES, n)) printf("Prime\n"); else { getSmallest(n, CVAL); printf("%I64d\n", minFactor); } } return 0; }

2262
Description

Goldbach's Conjecture

In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture: Every even number greater than 4 can be written as the sum of two odd prime numbers.

For example:
8 = 3 + 5. Both 3 and 5 are odd prime numbers. 20 = 3 + 17 = 7 + 13. 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23. Today it is still unproven whether the conjecture is right. (Oh wait, I have the proof of course, but it is too long to write it on the margin of this page.) Anyway, your task is now to verify Goldbach's conjecture for all even numbers less than a million.
146

Input
The input will contain one or more test cases. Each test case consists of one even integer n with 6 <= n < 1000000. Input will be terminated by a value of 0 for n.

Output
For each test case, print one line of the form n = a + b, where a and b are odd primes. Numbers and operators should be separated by exactly one blank like in the sample output below. If there is more than one pair of odd primes adding up to n, choose the pair where the difference b - a is maximized. If there is no such pair, print a line saying "Goldbach's conjecture is wrong."

Sample Input
8 20 42 0

Sample Output
8=3+5 20 = 3 + 17 42 = 5 + 37

Source
Ulm Local 1998

题目地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=2262 题目思路:对于任何一个偶数 n,从 x = 1 和 y = n - 1 开始,看 x、y 是否是质数,不 是则 x += 2, y += 2 这题需要开很大的内存,我 RE n 次,居然是因为数组开太小了,我这题耗时不 是很理想,但我的耗内存 在我看到的中是最小的, 所以看来 OJ 上的题只要能开内存的就尽量开。 估计我 这题用栈耗时了。 #include #include #include #include #include #include <iostream> <stdio.h> <math.h> <stack> <memory.h> <string.h>

using namespace std;

147

// 判断是否为质数的函数 int IsPrime ( int x ) { int i; if( x < 2 ) return 0; for( i = 2; i <= (int) ( sqrt( (double)x + 0.5 ) ); i++ ) if( x % i == 0) return 0; return 1; } int main() { // 输入数,输入数 / 2 向上延伸,输入数 / 2 向下延伸,输入数 / 2 int m_Input, m_Num_Max, m_Num_Min, m_InputToTwo; // 总体输出 char m_Output[ 1000000 ]; memset( m_Output, 0, 1000000 ); // 标识 m_Output 的 Pos int m_Output_Pos = 0; // 是否找到标识 bool b_Find; // 栈 stack<int> m_Stack; // 临时数 int m_Value_Top; // 循环输入 while ( scanf( "%d", &m_Input ) && ( m_Input != 0 ) ) { b_Find = true; // m_Input 肯定是一个偶数 m_InputToTwo = m_Input / 2; // 置值 m_Num_Max = m_Input - 1; m_Num_Min = 1; // 寻找,直至都为素数 或者 找不到 为止 while ( ( !IsPrime( m_Num_Max ) ) || ( !IsPrime( m_Num_Min ) ) ) { // 否则,前进 & 后退 2 格 m_Num_Max -= 2; m_Num_Min += 2;

148

// 如果发生如下情况,则输出 "Goldbach's conjecture is wrong." if ( ( m_Num_Max < m_InputToTwo ) || ( m_Num_Min > m_InputToTwo ) ) { char* m_TempChar = "Goldbach's conjecture is wrong.\n"; strcat( m_Output, m_TempChar ); b_Find = false; m_Output_Pos += strlen( m_TempChar ); break; } } // 如果找到了 if ( b_Find ) { // 将 m_Input 转换为字符串存入 m_Output while ( m_Input != 0 ) { m_Value_Top = m_Input % 10; m_Stack.push( m_Value_Top ); m_Input /= 10; } while ( !m_Stack.empty() ) { m_Value_Top = m_Stack.top(); m_Output[ m_Output_Pos++ ] = m_Value_Top + 48; m_Stack.pop(); } // 加入 = m_Output[ m_Output_Pos++ ] = ' '; m_Output[ m_Output_Pos++ ] = '='; m_Output[ m_Output_Pos++ ] = ' '; // 将 m_Num_Min 转换为字符串存入 m_Output while ( m_Num_Min != 0 ) { m_Value_Top = m_Num_Min % 10; m_Stack.push( m_Value_Top ); m_Num_Min /= 10; } while ( !m_Stack.empty() ) { m_Value_Top = m_Stack.top(); m_Output[ m_Output_Pos++ ] = m_Value_Top + 48; m_Stack.pop(); } // 加入 +

149

m_Output[ m_Output_Pos++ ] = ' '; m_Output[ m_Output_Pos++ ] = '+'; m_Output[ m_Output_Pos++ ] = ' '; // 将 m_Num_Max 转换为字符串存入 m_Output while ( m_Num_Max != 0 ) { m_Value_Top = m_Num_Max % 10; m_Stack.push( m_Value_Top ); m_Num_Max /= 10; } while ( !m_Stack.empty() ) { m_Value_Top = m_Stack.top(); m_Output[ m_Output_Pos++ ] = m_Value_Top + 48; m_Stack.pop(); } // 加入 \n m_Output[ m_Output_Pos++ ] = '\n'; } } // 输出 printf( "%s", m_Output ); system( "pause" ); return 0; }

2407
Description

Relatives

Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.

Input
There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.

Output
For each test case there should be single line of output answering the question posed above.

Sample Input
150

7 12 0

Sample Output
6 4

Source
Waterloo local 2002.07.01

这题从题意可以看出就是求比从 1~n - 1 从有几个数和 n 没有公共因子, 通常的算法很简 单就能够想到, 我开始也是按通常的做法写了一个, 觉得 可能会 TLE, 果不其然, 后来上网查了一下, 知道了欧拉函数, 这个就是求比 n 小的数 中与 n 互质(也就是没有公共因子)的算法, 看来还是那些经典的算法效率比较高, 比纯 用暴力试探高多了... 欧拉函数描述如下: 利用欧拉函数和它本身不同质因数的关系, 用筛法计算出某个范围内所有数的欧拉函数 值。 欧拉函数和它本身不同质因数的关系:欧拉函数ψ (N)=N{∏p|N} (1-1/ p)(P是数N的质因数) 。 如: ψ (10)=10×(1-1/2)×(1-1/5)=4; ψ (30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8; ψ (49)=49×(1-1/7)=42。 注意的是 P 是 N 的质因子, 这里求质因子还是不能够用常规的判断这个数是不是质数, 这 样的话可能还会 TLE, 网上学到他们用的一个 while() 循环,感觉还挺巧的, 学习了... #include <stdio.h> #include <math.h> int enlerFun(int n) { int count = n; int i = 2;

151

for(; i<=n; i++) if(n % i == 0) { count -= count / i; while(n % i == 0) n /= i; } return count; } int main() { int inputVal = 0; int count = 0; while(scanf("%d", &inputVal) && inputVal != 0) { count = enlerFun(inputVal); printf("%d\n", count); } return 0; }

2447
Description

RSA

RSA is the best-known public key encryption algorithm. In this algorithm each participant has a private key that is shared with no one else and a public key which is published so everyone knows it. To send a secure message to this participant, you encrypt the message using the widely known public key; the participant then decrypts the messages using his or her private key. Here is the procedure of RSA: First, choose two different large prime numbers P and Q, and multiply them to get N (= P * Q). Second, select a positive integer E (0 < E < N) as the encryption key such that E and T= (P - 1) * (Q - 1) are relatively prime. Third, compute the decryption key D such that 0 <= D < T and (E * D) mod T = 1. Here D is a multiplicative inverse of E, modulo T. Now the public key is constructed by the pair {E, N}, and the private key is {D, N}. P and Q can be discarded. Encryption is defined by C = (M ^ E) mod N, and decryption is defined by M = (C ^ D) mod N, here M, which is a non-negative integer and smaller than N, is the plaintext message and C is the resulting ciphertext.

152

To illustrate this idea, let’s see the following example: We choose P = 37, Q = 23, So N = P * Q = 851, and T = 792. If we choose E = 5, D will be 317 ((5 * 317) mod 792 = 1). So the public key is {5, 851}, and the private key is {317, 851}. For a given plaintext M = 7, we can get the ciphertext C = (7 ^ 5) mod 851 = 638. As we have known,for properly choosen very large P and Q, it will take thousands of years to break a key, but for small ones, it is another matter. Now you are given the ciphertext C and public key {E, N}, can you find the plaintext M?

Input
The input will contain several test cases. Each test case contains three positive integers C, E, N (0 < C < N, 0 < E < N, 0 < N < 2 ^ 62).

Output
Output the plaintext M in a single line.

Sample Input
638 5 851

Sample Output
7

Source
POJ Monthly,static

密码学:RSA 公钥密码 #include<stdlib.h> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; typedef unsigned __int64 u64; #define MAX 30 #define MAXN 5 u64 len, dig, limit; u64 factor[MAXN]; u64 mod(u64 a, u64 b, u64 n){ if(!a)return 0; else return ( ((a&dig)*b)%n + (mod(a>>len,b,n)<<len)%n )%n; } u64 by(u64 a, u64 b, u64 n){

153

u64 p; p = 8, len = 61; while(p<n){ p<<=4; len -=4; } dig = ((limit/p)<<1) - 1; return mod(a,b,n); } u64 random(){//产生随机数 u64 a; a = rand(); a *= rand(); a *= rand(); a *= rand(); return a; } u64 square_multiply(u64 x, u64 c, u64 n){//(x^c)%n 快速算法 u64 z=1; while(c){ if(c%2==1)z = by(z,x,n); x = by(x,x,n); c=(c>>1); } return z; } bool Miller_Rabin(u64 n){//Miller_Rabin 素数测试 if(n<2)return false; if(n==2)return true; if(!(n&1))return false; u64 k = 0, i, j, m, a; m = n - 1; while(m%2==0)m=(m>>1),k++; for(i=0;i<MAX;i++){ a = square_multiply(random()%(n-1)+1, m, n);//平方乘 if(a==1)continue; for(j=0;j<k;j++){ if(a==n-1)break; a = by(a,a,n); } if(j<k)continue; return false ; } return true;

154

} u64 gcd(u64 a,u64 b){ if(a==0) return b; else return gcd(b%a,a); } u64 f(u64 x, u64 n ){ return (by(x,x,n)+1)%n; } u64 Pollard(u64 n){ if(n<=2)return 0; if(!(n&1))return 2; u64 i, p, x,xx; for(i=0;i<MAX;i++){ x = random()%n; //或者直接用 x = i xx = f(x,n); p = gcd((xx+n-x)%n , n); while(p==1){ x = f(x,n); xx = f(f(xx,n),n); p = gcd((xx+n-x)%n,n)%n; } if(p)return p; } return 0; } u64 prime(u64 a){ if(Miller_Rabin(a))return a; u64 t = Pollard(a); if(t!=0) {return prime(t);} } u64 Euclid(u64 a,u64 b,__int64 &x,__int64 &y) { if(b==0) { x=1,y=0; return a; } u64 t,d; if(b!=0) d=Euclid(b,a%b,x,y); t=x; x=y;

155

if(b!=0) y=t-a/b*y; return d; } int main(){ u64 c,e,n,i,j,m,t,n0,T,ans,l; __int64 T0,x,y,d; limit = 1; limit = limit<<63; while(scanf("%I64u%I64u%I64u",&c,&e,&n)!=EOF){ m=0;n0=n; while(n%2==0){n/=2;factor[m++]=2;} while(n>1){ if(Miller_Rabin(n))break; t = prime(n); factor[m++] = t; if(t!=0) n/=t; } if(n>1)factor[m++]=n; //for(l=0;l<m;l++)printf("%I64u\n",factor[l]); T0=(__int64)(factor[0]-1)*(factor[1]-1); T=(u64)T0; Euclid(e,T,x,y); d=x; //printf("%I64d\n",d); //while(d<0)d+=T0; d=(d%T0+T0)%T0; //d=(__int64)d; // printf("%I64d %I64d\n",d,T0); ans=square_multiply(c,(u64)d,n0); printf("%I64u\n",ans); } }

2503
Description

Babelfish

You have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them.
156

Input
Input consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message of up to 100,000 words. Each dictionary entry is a line containing an English word, followed by a space and a foreign language word. No foreign word appears more than once in the dictionary. The message is a sequence of words in the foreign language, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters.

Output
Output is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as "eh".

Sample Input
dog ogday cat atcay pig igpay froot ootfray loops oopslay atcay ittenkay oopslay

Sample Output
cat eh loops

Hint
Huge input and output,scanf and printf are recommended.

Source
Waterloo local 2001.09.22
题目大意很简单,就是给你字典的对应信息,然后给你查询条件要求你输出字典查询结果, 如果字符串没有在字典中则输出"eh"。 恩,学到了一个新的函数 bsearch(),可以进行二分查找。先对字典使用 qsort 排序然后再 使用 bsearch()查找字符串即可。 还学到了一个输入函数 sscanf(),可以从一个字符串中读取内容,格式如下 sscanf (string str, string format [, string var1...])

#include <stdio.h> #include <stdlib.h>

157

#include <string.h> typedef struct { char en[11]; char fn[11]; }dict; dict a[100001]; /* 定义 qsort 比较函数 */ int q_cmp(const void * a,const void *b) { return strcmp(((dict*)a)->fn, ((dict*)b)->fn); } /* 定义 bsearch 比较函数 */ int b_cmp(const void* a, const void* b) { return strcmp((char*)a, ((dict*)b)->fn); } int main() { char str[30]; int i, sign; dict *p; i = 0; /* 查询标记记为"未开始" */ sign = 1; /* 读取字符串直到文件结束 */ while(gets(str)) { /* 遇到空行则开始排序字典 */ if (str[0] == '\0') { /* 查询标记记为"开始" */ sign = 0; qsort(a, i, sizeof(dict), q_cmp); continue; } /* 查询未开始时读取字典信息 */ if (sign)

158

{ /* 使用 sscanf 从 str 中读取查询要求 */ sscanf(str, "%s %s", a[i].en, a[i].fn); i++; } /* 查询开始时进行查询 */ else { /* 二分查找指定字符串 */ p = (dict*) bsearch(str, a, i, sizeof(dict), b_cmp); /* 找到则输出结果 */ if (p) { puts(p->en); } /* 找不到输出"eh" */ else { puts("eh"); } } } //system("pause"); return 0; }

2513
Description

Colored Sticks

You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?

Input
Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.

Output
If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.

Sample Input
159

blue red red violet cyan blue blue magenta magenta cyan

Sample Output
Possible

Hint
Huge input,scanf is recommended.

Source
The UofA Local 2000.10.14

这道题大意是:已知有 n 根木棒,每个木棒有两种颜色表示两端,问:能不能将所有的木棒 连接成一条直线(连接处颜色相同) 。 可以考虑无向图的欧拉通路问题: 将每种颜色看成图中的一个节点, 木棒看作连接节点的边, 于是判断两点: 1,每种颜色(节点)的度 2,是否为连通图 首先,每种颜色的度可以通过每条木棒的两端颜色的累积得到,问题是,每种颜色都是字符 串,怎么关联每种颜色和度呢? 最容易想到的是 Hash,这肯定是可行的。例如 degree [ hash(red) ]=5。表示颜色为红色 的度为 5。 但是, 既然提示用 trie 树来做, 那么 trie 树的节点的数据域就可以保存每种颜色的 id (相 当于分配的 hash 值, 可以通过一个全局变量自增产生) 这样经过将每种颜色字符串插入到 , tree 中以后,通过 trie 树的 search 操作就能高效的获取每种颜色对应的 id,没插入一种 颜色,为其产生一个 id,只需要注意相同颜色插入时的处理即可。 其次,判断无向图是否连通可以使用并查集来判定:经过 n-1 各 union 操作后,所有节点都 在一个集合(树形结构表示集合的话,即所有节点的父节点(集合代表)都一样) 。由于每 种颜色是由字符串来标示的,每个集合保存颜色对应的唯一 id。 通过上面两个步骤的判定,就可以得出结果。 #include <iostream> #include <cstring> using namespace std; const int max_size=500001; char s1[11],s2[11]; int p[max_size]; int r[max_size]; int degree[max_size]; int num=1;

160

struct TreeNode { int id;//the id of the string TreeNode * next[27]; TreeNode () { id=0; for(int i=0;i<27;i++) next[i]=NULL; } }; TreeNode * root; void insert(char *s ,TreeNode * root) { TreeNode *p = root; int i = 0; int l = strlen(s); for(i=0;i<l;i++) { if(p->next[s[i]-'a']==NULL) p->next[s[i]-'a']=new TreeNode; p=p->next[s[i]-'a']; } if(p->id==0)//first insert p->id = num++; } int search(char *s,TreeNode *root) { TreeNode * p = root; if(p==NULL) return -1; int i=0; int l = strlen(s); for(i=0;i<l;i++) { if(p->next[s[i]-'a']==NULL) return -1; else p=p->next[s[i]-'a']; } return p->id; } void make_set(int x) {

161

p[x]=x; r[x]=1; } int find_set(int x) { if(p[x]!=x) p[x]=find_set(p[x]); return p[x]; } void union_set(int x,int y) { if(r[x]>r[y]) p[y]=x; else if(r[x]<r[y]) p[x]=y; else { r[y]++; p[x]=y; } } int main() { root = new TreeNode; memset(p,0,sizeof(p)); memset(degree,0,sizeof(degree)); while(scanf("%s %s",s1,s2)!=EOF) { insert(s1,root); insert(s2,root); int id1 = search(s1,root); int id2 = search(s2,root); degree[id1]++; degree[id2]++; if(p[id1]==0) make_set(id1); if(p[id2]==0) make_set(id2); union_set(find_set(id1),find_set(id2)); } int i = 0; int sum=0; //if the num of nodes whose degree is odd are more than 2. for(i=1;i<num;i++)

162

{ if(degree[i]%2!=0)sum++; if(sum>2) { cout<<"Impossible"<<endl; return 0; } } //if the g is joint. for(i=1;i<num;i++) if(find_set(i) != find_set(1)) { cout<<"Impossible"<<endl; return 0 ; } cout<<"Possible"<<endl; }

ACM 算法: kurXX 最小生成树
#include <iostream> #include <math.h> #include <algorithm> using namespace std; #define M 501 #define LIM 20000000 struct edg{ int u,v; int w; }all_e[M*M/2]; bool operator < (const edg &a,const edg &b){ return a.w<b.w; } int set[M]; inline bool uni(int set[],int a,int b){ int ac=0,a2=a,b2=b,bc=0; while(set[a]!=0) {a=set[a];ac++;} if(a2!=a) set[a2]=a; while(set[b]!=0) {b=set[b];bc++;} if(b2!=b) set[b2]=b;
163

if(a==b) return false; if(ac<bc) set[a]=b; else set[b]=a; return true; } int main(){ int i,j,k,n,m,u,v,t; cin >> t; for(k=0;k<t;k++){ memset(set,0,sizeof(set)); cin >> n; int ei=0; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(t!=0){ edg e; e.u=i;e.v=j; scanf("%d",&e.w); if(i<j) all_e[ei++]=e; } } } sort(&all_e[0],&all_e[ei]); int count=0; int size=ei; int max=0; for(i=0;i<size && count < n-1;i++){ if(uni(set,all_e[i].u,all_e[i].v)){ count++; if(all_e[i].w>all_e[max].w) max=i; } } printf("%d\n",all_e[max].w); } return 0; }

Prim
#include <iostream> using namespace std;
164

#define M 2001 int set[M]={0},g[M][M]; char str[M][8]; inline void make_map(int n,int g[M][M]){ int i,j,k; for(i=1;i<=n;i++){ for(j=i+1;j<=n;j++){ int c=0; for(k=0;k<7;k++) if(str[i][k]!=str[j][k]) c++; g[i][j]=g[j][i]=c; } } } int main(){ int n,q[M],qf=0,ql=0,d[M],u; char c; scanf("%d%c",&n,&c); int i; while(n!=0){ memset(set,0,sizeof(set)); memset(g,0,sizeof(g)); for(i=1;i<=n;i++) { scanf("%s",&str[i]); q[i-1]=i; d[i]=2000000; } qf=0;ql=n-1; make_map(n,g); int sum=0; int f=false; while(qf<=ql){ int min=qf; for(i=qf+1;i<=ql;i++){ if(d[q[i]] < d[q[min]]) min=i; } swap(q[qf],q[min]); u=q[qf]; qf++; if(f) sum+=d[u]; for(i=1;i<=n;i++){ if(g[u][i] !=0 && g[u][i] < d[i]) d[i]=g[u][i]; } f=true; }

165

printf("The highest possible quality is 1/%d.\n",sum); scanf("%d%c",&n,&c); } return 0; }

堆实现最短路
#include <iostream> #include <string> #include <stdlib.h> #include <vector>; using namespace std; #define M 1001 #define LIM 2000000000 struct dd{ //最短距离 int w,q;//w 是距离值,q 是堆中的相对位置 }d[M],d2[M]; struct node{ int v,w; }; int h[M],hs; vector<node> g[M],g2[M]; void change_key(dd d[M],int v,int w){ d[v].w=w; int i=d[v].q; while(i>1 && d[h[i/2]].w>d[h[i]].w){ swap(h[i],h[i/2]); swap(d[h[i]].q,d[h[i/2]].q); i=i/2; } } inline void min_heaphy(dd d[M],int *a,int i,int s){//s 为堆大小 int l=i*2,r=i*2+1; int miner=i; if (l<=s && d[a[i]].w>d[a[l]].w) miner = l; else miner=i; if (r<=s && d[a[miner]].w>d[a[r]].w) miner=r; if(miner!=i){ swap(a[i],a[miner]);
166

swap(d[a[i]].q,d[a[miner]].q); min_heaphy(d,a,miner,s); } } inline void init(dd d[M],int n,int s){ //初始化图和堆 int i; hs=n; for(i=1;i<=n;i++){d[i].w=LIM;h[i]=d[i].q=i;} change_key(d,s,0); } inline void relax(dd d[M],int u,int v,int duv){ if(d[v].w>d[u].w+duv) change_key(d,v,d[u].w+duv); } void dijkstra(vector<node> g[M],dd d[M],int n,int s){ //n is |V| && s is the source init(d,n,s); int i; while(hs!=0){ int u=h[1]; swap(h[1],h[hs]); swap(d[h[1]].q,d[h[hs]].q); hs--; min_heaphy(d,h,1,hs); for(i=0;i<g[u].size();i++) relax(d,u,g[u][i].v,g[u][i].w); } }

最短路 DIJ 普通版
#define M 101 #define LIM 20000000 int g[M][M],d[M],fd[2][M][M],gt[M][M],set[M]; inline void init(int d[M],int n,int s){ //初始化图 int i; for(i=1;i<=n;i++) d[i]=LIM; d[s]=0; } inline void relax(int d[M],int u,int v,int duv){ if(d[v]>d[u]+duv) d[v]=d[u]+duv; }
167

void dijkstra(int g[M][M],int d[M],int n,int s){ //n is |V| && s is the source init(d,n,s); int q[M],ql=1,qf=1; //队列 int i; for(i=1;i<=n;i++) q[ql++]=i; while(qf!=ql){ int min=qf; for(i=qf;i<ql;i++) if(d[q[i]]<d[q[min]]) min=i; swap(q[qf],q[min]); //q[qf] is the min int u=q[qf++]; for(i=1;i<=n;i++){ if(g[u][i]!=0) relax(d,u,i,g[u][i]); } } }

floyd
#include <iostream> #include <vector> using namespace std; #define M 301 #define LIM 200000000 int w[M][M],d[2][M][M]; void floyd(int g[M][M],int d[2][M][M],int n){ int i,j,k; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ d[0][i][j]=g[i][j]; } d[0][i][i]=0; } //这里是令 d[0]=g for(k=1;k<=n;k++){ for(i=1;i<=n;i++) for(j=1;j<=n;j++){ int t1=k%2; int t2=(t1+1)%2; d[t1][i][j]=d[t2][i][j] < d[t2][i][k]+d[t2][k][j]?d[t2][i][j]:d[t2][i][k]+d[t2][k][j]; } } }

BELL_MAN
168

inline void init(int d[M],int n,int s){ //初始化图 int i; for(i=1;i<=n;i++) d[i]=2000000000; d[s]=0; } inline void relax(int d[M],int u,int v,int duv){ if(d[v]>d[u]+duv) d[v]=d[u]+duv; } void bell_man(int g[M][M],int d[M],int n,int s){ //n 个结点 s 为源点 int i,j,k; init(d,n,s); for(k=1;k<n;k++){ for(i=1;i<=n;i++) for(j=1;j<=n;j++){ if(g[i][j]!=0) relax(d,i,j,g[i][j]); } } }

拓扑排序
#include <iostream> #include <stack> #include <vector> #include <list> using namespace std; vector <int> order; void find_id(list<int> g[],int id[],int n){ //寻找入度,没有使用 int i; list<int>::iterator k; for(i=0;i<n;i++){ for(k=g[i].begin();k!=g[i].end();k++){ id[*k]++; } } } void topo(list<int> g[],int id[],int n,bool &OK,bool &incon){//OK==false 表示未确定顺序 incon==true 表示发现矛盾 stack<int> s; order.erase(order.begin(),order.end()); int t[26]; copy(&id[0],&id[n],&t[0]);
169

int i; for(i=0;i<n;i++){ if(id[i]==0) s.push(i); } if(s.size()!=1) OK=false; int count=0; while(!s.empty()){ int v=s.top(); s.pop(); count++; order.push_back(v); list<int>::iterator k; for(k=g[v].begin();k!=g[v].end();k++){ id[*k]--; if(id[*k]==0) s.push(*k); if(s.size()>1) OK=false; } } if(order.size() < n) OK=false; //矛盾发生,会导致这种情况,小心 if(count < n) incon=true; copy(&t[0],&t[n],&id[0]); }

DFS 强连通分支
#include <iostream> #include <algorithm> #include <vector> using namespace std; #define M 20005 vector<int> g[M],gt[M]; bool used[M]; int ft[M],sort_v[M],tim; bool comp(const int &u,const int &v){ return ft[u]>ft[v]; } inline int findp(int set[],int n){ int n2=n; while(set[n]!=0) n=set[n]; if(n2!=n) set[n2]=n; return n; } inline bool uni(int set[],int a,int b){ int ac=0,a2=a,b2=b,bc=0,t; while(set[a]!=0) {a=set[a];ac++;}
170

while(a2!=a) {t=set[a2]; set[a2]=a; a2=t;}; while(set[b]!=0) {b=set[b];bc++;} while(b2!=b) {t=set[b2]; set[b2]=b; b2=t;}; if(a==b) return false; if(ac<bc) set[a]=b; else set[b]=a; return true; } void dfs(vector<int> g[M],int u){ if(used[u]) return; tim++; used[u]=true; int i; for(i=0;i<g[u].size();i++){ dfs(g,g[u][i]); } tim++; ft[u]=tim; return; } void dfs2(vector<int> g[],int u,int r,int set[]){ if(used[u]) return; uni(set,u,r); used[u]=true; int i; for(i=0;i<g[u].size();i++){ dfs2(g,g[u][i],u,set); } return; } void scc(int n,vector<int> g[M],int set[]){ int i,j; tim=0; memset(used,0,sizeof(used)); memset(set,0,sizeof(set)); for(i=1;i<=n;i++) sort_v[i]=i; for(i=1;i<=n;i++) if(!used[i]) dfs(g,i); //compute finishing times sort(&sort_v[1],&sort_v[n+1],comp); //decreasing f[u] order memset(used,0,sizeof(used)); for(i=1;i<=n;i++) for(j=0;j<g[i].size();j++) gt[g[i][j]].push_back(i); //compute gt for(i=1;i<=n;i++) if(!used[sort_v[i]]) dfs2(gt,sort_v[i],sort_v[i],set); //make the scc } int main(){

171

int i,j,n,m,u,v,set[M]; cin >> n >> m; for(i=0;i<m;i++){ scanf("%d%d",&u,&v); g[u].push_back(v); } scc(n,g,set); int pi=1,ptosc[M]; struct Scc{ int p,n; }sc[M]; memset(sc,0,sizeof(sc)); for(i=1;i<=n;i++){ int p=findp(set,i); if(sc[p].p==0) {sc[p].p=pi; ptosc[pi++]=p;} sc[p].n++; } int n2=pi-1,od[M]; memset(od,0,sizeof(od)); for(i=1;i<=n;i++){ for(j=0;j<g[i].size();j++){ u=findp(set,i); v=findp(set,g[i][j]); if(sc[u].p!=sc[v].p) od[sc[u].p]++; } } int sum=0,s1=0; for(i=1;i<=n2;i++) if(od[i]==0) {s1++; sum+=sc[ptosc[i]].n;} if(s1!=1) sum=0; cout << sum << endl; }

最大匹配
#include <iostream> #include <string> #include <math.h> using namespace std; #define M 1001 int n,m,match[M],ans[M]; bool visit[M],g[M][M]; //O(n^3) bool dfs(int k,bool map[M][M]){ int t;
172

for(int i = 1; i <= m; i++){ if(map[k][i] && !visit[i]){ visit[i] = true; t = match[i]; match[i] = k; if(t == 0 || dfs(t,map)) return true; match[i] = t; } } return false; } int main(){ int i,sum=0,t,j,u,v; cin >> t; while(t--){ sum=0; memset(match,0,sizeof(match)); memset(g,0,sizeof(g)); scanf("%d%d",&n,&m); for(i=1;i<=m;i++){ scanf("%d%d",&u,&v); g[u][v]=true; } m=n; for(i=1;i<=n; i++){ memset(visit,0,sizeof(visit)); if(dfs(i,g)) sum++; } cout << n-sum << endl; } return 0; }

还有两个最大匹配模板
#include <iostream> #include <string> #include <math.h> #include <vector> using namespace std; #define M 3001 bool g[M][M]; int mk[M] ,cx[M],pred[M],open[M],cy[M],nx,ny;
173

//边少适用 O(n^3) int MaxMatchBFS() { int i , u , v , t , d , e , cur , tail , res(0) ; memset(mk , 0xff , sizeof(mk)) ; memset(cx , 0xff , sizeof(cx)) ; memset(cy , 0xff , sizeof(cy)) ; for (i = 0 ; i < nx ; i++){ pred[i] = -1 ; for (open[cur = tail = 0] = i ; cur <= tail && cx[i] == -1 ; cur++){ for (u = open[cur] , v = 0 ; v < ny && cx[i] == -1 ; v ++) if (g[u][v] && mk[v] != i) { mk[v] = i ; open[++tail] = cy[v] ; if (open[tail] >= 0) { pred[open[tail]] = u ; continue ; } for (d = u , e = v ; d != -1 ; t = cx[d] , cx[d] = e , cy[e] = d , e = t , d = pred[d]) ; } } if (cx[i] != -1) res++ ; } return res ; } int path(int u){ for (int v = 0 ; v < ny ; v++) if (g[u][v] && !mk[v]){ mk[v] = 1 ; if (cy[v] == -1 || path(cy[v])) { cx[u] = v ; cy[v] = u ; return 1 ; } } return 0 ; } //少适用 O(n^3) int MaxMatchDFS() { int res(0) ; memset(cx , 0xff , sizeof(cx)) ; memset(cy , 0xff , sizeof(cy)) ; for (int i = 0 ; i < nx ; i++) if (cx[i] == -1){ memset(mk , 0 , sizeof(mk)); res += path(i) ; }

174

return res ; }

最大权匹配,KM 算法
//此 KM 算法,坐标从 1 开始,记住 #include <iostream> #include <vector> #include <math.h> using namespace std; #define M 110 int n; // X 的大小 int lx[M], ly[M]; // 标号 bool sx[M], sy[M]; // 是否被搜索过 int match[M]; // Y(i) 与 X(match [i]) 匹配 // 从 X(u) 寻找增广道路,找到则返回 true bool path(int u,int weight[M][M]) { sx [u] = true; for (int v = 0; v < n; v ++) if (!sy [v] && lx[u] + ly [v] == weight [u] [v]) { sy [v] = true; if (match [v] == -1 || path(match [v],weight)) { match [v] = u; return true; } } return false; } // 参数 Msum 为 true ,返回最大权匹配,否则最小权匹配 int km(bool Msum,int weight[M][M]) { int i, j; if (!Msum) { for (i = 0; i < n; i ++) for (j = 0; j < n; j ++) weight [i] [j] = -weight [i] [j]; } // 初始化标号 for (i = 0; i < n; i ++) { lx [i] = -0x1FFFFFFF; ly [i] = 0; for (j = 0; j < n; j ++) if (lx [i] < weight [i] [j]) lx [i] = weight [i] [j]; }
175

memset(match, -1, sizeof (match)); for (int u = 0; u < n; u ++) while (1) { memset(sx, 0, sizeof (sx)); memset(sy, 0, sizeof (sy)); if (path(u,weight)) break; // 修改标号 int dx = 0x7FFFFFFF; for (i = 0; i < n; i ++) if (sx [i]) for (j = 0; j < n; j ++) if(!sy [j]) dx = min(lx[i] + ly [j] - weight [i] [j], dx); for (i = 0; i < n; i ++) { if (sx [i]) lx [i] -= dx; if (sy [i]) ly [i] += dx; } } int sum = 0; for (i = 0; i < n; i ++) sum += weight [match [i]] [i]; if (!Msum) { sum = -sum; for (i = 0; i < n; i ++) for (j = 0; j < n; j ++) weight [i] [j] = -weight [i] [j]; // 如果需要保持 weight [ ] [ ] 原来的值,这 里需要将其还原 } return sum; } struct Point{ int r,c; }; int main(){ int i,j,m; freopen("in","r",stdin); int w[M][M]; char c; Point pt;

176

while(cin >> n >> m && (n!=0 || m!=0)){ vector<Point> vh,vm; for(i=0;i<n;i++){ getchar(); for(j=0;j<m;j++){ scanf("%c",&c); if(c=='H'){ pt.r=i; pt.c=j; vh.push_back(pt); } if(c=='m'){ pt.r=i;pt.c=j; vm.push_back(pt); } } } for(i=0;i<vm.size();i++) w[i][j]=abs(vm[i].r-vh[j].r)+abs(vm[i].c-vh[j].c); n=vm.size(); cout << km(false,w)<< endl; } }

for(j=0;j<vh.size();j++)

两种欧拉路
无向图:
#define M 45 int used[M][M],id[M]; void dfs(int u,vector<int> g[],vector<int> &vans){ //O(E^2) int j,w,v,t; for(j=g[u].size()-1;j>=0;j--){ t=v=g[u][j]; w=u; if(v>w) swap(v,w); if(used[v][w]!=0){ used[v][w]--; dfs(t,g,vans); } } vans.push_back(u); }

177

有向图:
int n,m; vector<int> g[M],vans; void dfs(int u){ //O(E^2*log(e)) int j,t; Edg et; for(j=g[u].size()-1;j>=0;j--){ et.u=u; et.v=g[u][j]; if(mp[et]!=0){ mp[et]--; dfs(g[u][j]); } } vans.push_back(u); }

【最大流】Edmonds Karp
//求最小割集合的办法: //设置一个集合 A, 最开始 A={s},按如下方法不断扩张 A: //1 若存在一条边(u,v), 其流量小于容量,且 u 属于 A,则 v 加入 A //2 若存在(v,u), 其流量大于 0,且 u 属于 A,则 v 加入 A //A 计算完毕,设 B=V-A, //最大流对应的割集 E={(u,v) | u∈A,v∈B} //E 为割集,这是一定的 //【最大流】Edmonds Karp 算法求最大流,复杂度 O(V E^2)。返回最大流,输入图容量 //矩阵 g[M][M],取非零值表示有边,s 为源点,t 为汇点,f[M][M]返回流量矩阵。 int f[M][M],g[M][M]; int EdmondsKarp(int n,int s,int t){ int i,j,k,c,head,tail,flow=0; int r[M][M]; int prev[M],visit[M],q[M]; for (i=1;i<=n;i++) for (j=1;j<=n;j++) {f[i][j]=0;r[i][j]=g[i][j];} //初始化流量网络和残留网 络 while (1) { //在残留网络中找到一条 s 到 t 的最短路径 head=tail=0; memset(visit,0,sizeof(visit)); q[tail++]=s;
178

prev[s]=-1; visit[s]=1; while(head!=tail){ //宽度优先搜索从 s 到 t 的最短路径 k=q[head++]; for (i=1;i<=n;i++) if (!visit[i] && r[k][i]>0) { visit[i]=1; prev[i]=k; if (i==t) goto next; q[tail++]=i; } } next: if (!visit[t]) break; //流量已达到最大 c=99999999; j=t; while (j!=s) { i=prev[j]; if (c>r[i][j]) c=r[i][j]; j=i; } //下面改进流量 j=t; while (j!=s) { i=prev[j]; f[i][j]+=c; f[j][i]=-f[i][j]; r[i][j]=g[i][j]-f[i][j]; r[j][i]=g[j][i]-f[j][i]; j=i; } flow+=c; //cout << c << endl; } return flow; }

dinic
/* dinic BFS+多路增广 这个模板是 OIBH 上的 Code_Rush 的,他写的 Dinic 和别人的不太一样,速度更快 O(mn^2) */ #include<stdio.h> #include<list>
179

#include<queue> #include<string.h> #include <vector> #include <iostream> using namespace std; #define M 201 int pre[M]; int f[M][M],g[M][M]; bool b[M]={0}; //g 为输入的图容量矩阵,f 为返回流量矩阵 int dinic(int n,int s,int t) { memset(f,0,sizeof(f)); int ans=0; while(true) { queue<int> q; fill(pre,pre+n+2,-1); fill(b,b+n+2,0); q.push(s);b[s]=1; while(!q.empty()) { int x=q.front();q.pop(); if(x==t)break; for(int i=1;i<=n;i++) { if(!b[i]&&f[x][i]<g[x][i]) { pre[i]=x; b[i]=1; q.push(i); } } } if(pre[t]==-1)break; for(int i=1;i<=n;i++) { if(f[i][t]<g[i][t]&&(i==s||pre[i]!=-1)) { int v,low=g[i][t]-f[i][t]; pre[t]=i; for(v=t;pre[v]!=-1;v=pre[v]) low=low<g[pre[v]][v]-f[pre[v]][v]?low:g[pre[v]][v]-f[pre[v]][v]; if(low==0)continue; for(v=t;pre[v]!=-1;v=pre[v])

180

{ f[pre[v]][v]+=low; f[v][pre[v]]-=low; } ans+=low; } } } return ans; } int main(){ int m,n,i,j,u,v,w; while(cin >> m >> n){ memset(g,0,sizeof(g)); for(i=0;i<m;i++){ scanf("%d%d%d",&u,&v,&w); g[u][v]+=w; } cout << dinic(n,1,n) << endl; } }

【最小费用最大流】Edmonds Karp 对偶 算法
#define M 211 #define LIM 99999999 //【最小费用最大流】Edmonds Karp 对偶算法,复杂度 O(V^3E^2)。返回最大流,输入图 //容量矩阵 g[M][M],费用矩阵 w[M][M],取非零值表示有边,s 为源点,t 为汇点,f[M][M]返 //回流量矩阵,minw 返回最小费用。 int g[M][M],w[M][M],minw,f[M][M]; int DualityEdmondsKarp(int n,int s,int t){ int i,j,k,c,quit,flow=0; int best[M],prev[M]; minw=0; for (i=1;i<=n;i++) { for (j=1;j<=n;j++){ f[i][j]=0; if (g[i][j]) {g[j][i]=0;w[j][i]=-w[i][j];} } } while (1) { for (i=1;i<=n;i++) best[i]=LIM;
181

best[s]=0; do { quit=1; for (i=1;i<=n;i++){ if (best[i]<LIM) for (j=1;j<=n;j++){ if (f[i][j]<g[i][j] && best[i]+w[i][j]<best[j]){ best[j]=best[i]+w[i][j]; prev[j]=i; quit=0; } } } }while(!quit); if (best[t]>=LIM) break; c=LIM; j=t; while (j!=s) { i=prev[j]; if (c>g[i][j]-f[i][j]) c=g[i][j]-f[i][j]; j=i; } j=t; while (j!=s) { i=prev[j]; f[i][j]+=c; f[j][i]=-f[i][j]; j=i; } flow+=c; minw+=c*best[t]; } return flow; }

ACM 题目: 【题目】排球队员站位问题
┏━━━━━━━━┓图为排球场的平面图,其中一、二、三、四、五、六为位置编号, ┃ ┃二、三、四号位置为前排,一、六、五号位为后排。某队比赛时, ┃ ┃一、四号位放主攻手,二、五号位放二传手,三、六号位放副攻 ┠──┬──┬──┨手。队员所穿球衣分别为1,2,3,4,5,6号,但每个队
182

┃ 四 │ 三 │ 二 ┃员的球衣都与他们的站位号不同。已知1号、6号队员不在后排, ┠──┼──┼──┨2号、3号队员不是二传手,3号、4号队员不在同一排,5号、 ┃ 五 │ 六 │ 一 ┃6号队员不是副攻手。 ┗━━┷━━┷━━┛ 编程求每个队员的站位情况。 【算法分析】本题可用一般的穷举法得出答案。也可用回溯法。以下为回溯解法。 【参考程序】 type sset=set of 1..6; var a:array[1..6]of 1..6; d:array[1..6]of sset; i:integer; procedure output; {输出} begin if not( (a[3]in [2,3,4])= (a[4] in[2,3,4])) then begin { 3,4 号队员不在同一排 } write('number:');for i:=1 to 6 do write(i:8);writeln; write('weizhi:');for i:=1 to 6 do write(a[i]:8);writeln; end; end; procedure try(i:integer;s:sset); {递归过程 i:第 i 个人,s:哪些位置已安排人了} var j,k:integer; begin for j:=1 to 6 do begin {每个人都有可能站 1-6 这 6 个位置} if (j in d[i]) and not(j in s) then begin {j 不在 d[i]中,则表明第 i 号人不能站 j 位. j 如在 s 集合中,表明 j 位已 排人了} a[i]:=j; {第 i 人可以站 j 位} if i<6 then try(i+1,s+[j]) {未安排妥,则继续排下去} else output; {6 个人都安排完,则输出} end; end; end; begin for i:=1 to 6 do d[i]:=[1..6]-[i]; {每个人的站位都与球衣的号码不同} d[1]:=d[1]-[1,5,6]; d[6]:=d[6]-[1,5,6]; {1,6 号队员不在后排} d[2]:=d[2]-[2,5]; d[3]:=d[3]-[2,5]; {2,3 号队员不是二传手} d[5]:=d[5]-[3,6]; d[6]:=d[6]-[3,6]; {5,6 号队员不是副攻手} try(1,[]); end.

183

【题目】把自然数N分解为若干个自然 数之和。
【参考答案】 n 5 6 7 10 100 │ │ │ │ │ │ total 7 11 15 42 190569291

【参考程序】 var n:byte; num:array[0..255] of byte; total:word; procedure output(dep:byte); var j:byte; begin for j:=1 to dep do write(num[j]:3);writeln; inc(total); end; procedure find(n,dep:byte); {N:待分解的数,DEP:深度} var i,j,rest:byte; begin for i:=1 to n do {每一位从 N 到 1 去试} if num[dep-1]<=i then {保证选用的数大于前一位} begin num[dep]:=i; rest:=n - i; {剩余的数进行下一次递归调用} if (rest>0) then begin find(rest,dep+1);end else if rest=0 then output(dep);{刚好相等则输出} num[dep]:=0; end; end; begin {主程序} writeln('input n:');readln(n); fillchar(num,sizeof(num),0); total:=0; num[0]:=0; find(n,1); writeln('sum=',total); end.

184

【题目】把自然数N分解为若干个自然 数之积。
【参考程序】 var path :array[1..1000] of integer; total,n:integer; procedure find(k,sum,dep:integer); {K:} var b,d:Integer; begin if sum=n then {积等于 N} begin write(n,'=',path[1]); for d:=2 to dep-1 do write('*',path[d]); writeln;inc(total); exit; end; if sum>n then exit; {累积大于 N} for b:= trunc(n/sum)+1 downto k do {每一种可能都去试} begin path[dep]:=b; find(b,sum*b,dep+1); end; end; begin readln(n); total:=0; find(2,1,1);writeln('total:',total); readln; end.

【题目】马的遍历问题。
在N*M的棋盘中,马只能走日字。马从位置(x,y)处出发,把 棋盘的每一格都走一次,且只走一次。找出所有路径。 【参考程序】 {深度优先搜索法} const n=5;m=4; fx:array[1..8,1..2]of -2..2=((1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1), (-2,1),(-1,2)); {八个方向增量} var dep,i:byte; x,y:byte; cont:integer; {统计总数} a:array[1..n,1..m]of byte; {记录走法数组} procedure output; {输出,并统计总数}
185

var x,y:byte; begin cont:=cont+1; writeln; writeln('count=',cont); for y:=1 to n do begin for x:=1 to m do write(a[y,x]:3); writeln; end; { readln; halt;} end; procedure find(y,x,dep:byte); var i,xx,yy:integer; begin for i:=1 to 8 do begin xx:=x+fx[i,1];yy:=y+fx[i,2]; {加上方向增量,形成新的坐标} if ((xx in [1..m])and(yy in [1..n]))and(a[yy,xx]=0) then {判断新坐标是否出界,是否已走过?} begin a[yy,xx]:=dep; {走向新的坐标} if (dep=n*m) then output else find(yy,xx,dep+1); {从新坐标出发,递归下一层} a[yy,xx]:=0 {回溯,恢复未走标志} end; end; end; begin cont:=0; fillchar(a,sizeof(a),0); dep:=1; writeln('input y,x');readln(y,x); { x:=1;y:=1;} if (y>n) or(x>m) then begin writeln('x,y error!');halt;end; a[y,x]:=1; find(y,x,2); if cont=0 then writeln('No answer!') else write('The End!'); readln; end.

【题目】加法分式分解。
如:1/2=1/4+1/4.找出所有方案。 输入:N M N为要分解的分数的分母 M为分解成多少项 【参考程序】
186

program fenshifenjie; const nums=5; var t,m,dep:integer; n,maxold,max,j:longint; path:array[0..nums] of longint; maxok,p:boolean; sum,sum2:real; procedure print; var i:integer; begin t:=t+1; if maxok=true then begin maxold:=path[m];maxok:=false;end; write ('NO.',t); for i:=1 to m do write(' ',path[i]:4); writeln; if path[1]=path[m] then begin writeln('Ok! total:',t:4);readln;halt;end; end; procedure input; begin writeln ('input N:'); readln(n); writeln ('input M(M<=',nums:1,'):'); readln(m); if (n<=0) or (m<=0) or (m>4) or (n>maxlongint) then begin writeln('Invalid Input!');readln;halt;end; end; function sum1(ab:integer):real; var a,b,c,d,s1,s2:real; i:integer; begin if ab=1 then sum1:=1/path[1] else begin a:=path[1]; b:=1 ; c:=path[2]; d:=1; for i:=1 to ab-1 do begin s2:=(c*b+a*d); s1:=(a*c); a:=s1; b:=s2; c:=path[i+2];

187

end; sum1:=s2/s1; end; end; procedure back; begin dep:=dep-1; if dep<=m-2 then max:=maxold; sum:=sum-1/path[dep]; j:=path[dep]; end; procedure find; begin repeat dep:=dep+1; j:=path[dep-1]-1; p:=false; repeat j:=j+1; if (dep<>m) and (j<=max) then if (sum+1/j) >=1/n then p:=false else begin p:=true; path[dep]:=j; sum:=sum+1/path[dep]; end else if j>max then back; if dep=m then begin path[dep]:=j; sum2:=sum1(m); if (sum2)>1/n then p:=false; if (sum2)=1/n then begin print; max:=j; back; end; if (sum2<1/n) then back; if (j>=max) then back; end; until p until dep=0; end; begin INPUT; maxok:=true;

188

for t:=0 to m do path[t]:=n; dep:=0; t:=0; sum:=0; max:=maxlongint; find; readln; end.

【题目】地图着色问题
【参考程序1】 const lin:array[1..12,1..12] of 0..1 {区域相邻数组,1 表示相邻} =((0,1,1,1,1,1,0,0,0,0,0,0), (1,0,1,0,0,1,1,1,0,0,0,0), (1,1,0,1,0,0,0,1,1,0,0,0), (1,0,1,0,1,0,1,0,1,1,0,0), (1,0,0,1,0,1,0,0,0,1,1,0), (1,1,0,0,1,0,1,0,0,0,1,0), (0,1,0,0,0,1,0,1,0,0,1,1), (0,1,1,0,0,0,1,0,1,0,0,1), (0,0,1,1,0,0,0,1,0,1,0,1), (0,0,0,1,1,0,0,0,1,0,1,1), (0,0,0,0,1,1,1,0,0,1,0,1), (0,0,0,0,0,0,1,1,1,1,1,1)); var color:array[1..12] of byte; {color 数组放已填的颜色} total:integer; function ok(dep,i:byte):boolean; {判断选用色 i 是否可用} var k:byte; {条件:相邻的区域颜色不能相同} begin for k:=1 to dep do if (lin[dep,k]=1) and (i=color[k]) then begin ok:=false;exit;end; ok:=true; end; procedure output; {输出} var k:byte; begin for k:=1 to 12 do write(color[k],' ');writeln; total:=total+1; end; procedure find(dep:byte); {参数 dep:当前正在填的层数} var i:byte; begin for i:=1 to 4 do begin {每个区域都可能是 1-4 种颜色} if ok(dep,i) then begin
189

color[dep]:=i; if dep=12 then output else find(dep+1); color[dep]:=0; {恢复初始状态,以便下一次搜索} end; end; end; begin total:=0; {总数初始化} fillchar(color,sizeof(color),0); find(1); writeln('total:=',total); end. 【参考程序2】 const {lin 数组:代表区域相邻情况} lin:array[1..12] of set of 1..12 = ([2,3,4,5,6],[1,3,6,7,8],[1,2,4,8,9],[1,3,5,9,10],[1,4,6,10,11], [1,2,5,7,11],[12,8,11,6,2],[12,9,7,2,3],[12,8,10,3,4], [12,9,11,4,5],[12,7,10,5,6],[7,8,9,10,11]); color:array[1..4] of char=('r','y','b','g'); var a:array[1..12] of byte; {因有 12 个区域,故 a 数组下标为 1-12} total:integer; function ok(dep,i:integer):boolean; {判断第 dep 块区域是否可填第 i 种色} var j:integer; { j 为什么设成局部变量?} begin ok:=true; for j:=1 to 12 do if (j in lin[dep]) and (a[j]=i) then ok:=false; end; procedure output; {输出过程} var j:integer; { j 为什么设成局部变量?} begin inc(total); {方案总数加 1} write(total:4); {输出一种方案} for j:=1 to 12 do write(color[a[j]]:2);writeln; end; procedure find(dep:byte); var i:byte; { i 为什么设成局部变量?} begin for i:=1 to 4 do {每一区域均可从 4 种颜色中选一} begin if ok(dep,i) then begin {可填该色} a[dep]:=i; {第 dep 块区域填第 i 种颜色} if (dep=12) then output {填完 12 个区域}

190

else find(dep+1); {未填完} a[dep]:=0; {取消第 dep 块区域已填的颜色} end; end; end; begin {主程序} fillchar(a,sizeof(a),0); {记得要给变量赋初值!} total:=0; find(1); writeln('End.'); end.

【题目】放置方案
在 n*n 的正方形中放置长为 2,宽为 1 的长条块,问放置方案如何 【参考程序1】 const n=4; var k,u,v,result:integer; a:array[1..n,1..n]of char; procedure printf; {输出} begin result:=result+1; {方案总数加 1} writeln('--- ',result,' ---'); for v:=1 to n do begin for u:=1 to n do write(a[u,v]); writeln end; writeln; end; procedure try; {填放长条块} var i,j,x,y:integer; full:boolean; begin full:=true; if k<>trunc(n*n/2) then full:=false;{测试是否已放满} if full then printf; {放满则可输出} if not full then begin {未满} x:=0;y:=1; {以下先搜索未放置的第一个空位置} repeat x:=x+1; if x>n then begin x:=1;y:=y+1 end until a[x,y]=' '; {找到后,分两种情况讨论} if a[x+1,y]=' ' then begin {第一种情况:横向放置长条块} k:=k+1; {记录已放的长条数} a[x,y]:=chr(k+ord('@')); {放置} a[x+1,y]:=chr(k+ord('@'));
191

try; k:=k-1; a[x,y]:=' '; a[x+1,y]:=' '

{递归找下一个空位置放} {回溯,恢复原状}

end; if a[x,y+1]=' ' then begin {第二种情况:竖向放置长条块} k:=k+1; {记录已放的长条数} a[x,y]:=chr(k+ord('0')); {放置} a[x,y+1]:=chr(k+ord('0')); try; {递归找下一个空位置放} k:=k-1; a[x,y]:=' '; {回溯,恢复原状} a[x,y+1]:=' ' end; end; end; begin {主程序} fillchar(a,sizeof(a),' '); {记录放置情况的字符数组,初始值为空格} result:=0; k:=0; {k 记录已放的块数,如果 k=n*n/2,则说明已放满} try; {每找到一个空位置,把长条块分别横放和竖放试验} end. 【参考程序2】 const dai:array [1..2,1..2]of integer=((0,1),(1,0)); type node=record w,f:integer; end; var a:array[1..20,1..20]of integer; path:array[0..200]of node; s,m,n,nn,i,j,x,y,dx,dy,dep:integer; p,px:boolean; procedure inputn; begin { write('input n');readln(n);} n:=4; nn:=n*n;m:=nn div 2; end; procedure print; var i,j:integer; begin inc(s);writeln('no',s); for i:=1 to n do begin for j:=1 to n do write(a[i,j]:3);writeln;

192

end; writeln; end; function fg(h,v:integer):boolean; var p:boolean; begin p:=false; if (h<=n) and (v<=n) then if a[h,v]=0 then p:=true; fg:=p; end; procedure back; begin dep:=dep-1; if dep=0 then begin p:=true ;px:=true;end else begin i:=path[dep].w;j:=path[dep].f; x:=((i-1)div n )+1;y:=i mod n; if y=0 then y:=n; dx:=x+dai[j,1];dy:=y+dai[j,2]; a[x,y]:=0;a[dx,dy]:=0; end; end; begin inputn; s:=0; fillchar(a,sizeof(a),0); x:=0;y:=0;dep:=0; path[0].w:=0;path[0].f:=0; repeat dep:=dep+1; i:=path[dep-1].w; repeat i:=i+1;x:=((i-1)div n)+1; y:=i mod n;if y=0 then y:=n; px:=false; if fg(x,y) then begin j:=0;p:=false; repeat inc(j); dx:=x+dai[j,1];dy:=y+dai[j,2]; if fg(dx,dy) and (j<=2) then begin a[x,y]:=dep;a[dx,dy]:=dep;

193

path[dep].w:=i;path[dep].f:=j; if dep=m then begin print;dep:=m+1;back;end else begin p:=true;px:=true;end; end else if j>=2 then back else p:=false; until p; end else if i>=nn then back else px:=false; until px; until dep=0; readln; end.

【题目】找迷宫的最短路径。
(广度优先搜索算法) 【参考程序】 uses crt; const migong:array [1..5,1..5] of integer=((0,0,-1,0,0), (0,-1,0,0,-1), (0,0,0,0,0), (0,-1,0,0,0), (-1,0,0,-1,0)); {迷宫数组} fangxiang:array [1..4,1..2] of -1..1=((1,0),(0,1),(-1,0),(0,-1)); {方向增量数组} type node=record lastx:integer; {上一位置坐标} lasty:integer; nowx:integer; {当前位置坐标} nowy:integer; pre:byte; {本结点由哪一步扩展而来} dep:byte; {本结点是走到第几步产生的} end; var lujing:array[1..25] of node; {记录走法数组} closed,open,x,y,r:integer; procedure output; var i,j:integer; begin for i:=1 to 5 do begin for j:=1 to 5 do write(migong[i,j]:4); writeln;end; i:=open;
194

repeat with lujing[i] do write(nowy:2,',',nowx:2,' <--'); i:=lujing[i].pre; until lujing[i].pre=0; with lujing[i] do write(nowy:2,',',nowx:2); end; begin clrscr; with lujing[1] do begin {初始化第一步} lastx:=0; lasty:=0; nowx:=1;nowy:=1;pre:=0;dep:=1;end; closed:=0;open:=1;migong[1,1]:=1; repeat inc(closed); {队列首指针加 1,取下一结点} for r:=1 to 4 do begin {以 4 个方向扩展当前结点} x:=lujing[closed].nowx+fangxiang[r,1]; {扩展形成新的坐标值} y:=lujing[closed].nowy+fangxiang[r,2]; if not ((x>5)or(y>5) or (x<1) or (y<1) or (migong[y,x]<>0)) then begin {未出界,未走过则可视为新的结点} inc(open); {队列尾指针加 1} with lujing[open] do begin {记录新的结点数据} nowx:=x; nowy:=y; lastx:=lujing[closed].nowx;{新结点由哪个坐标扩展而来} lasty:=lujing[closed].nowy; dep:=lujing[closed].dep+1; {新结点走到第几步} pre:=closed; {新结点由哪个结点扩展而来} end; migong[y,x]:=lujing[closed].dep+1; {当前结点的覆盖范围} if (x=5) and (y=5) then begin {输出找到的第一种方案} writeln('ok,thats all right');output;halt;end; end; end; until closed>=open; {直到首指针大于等于尾指针,即所有结点已扩展完} end.

【题目】火车调度问题
【参考程序】

【算法一】const

max=10;

type shuzu=array[1..max] of 0..max; var stack,exitout:shuzu;
195

n,total:integer; procedure output(exitout:shuzu); var i:integer; begin for i:=1 to n do write(exitout[i]:2);writeln; inc(total); end; procedure find(dep,have,rest,exit_we

更多相关文档:

ACM试题及答案

ACM试题及答案_其它_高等教育_教育专区。中国石油大学华东 ACM 试题(黄色高亮为答案) 问题 A: A + B Problem 题目描述 给定两个整数 a, b,求两个数之和。...

部分ACM题目与答案

部分ACM题目答案_IT认证_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档部分ACM题目答案_IT认证_资格考试/认证_教育专区。1001 Sum Problem......

大学ACM考试题目及作业答案整理

大学ACM考试题目及作业答案整理_工学_高等教育_教育专区。大学ACM考试题目及作业答案整理 南京适用ACM 作业与答案整理 1、平面分割方法:设有 n 条封闭曲线画在平面...

ACM题目整理

ACM题目整理_计算机软件及应用_IT/计算机_专业资料。ACM大学生程序设计入门简介题目...Output 对于每组数据,输出仅一行,即你求出的标准答案。 二叉树的输出格式为: ...

ACM作业与答案整理

ACM 作业与答案整理 1、平面分割方法:设有 n 条封闭曲线画在平面上,而任何两...("pasue"); return 0; } 【题目】排球队员站位问题 题目】 ┏━━━┓图...

ACM竞赛试题集锦

ACM竞赛试题集锦_IT/计算机_专业资料。ACM竞赛试题集锦 取石子游戏 Time Limit:1S Memory Limit:1000K Total Submit:505 Accepted:90 Description 有两堆石子,数量...

ACM试题

ACM试题_IT认证_资格考试/认证_教育专区。ACM 试题及答案 猪的安家 Andy 和 Mary 养了很多猪。他们想要给猪安家。但是 Andy 没有足够的猪圈,很多猪只能够 在...

南洋理工acm题目与答案

南洋理工acm题目答案_IT认证_资格考试/认证_教育专区。南洋理工acm题目答案今日推荐 88份文档 2014全国高考状元联手分享状元笔记 ...

杭电ACM部分题目答案

杭电ACM部分题目答案_IT认证_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档杭电ACM部分题目答案_IT认证_资格考试/认证_教育专区。杭电 ACM 1001 Sum...

整理acm模板

整理acm模板_理学_高等教育_教育专区。1、KMP 算法 /* * next[] 的含义: ...[j]; } } return ans; } 经典题目:POJ 3167 /* * POJ 3167 Cow ...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com