HDU 2007'10 Programming Contest
点击打开链接
Secret Number
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7398 Accepted Submission(s): 3138
Problem Description 有一天, KIKI 收到一张奇怪的信, 信上要KIKI 计算出给定数各个位上数字为偶数的和.
eg. 5548
结果为12 , 等于 4 + 8
KIKI 很苦恼. 想请你帮忙解决这个问题.
Input 输入数据有多组,每组占一行,只有一个数字,保证数字在INT范围内.
Output 对于每组输入数据,输出一行,每两组数据之间有一个空行.
Sample Input
415326
3262
Sample Output
1210
Author kiki
//0MS 328K
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
char s[1007];
int main()
{int cas=0;while(cin>>s){if(cas){printf("n");}if(!cas)cas=1;int len=strlen(s),count=0;for(int i=0;i<len;i++){int a=s[i]-'0';if(a%2==0)count+=a;}printf("%dn",count);}return 0;
}
点击打开链接
Calculate S(n)
Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7140 Accepted Submission(s): 2643
Problem Description Calculate S(n).
S(n)=1
3+2
3 +3
3 +......+n
3 .
Input Each line will contain one integer N(1 < n < 1000000000). Process to end of file.
Output For each case, output the last four dights of S(N) in one line.
Sample Input
1
2
Sample Output
0001
0009
Author 天邪
因为要求后4位，所以当n大于10000的时候可以mod 10000。以此推类，如果要求后3位，可以mod 1000，求后两位mod 100.当然S(n)如果是求2次方，4次方，5次方等等，此规律也成立。不过求3次方，有公式:S(n)=(n*(n+1)/2)^2.而我是暴力过的。
//62MS 264K
#include<stdio.h>
int dp[10001]={0};
int main()
{int n;for(int i=1;i<=10000;i++)dp[i]=(dp[i-1]+i%10000*i%10000*i%10000)%10000;while(scanf("%d",&n)!=EOF){n%=10000;printf("%04dn",dp[n]%10000);}return 0;
}
点击打开链接
I Love This Game
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5265 Accepted Submission(s): 1821
Problem Description Do you like playing basketball ? If you are , you may know the NBA Skills Challenge . It is the content of the basketball skills . It include several parts , such as passing , shooting , and so on. After completion of the content , the player who takes the shortest time will be the winner . Now give you their names and the time of finishing the competition , your task is to give out the rank of them ; please output their name and the rank, if they have the same time , the rank of them will be the same ,but you should output their names in lexicographic order.You may assume the names of the players are unique.
Is it a very simple problem for you? Please accept it in ten minutes.
Input This problem contains multiple test cases! Ease test case contain a n(1<=n<=10) shows the number of players,then n lines will be given. Each line will contain the name of player and the time(mm:ss) of their finish.The end of the input will be indicated by an integer value of zero.
Output The output format is shown as sample below.
Please output the rank of all players, the output format is shown as sample below;
Output a blank line between two cases.
Sample Input
10
Iverson 17:19
Bryant 07:03
Nash 09:33
Wade 07:03
Davies 11:13
Carter 14:28
Jordan 29:34
James 20:48
Parker 24:49
Kidd 26:46
0
Sample Output
Case #1
Bryant 1
Wade 1
Nash 3
Davies 4
Carter 5
Iverson 6
James 7
Parker 8
Kidd 9
Jordan 10
Author 為傑沉倫
一个sort二重排序的问题，然后处理好rank就行了。
//0MS 244K
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct sa
{char s[27];int hour,min,rank;
}p[107],pp[107];
int cmp(sa a,sa b)
{if(a.hour==b.hour){if(a.min==b.min)return (strcmp(a.s,b.s)<0);return a.min<b.min;}return a.hour<b.hour;
}
int main()
{int n,cas=1;while(scanf("%d",&n),n){for(int i=0;i<n;i++)scanf("%s %d:%d",&p[i].s,&p[i].hour,&p[i].min);sort(p,p+n,cmp);if(cas!=1)printf("n");printf("Case #%dn",cas++);pp[0]=p[0];pp[0].rank=1;int k=0,r=1,rr=1;printf("%s %dn",p[0].s,r);for(int i=1;i<n;i++){int flag=0;if(p[i].hour!=pp[k].hour||p[i].min!=pp[k].min){r++;flag=1;}printf("%s %dn",p[i].s,r);if(!flag){r++;}pp[++k]=p[i];}}return 0;
}
点击打开链接
Has the sum exceeded
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3210 Accepted Submission(s): 679
Problem Description As we all know, in the computer science, an integer A is in the range of 32-signed integer, which means the integer A is between -2^31 and (2^31)-1 (inclusive), and A is a 64-signed integer, which means A is between -2^63 and (2^63)-1(inclusive). Now we give the K-signed range, and two K-signed integers A and B, you should check whether the sum of A and B is beyond the range of K-signed integer or not.
Input There will be many cases to calculate. In each case, there comes the integer K (2<=K<=64) first in a single line. Then following the line, there is another single line which has two K-signed integers A and B.
Output For each case, you should estimate whether the sum is beyond the range. If exceeded, print “Yes”, otherwise “WaHaHa”.
Sample Input
32
100 100
Sample Output
WaHaHa
Author Wangye
判断在k位下的两个数字之和是否超出这个范围。 硬加的话可能导致超出范围而MLE，因此要用k位下最大值减去其中一个数然后比较。 //0MS 228K
#include<stdio.h>
#include<string.h>
#include<math.h>
long long multi(long long a,long long b)//a*b
{long long ret=0;while(b>0){if(b&1)ret=(ret+a);b>>=1;a=(a<<1);}return ret;
}
long long quick_mod(long long a,long long b)//a^b
{long long ans=1;while(b){if(b&1){ans=multi(ans,a);b--;}b/=2;a=multi(a,a);}return ans;
}
int main()
{long long a,b,n;while(scanf("%I64d%I64d%I64d",&n,&a,&b)!=EOF){long long high=quick_mod(2,n-1);long long low=-high;high--;if(a==0&&b==0||a>0&&b<0||a<0&&b>0)//因为a和b已经在k位下，所以如果一正一负的话，它们的和肯定更小{printf("WaHaHan");continue;}if(a>0){if(high-a<b)printf("Yesn");//如果超出上界else printf("WaHaHan");continue;}if(low-a>b)printf("Yesn");//如果超出下界else printf("WaHaHan");}return 0;
}
点击打开链接
Just a Numble
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2083 Accepted Submission(s): 975
Problem Description Now give you two integers n m, you just tell me the m-th number after radix point in 1/n,for example n=4,the first numble after point is 2,the second is 5,and all 0 followed
Input Each line of input will contain a pair of integers for n and m(1<=n<=10^7,1<=m<=10^5)
Output For each line of input, your program should print a numble on a line,according to the above rules
Sample Input
4 2
5 7
123 123
Sample Output
5
0
8
Author YBB
直接模拟除法，每次都用余数*10，然后再除以n，一直进行m次。 //140MS 228K
#include<stdio.h>
int main()
{int n,m;while(scanf("%d%d",&n,&m)!=EOF){int ans,a=10,mod=10;if(n==1){printf("0n");continue;}for(int i=1;i<=m;i++){ans=a/n;a=a%n;a*=10;}printf("%dn",ans);}return 0;
}
点击打开链接
Mouse
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 577 Accepted Submission(s): 114
Problem Description A greedy mouse cici ate rat poison by mistake. To save herself, she have to drink.
Cici can only walk in four ways that marked in the photoes followed and only move in the region that colored blue..She expend energy every step.There are cheese in every position which cici can eat to gain energy once she is there.He will never reach the river if she run out of energy.The initially energy of cici is energy of the cheese at the coordinate (0,0).
if when the mouse arrive a position has 0 energy , he can't eat the cheese.
Now can you help the wretched monse to calculate whether can he get to the river.
If she can,calculate the minimun energy of the maximal energy of every possible position of the river(Y = N-1).
Input There are several test cases.In each case,there are three integers n(0<n<=200),m(0<m<=10),and k(0<k<=10)in the first line ,the next n lines followed. The second line has only one integer c(0<c<=100),the i-th line has m integers more than (i-1)th line.
k is the energy each step cost.
Output If the monkey can not get to the river,print "what a pity mouse!!" int one line;If she can,calculate the minimun energy of the maximal energy of every possible position of the river(Y = N-1).
Sample Input
7 2 3
5
3 6 4
6 9 2 5 6
2 5 3 7 1 6 7
8 9 3 2 6 3 8 9 5
3 5 3 6 4 3 5 6 8 4 2
2 6 3 3 6 7 8 5 3 1 4 5 6
Sample Output
11
Author Kiki
一只中了毒的老鼠，要从（1,1）的位置走到（n，i）的位置，每走到一个方格会消耗k点体力值，同时得到此方格的体力值，如果体力值小于0，就不能走了，让你判断能否到达，如果能够到达，让你求在每一步都取得最大体力值的情况下，在第n行中剩下的最小体力值。 //1015MS 3024K
#include<stdio.h>
#include<string.h>
#define M 207
#define inf 0x3f3f3f3f
int energy[M][M*10],can[M][M*10];
int dir[4][20]= {{0,1},{1,0},{1,2},{2,1}};//定义四个方向
int n,m,k;
int solve()
{can[1][1]=energy[1][1];for(int i=1; i<=n; i++)for(int j=1; j<=(i-1)*m+1; j++)if(can[i][j]-k>0)//如果走到此方格剩余的体力比要消耗的多，就可以行动for(int kk=0; kk<4; kk++){int xx=i+dir[kk][0];int yy=j+dir[kk][1];if(xx<=n&&yy<=(xx-1)*m+1&&(can[xx][yy]==-1||can[xx][yy]<energy[xx][yy]-k+can[i][j]))can[xx][yy]=can[i][j]+energy[xx][yy]-k;//更新每一个方格的最大值}int ans=inf;for(int j=1; j<=(n-1)*m+1; j++)if(can[n][j]<ans&&can[n][j]>0)ans=can[n][j];return ans;
}
int main()
{while(scanf("%d%d%d",&n,&m,&k)!=EOF){for(int i=1; i<=n; i++){for(int j=1; j<=(i-1)*m+1; j++){scanf("%d",&energy[i][j]);can[i][j]=-1;}}int ans=solve();if(ans==inf)printf("what a pity mouse!!n");//如果不能到达else printf("%dn",ans);}return 0;
}
点击打开链接
Matrix
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1635 Accepted Submission(s): 716
Problem Description Give you a matrix(only contains 0 or 1),every time you can select a row or a column and delete all the '1' in this row or this column .
Your task is to give out the minimum times of deleting all the '1' in the matrix.
Input There are several test cases.
The first line contains two integers n,m(1<=n,m<=100), n is the number of rows of the given matrix and m is the number of columns of the given matrix.
The next n lines describe the matrix:each line contains m integer, which may be either ‘1’ or ‘0’.
n=0 indicate the end of input.
Output For each of the test cases, in the order given in the input, print one line containing the minimum times of deleting all the '1' in the matrix.
Sample Input
3 3
0 0 0
1 0 1
0 1 0
0
Sample Output
2
Author Wendell
多次选择一横行或者一竖行，使得所有的1都包括。问至少几次使得所有1都包括。 最小点覆盖，将x作为一个集合，y作为一个集合，如果1，则将i，j连接，找最少的i和j使得覆盖所有连线，最小覆盖==最大匹配数。 //93MS 320K
#include<stdio.h>
#include<string.h>
#define M 107
int n,m;
int link[M],g[M][M];
bool vis[M];
int map[M][M];
bool find(int i)
{for(int j=1;j<=m;j++)if(g[i][j]&&!vis[j]){vis[j]=1;if(!link[j]||find(link[j])){link[j]=i;return true;}}return false;
}
int main()
{while(scanf("%d",&n),n){scanf("%d",&m);memset(link,0,sizeof(link));memset(g,0,sizeof(g));int count=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&map[i][j]);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)if(map[i][j]==1)g[i][j]=1;}for(int i=1;i<=n;i++){memset(vis,false,sizeof(vis));if(find(i))count++;}printf("%dn",count);}return 0;
}
点击打开链接
Ice_cream's world I
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 481 Accepted Submission(s): 260
Problem Description ice_cream's world is a rich country, it has many fertile lands. Today, the queen of ice_cream wants award land to diligent ACMers. So there are some watchtowers are set up, and wall between watchtowers be build, in order to partition the ice_cream’s world. But how many ACMers at most can be awarded by the queen is a big problem. One wall-surrounded land must be given to only one ACMer and no walls are crossed, if you can help the queen solve this problem, you will be get a land.
Input In the case, first two integers N, M (N<=1000, M<=10000) is represent the number of watchtower and the number of wall. The watchtower numbered from 0 to N-1. Next following M lines, every line contain two integers A, B mean between A and B has a wall(A and B are distinct). Terminate by end of file.
Output Output the maximum number of ACMers who will be awarded.
One answer one line.
Sample Input
8 10
0 1
1 2
1 3
2 4
3 4
0 5
5 6
6 7
3 6
4 7
Sample Output
3
Author Wiskey
给你一个图让你求图中最多有多少个环。 可以用并查集来做，如果两个点在同一个集合里面，那么他们就可以形成环。 //232K 534 B
#include<stdio.h>
int pre[10007];
int find(int x)
{while(x!=pre[x])x=pre[x];return x;
}
int main()
{int n,m,count;while(scanf("%d%d",&n,&m)!=EOF){for(int i=0; i<n; i++)pre[i]=i;count=0;for(int i=0; i<m; i++){int a,b;scanf("%d%d",&a,&b);int x=find(a);int y=find(b);if(x==y)count++;//如果这两个点在同一个集合里面，说明可以形成一个环else pre[x]=y;}printf("%dn",count);}}
点击打开链接
Ice_cream’s world II
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2453 Accepted Submission(s): 574
Problem Description After awarded lands to ACMers, the queen want to choose a city be her capital. This is an important event in ice_cream world, and it also a very difficult problem, because the world have N cities and M roads, every road was directed. Wiskey is a chief engineer in ice_cream world. The queen asked Wiskey must find a suitable location to establish the capital, beautify the roads which let capital can visit each city and the project’s cost as less as better. If Wiskey can’t fulfill the queen’s require, he will be punishing.
Input Every case have two integers N and M (N<=1000, M<=10000), the cities numbered 0…N-1, following M lines, each line contain three integers S, T and C, meaning from S to T have a road will cost C.
Output If no location satisfy the queen’s require, you must be output “impossible”, otherwise, print the minimum cost in this project and suitable city’s number. May be exist many suitable cities, choose the minimum number city. After every case print one blank.
Sample Input
3 1
0 1 14 4
0 1 10
0 2 10
1 3 20
2 3 30
Sample Output
impossible40 0
Author Wiskey
因为路径都是有向的，而且要将所有的点都包括，那么此题就是求不定根的最小树形图了。 //408K 2665 B
#include<stdio.h>
#include<string.h>
#include<math.h>
#define M 10007
#define inf 0x3f3f3f
using namespace std;
int pre[M],vis[M],id[M];
int in[M];
int n,m,ansi;struct Node//建立邻接表
{int u,v;int cost;
}E[M*M+5];int direct_mst(int root,int nv,int ne)
{int ret=0;while(true){//找最小入边for(int i=0;i<nv;i++)in[i]=inf;for(int i=0;i<ne;i++){int u=E[i].u;int v=E[i].v;if(E[i].cost<in[v]&&u!=v){pre[v]=u;if(u==root)ansi=i;in[v]=E[i].cost;}}for(int i=0;i<nv;i++){if(i==root)continue;if(in[i]==inf)return -1;}//找环int cntnode=0;memset(id,-1,sizeof(id));memset(vis,-1,sizeof(vis));in[root]=0;for(int i=0;i<nv;i++)//标记每个环{ret+=in[i];int v=i;while(vis[v]!=i&&id[v]==-1&&v!=root){vis[v]=i;v=pre[v];}if(v!=root&&id[v]==-1){for(int u=pre[v];u!=v;u=pre[u]){id[u]=cntnode;}id[v]=cntnode++;}}if(cntnode==0)break;//无环for(int i=0;i<nv;i++)if(id[i]==-1)id[i]=cntnode++;//缩点，重新标记for(int i=0;i<ne;i++){int v=E[i].v;E[i].u=id[E[i].u];E[i].v=id[E[i].v];if(E[i].u!=E[i].v){E[i].cost-=in[v];}}nv=cntnode;root=id[root];}return ret;
}int main()
{while(scanf("%d%d",&n,&m)!=EOF){int u,v,w,sum=0;for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&w);E[i].u=++u;E[i].v=++v;if(u!=v)E[i].cost=w;elseE[i].cost=inf;sum+=w;}sum++;for(int i=0;i<n;i++){E[m+i].u=0;E[m+i].v=i+1;E[m+i].cost=sum;}int ans=direct_mst(0,n+1,m+n);//n代表点的个数，m代表边的个数if(ans==-1||ans-sum>=sum)printf("impossiblen");//无法生成最小树形图elseprintf("%d %dn",ans-sum,ansi-m);printf("n");}return 0;
}
点击打开链接
Ice_cream’s world III
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 657 Accepted Submission(s): 213
Problem Description ice_cream’s world becomes stronger and stronger; every road is built as undirected. The queen enjoys traveling around her world; the queen’s requirement is like II problem, beautifies the roads, by which there are some ways from every city to the capital. The project’s cost should be as less as better.
Input Every case have two integers N and M (N<=1000, M<=10000) meaning N cities and M roads, the cities numbered 0…N-1, following N lines, each line contain three integers S, T and C, meaning S connected with T have a road will cost C.
Output If Wiskey can’t satisfy the queen’s requirement, you must be output “impossible”, otherwise, print the minimum cost in this project. After every case print one blank.
Sample Input
2 1
0 1 104 0
Sample Output
10impossible
Author Wiskey
最小生成树以及判断能否形成最小生成树。 //125MS 344K
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m;
int pre[1007];
struct E
{int u,v,w;
}edg[1007*100];
int cmp(E a,E b)
{return a.w<b.w;
}
int find(int x)
{while(x!=pre[x])x=pre[x];return x;
}
void unio(int a,int b)
{int x=find(a);int y=find(b);if(x==y)return;pre[x]=y;
}
int main()
{while(scanf("%d%d",&n,&m)!=EOF){int sum=0,edge=1;for(int i=0;i<=1000;i++)pre[i]=i;for(int i=0;i<m;i++){scanf("%d%d%d",&edg[i].u,&edg[i].v,&edg[i].w);}sort(edg,edg+m,cmp);for(int i=0;i<m;i++){if(find(edg[i].u)!=find(edg[i].v)){edge++;//边的个数sum+=edg[i].w;unio(edg[i].u,edg[i].v);}}int flag=0;if(edge!=n)printf("impossiblenn");else printf("%dnn",sum);}return 0;
}
