棋盘问题
Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u
Description
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
Sample Output
2
1
简单的暴力DFS
从棋盘的第一行开始。往下搜知道到达规定的步数或者出界了。其中加DFS中的最后一句是因为这一行可以不占。然后往下一行。
POJ1321.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 8+5
typedef struct NODE
{
bool row[MAXN];
}node;
char qipan[MAXN][MAXN];
int n,k;
int an;
void DFS(int step,int column,node statue)
{
if (step == k)
{
an++;
return;
}
if (column >= n)
return;
for(int i = 0;i < n;i++)
{
node temp = statue;
if (qipan[column][i] == '#' && !statue.row[i])
{
temp.row[i] = 1;
DFS(step+1,column+1,temp);
}
}
DFS(step,column+1,statue);
}
int main()
{
//int n;
while(scanf("%d%d",&n,&k),n!=-1||k!=-1)
{
for(int i = 0;i < n;i++)
{
char ctemp;
scanf("%c",&ctemp);
for(int j = 0;j < n;j++)
{
scanf("%c",&qipan[i][j]);
}
//scanf("%c",&ctemp);
}
an = 0;
node sta;
memset(sta.row,0,sizeof(sta.row));
DFS(0,0,sta);
printf("%d\n",an);
}
return 0;
}
Linear Cellular Automata
A biologist is experimenting with DNA modification of bacterial colonies being grown in a linear array of culture dishes. By changing the DNA, he is able ``program" the bacteria to respond to the population density of the neighboring dishes. Population is measured on a four point scale (from 0 to 3). The DNA information is represented as an array DNA, indexed from 0 to 9, of population density values and is interpreted as follows:
In any given culture dish, let K be the sum of that culture dish's density and the densities of the dish immediately to the left and the dish immediately to the right. Then, by the next day, that dish will have a population density of DNA[K].
The dish at the far left of the line is considered to have a left neighbor with population density 0.
The dish at the far right of the line is considered to have a right neighbor with population density 0.
Now, clearly, some DNA programs cause all the bacteria to die off (e.g., [0,0,0,0,0,0,0,0,0,0]). Others result in immediate population explosions (e.g., [3,3,3,3,3,3,3,3,3,3]). The biologist is interested in how some of the less obvious intermediate DNA programs might behave.
Write a program to simulate the culture growth in a line of 40 dishes, assuming that dish 20 starts with a population density of 1 and all other dishes start with a population density of 0.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
For each input set your program will read in the DNA program (10 integer values) on one line.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
For each input set it should print the densities of the 40 dishes for each of the next 50 days. Each day's printout should occupy one line of 40 characters. Each dish is represented by a single character on that line. Zero population densities are to be printed as the character ` '. Population density 1 will be printed as the character `.'. Population density 2 will be printed as the character `x'. Population density 3 will be printed as the character `W'.
Sample Input
1
0 1 2 0 1 3 3 2 3 0
Sample Output
bbbbbbbbbbbbbbbbbbb.bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbb...bbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbb.xbx.bbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb.bb.bb.bbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbb.........bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbb.xbbbbbbbx.bbbbbbbbbbbbbbb
bbbbbbbbbbbbb.bbxbbbbbxbb.bbbbbbbbbbbbbb
bbbbbbbbbbbb...xxxbbbxxx...bbbbbbbbbbbbb
bbbbbbbbbbb.xb.WW.xbx.WW.bx.bbbbbbbbbbbb
bbbbbbbbbb.bbb.xxWb.bWxx.bbb.bbbbbbbbbbb
Note: Whe show only the first ten lines of output (the total number of lines must be 50) and the spaces have been replaced with the character "b" for ease of reading. The actual output file will use the ASCII-space character, not "b".
题目理解了半天。到网上找了题意大概是这样的。
起初是一组只有第20个是1其他全是0的40个细菌的培养基吧
设为X[0]X[1]....X[39] X[0]左边X[-1]和X[39] X[40]右边的数量设置成0 假设其存在，程序中可以特殊处理一下
第二天的细菌的数量X2[i] = DNA[X1[i-1] ＋ X1[i] + X1[i+1]] X2 X1表示第一天、第二天的培养基
UVA457.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char ddish[50][41];
int DNA[10];
int C[300];
int main()
{
int T;
C[' '] = 0;
C['.'] = 1;
C['x'] = 2;
C['W'] = 3;
C[0] = ' ';
C[1] = '.';
C[2] = 'x';
C[3] = 'W';
int ok = 1;
for(scanf("%d",&T);T;T--)
{
if (ok)
{
ok = 0;
}
else
{
printf("\n");
}
for(int i = 0;i < 50;i++)
{
for(int j = 0;j < 40;j++)
{
ddish[i][j] = ' ';
}
ddish[i][40] = '\0';
}
ddish[0][19] = '.';
for(int i = 0;i < 10;i++)
{
scanf("%d",&DNA[i]);
}
for(int i = 1;i < 50;i++)
{
ddish[i][0] = C[DNA[(C[(int)ddish[i-1][0]] + C[(int)ddish[i-1][1]])]];
ddish[i][39] = C[DNA[(C[(int)ddish[i-1][39]] + C[(int)ddish[i-1][38]])]];
for(int j = 1;j < 39;j++)
{
ddish[i][j] = C[DNA[(C[(int)ddish[i-1][j-1]] + C[(int)ddish[i-1][j+1]] + C[(int)ddish[i-1][j]])]];
}
}
for(int i = 0;i < 50;i++)
{
printf("%s\n",ddish[i]);
}
}
return 0;
}
数塔
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16400 Accepted Submission(s): 9853
Problem Description
在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：
有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？
已经告诉你了，这是个DP的题目，你能AC吗?
Input
输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。
Output
对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。
Sample Input
1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
貌似不是DP，很简单的从塔底往上走，取一个顶点下两个分支最大值加到这个顶点。加到塔顶就是最优解了。
HDU2084.cpp
#include <iostream>
#include <cstdio>
using namespace std;
#define MAXN 100+10
int DP[MAXN][MAXN];
int main()
{
int T,n;
scanf("%d",&T);
for(int i = 0;i < T;i++)
{
scanf("%d",&n);
for(int k = 1;k <= n;k++)
{
for(int j = 1;j <= k;j++)
{
scanf("%d",&DP[k][j]);
}
}
if (n == 1)
{
printf("%d\n",DP[1][1]);
continue;
}
for(int i = n-1;i >= 1;i--)
{
for(int j = 1;j <= i;j++)
{
DP[i][j] += max(DP[i+1][j],DP[i+1][j+1]);
}
}
printf("%d\n",DP[1][1]);
}
return 0;
}
简易版之最短距离
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8774 Accepted Submission(s): 3928
Problem Description
寒假的时候，ACBOY要去拜访很多朋友，恰巧他所有朋友的家都处在坐标平面的X轴上。ACBOY可以任意选择一个朋友的家开始访问，但是每次访问后他都必须回到出发点，然后才能去访问下一个朋友。
比如有4个朋友，对应的X轴坐标分别为1， 2， 3， 4。当ACBOY选择坐标为2的点做为出发点时，则他最终需要的时间为 |1-2|+|2-2|+|3-2|+|4-2| = 4。
现在给出Ｎ个朋友的坐标，那么ACBOY应该怎么走才会花费时间最少呢？
Input
输入首先是一个正整数M，表示M个测试实例。每个实例的输入有2行，首先是一个正整数N（N <= 500)，表示有N个朋友，下一行是N个正整数，表示具体的坐标(所有数据均<=10000).
Output
对于每一个测试实例，请输出访问完所有朋友所花的最少时间，每个实例的输出占一行。
Sample Input
2
2
2 4
3
2 4 6
Sample Output
2
4
这题我是这么想的，既然要是都要回到原来的点，那么就需要以最中间的一个点为起点。
先排序。然后这就分为奇数个点和偶数个点，奇数个点就直接用最中间的点，偶数点就把中间的两个点的距离都遍历。找到最小值就行了。
HDU2083.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 500+10
int s[MAXN];
int main()
{
int M,N;
for(cin>>M;M;M--)
{
cin>>N;
for(int j = 0;j < N;j++)
{
scanf("%d",&s[j]);
}
sort(s,s+N);
int T;
if (N%2)
{
T = (N+1)/2 - 1;
}
else
{
T = (N/2) - 1;
}
int sum = 0;
for(int j = 0;j < N;j++)
{
sum += abs(s[T] - s[j]);
}
int sum2 = 0, T2 = (N/2);
if (!(N%2))
{
for(int j = 0;j < N;j++)
{
sum2 += abs(s[T] - s[j]);
}
if (sum2 < sum)
sum = sum2;
}
printf("%d\n",sum);
}
return 0;
}
手机短号
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13321 Accepted Submission(s): 8443
Problem Description
大家都知道，手机号是一个11位长的数字串，同时，作为学生，还可以申请加入校园网，如果加入成功，你将另外拥有一个短号。假设所有的短号都是是 6+手机号的后5位，比如号码为13512345678的手机，对应的短号就是645678。
现在，如果给你一个11位长的手机号码，你能找出对应的短号吗？
Input
输入数据的第一行是一个N(N <= 200)，表示有N个数据，接下来的N行每一行为一个11位的手机号码。
Output
输出应包括N行，每行包括一个对应的短号，输出应与输入的顺序一致。
Sample Input
2
13512345678
13787654321
Sample Output
645678
654321
水题。简单读取字符串输出“6”+字符串的后五位就行了
HDU2081.cpp
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int main()
{
int T;
string A;
while(cin>>T)
{
for(int i = 0;i < T;i++)
{
cin>>A;
printf("6");
for(int j = 6;j < 11;j++)
{
printf("%c",A[j]);
}
printf("\n");
}
}
return 0;
}
Fibbonacci Number
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10868 Accepted Submission(s): 5549
Problem Description
Your objective for this question is to develop a program which will generate a fibbonacci number. The fibbonacci function is defined as such:
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)
Your program should be able to handle values of n in the range 0 to 50.
Input
Each test case consists of one integer n in a single line where 0≤n≤50. The input is terminated by -1.
Output
Print out the answer in a single line for each test case.
Sample Input
3
4
5
-1
Sample Output
2
3
5
水题，先预处理就可以到前50个然后按输入读数组就可以了
HDU2070.cpp
#include <iostream>
#include <cstdio>
using namespace std;
#define MAXN 50+10
__int64 F[MAXN];
int main()
{
F[0] = 0; F[1] = 1;
for(int i = 2;i <= 50;i++)
{
F[i] = F[i-1] + F[i-2];
}
int n;
while(scanf("%d",&n),n!=-1)
{
printf("%I64d\n",F[n]);
}
return 0;
}
Max Num
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10948 Accepted Submission(s): 7029
Problem Description
There are some students in a class, Can you help teacher find the highest student .
Input
There are some cases. The first line contains an integer t, indicate the cases; Each case have an integer n ( 1 ≤ n ≤ 100 ) , followed n students’ height.
Output
For each case output the highest height, the height to two decimal plases;
Sample Input
2
3 170.00 165.00 180.00
4 165.00 182.00 172.00 160.00
Sample Output
180.00
182.00
水题，不解释了
HDU2071.cpp
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
//freopen("out.txt","w",stdout);
double max = -1;
int T;
while(scanf("%d",&T)!=EOF)
{
for(int ii = 0;ii < T;ii++)
{
int n;
scanf("%d",&n);
max = -1;
double in;
for(int i = 0;i < n;i++)
{
scanf("%lf",&in);
if (in > max)
{
max = in;
}
}
printf("%.2lf\n",max);
}
}
return 0;
}
A - Hashmat the Brave Warrior
Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
Description
Hashmat is a brave warrior who with his group of young soldiers moves from one place to another to fight against his opponents. Before fighting he just calculates one thing, the difference between his soldier number and the opponent's soldier number. From this difference he decides whether to fight or not. Hashmat's soldier number is never greater than his opponent.
Input
The input contains two integer numbers in every line. These two numbers in each line denotes the number of soldiers in Hashmat's army and his opponent's army or vice versa. The input numbers are not greater than 2^32. Input is terminated by End of File.
Output
For each line of input, print the difference of number of soldiers between Hashmat's army and his opponent's army. Each output should be in seperate line.
Sample Input
10 12
10 14
100 200
Sample Output
2
4
100
本题主要是要注意Hashmat's soldier number is never greater than his opponent.这一句。所以读入后要比较一下大小。
UVA10055.cpp
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
long long a,b,c;
while(scanf("%lld%lld",&a,&b)!=EOF)
{
if (a > b)
{
c = a;
a = b;
b = c;
}
printf("%lld\n",b-a);
}
return 0;
}
The Collatz Sequence
An algorithm given by Lothar Collatz produces sequences of integers, and is described as follows:
Step 1:
Choose an arbitrary positive integer A as the first item in the sequence.
Step 2:
If A = 1 then stop.
Step 3:
If A is even, then replace A by A / 2 and go to step 2.
Step 4:
If A is odd, then replace A by 3 * A + 1 and go to step 2.
It has been shown that this algorithm will always stop (in step 2) for initial values of A as large as 109, but some values of A encountered in the sequence may exceed the size of an integer on many computers. In this problem we want to determine the length of the sequence that includes all values produced until either the algorithm stops (in step 2), or a value larger than some specified limit would be produced (in step 4).
Input
The input for this problem consists of multiple test cases. For each case, the input contains a single line with two positive integers, the first giving the initial value of A (for step 1) and the second giving L, the limiting value for terms in the sequence. Neither of these, A or L, is larger than 2,147,483,647 (the largest value that can be stored in a 32-bit signed integer). The initial value of A is always less than L. A line that contains two negative integers follows the last case.
Output
For each input case display the case number (sequentially numbered starting with 1), a colon, the initial value for A, the limiting value L, and the number of terms computed.
Sample Input
3 100
34 100
75 250
27 2147483647
101 304
101 303
-1 -1
Sample Output
Case 1: A = 3, limit = 100, number of terms = 8
Case 2: A = 34, limit = 100, number of terms = 14
Case 3: A = 75, limit = 250, number of terms = 3
Case 4: A = 27, limit = 2147483647, number of terms = 112
Case 5: A = 101, limit = 304, number of terms = 26
Case 6: A = 101, limit = 303, number of terms = 1
本题其实简单，前面A,L用的都是int类型然后超时了，接着我用__int64，服务器不识别。然后又用long long 类型才秒过
题意：给你一个初始A递归：如果A==1则停止，如果A是偶数则A = A / 2 如果A是奇数 则 A = 3 * A + 1
这里还有L的用处，L是限定A的大小，如果上述步骤中A超过了L也直接停止 输出 步骤数
UVA694.cpp
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
long long A,L;
int C = 0;
long long a,b;
while(scanf("%lld%lld",&A,&L),A>=0&&L>=0)
{
b = 0;
a = A;
while(b++,a != 1 && b < L)
{
if (a%2)
{
a = 3 * a + 1;
if (a > L)
{
break;
}
}
else
{
a /= 2;
}
}
printf("Case %d: A = %lld, limit = %lld, number of terms = %lld\n",++C,A,L,b);
}
return 0;
}
RPG的错排
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5666 Accepted Submission(s): 2325
Problem Description
今年暑假杭电ACM集训队第一次组成女生队,其中有一队叫RPG,但做为集训队成员之一的野骆驼竟然不知道RPG三个人具体是谁谁。RPG给他机会让他猜猜，第一次猜：R是公主，P是草儿，G是月野兔；第二次猜：R是草儿，P是月野兔，G是公主；第三次猜：R是草儿，P是公主，G是月野兔；......可怜的野骆驼第六次终于把RPG分清楚了。由于RPG的带动，做ACM的女生越来越多，我们的野骆驼想都知道她们，可现在有N多人，他要猜的次数可就多了，为了不为难野骆驼，女生们只要求他答对一半或以上就算过关，请问有多少组答案能使他顺利过关。
Input
输入的数据里有多个case,每个case包括一个n，代表有几个女生，（n<=25）, n = 0输入结束。
Sample Input
1 2 0
Sample Output
1 1
本题主要是全错位排列。开始先考虑人数n奇偶，奇数就从猜对n/2+1开始，偶数就从n/2开始，一直循环到n.
假设猜对s个，没猜对t个，其中t = n-s。 组数为C（n,s)*剩余t个人全部没猜中的所有情况。剩余t个人全部没有猜中就是全错位排列
百度一下可知道其递推公式为 f(n)=nf(n-1)+(-1)^(n-2) 又知道 1个元素没有全错位排列，2个元素的全错位排列有1种，3个元素的全错位排列有2种，4个元素的全错位排列有9种，5个元素的全错位排列有44种。
于是可以用for循环递推到13
HDU2068.cpp
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
#define MAXN 25+5
int F[MAXN];
double zuhe(int up,int down);
double jiecheng(int a);
int main()
{
F[1] = 0;
F[2] = 1;
for(int i = 3;i <= 13;i++)
{
F[i] = i*F[i-1] + pow(-1,i-2);
}
F[0] = 1;
int n;
while(cin>>n,n!=0)
{
__int64 an = 0;
int s,t;//s表示猜对的人数 t表示没猜对的人数
if (n%2)
{
s = n/2 + 1;
}
else
{
s = n/2;
}
t = n - s;
do
{
an += zuhe(s,n)*F[t];
}
while(s++,t--);
printf("%I64d\n",an);
}
return 0;
}
double jiecheng(int a)
{
double s = 1;
for(int i = 1;i <= a;i++)
{
s *= i;
}
return s;
}
double zuhe(int up,int down)
{
return jiecheng(down)/(jiecheng(up)*jiecheng(down-up));
}