整理出ACM所有题目和答案解析

1000 A + B Problem

Problem Description

Calculate A + B.

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 int main() {

int a,b;

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

1001 Sum Problem

学习指导参考

WORD格式整理版

Problem Description

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 main() {

int n,i,sum; sum=0;

while((scanf(\"%d\",&n)!=-1)) {

sum=0;

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

学习指导参考

WORD格式整理版

sum+=i;

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

1002 A + B Problem II

Problem Description

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\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

11223344556677 998877665544332211

Sample Output

Case 1:

学习指导参考

WORD格式整理版

1 + 2 = 3

Case 2:

11223344556677 + 998877665544332211 = 1111111111111111110

Author

Ignatius.L

代码：

#include #include

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)

学习指导参考

WORD格式整理版

printf(\"1\");

for(i = len_max - 1; i >= 0; --i){ printf(\"%d\", c[i]); }

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

printf(\"\\n\"); }

return 0; }

1005 Number Sequence

Problem Description

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

学习指导参考

WORD格式整理版

Author

CHEN, Shunbao

Source

ZJCPC2004

Recommend

JGShining

代码：

#include 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; }

学习指导参考

WORD格式整理版

1008 Elevator

Problem Description

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.

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

学习指导参考

WORD格式整理版

JGShining

代码：

#include 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]); sum+=5; }

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

return 0;

}

1009 FatMouse' Trade

Problem Description

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

学习指导参考

WORD格式整理版

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

代码：

#include #include #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\ while(m!=-1&&n!=-1) {

sum=0;

memset(J,0,MAX*sizeof(int));

学习指导参考

WORD格式整理版

memset(F,0,MAX*sizeof(int)); memset(P,0,MAX*sizeof(double)); for(i=0;ifor(j=i+1;jif(P[i]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;iif(mprintf(\"%.3lf\\n\ }

return 0; }

1021 Fibonacci Again

Problem Description

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.

学习指导参考

WORD格式整理版

Sample Input

0 1 2 3 4 5

Sample Output

no no yes no no no

Author

Leojay

Recommend

JGShining

#include int main() {

long n;

while(scanf(\"%ld\",&n) != EOF) if (n%8==2 || n%8==6) printf(\"yes\\n\"); else

printf(\"no\\n\"); return 0; }

学习指导参考

WORD格式整理版

10 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

解答：

学习指导参考

WORD格式整理版

#include main() {

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

学习指导参考

WORD格式整理版

Recommend

JGShining

解答：

#include #define M 1000 void main() {

int a ,b,n,j[M],i;

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

i=0;

while(iprintf(\"%d\",j[i]); i++;

printf(\"\\n\"); } }

1091 A+B for Input-Output Practice

(III)

Problem Description

Your task is to Calculate a + b.

Input

学习指导参考

WORD格式整理版

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 30

Author

lcy

Recommend

JGShining

解答：

#include main() {

int a,b;

scanf(\"%d %d\",&a,&b); while(!(a==0&&b==0)) {

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

学习指导参考

WORD格式整理版

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.

Sample Input

4 1 2 3 4 5 1 2 3 4 5 0

Sample Output

10 15

Author

lcy

Recommend

JGShining

解答：

学习指导参考

WORD格式整理版

#include int main() {

int n,sum,i,t;

while(scanf(\"%d\",&n)!=EOF&&n!=0) {

sum=0;

for(i=0;iscanf(\"%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

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

学习指导参考

WORD格式整理版

10 15

Author

lcy

解答：

#include main() {

int n,a,b,i,j,sum; sum=0;

while(scanf(\"%d\\n\",&n)!=-1) {

for(i=0;iscanf(\"%d\",&b); for(j=0;jscanf(\"%d\",&a); sum+=a; }

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

1094 A+B for Input-Output Practice

(VI)

Problem Description

Your task is to calculate the sum of some integers.

Input

学习指导参考

WORD格式整理版

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 main() {

int n,a,b,i,j,sum; sum=0;

while(scanf(\"%d\\n\",&n)!=-1) {

for(j=0;jscanf(\"%d\",&a); sum+=a; }

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

学习指导参考

WORD格式整理版

}

[ 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

学习指导参考

WORD格式整理版

main() {

int a,b;

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

学习指导参考

WORD格式整理版

Recommend

JGShining

解答：

int main() {

int a,b,i,j,l[1000],k; scanf(\"%d\",&i); getchar();

for(j=1;j<=i;j++) 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平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：

学习指导参考

WORD格式整理版

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

Input

输入数据有多组。每组数据的第一行为以正整数n(0Output

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

Sample Input

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

Sample Output

4

Author

lwg

代码：

#include #include #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;iscanf(\"%d%d\

学习指导参考

WORD格式整理版

arr[m][n+1]++;

if(countfor(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\}

int main() {

int num;

scanf(\"%d\ while(num) {

res(num);

scanf(\"%d\ }

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

学习指导参考

WORD格式整理版

Sample Output

0.50 0.60 0.88

Author

Speakless

Source

Gardon-DYGG Contest 2

Recommend

JGShining

代码：

#include #include

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));

if(fabs(lamda-1.0){

double res = (1-pow(lamda, n))/(1-pow(lamda, m+n)); printf(\"%.2lf\\n\ } } }

int main() {

int n, m; double p, q;

while(scanf(\"%d%d%lf%lf\ solve(n, m, p, q); }

return 0; }

学习指导参考

WORD格式整理版

1213 How Many Tables

Problem Description

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

Source

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

Recommend

Eddy

学习指导参考

WORD格式整理版

代码：#include #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;iif(start[i]!=0) return 0; return 1; }

int inSet(int index) {

int i;

for(i=0;iif(arr[i]==index) return 1; return 0; }

void deal() {

int i;

int space=0; for(i=0;iif(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(iif(start[i]==0) { i++; continue; } if(i==0) {

if(start[i]!=end[i]) { arr[res++]=start[i];

学习指导参考

WORD格式整理版

arr[res++]=end[i]; }

else arr[res++]=start[i]; start[i]=end[i]=0; } else {

for(j=0;jif(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\ while(num--) {

scanf(\"%d%d\

for(i=0;ireturn 0;

学习指导参考

WORD格式整理版

}

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 #include #define MAX 20000

学习指导参考

WORD格式整理版

int arr[MAX];

int main() {

int num,temp,i,flage;

int sum,start,end,max=-32768; scanf(\"%d\ while(num!=0) {

memset(arr,0,MAX*sizeof(int)); for(i=0;iscanf(\"%d\ sum=0; temp=0; max=-32768; flage=0;

for(i=0;iif(arr[i]>=0) flage=1; sum+=arr[i];

if(maxif(flage) printf(\"%d %d %d\\n\ else printf(\"0 %d %d\\n\ scanf(\"%d\ }

return 0; }

1232 畅通工程

Problem Description

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

Input

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 注意:两个城市之间可以有多条道路相通,也就是说 3 3

学习指导参考

WORD格式整理版

1 2 1 2 2 1

这种输入也是合法的

当N为0时，输入结束，该用例不被处理。

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

#include #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++) {

学习指导参考

WORD格式整理版

for(j=0;jif(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; //从第一组元素开始继续遍历 } }

for(j=0;jif(res[arr[j][0]]*res[arr[j][1]]==0) break; //遇到首或尾没有归类的情况的时候跳出

if(jelse break; //如果当前数据全部归类则跳出所有循环 for(j=0;jif(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\ else if(rest==0) {

if(set==1) printf(\"0\\n\"); else printf(\"%d\\n\ }

else printf(\"%d\\n\}

int main() {

int i;

scanf(\"%d\ while(n) {

scanf(\"%d\

for(i=0;iscanf(\"%d\ }

学习指导参考

WORD格式整理版

return 0; }

2000 ASCII码排序

Problem Description

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

Input

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

Output

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

Sample Input

qwe asd zxc

Sample Output

e q w a d s c x z

Author

lcy

Source

C语言程序设计练习（一）

Recommend

JGShining

解答：

#include

学习指导参考

WORD格式整理版

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(bprintf(\"%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)

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

2001 计算两点间的距离

Problem Description

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

Input

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

Output

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

学习指导参考

WORD格式整理版

Sample Input

0 0 0 1 0 1 1 0

Sample Output

1.00 1.41

Author

lcy

Source

C语言程序设计练习（一）

Recommend

JGShining

解答：

#include #include main() {

double a,b,c,d,s;

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

根据输入的半径值，计算球的体积。

学习指导参考

WORD格式整理版

Input

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

Output

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

Sample Input

1 1.5

Sample Output

4.1 14.137 Hint

#define PI 3.1415927

Author

lcy

Source

C语言程序设计练习（一）

Recommend

JGShining

解答：

#include #define PI 3.1415927 main() {

double a,v;

while(scanf(\"%lf\",&a)!=EOF) {

v=4*PI*a*a*a/3;

printf(\"%.3lf\\n\",v); } }

学习指导参考

WORD格式整理版

2003 求绝对值

Problem Description

求实数的绝对值。

Input

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

Output

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

Sample Input

123

-234.00

Sample Output

123.00 234.00

Author

lcy

Source

C语言程序设计练习（一）

Recommend

JGShining

解答：

#include main() {

double a;

while(scanf(\"%lf\",&a)!=EOF) {

学习指导参考

WORD格式整理版

if(a<0) a=-a;

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

2004 成绩转换

Problem Description

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

Input

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

Output

对于每组输入数据，输出一行。如果输入数据不在0~100范围内，请输出一行：“Score error!”。

Sample Input

56 67 100 123

Sample Output

E D A

Score is error!

Author

lcy

学习指导参考

is WORD格式整理版

Source

C语言程序设计练习（一）

Recommend

JGShining

解答：

#include 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

学习指导参考

WORD格式整理版

Sample Output

20 71

Author

lcy

Source

C语言程序设计练习（一）

Recommend

JGShining

解答：

#include 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;

学习指导参考

WORD格式整理版

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; 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

学习指导参考

WORD格式整理版

Sample Output

3 15

Author

lcy

Source

C语言程序设计练习（一）

Recommend

JGShining

解答：

#include main() {

int n,s,i,a;

while(scanf(\"%d\",&n)!=EOF) {

s=1;

for(i=0;iscanf(\"%d\",&a); if(a%2==1) s=s*a; else ; }

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

2007 平方和与立方和

Problem Description

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

学习指导参考

WORD格式整理版

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 int main() {

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);

学习指导参考

WORD格式整理版

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语言程序设计练习（二）

Recommend

JGShining

学习指导参考

WORD格式整理版

解答：

#include

int main() {

int n,i,b1,b2,b3; double a[101];

while(scanf(\"%d\",&n)!=EOF && n!=0) {

for(i=0;ifor(i=0;iif(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

学习指导参考

WORD格式整理版

Sample Output

94.73 3.41

Author

lcy

Source

C语言程序设计练习（二）

Recommend

JGShining

解答：

#include #include main() {

double n,m,s,w,i;

while(scanf(\"%lf%lf\",&n,&m)!=EOF) { s=n;

for(i=1;in=sqrt(n); s=s+n; }

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

2010 水仙花数

Problem Description

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

学习指导参考

WORD格式整理版

Input

输入数据有多组，每组占一行，包括两个整数m和n（100<=m<=n<=999）。

Output

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

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

Sample Input

100 120 300 380

Sample Output

no

370 371

Author

lcy

Source

C语言程序设计练习（二）

Recommend

JGShining

解答：

#include 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)

学习指导参考

WORD格式整理版

{

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) {

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项的和。

学习指导参考

WORD格式整理版

Output

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

Sample Input

2 1 2

Sample Output

1.00 0.50

Author

lcy

Source

C语言程序设计练习（二）

Recommend

JGShining

解答：

#include #include main() {

double m,n,i,s,j,k,a;

while(scanf(\"%lf\",&m)!=EOF) {

for(i=0;is=0;

scanf(\"%lf\",&n); for(j=1;j<=n;j++)

s=s+1/j*pow(-1,j+1);

学习指导参考

WORD格式整理版

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

} }

2012 素数判定

Problem Description

对于表达式n^2+n+41，当n在（x,y）范围内取整数值时（包括x,y）(-39<=xInput

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

Output

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

Sample Input

0 1 0 0

Sample Output

OK

Author

lcy

Source

C语言程序设计练习（二）

Recommend

JGShining

学习指导参考

WORD格式整理版

解答：

#include 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;jd=k%j; if(d==0) w++; } }

if(w==0)

printf(\"OK\\n\"); else

printf(\"Sorry\\n\");

} }

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

Problem Description

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

Input

输入数据有多组，每组占一行，每行的第一个数是n(2学习指导参考

WORD格式整理版

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 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;iscanf(\"%d\",&a[i]); k++; b=a[0]; w=w+a[i]; }

学习指导参考

WORD格式整理版

for(i=0;iif(a[i]>s) s=a[i]; }

for(i=1;iif(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

学习指导参考

WORD格式整理版

Source

C语言程序设计练习（三）

Recommend

lcy

解答：

#include 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;is=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(\" \");

学习指导参考

WORD格式整理版

printf(\"%d\",k); r=r+1; }

} s=0;

if(w!=0) {

for(j=0;js=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

学习指导参考

WORD格式整理版

5 5 4 3 2 1 0

Sample Output

1 2 3 4 1 4 3 2 5

Author

lcy

Source

C语言程序设计练习（三）

Recommend

lcy

解答：

#include main() {

int n,a[100],i,j,k,s,w;

while(scanf(\"%d\",&n)!=EOF&&n!=0) {

j=0;

for(i=0;iscanf(\"%d\",&a[i]); k=a[0]; }

for(i=0;iif(k>a[i]) {

k=a[i]; j=i; } }

w=a[0];

学习指导参考

WORD格式整理版

a[0]=k; a[j]=w;

for(i=0;iprintf(\"%d\",a[i]); if(n-i!=1) printf(\" \"); }

printf(\"\\n\"); } }

2017 字符串统计

Problem Description

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

Input

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

Output

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

Sample Input

2

asdfasdf123123asdfasdf asdf111111111asdfasdfasdf

Sample Output

6 9

Author

lcy

解答：

学习指导参考

WORD格式整理版

#include main() {

int n,i,j,a; char s[1000];

while(scanf(\"%d\",&n)!=EOF) {

getchar();

for(i=0;igets(s); a=0;

for(j=0;s[j]!='\\0';j++) {

if((s[j]<='9')&&(s[j]>='0')) a=a+1; }

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

学习指导参考

WORD格式整理版

Sample Output

1 2 3 4

Author

lcy

Source

C语言程序设计练习（三）

Recommend

lcy

解答：

#include main() {

int n,m,a[100],b[100],i,j,k,s,w,d; scanf(\"%d%d\",&n,&m); while(!(n==0&&m==0)) {

w=0;

for(i=0;iif(mprintf(\"%d\",m); for(j=0;jprintf(\" \");

printf(\"%d\",a[j]); } } else {

for(j=0;jif(m>a[j]) w=w+1;

学习指导参考

WORD格式整理版

}

for(j=0;jprintf(\"%d\",a[j]); printf(\" \"); }

printf(\"%d\",m); for(j=w;jprintf(\" \"); printf(\"%d\",a[j]); } }

printf(\"\\n\");

scanf(\"%d%d\",&n,&m); } }

2020 绝对值排序

Problem Description

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

Input

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

Output

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

Sample Input

3 3 -4 2 4 0 1 2 -3 0

Sample Output

-4 3 2

学习指导参考

WORD格式整理版

-3 2 1 0

Author

lcy

Source

C语言程序设计练习（三）

Recommend

lcy

解答：

#include 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;ifor(j=0;jc=0;

for(i=0;iif(a[i]<0) m=-a[i];

else m=a[i]; if(c<=m) { c=m;

b[j]=a[i]; k=i; }

}

a[k]=0; if(f)

printf(\" \");

printf(\"%d\",b[j]);

学习指导参考

WORD格式整理版

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

Author

lcy

Source

学习指导参考

WORD格式整理版

C语言程序设计练习（四）

Recommend

lcy

解答：

#include 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;iscanf(\"%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 人见人爱A+B

Problem Description

HDOJ上面已经有10来道A+B的题目了，相信这些题目曾经是大家的最爱，希望今天的这个A+B能给大家带来好运，也希望这个题目能唤起大家对ACM曾经的热爱。

这个题目的A和B不是简单的整数，而是两个时间，A和B 都是由3个整数组成，分别表示时分秒，比如，假设A为34 45 56，就表示A所表示的时间是34小时 45分钟 56秒。

Input

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

学习指导参考

WORD格式整理版

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 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{ 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) {

学习指导参考

WORD格式整理版

c=c-60; j=j+1; }

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 今年暑假不AC

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

Problem Description

“今年暑假不AC？” “是的。”

“那你干什么呢？” “看世界杯呀，笨蛋！” “@#$%^&*%...”

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

Input

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

Output

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

学习指导参考

WORD格式整理版

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

Source

ACM程序设计期末考试（2006/06/07）

Recommend

lcy

代码：

#include #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\}

void prc() {

int i,j;

for(i=0;iscanf(\"%d %d\ for(i=0;i学习指导参考

WORD格式整理版

{

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]; } } res(); }

int main() {

scanf(\"%d\ while(num) {

prc();

scanf(\"%d\ }

return 0; }

2039 三角形

Problem Description

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

Input

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

Output

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

学习指导参考

WORD格式整理版

Sample Input

2 1 2 3 2 2 2

Sample Output

NO YES

Author

linle

Source

2005实验班短学期考试

Recommend

lcy

解答：

#include main() {

double n,a,b,c,i;

while(scanf(\"%lf\",&n)!=EOF) {

for(i=0;iscanf(\"%lf%lf%lf\",&a,&b,&c); if((a+b)>c&&(b+c)>a&&(a+c)>b) printf(\"YES\\n\"); else

printf(\"NO\\n\"); } } }

2040 亲和数

学习指导参考

WORD格式整理版

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；A,B <= 600000 ;

Output

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

Sample Input

2

220 284 100 200

Sample Output

YES NO

Author

linle

Source

2005实验班短学期考试

Recommend

lcy

学习指导参考

其中 0 <= WORD格式整理版

解答：

#include main() {

double n,a,b,c,i;

while(scanf(\"%lf\",&n)!=EOF) {

for(i=0;iscanf(\"%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难题:

有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.

以上就是著名的RPG难题.

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

Input

输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成，(0Output

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

Sample Input

1 2

学习指导参考

WORD格式整理版

Sample Output

3 6

Author

lcy

Source

递推求解专题练习（For Beginner）

Recommend

lcy

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

代码：#include

int main() {

__int i,arr[51]; __int 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\ {

printf(\"%Id\\n\ }

return 0; }

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

Problem Description

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

学习指导参考

WORD格式整理版

首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排; 然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个. 最后,揭开盖头,如果找错了对象就要当众跪搓衣板...

看来做新郎也不是容易的事情...

假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.

Input

输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据，每行包含两个整数N和M(1Output

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

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

int main(void)

学习指导参考

WORD格式整理版

{

int i, m, n;

__int 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]); }

scanf(\"%d\

while (i-- && scanf(\"%d%d\

printf(\"%Id\\n\ return 0; }

2056 Rectangles

Problem Description

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

学习指导参考

WORD格式整理版

Recommend

linle

代码：

#include

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; tmpy1=(y1>y3)?y1:y3; tmpy2=(y2>y4)?y4:y2; if(tmpx1printf(\"%.2lf\\n\ 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\ {

res(x1,y1,x2,y2,x3,y3,x4,y4); }

return 0; }

2073 无限的路

Problem Description

甜甜从小就喜欢画图画，最近他买了一支智能画笔，由于刚刚接触，所以甜甜只会用它来画

直线，于是他就在平面直角坐标系中画出如下的图形：

学习指导参考

WORD格式整理版

甜甜的好朋友蜜蜜发现上面的图还是有点规则的，于是他问甜甜：在你画的图中，我给你两

个点，请你算一算连接两点的折线长度（即沿折线走的路线长度）吧。

Input

第一个数是正整数N（≤100）。代表数据的组数。

每组数据由四个非负整数组成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.6 54985.047 0.000

Author

Lily

Source

浙江工业大学网络选拔赛

Recommend

学习指导参考

WORD格式整理版

linle

代码：

#include #include #include using namespace std; int main(void) {

int n, x[3], y[3]; double s;

scanf(\"%d\

while (n-- && scanf(\"%d%d%d%d\ {

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\ 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\ } }

return 0; }

2084 数塔

Problem Description

在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

学习指导参考

WORD格式整理版

已经告诉你了，这是个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

#include #define MAX 101

int arr[MAX][MAX][2]; void res()

学习指导参考

WORD格式整理版

{

int n; int i,j;

memset(arr,0,MAX*MAX*sizeof(int)); scanf(\"%d\

for(i=0;ifor(j=0;j<=i;j++) { scanf(\"%d\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\}

int main() {

int num;

scanf(\"%d\

while(num--) { res(); } return 0; }

2201 熊猫阿波的故事

Problem Description

凡看过功夫熊猫这部电影的人都会对影片中那只憨憨的熊猫阿波留下相当深的印象，胖胖的熊猫阿波自从打败了凶狠强悍的雪豹泰龙以后，在和平谷的地位是越来越高，成为谷中第一的功夫大师。并因此他父亲经营的面馆的生意也越来越好，店里每天都会有许多慕名而来吃面和想拜阿波为师的人。

一日，阿波收到了一张请柬，请柬里说在遥远的美国将召开全球比武大会，特邀请阿波过去做嘉宾。阿波当然很高兴，因为自己长这么大都还没出过和平谷，更何况是出国去那遥远的美国。于是他托人买了当晚的机票，阿波来到机场发现其他乘客们正准备按机票上的号码(1,2,3,.....,n)依次排队上飞机，由于阿波是第一次坐飞机，所以他想先一步登机，因此他插队第一个登上了飞机，并且他也不看机票，随机的选择了一个座位坐下了。乘客们都很气氛，他们想：既然阿波都不遵守规定，那么我为什么要遵守呢？因此后面所有的人也都随意地找了位置坐下来，并且坚决不让座给其他的乘客。 现在的问题是这样的：在这样的情况下，第i个乘客(除去熊猫阿波外)坐到原机票位置的概率是多少?

学习指导参考

WORD格式整理版

Input

输入包含多组测试数据，每组数据占一行，包含两个整数，分别是n和m(n>=m)，n表示共有n个乘客(包括阿波)，m表示第m个乘客。

Output

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

每组输出占一行。

Sample Input

2 1 11 3

Sample Output

0.50 0.09

Author

Eddy

Recommend

lcy

代码：

#include using namespace std;

int main() {

double n, m;

while( cin >> n >> m) {

double k = 1/ n; printf(\"%.2f\ cout << endl; }

return 0; }

2212 DFS

Problem Description

A DFS(digital factorial sum) number is found by summing the factorial of every digit of a positive integer.

学习指导参考

WORD格式整理版

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, 21474837] ).

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

Output

Output all the DFS number in increasing order.

Sample Output

1 2 ......

Author

zjt

Recommend

Lcy

代码：

#include main() {

printf(\"1\\n2\\n145\\n40585\\n\"); }

2304 Electrical Outlets

Problem Description

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.

学习指导参考

WORD格式整理版

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

Source

NCPC2005

Recommend

zty

代码：

#include int main() {

int sum,num,t,n,i; scanf(\"%d\ while(t--) {

scanf(\"%d\ sum=0;

for(i=0;iscanf(\"%d\ sum+=num;

学习指导参考

WORD格式整理版

}

printf(\"%d\\n\ }

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.

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.

学习指导参考

WORD格式整理版

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 main() {

int n,i,s,x,y,a;

while(scanf(\"%d\ {

x=0,y=1000;

for(i=1,s=0;i<=n;i++) {

scanf(\"%d\ s+=a; if(a>x) x=a; if(aprintf(\"%d\\n\ } }

2317 Nasty Hacks

Problem Description

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

学习指导参考

WORD格式整理版

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

666

that the input will follow these restrictions: -10 ≤ r, e ≤ 10 and 0 ≤ c ≤ 10.

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 main() {

int i;

long a[3],k; scanf(\"%d\ while(i--) {

scanf(\"%ld%ld%ld\ k=a[1]-a[2]; if(a[0]printf(\"advertise\\n\");

学习指导参考

WORD格式整理版

}

}

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）——测试帐号（杭州）

学习指导参考

WORD格式整理版

Recommend

lcy

代码：

#include int main() {

int a,b,c,d,sum;

while(scanf(\"%d%d%d%d\ {

sum=a*(a-1)/2*b; if(sum==d)

printf(\"%d\\n\ else

printf(\"%d\\n\ }

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

学习指导参考

WORD格式整理版

Source

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

Recommend

lcy

代码：

#include main() {

int n,m,i,j; scanf(\"%d\ while(n--) {

scanf(\"%d\ for(i=0;ifor(j=0;j2501 Tiling_easy version

Problem Description

有一个大小是 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

学习指导参考

WORD格式整理版

3 171 2731

Source

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

Recommend

lcy

代码：

#include 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]; scanf(\"%d\ while(t--) {

scanf(\"%d\

printf(\"%d\\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

学习指导参考

WORD格式整理版

3 1 2 3

Sample Output

1 3 8

Source

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

Recommend

lcy

代码： main() {

int n,m;

scanf(\"%d\ while(n--) {

scanf(\"%d\

printf(\"%d\\n\ } }

2503 a/b + c/d

Problem Description

给你2个分数，求他们的和，并要求和为最简形式。

Input

输入首先包含一个正整数T（T<=1000），表示有T组测试数据，然后是T行数据，每行包含四个正整数a,b,c,d（0Output

对于每组测试数据，输出两个整数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

学习指导参考

WORD格式整理版

Source

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

Recommend

lcy

代码：

#include using namespace std; int (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\ t1=a*d+b*c; t2=b*d;

t=(t1,t2);

printf(\"%d %d\\n\ }

return 0; }

2504 又见GCD

Problem Description

有三个正整数a,b,c(0学习指导参考

WORD格式整理版

Input

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

Output

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

Sample Input

2 6 2 12 4

Sample Output

4 8

Source

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

Recommend

lcy

代码：

#include int (int a,int b) {

return a%b==0 ? b : (b,a%b); }

int main() {

int n,a,b,c,temp,i; scanf(\"%d\ while(n--){

scanf(\"%d%d\ temp=a/b;

for(i=2;ic=b*i;

printf(\"%d\\n\ }

return 0; }

学习指导参考

WORD格式整理版

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 #include int main() {

int T, n, m, i; double num;

scanf(\"%d\ while (T--) {

scanf(\"%d%d\ num=1;

for (i=1;i<=m;i++)

num*=(1.0*(n-i+1)/i);

printf(\"%.f\\n\ }

学习指导参考

WORD格式整理版

return 0; }

方法二：

这里用到的数学公式为：

cc

m=

m

+c

m（注意用一维数组来计算此式的技巧）

nn1

n1

代码：

#include

#include #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\

memset(arr,0,MAX*sizeof(int)); while(num--) {

scanf(\"%d%d\

printf(\"%ld\\n\ }

return 0; }

2520 我是菜鸟，我怕谁 学习指导参考

WORD格式整理版

Problem Description

lin2144是一只小菜鸟，都是笨鸟先飞，lin2144想来个菜鸟先飞，他从0点出发

一开始的飞行速度为1m/s，每过一个单位时间lin2144的飞行速度比上一个单位时间的飞行速度快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 int main() {

int t;

__int n,k; scanf(\"%d\ while(t--) {

scanf(\"%Id\ k=n*n;

if(k>10000)

printf(\"%Id\\n\ else

printf(\"%Id\\n\ }

return 0; }

学习指导参考

WORD格式整理版

2521 反素数

Problem Description

反素数就是满足对于任意i(0Input

第一行输入n,接下来n行测试数据

输入包括a,b, 1<=a<=b<=5000,表示闭区间[a,b].

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) {

学习指导参考

WORD格式整理版

c[j]++;

} }

scanf(\"%d\ for(i=0;imax=0;

scanf(\"%d%d\ for(j=a;j<=b;j++) if(c[j]>max) {

max=c[j];t=j; }

printf(\"%d\\n\ }

return 0; }

2522 A simple problem

Problem Description

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

学习指导参考

WORD格式整理版

Recommend

gaojie

代码：

#include #include char b[500001]={0}; int main() {

int t,i,d,n,s; scanf(\"%d\ while(t--) {

memset(b,0,sizeof(b)); scanf(\"%d\ if(n<0) {

printf(\"-\"); n=-n; }

if(n==1) {

printf(\"%d\\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\ d=d*10-s*n; }

printf(\"\\n\"); } }

学习指导参考

WORD格式整理版

2523 SORT AGAIN

Problem Description

给你N个整数,x1,x2...xn，任取两个整数组合得到|xi-xj|,(0Input

输入数据首先包含一个正整数C，表示包含C组测试用例.

每组测试数据的第一行包含两个整数N，K。(1Output

对于每组测试数据，请输出第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 #include using namespace std; int main() {

int n,m,t,a[1001],b[2002],w,i,j; scanf(\"%d\ while(n--) {

scanf(\"%d%d\ memset(b,-1,sizeof(b)); w=0;

for(i=0;i学习指导参考

WORD格式整理版

scanf(\"%d\ for(i=m-1;i>=0;i--) for(j=0;jb[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\ break; } } } }

return 0; }

2524 矩形A + B

Problem Description

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

Input

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

Output

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

Sample Input

学习指导参考

WORD格式整理版

2 1 2 2 4

Sample Output

3 30

Source

HDU 2008-10 Programming Contest

Recommend

gaojie

代码：

#include int main() {

int t, n, m; scanf(\"%d\ while (t--) {

scanf(\"%d%d\

printf(\"%d\\n\ }

return 0; }

2535 Vote

Problem Description

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

学习指导参考

WORD格式整理版

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

int main() {

int n, t, c,f[102], i, j, k;

while(scanf(\"%d\ {

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

学习指导参考

WORD格式整理版

{

scanf(\"%d\ }

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

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\ }

return 0; }

2537 8球胜负

Problem Description

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

学习指导参考

WORD格式整理版

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

学习指导参考

WORD格式整理版

Recommend

lcy

代码：

#include using namespace std; char dig[20]; int main() {

int n;

while(cin>>n&&n) {

int sum1=0,sum2=0; for(int i=0;icin>>dig[i];

if(dig[i]=='R') sum1++; if(dig[i]=='Y') sum2++; }

if(sum1<7&&sum2<7&&dig[n-1]=='L'||sum1==7&&sum2<7||sum1==7&&sum2==7&&dig[n-1]=='B')

cout<<\"Red\"<cout<<\"Yellow\"<}

return 0; }

2539 点球大战

Problem Description

在足球比赛中，有不少赛事，例如世界杯淘汰赛和欧洲冠军联赛淘汰赛中，当比赛双方经过正规比赛和加时赛之后仍然不分胜负时，需要进行点球大战来决定谁能够获得最终的胜利。点球大战的规则非常简单，两方轮流派出球员罚点球，每方各罚5个。当5轮点球结束以后如果仍然不分胜负，则进入一轮定胜负的阶段。两方各派一名球员罚点球，直到有一方罚进而另一方没有进为止。

在北美职业冰球联赛中，也有点球大战。与足球的规则不同的是，它只先罚3轮点球，随后就进入一轮定胜负的阶段，而其他的规则完全一样。

在本题中，输入将给出每次点球是否罚进，而你的任务则是输出一个“比分板”。

学习指导参考

WORD格式整理版

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)。

学习指导参考

WORD格式整理版

Source

UESTC 6th Programming Contest Online

Recommend

lcy

代码：

#include #include int main() {

int T,a[9],b[9],t,i,j,k,len,sum1,sum2; char s[100];

while(scanf(\"%d\ {

getchar(); j=k=0;

for(t=0;tgets(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; }

学习指导参考

WORD格式整理版

}

sum1=sum2=0;

for(i=1;i<=j;i++)

printf(\"%d \ printf(\"Score\\n\"); for(i=0;iif(a[i]==0)

printf(\"X \"); else

printf(\"O \"); sum1+=a[i]; }

printf(\"%d\\n\ for(i=0;iif(b[i]==0)

printf(\"X \"); else

printf(\"O \"); sum2+=b[i]; } if(kprintf(\"- \"); printf(\"%d\\n\ } }

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

学习指导参考

WORD格式整理版

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

Output

输出剑气的最小伤害值M，保留小数点后一位 （可以使用.1lf）

Sample Input

2 0 0 3 4 4 0 0 3

Sample Output

5.0 5.0

Author

英雄哪里出来

Source

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

Recommend

lcy

代码：

#include #include int main() {

int t;

double a,b,c,d,ans; scanf(\"%d\ while(t--) {

scanf(\"%lf%lf%lf%lf\

ans = sqrt(((a-c)*(a-c)+(b-d)*(b-d))*1.0); printf(\"%.1lf\\n\ } }

2548 两军交锋

Problem Description

话说辽军与MCA相峙多年,终于在一个秋日的早晨爆发了一次大规模的冲突.情况是这样子

学习指导参考

WORD格式整理版

的,当天上午,由耶律-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

Author

Teddy

Source

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

Recommend

lcy

代码：

#include int main() {

int t;

double u,v,w,l,ans; scanf(\"%d\ while(t--) {

scanf(\"%lf%lf%lf%lf\ ans = w*l/(u+v);

printf(\"%.3lf\\n\ } }

学习指导参考

WORD格式整理版

2549 壮志难酬

Problem Description

话说MCA山上各路豪杰均出山抗敌，去年曾在江湖威名显赫的，江湖人称<万军中取上将首级舍我其谁>的甘露也不甘示弱，“天将降大任于斯人也，必先劳其筋骨，饿其体肤，空乏其身”他说。可惜，由于去年取上将首级时不慎右手右关节第七次骨折，养伤达一年之久，空有一腔抱负却壮志难酬，如今天下危亡，习武之人又怎能袖手旁观，于是他决定出山协助威士忌共抗辽贼，这时他的对头枫冰叶子出现，两人都是水属性，但由于十年前的一场恩怨（这是后话）势成水火。

枫冰叶子要求甘露回答一个问题，否则不让他离开，可惜甘露绞尽脑汁未果，希望你来帮他解决，助他完成大业。

问题是这样的：给你一个小数x，让你算出小数点后第n位是什么，(1 <= n <= 6)

Input

首先输入一个t,表示有t组数据，跟着t行：

每行输入一个小数（输入数据保证一定是a.b的形式,为了简单化问题，没有循环小数的情况）

然后跟一个n,表示小数点后第几位

Output

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

Sample Input

3 1.234 1 2.345 2 3.456 3

Sample Output

2 4 6

Author

英雄哪里出来

Source

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

Recommend

lcy

代码：

#include

学习指导参考

WORD格式整理版

#include char x[99]; int main() {

int i,n,t,len,ans; scanf(\"%d\

while(t--&&scanf(\"%s %d\ {

len = strlen(x); for(i=0; i2550 百步穿杨

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 ) 输入数据保证每一个Ai都是不同的.

Output

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

Sample Input

1 4 3 4 4 5 5 6 6 7

Sample Output

>+-+> >+-+> >+-+> >+-+> >+--+> >+--+> >+--+> >+--+> >+--+> >+---+> >+---+> >+---+> >+---+> >+---+> >+---+> >+----+> >+----+> >+----+> >+----+> >+----+> >+----+> >+----+>

学习指导参考

WORD格式整理版

Author

Teddy

Source

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

Recommend

lcy

代码：

#include using namespace std;

char a[40]=\">+\"; int b[2][51]; int main() {

int i,j,n,t; scanf(\"%d\

while(t--&&scanf(\"%d\ {

for(i=0; iscanf(\"%d%d\ for(i=0; ib[0][j]) {

swap(b[0][i],b[0][j]); swap(b[1][i],b[1][j]); }

for(i=0; ifor(j=2; ja[j] = '+'; a[j+1] = '>'; a[j+2] = '\\0';

for(j=0; j学习指导参考

WORD格式整理版

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 int num[1001]={0}; int main() {

int n,i,m;

学习指导参考

WORD格式整理版

for(i=1;i<1001;i++) //这里先把每个月逐青种的竹子总数计算出来 num[i]=num[i-1]+i*i*i; //以后的数据处理就可以直接找这的计算结果 scanf(\"%d\ while(n--) {

scanf(\"%d\ for(i=0;;i++)

if(m>num[i]&&m<=num[i+1]) //i遍历找到符合条件的数 break; printf(\"%d\\n\ } }

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均为实数

学习指导参考

WORD格式整理版

Output

输出 v*u-s*u-s*v 的值，为了简单起见，如果是小数，直接取整

比如：答案是1.7 则输出 1

Sample Input

1 1 2

Sample Output

1

Author

英雄哪里出来

Source

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

Recommend

lcy

代码：

#include #include

int main() {

int t;

double s,u,v,ans; scanf(\"%d\

while(t--&&scanf(\"%lf%lf\ {

v = atan(1.0/s)-atan(1.0/u); v = 1.0/tan(v); ans = v*u-s*u-s*v; printf(\"%.0lf\\n\ } }

2553 N皇后问题

Problem Description

学习指导参考

WORD格式整理版

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

Input

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

Output

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

Sample Input

1 8 5 0

Sample Output

1 92 10

Author

cgf

Source

2008 HZNU Programming Contest

Recommend

lcy

代码：

#include

int a[11]={0,1,0,0,2,10,4,40,92,352,724}; int main() {

int n;

while(scanf(\"%d\ printf(\"%d\\n\}

2554 N对数的排列问题

Problem Description

有N对双胞胎，他们的年龄分别是1，2，3，……，N岁，他们手拉手排成一队到野外去玩，要经过一根独木桥，为了安全起见，要求年龄大的和年龄小的排在一起，好让年龄大的保护年龄小的，然后从头到尾，每个人报告自己的年龄，就得到了一个年龄的序列。比如有4对双胞胎，他们报出来的年龄序列是：41312432。突然，他们中间最聪明的小明发现了一个有

学习指导参考

WORD格式整理版

趣的现象，原来，这个年龄序列有一个规律，两个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

Recommend

lcy

代码：

#include int main() {

int n;

while(scanf(\"%d\

puts((n+1)/2%2?\"N\":\"Y\"); }

2555 人人都能参加第30届校田径运

动会了

Problem Description

学习指导参考

WORD格式整理版

杭州师范大学第29届田径运动会的闭幕了，本届运动会是我校规模最大，参赛人数最多的一次运动会。在两天半时间里，由学生、教工组成的61支代表队共26名运动员参加了比赛。比赛期间，运动健儿赛出了风格、赛出了水平，共有9人次打破6项校纪录。

我们寝室的4名同学是我班最卖力的啦啦队员，每天都在看台上为班级里的运动员们加油助威，为我班获得精神文明奖立下了汗马功劳。可是遗憾的是，与我校的其他近2万名同学一样，我们自己不能上场表演 ：(

于是，我们4名同学为下一届校运会发明了一种人人都能参加的比赛项目：

在地面上有N 个大小不等的长方形陷阱，每个陷阱的周长各不相同，每个参赛者都有一个沙包，闭上眼睛把它扔向地面，如果沙包掉到了某个陷阱里，那么这个参赛者根据这个陷阱的周长长度（如50米），绕跑道跑陷阱的周长长度（如50米），如果沙包没有掉到任何一个陷阱里，那么恭喜你，你跑0米。

有m<20000个同学参加了比赛，为了给跑步跑得最多的三位同学(冠军、亚军、季军)颁发安慰奖，必须给这m个同学的跑的长度按从多到少排序。

如下图一样的坐标系与长方形，这些长方形（陷阱）的四条边都与X轴或Y轴平行，它们之间互不相交，它们的左上角顶点的坐标与右下角顶点的坐标已知，给定一个你扔出去的沙包（看作是一个点）的坐标，可以得到你要跑的距离。（注意，这里的坐标值都不超过10000）

Input

第一行是两个正整数m<20000，n<100，它表示有m 个同学参加了扔沙包比赛，有n个陷阱。 接下去m行是m个同学扔出去的沙包的坐标，每一行都是两个正整数。

接下去的n行是陷阱的坐标，每行有4个正整数，它们从左到右分别是：陷阱左下角顶点的横坐标的值、陷阱左下角顶点的纵坐标的值，陷阱右上角顶点的横坐标的值、陷阱右上角顶点的纵坐标的值。

Output

学习指导参考

WORD格式整理版

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

代码：

#include #include 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);

学习指导参考

WORD格式整理版

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\ for(mi=0;mip[mi]=&player[mi];

scanf(\"%d%d\ p[mi]->len=0; }

for(ni=0;niscanf(\"%d%d%d%d\ 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;miprintf(\"%d\\n\ }

return 0; }

void meters(PLAYER *p[],int m,RECTANGLE rec[],int n) {

int ni,mi;

for(mi=0;miif(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学习指导参考

WORD格式整理版

k=i;

for(j=i+1;jif(p[k]->lenlen) k=j; t=p[i];p[i]=p[k];p[k]=t; } }

2560 Buildings

Problem Description

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.

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

学习指导参考

WORD格式整理版

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 int main() {

int n,a,b,m,t,sum=0; scanf(\"%d\ while(n--) {

scanf(\"%d%d\ t=a*b; sum=0; while(t--) {

scanf(\"%d\ if(m==1) sum++; }

printf(\"%d\\n\ } }

2561 Problem Description

求n个整数中倒数第二小的数。

学习指导参考

第二小整数WORD格式整理版

每一个整数都看成一个数，比如，有三个数分别是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 main() {

int T,i,n,a,f,s,m;

for(scanf(\"%d\ {

scanf(\"%d\ f=100; s=100;

for(i=0;iscanf(\"%d\ if(a<=s) s=a;

if(s<=f) {m=s;s=f;f=m;} }

printf(\"%d\\n\

学习指导参考

WORD格式整理版

} }

2562 奇偶位互换

Problem Description

给定一个长度为偶数位的0,1字符串，请编程实现串的奇偶位互换。

Input

输入包含多组测试数据；

输入的第一行是一个整数C，表示有C测试数据；

接下来是C组测试数据，每组数据输入均为0,1字符串，保证串长为偶数位(串长<=50)。

Output

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

Sample Input

2 0110 1100

Sample Output

1001 1100

Author

yifenfei

Source

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

Recommend

yifenfei

代码：

#include #include int main() {

int n,i;

char s[100],temp; scanf(\"%d\ while(n--) {

学习指导参考

WORD格式整理版

scanf(\"%s\

for(i=0;itemp=s[i]; s[i]=s[i+1]; s[i+1]=temp; }

for(i=0;ireturn 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

学习指导参考

WORD格式整理版

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

Recommend

yifenfei

代码：

#include 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\ }

return 0; }

25 词组缩写

Problem Description

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

Input

输入的第一行是一个整数T，表示一共有T组测试数据；

接下来有T行，每组测试数据占一行，每行有一个词组，每个词组由一个或多个单词组成；每组的单词个数不超过10个，每个单词有一个或多个大写或小写字母组成； 单词长度不超过10，由一个或多个空格分隔这些单词。

Output

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

学习指导参考

WORD格式整理版

Sample Input

1 end of file

Sample Output

EOF

Author

lemon

Source

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

Recommend

yifenfei

代码：

#include\"stdio.h\" int main() {

int t,i,n;

char str[120],a[13]; scanf(\"%d\ 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 {

学习指导参考

WORD格式整理版

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); } }

return 0; }

2565 放大的X

Problem Description

请你编程画一个放大的’X’。 如3*3的’X’应如下所示： X X X X X

5*5的’X’如下所示： X X X X X X X X X

Input

输入数据第一行是一个整数T，表示有T组测试数据； 接下来有T行，每行有一个正奇数n（3 <= n <= 79），表示放大的规格。

Output

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

Sample Input

2 3 5

Sample Output

学习指导参考

WORD格式整理版

X X X X X X X X X X X X X X

Author

lemon

Source

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

Recommend

yifenfei

代码：

#include #include using namespace std;

int main(int argc, char *argv[]) {

int a,n,t; int i,j,k,i1; cin>>t;

for(i1=0;i1cin>>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<<\" \";

学习指导参考

WORD格式整理版

}

cout<cout<return EXIT_SUCCESS; }

2566 统计硬币

Problem Description

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

Input

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

Output

对于每组测试数据，请输出可能的组合方式数； 每组输出占一行。

Sample Input

2 3 5 4 8

Sample Output

1 2

Author

lemon

Source

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

Recommend

yifenfei

代码：

#include void main() {

int n,m,i,j,k,num,T;

学习指导参考

WORD格式整理版

scanf(\"%d\ while(T--) {

scanf(\"%d%d\ 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\ } }

2567 寻梦

Problem Description

每个人的童年都可能梦想过自己成为一个英雄，尤其是喜欢武侠的男生，Yifenfei也不例外

童年的他常常梦想自己能成为一个绝世英雄，手拿一把灿灿发亮的宝剑，手挽一位长发飘逸的秀丽气质MM ^_^ ，散步于清幽的泉边小道，微风吹过，飘落两片枫叶。。。。。。 正由于成天陶醉于这种脱世的意境之中，导致此人老大不小依旧形单影只，每天只能在人潮中孤单上路。。。。。。

现在就让我们为这个可怜的人创造一个机会，权当假设yifenfei现在已经捕获一位MM的芳心，但该MM被并且极其可恶的大魔头（AC女之杀手 lemon）抓走。为了正义，为了MM，燃烧吧。。。。。。

好了，现在就正式开始我们的行程，接下来将有6关等待着yifenfei,让我们帮助他战胜的lemon大魔王吧。

来到大魔王居住的千年古墓前，呈现在yifenfei眼前的是墓碑上神秘的字符，经过仔细研究，发现原来这是开启古墓入口的方法。 墓碑上有2行字符串，其中第一个串的长度为偶数，现在要求把第2个串插入到第一个串的正，如此便能开启墓碑进入墓中。

学习指导参考

WORD格式整理版

Input

输入数据首先给出一个整数n，表示测试数据的组数。

然后是n组数据，每组数据2行，每行一个字符串，长度大于0，小于50，并且第一个串的长度必为偶数。

Output

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

Sample Input

2 HDCM UA Aw CFlo

Sample Output

HDUACM ACFlow

Author

yifenfei

Source

ACM程序设计期末考试081230

Recommend

yifenfei

学习指导参考

WORD格式整理版

代码：

#include #include main() {

int n,l1,l2,i,j; char a[100],b[50]; scanf(\"%d\ while(n--) {

for(i=0;i<50;i++) {a[i]=0;b[i]=0;} j=0;

scanf(\"%s %s\ l1=strlen(a); l2=strlen(b);

for(i=l1/2;ifor(i=l1/2;i2568 前进

Problem Description

轻松通过墓碑，进入古墓后，才发现里面别有洞天。

突然，Yifenfei发现自己周围是黑压压的一群蝙蝠，个个扇动翅膀正准备一起向他发起进攻！

形势十分危急！

好在此时的yifenfei已经不是以前那个经常被lemon抢走MM的菜鸟了！面对众多蝙蝠的嗜血狂攻，只见yifenfei使出轻灵的剑法，刷，刷，刷，瞬间搞定…… 现已知yifenfei使用了2招（剑招A和剑招B）：剑招A，一招能杀死一半的蝙蝠。但是如果当前的蝙蝠数为奇数，那么就必须先出一招剑招B杀死其中任意一个，使蝙蝠数为偶数，再出剑招A。

现在请问：杀死n只蝙蝠需要使出多少招剑招B？

学习指导参考

WORD格式整理版

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 main() {

学习指导参考

WORD格式整理版

int n,a,t;

scanf(\"%d\ while(n--) {

t=0;

scanf(\"%d\

while(a&&a%2==0) a/=2; while(a&&a%2) {

t++; a-=1;

while(a&&a%2==0) a/=2; }

printf(\"%d\\n\ } }

2569 彼岸

Problem Description

突破蝙蝠的包围，yifenfei来到一处悬崖面前，悬崖彼岸就是前进的方向，好在现在的yifenfei已经学过御剑术，可御剑轻松飞过悬崖。

现在的问题是：悬崖中间飞着很多红，黄，蓝三种颜色的珠子，假设我们把悬崖看成一条长度为n的线段，线段上的每一单位长度空间都可能飞过红，黄，蓝三种珠子，而yifenfei必定会在该空间上碰到一种颜色的珠子。如果在连续3段单位空间碰到的珠子颜色都不一样，则yifenfei就会坠落。 比如经过长度为3的悬崖，碰到的珠子先后为 “红黄蓝”，或者 “蓝红黄” 等类似情况就会坠落，而如果是 “红黄红” 或者 “红黄黄”等情况则可以安全到达。 现在请问：yifenfei安然抵达彼岸的方法有多少种？

学习指导参考

WORD格式整理版

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 #include using namespace std; int result[40];

学习指导参考

WORD格式整理版

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 Parity

Problem Description

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 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

学习指导参考

WORD格式整理版

zty

代码：

#include using namespace std; #include int main() {

int i,flag,count,size; char a[100000],c;

while(scanf(\"%s\ {

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 {

if(count%2==1)c='1'; else c='0'; }

for(i=0;ireturn 0; }

2577 How to Type

学习指导参考

WORD格式整理版

Problem Description

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\c, m, Caps lock, the answer is 8

Author

Dellenge

Source

HDU 2009-5 Programming Contest

Recommend

lcy

代码：#include

#include #define MAX 200 int arr[MAX][4];

学习指导参考

WORD格式整理版

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;iif(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;

学习指导参考

WORD格式整理版

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;}

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]){ tmp=arr[len-1][0]+1; if(tmpif(arr[len-1][0]) { tmp=arr[len-1][0]; if(tmpprintf(\"%d\\n\}

//Caps Shift:0-00;1-01;2-10;3-11 int main() {

int num;

scanf(\"%d\ while(num--) {

学习指导参考

WORD格式整理版

scanf(\"%s\

memset(arr,0,strlen(str)*4*sizeof(int)); proc(); }

return 0; }

北京大学： 1035 Spell checker

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.

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

学习指导参考

WORD格式整理版

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 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

学习指导参考

WORD格式整理版

fi: i

mre: more me

Source

Northeastern Europe 1998

开始做字符串的题目，本人觉得最头痛噶野，好鬼唔锺意处理字符串噶野。不过唯有硬住头皮上啦。

呢条题有个奇怪噶地方，就系用STL做的话，点都系TLE，后来改翻用C语言甘样慢慢搞先过，重要用左将近1s.

注意：（1）用另一个字符数组记录字典，然后排序，用于二分查找的。

（2）先处理与被检查数组相同长度的，然后系，比距长的，最后系比距短的。

（3）数组开得足够大啦

#include #include #include 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);

学习指导参考

WORD格式整理版

}

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++) { 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<} 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<printf(\" %s\ break; } } }

学习指导参考

WORD格式整理版

}

cout << endl; } } }

int main() { input(); solve(); return 0; }

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

学习指导参考

WORD格式整理版

浙江

这题用的是解线性同余方程的方法，之前没接触到过，搜索资料后看到一个人的博客里面讲的很好就拷贝过来了。内容如下：

对于方程：ax≡b(mod m)，a，b，m都是整数，求解x 的值，这个就是线性同余方程。 符号说明：

mod表示：取模运算

ax≡b(mod m)表示：(ax - b) mod m = 0，即同余 (a,b)表示：a和b的最大公约数

求解ax≡b(mod n)的原理：对于方程ax≡b(mod n)，存在ax + by = (a,b)，x，y是整数。而ax≡b(mod n)的解可以由x，y来堆砌。具体做法如下：

第一个问题：求解(a,b)

定理一：(a,b) = (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 = (a,b)

定理二：ax + by = (a,b)= (b,a mod b) = b * x' + (a mod b) * y'

= b * x' + (a - a / b * b) * y' = a * y' + b * (x' - a / b * y') = a * x + b * y 则：x = y'

y = x' - a / b * y'

学习指导参考

WORD格式整理版

以上内容转自hi.baidu.com/redcastle/blog/item/934b232dbc40d336349bf7e4.html

由这个可以得出扩展的欧几里德算法：

int exGcd(int a, int b, int &x, int &y) {

if(b == 0) {

x = 1; y = 0; return a; }

int r = exGcd(b, a % b, x, y); int t = x; x = y;

y = t - a / b * y; return r; }

代码：

#include #include #include #include

using namespace std;

__int mm,nn,xx,yy,l; __int c,d,x,y;

__int modd(__int a, __int b) {

if(a>=0) return a%b; else

return a%b+b; }

__int exGcd(__int a, __int b) {

if(b==0) { x=1;

学习指导参考

WORD格式整理版

y=0;

return a; }

__int r=exGcd(b, a%b); __int t=x; x=y;

y=t-a/b*y; return r; }

int main() {

scanf(\"%Id %Id %Id %Id %Id\ 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(\"%Id\\n\

system(\"pause\"); return 0; }

1142 Smith Numbers

Description

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

学习指导参考

WORD格式整理版

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 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？

学习指导参考

WORD格式整理版

用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进行了质因数分解

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

#include

#include 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 ) {

学习指导参考

WORD格式整理版

sum += Sum( i ); number /= i; i = 2; } else { ++i; }

//以上的代码做了无谓的计算，可用下面的代码，更新于20090904 //while( number % i == 0 ) //{

// sum += sum(i); // number /= i; //} // ++i; }

sum += Sum( number );

if ( sum == sumOfNumber && number != temp ) {

return true; } else {

return false; } }

int main() {

while( true ) {

int num;

scanf(\"%d\ if ( num == 0 ) {

break; }

while( true ) {

if ( SmithNumber(++num)) {

printf(\"%d\\n\

学习指导参考

WORD格式整理版

break; } } }

return 0; }

1200 Crazy Search

Description

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 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

学习指导参考

WORD格式整理版

Huge input,scanf is recommended.

Source

Southwestern Europe 2002

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

#include #include int n,nc;

char str[20000000]; char asca[128]; int hash[16000005];

int main() {

while(scanf(\"%d%d\\n\ {

scanf(\"%s\ 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-1sum=0;

for(j=i;j<=i+n-1;j++) {

sum=sum*nc+asca[str[j]]-1; }

if(hash[sum]==0) {

学习指导参考

WORD格式整理版

hash[sum]=1; cnt++; } }

printf(\"%d\\n\

} }

1811 Prime Test

Description

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

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\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

学习指导参考

WORD格式整理版

#include #include

#define MAX_L //最长位数

#define TIMES 8 //miller robin素性测试的测试次数 #define MAX_VAL (pow(2.0, 60)) //定义最大值 #define CVAL 200 using namespace std; //最小的素因子 __int 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

__int multAndMod(__int a, __int b, __int n) {

a = a % n;

__int 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以提升一位

学习指导参考

WORD格式整理版

__int modAndExp(__int a, __int b, __int n) {

a = a % n;

__int 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(__int a, __int n) {

__int 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); __int 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\ return false;

学习指导参考

WORD格式整理版

}

cur = now; }

if(cur != 1) {

//printf(\"a:%Id u:%Id n:%Id val:%Id\\n\ return false; }

//printf(\"a:%Id u:%Id n:%Id val:%Id\\n\ return true; }

//利用Miller Robin对n进行n次素性测试 bool testPrime(int times, __int n) {

if(n == 2) return true;

if(n % 2 == 0) return false; __int a; int t; srand(time(NULL));

for(t = 1; t <= times; t++) {

a = rand() % (n - 1) + 1;

if(!millerRobin(a, n)) return false; }

return true; }

__int (__int a, __int b) {

if(b == 0) return (a); return (b, a % b); }

__int PollardRho(__int n, int c) {

int i = 1;

srand(time(NULL));

__int x = rand() % n; __int y = x; int k = 2; while(true) {

i = i + 1;

x = (modAndExp(x, 2, n) + c) % n; __int d = (y - x, n); if(1 < d && d < n) return d;

if(y == x) return n; //重复了, 说明当前x下无解，需要重新启动PollardRho

学习指导参考

WORD格式整理版

if(i == k) {

y = x; k = k * 2; } } }

void getSmallest(__int n, int c) {

if(n == 1) return;

//判断当前因子是否为素数 if(testPrime(TIMES, n)) {

if(n < minFactor) minFactor = n; return; }

__int val = n;

//循环，知道找到一个因子 while(val == n)

val = PollardRho(n, c--); //二分

getSmallest(val, c); getSmallest(n / val, c); }

int main() {

int caseN; __int n;

scanf(\"%d\ while(caseN--) {

scanf(\"%Id\ minFactor = MAX_VAL;

if(testPrime(TIMES, n)) printf(\"Prime\\n\"); else {

getSmallest(n, CVAL);

printf(\"%Id\\n\ } }

return 0; }

学习指导参考

WORD格式整理版

2262 Goldbach's Conjecture

Description

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.

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

学习指导参考

WORD格式整理版

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

using namespace std;

// 判断是否为质数的函数 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;

学习指导参考

WORD格式整理版

// 是否找到标识 bool b_Find; // 栈

stack m_Stack; // 临时数

int m_Value_Top; // 循环输入

while ( scanf( \"%d\ {

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;

// 如果发生如下情况，则输出 \"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();

学习指导参考

WORD格式整理版

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(); }

// 加入 +

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\ system( \"pause\" );

学习指导参考

WORD格式整理版

return 0; }

2407 Relatives

Description

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

7 12 0

Sample Output

6 4

Source

Waterloo local 2002.07.01

这题从题意可以看出就是求比从1~n - 1从有几个数和n没有公共因子， 通常的算法很简单就能够想到， 我开始也是按通常的做法写了一个， 觉得

可能会TLE, 果不其然， 后来上网查了一下， 知道了欧拉函数， 这个就是求比n小的数中与n互质（也就是没有公共因子）的算法， 看来还是那些经典的算法效率比较高， 比纯用暴力试探高多了...

欧拉函数描述如下：

利用欧拉函数和它本身不同质因数的关系，用筛法计算出某个范围内所有数的欧拉函数值。

学习指导参考

WORD格式整理版

欧拉函数和它本身不同质因数的关系：欧拉函数ψ（Ｎ）＝Ｎ｛∏ｐ｜Ｎ｝（１－１/ｐ）。（Ｐ是数Ｎ的质因数）

如：

ψ（１０）＝１０×（１－１/２）×（１－１/５）＝４；

ψ（３０）＝３０×（１－１/２）×（１－１/３）×（１－１/５）＝８；

ψ（４９）＝４９×（１－１/７）＝４２。

注意的是P是N的质因子， 这里求质因子还是不能够用常规的判断这个数是不是质数， 这样的话可能还会TLE, 网上学到他们用的一个while() 循环，感觉还挺巧的， 学习了...

#include #include int enlerFun(int n) {

int count = n; int i = 2;

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\ {

count = enlerFun(inputVal); printf(\"%d\\n\ }

return 0; }

2447 RSA

学习指导参考

WORD格式整理版

Description

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.

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

学习指导参考

WORD格式整理版

7

Source

POJ Monthly,static

密码学:RSA公钥密码

#include #include #include #include using namespace std;

typedef unsigned __int u; #define MAX 30 #define MAXN 5

u len, dig, limit; u factor[MAXN];

u mod(u a, u b, u n){ if(!a)return 0;

else return ( ((a&dig)*b)%n + (mod(a>>len,b,n)<u by(u a, u b, u n){ u p;

p = 8, len = 61; while(pp<<=4; len -=4; }

dig = ((limit/p)<<1) - 1; return mod(a,b,n); }

u random(){//产生随机数 u a;

a = rand(); a *= rand(); a *= rand(); a *= rand(); return a; }

u square_multiply(u x, u c, u n){//(x^c)%n快速算法 u z=1; while(c){

if(c%2==1)z = by(z,x,n);

学习指导参考

WORD格式整理版

x = by(x,x,n); c=(c>>1); }

return z; }

bool Miller_Rabin(u n){//Miller_Rabin素数测试 if(n<2)return false; if(n==2)return true; if(!(n&1))return false; u k = 0, i, j, m, a; m = n - 1;

while(m%2==0)m=(m>>1),k++; for(i=0;ia = square_multiply(random()%(n-1)+1, m, n);//平方乘 if(a==1)continue; for(j=0;jif(a==n-1)break; a = by(a,a,n); }

if(jreturn true; }

u (u a,u b){

if(a==0) return b;

else return (b%a,a); }

u f(u x, u n ){

return (by(x,x,n)+1)%n; }

u Pollard(u n){

if(n<=2)return 0; if(!(n&1))return 2; u i, p, x,xx;

for(i=0;ip = ((xx+n-x)%n , n); while(p==1){

x = f(x,n);

xx = f(f(xx,n),n);

p = ((xx+n-x)%n,n)%n; }

学习指导参考

WORD格式整理版

if(p)return p; }

return 0; }

u prime(u a){

if(Miller_Rabin(a))return a; u t = Pollard(a); if(t!=0)

{return prime(t);} }

u Euclid(u a,u b,__int &x,__int &y) {

if(b==0) {

x=1,y=0; return a; }

u t,d; if(b!=0)

d=Euclid(b,a%b,x,y); t=x; x=y; if(b!=0) y=t-a/b*y; return d; }

int main(){

u c,e,n,i,j,m,t,n0,T,ans,l; __int T0,x,y,d; limit = 1;

limit = limit<<63;

while(scanf(\"%Iu%Iu%Iu\ 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学习指导参考

WORD格式整理版

T0=(__int)(factor[0]-1)*(factor[1]-1); T=(u)T0;

Euclid(e,T,x,y); d=x;

//printf(\"%Id\\n\ //while(d<0)d+=T0;

d=(d%T0+T0)%T0; //d=(__int)d;

// printf(\"%Id %Id\\n\

ans=square_multiply(c,(u)d,n0); printf(\"%Iu\\n\ } }

2503 Babelfish

Description

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.

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

学习指导参考

WORD格式整理版

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 #include #include

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);

学习指导参考

WORD格式整理版

}

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) {

/* 使用sscanf从str中读取查询要求 */ sscanf(str, \"%s %s\ i++; }

/* 查询开始时进行查询 */ else {

/* 二分查找指定字符串 */

p = (dict*) bsearch(str, a, i, sizeof(dict), b_cmp); /* 找到则输出结果 */ if (p) {

puts(p->en); }

/* 找不到输出\"eh\" */ else {

puts(\"eh\"); }

学习指导参考

WORD格式整理版

}

} }

//system(\"pause\"); return 0;

2513 Colored Sticks

Description

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

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根木棒，每个木棒有两种颜色表示两端，问：能不能将所有的木棒连接成一条直线（连接处颜色相同）。 可以考虑无向图的欧拉通路问题：将每种颜色看成图中的一个节点，木棒看作连接节点的边，

学习指导参考

WORD格式整理版

于是判断两点：

1，每种颜色（节点）的度 2，是否为连通图

首先，每种颜色的度可以通过每条木棒的两端颜色的累积得到，问题是，每种颜色都是字符串，怎么关联每种颜色和度呢？

最容易想到的是Hash，这肯定是可行的。例如degree [ hash(red) ]=5。表示颜色为红色的度为5。 但是，既然提示用trie树来做，那么trie树的节点的数据域就可以保存每种颜色的id（相当于分配的hash值，可以通过一个全局变量自增产生），这样经过将每种颜色字符串插入到tree中以后，通过trie树的search操作就能高效的获取每种颜色对应的id，没插入一种颜色，为其产生一个id，只需要注意相同颜色插入时的处理即可。

其次，判断无向图是否连通可以使用并查集来判定：经过n-1各union操作后，所有节点都在一个集合（树形结构表示集合的话，即所有节点的父节点（集合代表）都一样）。由于每种颜色是由字符串来标示的，每个集合保存颜色对应的唯一id。 通过上面两个步骤的判定，就可以得出结果。

#include #include 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;

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学习指导参考

WORD格式整理版

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;iif(p->next[s[i]-'a']==NULL) return -1; else

p=p->next[s[i]-'a']; }

return p->id; }

void make_set(int x) {

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;

学习指导参考

WORD格式整理版

} }

int main() {

root = new TreeNode; memset(p,0,sizeof(p));

memset(degree,0,sizeof(degree)); while(scanf(\"%s %s\ {

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;iif(degree[i]%2!=0)sum++; if(sum>2) {

cout<<\"Impossible\"<//if the g is joint. for(i=1;iif(find_set(i) != find_set(1)) {

cout<<\"Impossible\"<cout<<\"Possible\"<学习指导参考

WORD格式整理版

ACM算法： kurXX最小生成树

#include #include #include 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.wint 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; if(a==b) return false; if(acint main(){

int i,j,k,n,m,u,v,t; cin >> t;

for(k=0;kmemset(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\ if(i学习指导参考

WORD格式整理版

all_e[ei++]=e; } } }

sort(&all_e[0],&all_e[ei]); int count=0; int size=ei; int max=0;

for(i=0;iif(all_e[i].w>all_e[max].w) max=i; } }

printf(\"%d\\n\ }

return 0; }

Prim

#include using namespace std; #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\

学习指导参考

WORD格式整理版

}

int i;

while(n!=0){

memset(set,0,sizeof(set)); memset(g,0,sizeof(g)); for(i=1;i<=n;i++) {

scanf(\"%s\ 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; }

printf(\"The highest possible quality is 1/%d.\\n\ scanf(\"%d%c\}

return 0;

堆实现最短路

#include #include #include #include ; using namespace std; #define M 1001

#define LIM 2000000000

struct dd{ //最短距离

int w,q;//w是距离值,q是堆中的相对位置

学习指导参考

WORD格式整理版

}d[M],d2[M]; struct node{ int v,w; };

int h[M],hs;

vector 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]);

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 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];

学习指导参考

WORD格式整理版

}

}

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最短路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; }

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;iif(g[u][i]!=0) relax(d,u,i,g[u][i]); } } }

floyd

学习指导参考

WORD格式整理版

#include #include 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

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;kfor(j=1;j<=n;j++){

if(g[i][j]!=0) relax(d,i,j,g[i][j]);

学习指导参考

<

WORD格式整理版

}

}

}

拓扑排序

#include #include #include #include

using namespace std; vector order;

void find_id(list g[],int id[],int n){ //寻找入度,没有使用 int i;

list::iterator k; for(i=0;ifor(k=g[i].begin();k!=g[i].end();k++){ id[*k]++; } } }

void topo(list g[],int id[],int n,bool &OK,bool &incon){//OK==false 表示未确定顺序 incon==true 表示发现矛盾 stack s;

order.erase(order.begin(),order.end()); int t[26];

copy(&id[0],&id[n],&t[0]); int i;

for(i=0;iif(s.size()!=1) OK=false; int count=0;

while(!s.empty()){

int v=s.top(); s.pop(); count++; order.push_back(v); list::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; } }

学习指导参考

WORD格式整理版

}

if(order.size() < n) OK=false; //矛盾发生,会导致这种情况,小心 if(count < n) incon=true; copy(&t[0],&t[n],&id[0]);

DFS强连通分支

#include #include #include using namespace std; #define M 20005

vector 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++;}

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(acvoid dfs(vector g[M],int u){ if(used[u]) return; tim++;

used[u]=true; int i;

for(i=0;itim++;

学习指导参考

WORD格式整理版

ft[u]=tim; return; }

void dfs2(vector g[],int u,int r,int set[]){ if(used[u]) return; uni(set,u,r);

used[u]=true; int i;

for(i=0;ireturn; }

void scc(int n,vector 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;jfor(i=1;i<=n;i++) if(!used[sort_v[i]]) dfs2(gt,sort_v[i],sort_v[i],set); //make the scc }

int main(){

int i,j,n,m,u,v,set[M]; cin >> n >> m; for(i=0;iscanf(\"%d%d\ 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;}

学习指导参考

WORD格式整理版

}

sc[p].n++; }

int n2=pi-1,od[M];

memset(od,0,sizeof(od)); for(i=1;i<=n;i++){

for(j=0;ju=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 #include #include 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;

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;

学习指导参考

WORD格式整理版

}

while(t--){ sum=0;

memset(match,0,sizeof(match)); memset(g,0,sizeof(g)); scanf(\"%d%d\ for(i=1;i<=m;i++){

scanf(\"%d%d\ 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 #include #include #include using namespace std; #define M 3001 bool g[M][M];

int mk[M] ,cx[M],pred[M],open[M],cy[M],nx,ny; //边少适用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 ; }

学习指导参考

WORD格式整理版

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) ; }

return res ; }

最大权匹配,KM算法

//此KM算法，坐标从1开始，记住 #include #include #include using namespace std; #define M 110

int n; // X 的大小 int lx[M], ly[M]; // 标号

bool sx[M], sy[M]; // 是否被搜索过

学习指导参考

WORD格式整理版

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]; }

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);

学习指导参考

WORD格式整理版

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\ int w[M][M];

char c; Point pt;

while(cin >> n >> m && (n!=0 || m!=0)){ vector vh,vm; for(i=0;ifor(j=0;jpt.r=i; pt.c=j; vh.push_back(pt); }

if(c=='m'){

pt.r=i;pt.c=j; vm.push_back(pt); }

学习指导参考

WORD格式整理版

} }

for(i=0;iw[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两种欧拉路

无向图：

#define M 45

int used[M][M],id[M];

void dfs(int u,vector g[],vector &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); }

有向图：

int n,m;

vector 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]); }

学习指导参考

WORD格式整理版

}

}

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;

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;

学习指导参考

WORD格式整理版

}

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 #include #include #include #include #include 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)

学习指导参考

WORD格式整理版

{ queue 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]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]int v,low=g[i][t]-f[i][t]; pre[t]=i;

for(v=t;pre[v]!=-1;v=pre[v])

low=lowfor(v=t;pre[v]!=-1;v=pre[v]) {

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){

学习指导参考

WORD格式整理版

}

}

memset(g,0,sizeof(g)); for(i=0;iscanf(\"%d%d%d\ 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; best[s]=0; do {

quit=1;

for (i=1;i<=n;i++){ if (best[i]for (j=1;j<=n;j++){

if (f[i][j]学习指导参考

WORD格式整理版

}

}

}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题目：

【题目】排球队员站位问题

┏━━━━━━━━┓图为排球场的平面图，其中一、二、三、四、五、六为位置编号， ┃ ┃二、三、四号位置为前排，一、六、五号位为后排。某队比赛时， ┃ ┃一、四号位放主攻手，二、五号位放二传手，三、六号位放副攻 ┠──┬──┬──┨手。队员所穿球衣分别为１，２，３，４，５，６号，但每个队 ┃ 四 │ 三 │ 二 ┃员的球衣都与他们的站位号不同。已知１号、６号队员不在后排， ┠──┼──┼──┨２号、３号队员不是二传手，３号、４号队员不在同一排，５号、 ┃ 五 │ 六 │ 一 ┃６号队员不是副攻手。 ┗━━┷━━┷━━┛ 编程求每个队员的站位情况。

【算法分析】本题可用一般的穷举法得出答案。也可用回溯法。以下为回溯解法。 【参考程序】

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

学习指导参考

WORD格式整理版

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.

【题目】把自然数Ｎ分解为若干个自然

数之和。

【参】

n │ total

5 │ 7 6 │ 11 7 │ 15 10 │ 42

100 │ 190569291

学习指导参考

WORD格式整理版

【参考程序】

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.

【题目】把自然数Ｎ分解为若干个自然

数之积。

【参考程序】

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]);

学习指导参考

WORD格式整理版

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.

【题目】马的遍历问题。

在Ｎ＊Ｍ的棋盘中，马只能走日字。马从位置(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; {输出,并统计总数} 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

学习指导参考

WORD格式整理版

{判断新坐标是否出界,是否已走过?} 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.找出所有方案。

输入：Ｎ Ｍ Ｎ为要分解的分数的分母 Ｍ为分解成多少项 【参考程序】

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;

学习指导参考

WORD格式整理版

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]; 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;

学习指导参考

WORD格式整理版

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;

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

【题目】地图着色问题

【参考程序１】

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),

学习指导参考

WORD格式整理版

(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 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.

【参考程序２】

const {lin数组:代表区域相邻情况} lin:array[1..12] of set of 1..12 =

学习指导参考

WORD格式整理版

([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个区域} 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的长条块,问放置方案如何

学习指导参考

WORD格式整理版

【参考程序１】 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('@')); 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;

学习指导参考

WORD格式整理版

end;

begin {主程序}

fillchar(a,sizeof(a),' '); {记录放置情况的字符数组,初始值为空格} result:=0; k:=0; {k记录已放的块数,如果k=n*n/2,则说明已放满} try; {每找到一个空位置,把长条块分别横放和竖放试验} end.

【参考程序２】

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; 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

学习指导参考

WORD格式整理版

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; 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.

学习指导参考

WORD格式整理版

【题目】找迷宫的最短路径。

（广度优先搜索算法） 【参考程序】 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; 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

学习指导参考

WORD格式整理版

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; 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_weizhi:integer;stack,exitout:shuzu); {dep:步数,have:入口处有多少辆车;rest:车站中有多少车;} {exit_weizhi:从车站开出后,排在出口处的位置;}

{stack:车站中车辆情况数组;exitout:出口处车辆情况数组} var i:integer;

begin {分入站,出站两种情况讨论} if have>0 then begin {还有车未入站}

学习指导参考

WORD格式整理版

stack[rest+1]:=n+1-have; {入站} if dep=2*n then output(exitout) else find(dep+1,have-1,rest+1,exit_weizhi,stack,exitout); end; if rest>0 then begin {还有车可出站} exitout[exit_weizhi+1]:=stack[rest]; {出站} if dep=2*n then output(exitout) {经过2n步后,输出一种方案} else find(dep+1,have,rest-1,exit_weizhi+1,stack,exitout); end; end;

begin

writeln('input n:'); readln(n);

fillchar(stack,sizeof(stack),0); fillchar(exitout,sizeof(exitout),0); total:=0;

find(1,n,0,0,stack,exitout); writeln('total:',total); readln; end.

【解法2】用穷举二进制数串的方法完成.

uses crt;

var i,n,m,t:integer;

a,s,c:array[1..1000] of integer; procedure test;

var t1,t2,k:integer; notok:boolean; begin

t1:=0;k:=0;t2:=0; i:=0;

notok:=false;

repeat {二进制数串中,0表示出栈,1表示入栈} i:=i+1; {数串中第I位}

if a[i]=1 then begin {第I位为1,则表示车要入栈} inc(k); {栈中车数}

inc(t1); {入栈记录,T1为栈指针,S为栈数组} s[t1]:=k; end

else {第I位为0,车要出栈}

if t1<1 then notok:=true {已经无车可出,当然NOT_OK了} else begin inc(t2);c[t2]:=s[t1];dec(t1);end;

学习指导参考

WORD格式整理版

{栈中有车,出栈,放到C数组中去,T2为C的指针,栈指针T1下调1}

until (i=2*n) or notok; {整个数串均已判完,或中途出现不OK的情况} if (t1=0) and not notok then begin {该数串符合出入栈的规律则输出} inc(m);write('[',m,']');

for i:=1 to t2 do write(c[i]:2); writeln; end; end; begin

clrscr; write('N=');readln(n); m:=0;

for i:=1 to 2*n do a[i]:=0; { repeat {循环产生N位二进制数串}

test; {判断该数串是否符合车出入栈的规律} t:=2*n;

a[t]:=a[t]+1; {产生下一个二进制数串} while (t>1) and (a[t]>1) do begin a[t]:=0;dec(t);a[t]:=a[t]+1; end; until a[1]=2; readln; end.

N: 4 6 7 8 TOTAL: 14 132 429 1430

【题目】农夫过河。

一个农夫带着一只狼，一只羊和一些菜过河。河边只有一条一船，由

于船太小，只能装下农夫和他的一样东西。在无人看管的情况下，狼要吃羊，羊 要吃菜，请问农夫如何才能使三样东西平安过河。 【算法分析】

将问题数字化。用１代表狼，２代表羊，３代表菜。则在河某一边物体的分布有以下 ８种情况。

┏━━━━┯━┯━━━━━┯━━━━━━━━┯━━━┓ ┃物体个数│０│ １ │ ２ │ ３ ┃ ┠────┼─┼─┬─┬─┼──┬──┬──┼───┨ ┃分布情况│０│１│２│３│1,2 │1,3 │2,3 │1,2,3 ┃ ┠────┼─┼─┼─┼─┼──┼──┼──┼───┨ ┃代码之和│０│１│２│３│３ │ ４ │ ５ │ ６ ┃ ┠────┼─┼─┼─┼─┼──┼──┼──┼───┨ ┃是否相克│ │ │ │ │相克│ │相克│ ┃ ┗━━━━┷━┷━┷━┷━┷━━┷━━┷━━┷━━━┛

学习指导参考

WORD格式整理版

当（两物体在一起而且）代码和为３或５时，必然是相克物体在一起的情况。 【参考程序】 const

wt:array[0..3]of string[5]=(' ', 'WOLF ','SHEEP','LEAVE'); var left,right:array[1..3] of integer ;

what,i,total,left_rest,right_rest:integer; procedure print_left; {输出左岸的物体} var i:integer; begin

total:=total+1;

write('(',total,')'); {第几次渡河} for i:=1 to 3 do write(wt[left[i]]); write('|',' ':4); end;

procedure print_right;{输出右岸的物体} var i:integer; begin

write(' ':4,'|');

for i:=1 to 3 do if right[i]<>0 then write(wt[right[i]]); writeln; end;

procedure print_back(who:integer); {右岸矛盾时，需从右岸捎物体→左岸} var i:integer; begin

for i:=1 to 3 do begin if not ((i=who) or (right[i]=0)) then begin {要捎回左岸的物体不会时刚刚从左岸带来的物体，也不会是不在右岸的物体} what:=right[i]; right[i]:=0; print_left; {输出返回过程} write('<-',wt[i]); print_right; left[i]:=what; {物体到达左岸} end; end; end; begin

total:=0;

for i:=1 to 3 do begin left[i]:=i; right[i]:=0;end; repeat

for i:=1 to 3 do {共有３种物体} if left[i]<>0 then {第Ｉ种物体在左岸} begin what:=left[i];left[i]:=0; {what:放置将要过河的物体编号}

学习指导参考

WORD格式整理版

left_rest:=left[1]+left[2]+left[3]; {求左岸剩余的物体编号总和} if (left_rest=3) or (left_rest=5) then left[i]:=what {假如左岸矛盾，则不能带第Ｉ种过河，尝试下一物体} else {否则可带过河} begin print_left; {输出过河过程} write('->',wt[i]); print_right; right[i]:=what; {物体到达右岸} if left_rest=0 then halt; {左岸物体已悉数过河} right_rest:=right[1]+right[2]+right[3]; {求右岸剩余的物体编号总和} if (right_rest=3)or(right_rest=5) then print_back(i) {右岸有矛盾，要捎物体回左岸} else begin print_left; {右岸有矛盾，空手回左岸} write('<-',' ':5); print_right; end; end; end;

until false; {不断往返} end.

【题目】七段数码管问题。

从一个数字变化到其相邻的数字只需要通过某些段(数目不限)

1 或拿走某些段(数目不限)来实现.但不允许既增加段又拿起段. ┏━┓ 例如:3可以变到9,也可以变到1 6┃ 7┃2 ━┓ ┏━┓ ━┓ ┃ ┣━┫ ┃ ┃ ┃ ┃ ┃ 5┃ ┃3 ━┫ → ┗━┫ ━┫ → ┃ ┗━┛ ┃ ┃ ┃ ┃ 4 ━┛ ━┛ ━┛ ┃

要求:(1)判断从某一数字可以变到其它九个数字中的哪几个.

(2)找出一种排列这十个数字的方案,便这样组成的十位数数值最小. type kkk=set of 0..9;

const a:array[-1..9] of set of 1..7 =([5,6],[1,2,3,4,5,6],[2,3],[1,2,4,5,7],[1,2,3,4,7],[2,3,6,7], [1,3,4,6,7],[1,3,4,5,6,7],[1,2,3],[1,2,3,4,5,6,7],[1,2,3,4,6,7]); var

i,j:integer;

b:array[-2..9] of set of 0..9;

procedure number(p:string;s,l:integer;k:kkk);

{P:生成的数;s:用了几个数字;i:前一个是哪个数字;k:可用的数字}

学习指导参考

WORD格式整理版

var i:integer; begin

for i:=0 to 9 do if (i in k) and ( i in b[l]) then begin {数字i未用过,且i可由前一个采用的数字变化而来} if s=10 then begin writeln('Min:',p,i);readln;halt;end else number(p+chr(48+i),s+1,i,k-[i]); end; end;

begin

for i:=1 to 9 do b[i]:=[]; b[-2]:=[0..9]; for i:=-1 to 8 do for j:=i+1 to 9 do if (a[i]<=a[j]) or (a[j]<=a[i]) then begin b[i]:=b[i]+[j]; b[j]:=b[j]+[abs(i)]; end; b[1]:=b[1]+b[-1]; for i:=0 to 9 do begin write(i,' may turn to :'); for j:=0 to 9 do if j in b[i] then write(j,' '); writeln; end;

number('',1,-2,[0..9]); End.

【题目】 求相邻的格的数不连续

把1-8这8个数放入下图8个格中,要求相邻的格(横,竖,对角线)上填的数不连

续.

┌─┐ │①│ ┌─┼─┼─┐ │②│③│④│ ├─┼─┼─┤ │⑤│⑥│⑦│ └─┼─┼─┘ │⑧│ └─┘ 【参考程序】

const lin:array[1..8] of set of 1..8 = ([3,2,4],[1,6,3,5],[5,7,1,2,4,6],[1,6,3,7],

学习指导参考

WORD格式整理版

[3,8,2,6],[2,4,3,5,7,8],[3,8,4,6],[5,7,6]); var a:array[1..8] of integer; total,i:integer; had:set of 1..8;

function ok(dep,i:integer):boolean; {判断是否能在第dep格放数字i} var j:integer; begin

ok:=true;

for j:=1 to 8 do {相邻且连续则不行} if (j in lin[dep]) and (abs(i-a[j])=1) then ok:=false; if i in had then ok:=false; {已用过的也不行} end;

procedure output; {输出一种方案} var j:integer; begin inc(total); write(total,':'); for j:=1 to 8 do write(a[j]:2);writeln; end;

procedure find(dep:byte); var i:byte; begin for i:=1 to 8 do begin {每一格可能放1-8这8个数字中的一个} if ok(dep,i) then begin a[dep]:=i; {把i放入格中} had:=had+[i]; {设置已放过标志} if (dep=8) then output else find(dep+1); a[dep]:=10; {回溯,恢复原状态} had:=had-[i]; end; end; end; begin

fillchar(a,sizeof(a),10); total:=0; had:=[]; find(1);

writeln('End.'); end.

【题目】 棋盘上放棋子

在4×4的棋盘上放置8个棋,要求每一行,每一列上只能放置2个.

【参考程序1】

学习指导参考

WORD格式整理版

算法:8个棋子,填8次.深度为8.注意判断是否能放棋子时,两个两个为一行. var a:array[1..8] of 0..4;

line,bz:array[1..4] of 0..2; {line数组:每行已放多少个的计数器} {bz数组: 每列已放多少个的计数器} total:integer;

procedure output; {输出} var i:integer; begin

inc(total); write(total,': ');

for i:=1 to 8 do write(a[i]); writeln; end;

function ok(dep,i:integer):boolean; begin

ok:=true;

if dep mod 2 =0 then {假如是某一行的第2个,其位置必定要在第1个之后} if (i<=a[dep-1]) then ok:=false;

if (bz[i]=2) or(line[dep div 2]=2) then ok:=false; {某行或某列已放满2个} end;

procedure find(dep:integer); var i:integer; begin

for i:=1 to 4 do begin if ok(dep,i) then begin a[dep]:=i; {放在dep行i列} inc(bz[i]); {某一列记数器加1} inc(line[dep div 2]); {某一行记数器加1} if dep=8 then output else find(dep+1); dec(bz[i]); {回溯} dec(line[dep div 2]); a[dep]:=0; end; end; end; begin

total:=0; fillchar(a,sizeof(a),0); fillchar(bz,sizeof(bz),0); find(1); end.

【参考程序2】

算法:某一行的放法可能性是(1,2格),(1,3格),(1,4格)....共6种放法 const

fa:array[1..6] of array[1..2]of 1..4=((1,2),(1,3),(1,4),(2,3),(2,4),(3,4)); {六种可能放法的行坐标} var

学习指导参考

WORD格式整理版

a:array[1..8] of 0..4;

bz:array[1..4] of 0..2; {列放了多少个的记数器} total:integer; procedure output; var i:integer; begin

inc(total);

write(total,': ');

for i:=1 to 8 do write(a[i]); writeln; end;

function ok(dep,i:integer):boolean; begin

ok:=true; {判断现在的放法中,相应的两列是否已放够2个} if (bz[fa[i,1]]=2) or (bz[fa[i,2]]=2) then ok:=false; end;

procedure find(dep:integer); var i:integer; begin

for i:=1 to 6 do begin {共有6种可能放法} if ok(dep,i) then begin a[(dep-1)*2+1]:=fa[i,1];{一次连续放置2个} a[(dep-1)*2+2]:=fa[i,2]; inc(bz[fa[i,1]]); {相应的两列,记数器均加1} inc(bz[fa[i,2]]); if dep=4 then output else find(dep+1); dec(bz[fa[i,1]]); {回溯} dec(bz[fa[i,2]]); a[(dep-1)*2+1]:=0; a[(dep-1)*2+2]:=0; end; end; end; begin

total:=0; fillchar(a,sizeof(a),0); fillchar(bz,sizeof(bz),0); find(1); end.

【题目】迷宫问题.

求迷宫的路径.(深度优先搜索法)

【参考程序1】 const

Road:array[1..8,1..8]of 0..3=((1,0,0,0,0,0,0,0),

学习指导参考

WORD格式整理版

(0,1,1,1,1,0,1,0), (0,0,0,0,1,0,1,0), (0,1,0,0,0,0,1,0), (0,1,0,1,1,0,1,0), (0,1,0,0,0,0,1,1), (0,1,0,0,1,0,0,0), (0,1,1,1,1,1,1,0)); {迷宫数组}

FangXiang:array[1..4,1..2]of -1..1=((1,0),(0,1),(-1,0),(0,-1));{四个移动方向} WayIn:array[1..2]of byte=(1,1); {入口坐标} WayOut:array[1..2]of byte=(8,8); {出口坐标} Var i,j,Total:integer; Procedure Output; var i,j:integer; Begin

For i:=1 to 8 do begin for j:=1 to 8 do begin if Road[i,j]=1 then write(#219); {1:墙} if Road[i,j]=2 then write(' '); {2:曾走过但不通的路} if Road[i,j]=3 then write(#03) ; {3:沿途走过的畅通的路} if Road[i,j]=0 then write(' ') ; {0:原本就可行的路} end; writeln;

end; inc(total); {统计总数} readln; end;

Function Ok(x,y,i:byte):boolean; {判断坐标(X,Y)在第I个方向上是否可行} Var NewX,NewY:shortint; Begin

Ok:=True;

Newx:=x+FangXiang[i,1]; Newy:=y+FangXiang[i,2];

If not((NewX in [1..8]) and (NewY in [1..8])) then Ok:=False; {超界?} If Road[NewX,NewY]=3 then ok:=false; {是否已走过的路?} If Road[NewX,NewY]=1 then ok:=false; {是否墙?} End;

Procedure Howgo(x,y:integer); Var i,NewX,NewY:integer; Begin

For i:=1 to 4 do Begin {每一步均有4个方向可选择} If Ok(x,y,i) then Begin {判断某一方向是否可前进} Newx:=x+FangXiang[i,1]; {前进,产生新的坐标} Newy:=y+FangXiang[i,2]; Road[Newx,Newy]:=3; {来到新位置后,设置已走过标志} If (NewX=WayOut[1]) and(NewY=WayOut[2]) Then Output Else Howgo(Newx,NewY); {如到出口则输出,否则下一步递归}

学习指导参考

WORD格式整理版

Road[Newx,Newy]:=2; {堵死某一方向,不让再走,以免打转} end; end; End; Begin

total:=0;

Road[wayin[1],wayin[2]]:=3; {入口坐标设置已走标志} Howgo(wayin[1],wayin[2]); {从入口处开始搜索} writeln('Total is ',total); {统计总数} end.

【题目】一笔画问题

从某一点出发,经过每条边一次且仅一次.(具体图见高级本P160)

【参考程序】

const max=6;{顶点数为6}

type shuzu=array[1..max,1..max]of 0..max; const a:shuzu {图的描述与定义 1:连通;0:不通} =((0,1,0,1,1,1), (1,0,1,0,1,0), (0,1,0,1,1,1), (1,0,1,0,1,1), (1,1,1,1,0,0), (1,0,1,1,0,0)); var

bianshu:array[1..max]of 0..max; {与每一条边相连的边数} path:array[0..1000]of integer; {记录画法,只记录顶点} zongbianshu,ii,first,i,total:integer; procedure output(dep:integer); {输出各个顶点的画法顺序} var sum,i,j:integer; begin

inc(total);

writeln('total:',total);

for i:=0 to dep do write(Path[i]);writeln; end;

function ok(now,i:integer;var next:integer):boolean;{判断第I条连接边是否已行过} var j,jj:integer; begin

j:=0; jj:=0;

while jj<>i do begin inc(j);if a[now,j]<>0 then inc(jj);end; next:=j;

{判断当前顶点的第I条连接边的另一端是哪个顶点,找出后赋给NEXT传回} ok:=true;

if (a[now,j]<>1) then ok:=false; {A[I,J]=0:原本不通}

学习指导参考

WORD格式整理版

end; { =2:曾走过} procedure init; {初始化} var i,j :integer; begin

total:=0; {方案总数} zongbianshu:=0; {总边数} for i:=1 to max do for j:=1 to max do if a[i,j]<>0 then begin inc(bianshu[i]);inc(zongbianshu);end; {求与每一边连接的边数bianshu[i]}

zongbianshu:=zongbianshu div 2; {图中的总边数} end;

procedure find(dep,nowpoint:integer); {dep:画第几条边;nowpoint:现在所处的顶点} var i,next,j:integer; begin

for i:=1 to bianshu[nowpoint] do {与当前顶点有多少条相接,则有多少种走法} if ok(nowpoint,i,next) then begin {与当前顶点相接的第I条边可行吗?} {如果可行,其求出另一端点是NEXT} a[nowpoint,next]:=2; a[next,nowpoint]:=2; {置成已走过标志} path[dep]:=next; {记录顶点,方便输出} if dep < zongbianshu then find(dep+1,next) {未搜索完每一条边} else output(dep); path[dep]:=0; {回溯} a[nowpoint,next]:=1; a[next,nowpoint]:=1; end; begin

init; {初始化,求边数等}

for first:=1 to max do {分别从各个顶点出发,尝试一笔画} fillchar(path,sizeof(path),0); path[0]:=first; {记录其起始的顶点} writeln('from point ',first,':');readln;

find(1,first); {从起始点first,一条边一条边地画下去} end.

【题目】城市遍历问题.

给出六个城市的道路连接图,找出从某一城市出发,遍历每个城市一次且仅一次的

最短路径

及其路程长度.(图见高级本P147} 【参考程序】 const

学习指导参考

WORD格式整理版

a:array[1..6,1..6]of 0..10 {城市间连接图.数字表示两城市间的路程} =((0,4,8,0,0,0), (4,0,3,4,6,0), (8,3,0,2,2,0), (0,4,2,0,4,9), (0,6,2,4,0,4), (0,0,0,9,4,0)); var

had:array[1..6]of boolean; {某个城市是否已到过} pathmin,path:array[1..6]of integer; {记录遍历顺序} ii,first,i,summin,total:integer;

procedure output(dep:integer); sum,i,j:integer; sum:=0; i:=2 6 {求这条路的路程总长} if sum><6 then find(dep+1)

else output(dep); had[i]:=false; {回溯} path[dep]:=0; end; end; begin

for first:=1 to 6 do begin {轮流从每一个城市出发,寻找各自的最短路} fillchar(had,sizeof(had),false); fillchar(path,sizeof(path),0); total:=0;

SumMin:=maxint; {最短路程}

path[1]:=first;had[first]:=true;{处理出发点的城市信息,记录在册并置到过标志}

find(2); {到下一城市} writeln('from city ',first,' start,total is:',total,' the min sum:',summin); for i:=1 to 6 do write(PathMin[i]);writeln; {输出某个城市出发的最短方案} end; end.

【题目】棋子移动问题

[参考程序] const

n=3; {n<5} type

ss=string[2*n+1];

ar=array[1..630]of ss; var

a:ar;

f,z:array[1..630] of integer;

学习指导参考

WORD格式整理版

i,j,k,m,h,t,k1:integer; s,d:ss; q:boolean;

procedure print (x:integer); var t:array[1..100] of integer; y:integer; begin

y:=0; repeat

y:=y+1; t[y]:=x; x:=f[x]; until x=0;

writeln(a[t[y]]:2*n+4);

writeln(copy('-------------------------',1,2*n+5)); for x:=2 to y do writeln(x-1:2,':',a[t[y+1-x]]); end; begin

s:='_';d:='_';

for i:=1 to n do begin s:='o'+s+'*'; d:='*'+d+'o'; end;

a[1]:=s;f[1]:=0;z[1]:=n+1; q:=false;

i:=1;j:=2; t:=0; repeat

for h:=1 to 4 do begin

k:=z[i];k1:=k;s:=a[i]; case h of

1:if k>1 then k1:=k-1;

2:if k<(2*n+1) then k1:=k+1;

3:if (k>2) and (s[k-1]<>s[k-2]) then k1:=k-2; 4:if (k<(2*n)) and(s[k+1]<>s[k+2]) then k1:=k+2; end;

if k<>k1 then begin

s[k]:=s[k1];s[k1]:='_'; m:=1;

while (a[m]<>s) and (m< j-1) do m:=m+1; if a[m] >>s then begin

a[j]:=s;f[j]:=i;z[j]:=k1; if s=d then begin print(j); q:=true;

学习指导参考

WORD格式整理版

end; j:=j+1; end;

end;

end; {end for} i:=i+1;

until q or (i=j); readln; end.

【题目】求集合元素问题（1,2x+1,3X+1

类)

某集合Ａ中的元素有以下特征： (1)数1是A中的元素

(2)如果X是A中的元素,则2x+1,3x+1也是A中的元素 (3)除了条件(1),(2)以外的所有元素均不是A中的元素 [参考程序1] uses crt,dos;

var a:array[1..10000]of longint; b:array[1..10000]of boolean; times,n,m,long,i:longint;

hour1,minute1,second1,sec1001:word; hour2,minute2,second2,sec1002:word; begin

write('N=');readln(n);

{ gettime(hour1,minute1,second1,sec1001); times:=minute1*60+second1; writeln(minute1,':',second1);} fillchar(b,sizeof(b),0); a[1]:=1;m:=2;long:=1; while long<=n do begin for i:=1 to long do

if (a[i]*2=m-1) or (a[i]*3=m-1) then if not b[m] then begin

inc(long);a[long]:=m;b[m]:=true;break; end; inc(m); end;

{ gettime(hour2,minute2,second2,sec1002);

学习指导参考

WORD格式整理版

times:=minute2*60+second2-times; writeln(minute2,':',second2);

writeln('Ok! Uses Time: ',times);} for i:=1 to n do write(a[i],' '); readln; end.

[参考程序2] uses crt;

const n=10000;

var a:array[1..n] of longint; i,j,k,l,y:longint; begin

clrscr;

fillchar(a,sizeof(a),0); i:=1;j:=1; a[i]:=1; repeat

y:=2*a[i]+1; k:=j;

while y〈a[k] do begin a[k+1]:=a[k]; k:=k-1; end;

if y>a[k] then begin a[k+1]:=y;j:=j+1; end

else for l:=k+1 to j do a[l]:=a[l+1]; j:=j+1;

a[j]:=3*a[i]+1; inc(i); until k>=n;

for i:=1 to n do begin write(a[i],' ');

if (i mod 10 =0 ) or (i=n) then writeln end; end.

[参考程序3] uses crt;

var a:array[1..10000]of longint;

n,i,one,another,long,s,x,y:longint; begin

write('n=');readln(n);

a[1]:=1;long:=1;one:=1;another:=1;

while longy then begin s:=y;inc(another);end

学习指导参考

WORD格式整理版

else begin s:=x;inc(one);inc(another);end; inc(long);a[long]:=s; end;

for i:=1 to n do write(a[i],' '); end.

[参考程序4] var n:integer; top,x:longint;

function init(x:longint):boolean; begin

if x=1 then init:=true

else if((x-1)mod 2=0)and(init((x-1)div 2))

or((x-1)mod 3=0)and(init((x-1)div 3))then init:=true

else init:=false; end; begin

write('input n:'); readln(n); x:=0; top:=0;

while top< n do begin x:=x+1;

if init(x) then top:=top+1; write(x:8); end;

write('output end.'); readln end.

学习指导参考