@lawk97
2016-12-11T17:57:09.000000Z
字数 7934
阅读 899
作业
[HDU - 5090]
Tom and Jerry are playing a game with tubes and pearls. The rule of
the game is:1) Tom and Jerry come up together with a number K.
2) Tom provides N tubes. Within each tube, there are several pearls.
The number of pearls in each tube is at least 1 and at most N.3) Jerry puts some more pearls into each tube. The number of pearls
put into each tube has to be either 0 or a positive multiple of K.
After that Jerry organizes these tubes in the order that the first
tube has exact one pearl, the 2nd tube has exact 2 pearls, …, the Nth
tube has exact N pearls.4) If Jerry succeeds, he wins the game, otherwise Tom wins.
Write a program to determine who wins the game according to a given N,
K and initial number of pearls in each tube. If Tom wins the game,
output “Tom”, otherwise, output “Jerry”.
Input
The first line contains an integer M (M<=500), then M games follow.
For each game, the first line contains 2 integers, N and K (1 <= N <=
100, 1 <= K <= N), and the second line contains N integers presenting
the number of pearls in each tube.
Output
For each game, output a line containing either “Tom” or “Jerry”.
题意
有n个管子，每个管子有最少一个，最多n个珍珠。现在向每个管子中添加0 个，或k的正整数倍个珍珠。如果添加完成后，经过排序，可以使得n个管子中的珍珠数依次分别是1到n，则认为Jerry胜利，输出Jerry。如果不能，则认为Tom胜利，输出Tom。
思路
可以看做是要想办法凑出从1到n的n个数。同时，每次可以添加的数，都可以看做是k的非负整数倍(k*0=0)。
如果现计划凑出某个数，已经确定既可以用某个较小的数通过增加k的倍数的形式，也可以用某个相对更大的数通过增加k的倍数的形式来凑。那么如果我们计划用其中一个数去凑这个目标数，用另一个数去凑比目标数更大的数的话，无论选择哪个数去凑目标数，都不会对比这个数大的数造成影响。因为用这两个数，去凑更大的数时，可以将它们认为是等效的。
在凑从1到n这n个数的过程中，每次的目标数都是当前最小的，因此在可以凑出这个目标数的范围内选一个数即可。显然依次选择最易操作，当然我们并不是每次一定要选择尽可能小的，只是因为这样好操作而已。
代码
#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <string>using namespace std;int m;int main(){scanf("%d",&m);while(m--){int n,k,flag=1;scanf("%d%d",&n,&k);int a[105],v[105];for(int i=0;i<n;i++)scanf("%d",&a[i]);memset(v, 0, sizeof(v));sort(a, a+n);for(int i=0;i<n;i++){int x=a[i];flag=1;while(x<=n){if(v[x]==0){v[x]=1;flag=0;break;}x+=k;}if(flag)break;}if(flag)printf("Tom\n");elseprintf("Jerry\n");}return 0;}
[HDU - 5092]
Fish likes to take photo with his friends. Several days ago, he found
that some pictures of him were damaged. The trouble is that there are
some seams across the pictures. So he tried to repair these pictures.He scanned these pictures and stored them in his computer. He knew it
is an effective way to carve the seams of the images He only knew that
there is optical energy in every pixel.He learns the following principle of seam carving.
Here seam carving refers to delete through
horizontal or vertical line of pixels across the whole image to
achieve image scaling effect. In order to maintain the characteristics
of the image pixels to delete the importance of the image lines must
be weakest. The importance of the pixel lines is determined in
accordance with the type of scene images of different energy content.
That is, the place with the more energy and the richer texture of the
image should be retained. So the horizontal and vertical lines having
the lowest energy are the object of inspection. By constantly deleting
the low-energy line it can repair the image as the original scene.For an original image G of m*n, where m and n are the row and column
of the image respectively. Fish obtained the corresponding energy
matrix A. He knew every time a seam with the lowest energy should be
carved. That is, the line with the lowest sum of energy passing
through the pixels along the line, which is a 8-connected path
vertically or horizontally.Here your task is to carve a pixel from the first row to the final row
along the seam. We call such seam a vertical seam.
Input
There several test cases. The first line of the input is an integer T,
which is the number of test cases, 0 integers m, n, which are the row and column of the energy matrix of an
image, (0
Output
For each test case, print “Case #” on the first line, where # is the
order number of the test case (starting with 1). Then print the column
numbers of the energy matrix from the top to the bottom on the second
line. If there are more than one such seams, just print the column
number of the rightmost seam.
题意
现要修补照片，遵从以下法则：
将照片看做是一个由像素点构成的m排n列的矩阵。从第一排往下一排一排地选择像素点，每排只选择一个像素点，要求当前排的选定点，与下一排的选定点或垂直或以45度斜线相连。找出所有选定像素点的权值和最小的方案。如果同时有很多种方案，选择连线尽可能靠右的方案。
思路
动态规划。从左往右，从上到下，找出到每个点时当前的总权重和最大值，并记录对应的上一个点的位置。之后找出最后一排中，到该点的总权重和最大的点。并一步步倒推，找出其对应方案的连线方式。
代码
#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <string>using namespace std;int t;struct visi{int sum,last;};int main(){scanf("%d",&t);for(int k=1;k<=t;k++){int m,n,map[105][105];visi v[105][105];scanf("%d%d",&m,&n);for(int i=0;i<m;i++)for(int j=0;j<n;j++)scanf("%d",&map[i][j]);for(int i=0;i<m;i++){for(int j=0;j<n;j++){int pos=j+1;v[i][j].sum=map[i][j];if(i==0)continue;if(j+1>=n)pos=j;else if (v[i-1][j].sum<v[i-1][j+1].sum)pos=j;if(j-1>=0&&v[i-1][j-1].sum<v[i-1][pos].sum)pos=j-1;v[i][j].sum+=v[i-1][pos].sum;v[i][j].last=pos;}}int l=n-1;for(int i=n-2;i>=0;i--){if(v[m-1][i].sum<v[m-1][l].sum)l=i;}int ans[105],step=0;ans[step++]=l+1;while(step<m){l=v[m-step][l].last;ans[step++]=l+1;}printf("Case %d\n",k);for(int i=m-1;i>=0;i--){if(i<m-1)printf(" ");printf("%d",ans[i]);}printf("\n");}return 0;}
[HDU - 5095]
SVM（Support Vector Machine）is an important classification tool, which
has a wide range of applications in cluster analysis, community
division and so on. SVM The kernel functions used in SVM have many
forms. Here we only discuss the function of the form f(x,y,z) = ax^2 +
by^2 + cy^2 + dxy + eyz + fzx + gx + hy + iz + j. By introducing new
variables p, q, r, u, v, w, the linearization of the function f(x,y,z)
is realized by setting the correspondence x^2 <-> p, y^2 <-> q, z^2
<-> r, xy <-> u, yz <-> v, zx <-> w and the function f(x,y,z) = ax^2 +
by^2 + cy^2 + dxy + eyz + fzx + gx + hy + iz + j can be written as
g(p,q,r,u,v,w,x,y,z) = ap + bq + cr + du + ev + fw + gx + hy + iz + j,
which is a linear function with 9 variables.Now your task is to write a program to change f into g.
Input
The input of the first line is an integer T, which is the number of
test data (T<120). Then T data follows. For each data, there are 10
integer numbers on one line, which are the coefficients and constant
a, b, c, d, e, f, g, h, i, j of the function f(x,y,z) = ax^2 + by^2 +
cy^2 + dxy + eyz + fzx + gx + hy + iz + j.
Output
For each input function, print its correspondent linear function with
9 variables in conventional way on one line.
题意
给出函数f(x,y,z) = ax^2 + by^2 + cy^2 + dxy + eyz + fzx + gx + hy + iz + j 中的所有参数的值，现要执行以下操作：
x^2 <-> p, y^2 <-> q, z^2 <-> r, xy <-> u, yz <-> v, zx <-> w 。
操作完成后，得到g(p,q,r,u,v,w,x,y,z) = ap + bq + cr + du + ev + fw + gx + hy + iz + j。
根据常规的书写习惯，输出g(p,q,r,u,v,w,x,y,z)的表达式。
思路
题目本身没有难度。麻烦的地方在于细节的把握。
对于非常数项，如果系数为0，则该项为0，即不用输出。如果系数为正，要注意如果不是第一个输出的项的话，需要补全“+”号。如果系数为1或-1，符号‘1’不能输出。
对于常数项，如果常数项为0的话,若之前有非常数项输出，则不用输出常数项；若之前没有非常数项输出，则需要输出0。
代码
#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <string>using namespace std;int t;char h[]={'p','q','r','u','v','w','x','y','z'};int main(){scanf("%d",&t);while(t--){int flag=0,x;for(int i=0;i<9;i++){scanf("%d",&x);if(x>1){if(flag)printf("+");printf("%d%c",x,h[i]);flag=1;}else if(x==1){if(flag)printf("+");printf("%c",h[i]);flag=1;}else if(x==-1){printf("-%c",h[i]);flag=1;}else if(x<0){printf("%d%c",x,h[i]);flag=1;}}scanf("%d",&x);if(x>0){if(flag)printf("+");printf("%d",x);}else if (x==0&&!flag)printf("%d",x);else if(x<0)printf("%d",x);printf("\n");}return 0;}
[HDU - 5578]
NN frogs from different countries are standing in a line. Each
country is represented by a lowercase letter. The distance between
adjacent frogs (e.g. the 1st1st and the 2nd2nd frog, the N−1thN−1th
and the NthNth frog, etc) are exactly 11. Two frogs are friends if
they come from the same country.The closest friends are a pair of friends with the minimum distance.
Help us find that distance.
Input
First line contains an integer TT, which indicates the number of test
cases.Every test case only contains a string with length NN, and the ithith
character of the string indicates the country of ithith frogs.⋅⋅ 1≤T≤50.
⋅⋅ for 80% data, 1≤N≤100.
⋅⋅ for 100% data, 1≤N≤1000.
⋅⋅ the string only contains lowercase letters.
Output
For every test case, you should output " Case #x: y", where xx
indicates the case number and counts from 11 and yy is the result. If
there are no frogs in same country, output −1−1 instead.
题意
给出一列小写字母，每个相邻的字母之间的距离为1。找出两个相同字母之间的最小距离。
思路
从前往后依次遍历。如果当前的字母之前已找到过，即存在该字母的‘最新位置‘，则求出其与该字母的‘最新位置‘之间的距离。完成此步后，无论之前有没有找到过该字母，将当前字母的位置记录为该字母的’最新位置‘。每算出一次距离，判断是否要更新当前找到的’最小距离‘。
代码
#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <string>using namespace std;int t;int main(){scanf("%d",&t);for (int i=1; i<=t; i++){char a[1005];int p[30];int len,ans,flag=0;scanf("%s",a);len=(int)strlen(a)-1;ans=len;memset(p, -1, sizeof(p));for(int i=0;i<len;i++){if(p[a[i]-'a']!=-1){flag=1;if(i-p[a[i]-'a']<ans)ans=i-p[a[i]-'a'];}p[a[i]-'a']=i;}printf("Case #%d: ",i);if(!flag)printf("-1\n");elseprintf("%d\n",ans);}return 0;}