HDOJ水题集合4:杂题
概述
Solved Problem ID Title Ratio(Accepted / Submitted)
1001 更高、更快、更强 41.30%(19/46)(模拟)
1002 迷宫事件,胡恺再现 23.53%(8/34)(BFS)
1003 抗旱救灾,承轩有责 25.40%(16/63)(并查集)
1004 家瑞学信奥 10.00%(4/40)(DP)
1001 更高、更快、更强
更高、更快、更强
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 46 Accepted Submission(s) : 19
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
我们都知道,奥林匹克的精神是“更高,更快,更强”!
信息学奥林匹克也是奥林匹克哦~
大家作为信息学奥林匹克竞赛的爱好者,也应该有着同样的追求~
今天,你的任务就是要找出哪一个更快,哪一个更高,哪一个更强。
Input
输入数据第一行是一个整数T( 1 < =T< = 50 ),表示有T组测试用例。
每组测试案例包含3行:
第一行是纪录的类型,我们有三种类型“Faster” 、“Higher” 或 “Stronger” 。
第二行是一个正整数n表示纪录的个数。
第三行有n个正整数,即记录数据。
所有整数均小于2008。
Output
每组数据输出一行。
如果该类型是“Faster” ,则表示的是时间记录,你应该输出速度最快的那一个。
如果该类型是“Higher” ,则表示长度的记录,你应该输出最高的那一个。
如果类型是“Stronger” ,表示重量的纪录。你应该输出最强的那一个。
Sample Input
3
Faster
3
10 11 12
Higher
4
3 5 4 2
Stronger
2
200 200
Sample Output
10
5
200
#include<bits/stdc++.h>
using namespace std;
int a[5050];
int main(){
int T; cin>>T;
while(T--){
string s; int n; cin>>s>>n;
for(int i=1; i<=n; i++)cin>>a[i];
sort(a+1,a+n+1);
if(s=="Faster")cout<<a[1]<<"\n";
else if(s=="Higher")cout<<a[n]<<"\n";
else if(s=="Stronger")cout<<a[n]<<"\n";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
1002 迷宫事件,胡恺再现
迷宫事件,胡恺再现
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 34 Accepted Submission(s) : 8
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
“张晨乐陷入迷宫事件”还没有过去几天,又发生了一件类似的事件!
王胡恺,作为张晨乐的文渊中学同学,一直对上次的那个迷宫充满好奇,他很想知道是什么一个迷宫能把张晨乐弄得那么狼狈,他决定一探究竟。
就在前天,王胡恺无视老师的警告,一个人悄悄地进入了迷宫,他刚刚进去不久,迷宫又开始摇晃,他意识到:这次闯大祸了,要是被困住,没吃没喝事小,不能参加丁爸的信奥考试就太遗憾了!于是,王胡恺不顾一切地想冲出这个迷宫。
迷宫是一个大小为N*M的矩形,有一扇门,一开始,门是打开的,并将在T秒后关闭。因此,王胡恺必须最迟在第T秒钟到达门口。
每一秒,他都可以向上,下,左,右四个相邻的位置中的任意一个移动,请问,可怜的王胡恺能够逃出迷宫吗?
Input
输入由多个测试用例组成。
每个测试用例的第一行包含三个整数N,M和T(1 <N,M <7; 0 <T <50),分别表示迷宫的大小为N*M,门将在T秒后关闭。
接下来的N行给出迷宫布局,每行包含M个字符。
每个字符含义如下:
‘X’:不能进入的墙
‘S’:起点
‘D’:门
‘.’:可以行走的地方
输入以三个0结束,这个测试用例不被处理。
Output
对于每组测试数据,如果王胡恺能够逃出迷宫,则请输出“YES”,否则,请输出“NO”。
每组数据输出占一行。
Sample Input
4 4 5
S.X.
…X.
…XD
…
3 4 5
S.X.
…X.
…D
0 0 0
Sample Output
NO
YES
Source
丁爸信奥培训(2018春)- 结业测试(0)
#include<bits/stdc++.h>
using namespace std;
char a[10][10];
int vis[10][10];
struct node{int x, y, step; char ch;};
const int dx[] = {0,0,-1,1};
const int dy[] = {1,-1,0,0};
int main(){
int n, m, t;
while(cin>>n>>m>>t){
if(n==0&&m==0&&t==0)break;
memset(vis, 0, sizeof(vis));
int sx, sy, ans = 1e9;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin>>a[i][j];
if(a[i][j]=='S')sx = i, sy = j;
}
}
queue<node> q;
q.push((node){sx,sy,0,'S'});
while(q.size()){
node t = q.front(); q.pop();
if(t.ch=='X')continue;
if(t.ch=='D' && t.step<=ans)ans = t.step;
for(int i = 0; i < 4; i++){
int nx = t.x+dx[i], ny=t.y+dy[i];
if(nx>=1 && nx<=n&&ny>=1 &&ny<=m && !vis[nx][ny]){
q.push((node){nx,ny,t.step+1,a[nx][ny]});
vis[nx][ny] = 1;
}
}
}
if(ans<=t)cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
1003 抗旱救灾,承轩有责
抗旱救灾,承轩有责
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 63 Accepted Submission(s) : 16
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
正所谓——“百年不遇年年遇”!
某年夏天,中国西南诸省再次出现了“百年不遇”的严重旱情!
由于灾情越来越严重,很多学校师生的用水困难已成为最急需解决的问题,而要给各学校提供用水,就必须先知道各学校是否与水库有道路相连。
胡承轩——国家防汛抗旱总指挥部总指挥,现在想请你编写一个程序,读入所有道路的信息,计算有多少学校没有路与水库相通。
同学们,好好学信奥,为胡总指挥分忧~
Input
输入有多组数据。
每组数据第一行包括两个正整数n,m(0<n<1000, 0<m<=(n*(n+1)/2), n表示学校的数目,m表示道路的数目),学校用1到n的整数编号,水库的编号永远记为0;
接下来有m行,每行有两个数a和b,a和b用一个空格分开,表示a到b有一条路。
请处理到文件结束。
Output
对于每组输入数据:
如果所有的学校均与水库相通,则请在一行内输出0;
如果有学校不通水库,则请输出与水库无路连接的学校个数;
每组数据的输出占一行。
Sample Input
4 4
0 1
0 2
1 2
2 3
Sample Output
1
Source
丁爸信奥培训(2018春)- 结业测试(0)
#include<bits/stdc++.h>
using namespace std;
int fa[10010];
void init(int n){for(int i = 0; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}
int count(int n){int cnt=0; for(int i = 1; i <= n; i++)if(fa[i]==i)cnt++;return cnt;}
int main(){
int n, m;
while(cin>>n>>m){
init(n);
for(int i = 1; i <= m; i++){
int x, y; cin>>x>>y;
merge(x,y);
}
int cnt = 0;
for(int i = 1; i <= n; i++){
if(find(0)!=find(i))cnt++;
}
cout<<cnt<<"\n";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
1004 家瑞学信奥
家瑞学信奥
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 40 Accepted Submission(s) : 4
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
张家瑞已经在丁爸信奥培训班学习了一段时间,水平也有了很大的提高。
但是,他仍然不满足于现状,想更快地提高自己的水平,于是他便向丁爸要题目来做,丁爸给了他这样一个问题:
有n个数,第i个数的值为a[i],现在要从中挑出一些数,使得挑出的数的和最大。
需要指出的是,挑出的数必须满足这样一个条件:如果数字x被挑出,那么数字x-1和数字x+1都不能被挑出。
求挑出的数的和最大值为多少?
Hint
温馨提醒:
如果数字x被挑出,那么数字x-1和数字x+1都不能被挑出。
不要误读成:
如果第x个数字被挑出,那么第x-1和第x+1个数字都不能被挑出。
Input
输入数据第一行为一个正整数T,代表有T组测试数据(T<=10)。
每组数据中:
第一行为整数N,表示有N个数(2<=N<=100,000)。
接下来一行有N个数,记为a[1]…a[n], 其中a[i]对应第i个数的值(1<=a[i]<=100,000)。
Output
请计算挑出的数和最大值为多少。
每组数据输出一行。
Sample Input
4
2
1 2
3
1 2 3
9
1 2 1 3 2 2 2 2 3
4
1 2 3 3
Sample Output
2
4
10
7
Author
NMfloat
Source
Alpha Test
//题意:给出n个数,从中选出任意个使得和最大。若x选了,则x-1和x+1不能选。
//思路:f[i]表示选到数字i为止能获得最大和,转移时考虑第i个数选还是不选,f[i]=max(f[i-2]+a[i],f[i-1]);
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
LL a[maxn], f[maxn];
vector<LL>vc;
int main(){
int T; scanf("%d",&T);
while(T--){
vc.clear();
memset(a,0,sizeof(a));
//memset(f,0,sizeof(f));
int n; scanf("%d",&n);
for(int i = 1; i <= n; i++){
LL x; scanf("%lld",&x);
if(!a[x])vc.push_back(x);
a[x] += x;
}
sort(vc.begin(), vc.end());
f[0] = a[vc[0]];
for(int i = 1; i < vc.size(); i++){
if(vc[i]==vc[i-1]+1)
f[i] = max(f[i-1],f[i-2]+a[vc[i]]);
else
f[i] = f[i-1]+a[vc[i]];
}
//cout<<f[vc.size()-1]<<"\n";
printf("%lld\n",f[vc.size()-1]);
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
文章来源: gwj1314.blog.csdn.net,作者:小哈里,版权归原作者所有,如需转载,请联系作者。
原文链接:gwj1314.blog.csdn.net/article/details/115243783
- 点赞
- 收藏
- 关注作者
评论(0)