BestCoder Round #42(3/4)

2024-08-28 07:32
文章标签 round 42 bestcoder

本文主要是介绍BestCoder Round #42(3/4),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

http://acm.hdu.edu.cn/showproblem.php?pid=5232

Shaking hands

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 169    Accepted Submission(s): 147


Problem Description
Today is Gorwin’s birthday, so she holds a party and invites her friends to participate. She will invite n friends, for convenience, Gorwin numbers them from 1 to n. Some of them have known each other, But some of them have not. Those friends whose have known each other will shake hands with each other, and drink one cup of champagne. Gorwin wants to know how many cups of champagne she should prepare. Can you help her?

Input
Multiple test cases (about 30), the first line of each case contains an integer n which indicates Gorwin will invite n friends to her party. 

Next n lines will give a n*n matrix, if a[i][j] is 1, then friend i and friend j have known each other, otherwise they have not known each other.

Please process to the end of file.

[Technical Specification]

All input entries are integers.

1<=n<=30

0<=a[i][j]<=1

a[i][i]=0;

a[i][j]=a[j][i] for i!=j

Output
For each case, output an integer which denotes total cups of champagne Gorwin should prepare in a single line.

Sample Input
    
2 0 0 0 0 3 0 0 1 0 0 0 1 0 0

Sample Output
    
4 8
Hint
For the second case, Gorwin will shake hands with all her friends, then Gorwin drink three cups of champagne, each friends drink one cup. Friend 1 and friend 3 know each other,every of them drinks one cup again. So the total cups is 3+3+2=8.

Source
BestCoder Round #42
/* ***********************************************
Author :
Created Time :2015/5/23 18:55:44
File Name :1.cpp
************************************************ */

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 1<<30
#define maxn 10000+10
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << 61;
const
double eps=1e-5;
using namespace
std;

bool
cmp(int a,int b){
return
a>b;
}

int
a[33][33];
int
main()
{

#ifndef ONLINE_JUDGE
//freopen("in.txt","r",stdin);
#endif
//freopen("out.txt","w",stdout);
int n;
while
(cin>>n){
int
num=0;
for
(int i=1;i<=n;i++)
for
(int j=1;j<=n;j++)
cin>>a[i][j];
for
(int i=1;i<=n;i++)
for
(int j=1;j<=i;j++){
if
(a[i][j]==1)
num++;
}

cout<<n*2+num*2<<endl;
}

return
0;
}

Gunner II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 917    Accepted Submission(s): 372


Problem Description
Long long ago, there was a gunner whose name is Jack. He likes to go hunting very much. One day he go to the grove. There are n birds and n trees. The i-th bird stands on the top of the i-th tree. The trees stand in straight line from left to the right. Every tree has its height. Jack stands on the left side of the left most tree. When Jack shots a bullet in height H to the right, the nearest bird which stands in the tree with height H will falls.

Jack will shot many times, he wants to know which bird will fall during each shot.

Input
There are multiple test cases (about 5), every case gives n, m in the first line, n indicates there are n trees and n birds, m means Jack will shot m times. 

In the second line, there are n numbers h[1],h[2],h[3],…,h[n] which describes the height of the trees.

In the third line, there are m numbers q[1],q[2],q[3],…,q[m] which describes the height of the Jack’s shots.

Please process to the end of file.

[Technical Specification]

All input items are integers.

1<=n,m<=100000(10^5)

1<=h[i],q[i]<=1000000000(10^9)

Output
For each q[i], output an integer in a single line indicates the id of bird Jack shots down. If Jack can’t shot any bird, just output -1.

The id starts from 1.

Sample Input
    
5 5 1 2 3 4 1 1 3 1 4 2

Sample Output
    
1 3 5 4 2
Hint
Huge input, fast IO is recommended.

Source
BestCoder Round #42
题目大意:给定n棵树的高度,给定m个射击高度,每次射击输出对应的树的最小的下标。
该开始用队列模拟的,G++ MLE了,C++AC
/* ***********************************************
Author :
Created Time :2015/5/23 19:32:56
File Name :1.cpp
************************************************ */

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 1<<30
#define maxn 10000+10
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << 61;
const
double eps=1e-5;
using namespace
std;

bool
cmp(int a,int b){
return
a>b;
}


map<int,queue<int> >mp;
int
main()
{

#ifndef ONLINE_JUDGE
//freopen("in.txt","r",stdin);
#endif
//freopen("out.txt","w",stdout);
int n,m;
int
a;
while
(cin>>n>>m){
mp.clear();
for
(int i=1;i<=n;i++){
scanf("%d",&a);
mp[a].push(i);
}

for
(int i=1;i<=m;i++){
scanf("%d",&a);
if
(mp[a].empty())printf("-1\n");
else
printf("%d\n",mp[a].front()),mp[a].pop();
}
}

return
0;
}
下面的是按照标程写的离散化+vector,其中离散化使用map做的。注意vector的erase函数是o(n)的时间复杂度的,所以用erase会超时,这里的删除操作用的数组模拟
/* ***********************************************
Author :
Created Time :2015/5/25 13:50:31
File Name :1.cpp
************************************************ */

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 1<<30
#define maxn 100000+10
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << 61;
const
double eps=1e-5;
using namespace
std;

vector<int>v[maxn];

map<int,int>mp;
int
mark[maxn];
int
main()
{

#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
//freopen("out.txt","w",stdout);
int n,m;
while
(cin>>n>>m){
mp.clear();
int
a;
int
cnt=0;
for
(int i=0;i<n;i++){
scanf("%d",&a);
if
(!mp[a]){
mp[a]=++cnt;//注意cnt最好不用0 会有冲突
v[mp[a]].clear();
v[mp[a]].push_back(i+1);
mark[mp[a]]=0;
}

else
v[mp[a]].push_back(i+1);
}

for
(int i=0;i<m;i++){
scanf("%d",&a);
if
(!mp[a]||v[mp[a]].size()<=mark[mp[a]])puts("-1");
else
{
printf("%d\n",v[mp[a]][mark[mp[a]]++]);
//v[mp[a]].erase(v[mp[a]].begin());
}
}
}

return
0;
}

Happy birthday

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 296    Accepted Submission(s): 153


Problem Description
Today is Gorwin’s birthday. So her mother want to realize her a wish. Gorwin says that she wants to eat many cakes. Thus, her mother takes her to a cake garden. 

The garden is splited into n*m grids. In each grids, there is a cake. The weight of cake in the i-th row j-th column is  {w_{ij}} kilos, Gorwin starts from the top-left(1,1) grid of the garden and walk to the bottom-right(n,m) grid. In each step Gorwin can go to right or down, i.e when Gorwin stands in (i,j), then she can go to (i+1,j) or (i,j+1) (However, she can not go out of the garden). 

When Gorwin reachs a grid, she can eat up the cake in that grid or just leave it alone. However she can’t eat part of the cake. But Gorwin’s belly is not very large, so she can eat at most K kilos cake. Now, Gorwin has stood in the top-left grid and look at the map of the garden, she want to find a route which can lead her to eat most cake. But the map is so complicated. So she wants you to help her.

Input
Multiple test cases (about 15), every case gives n, m, K in a single line.

In the next n lines, the i-th line contains m integers  {w_{i1}},{w_{i{\rm{2}}}},{w_{i3}}, \cdots {w_{im}} which describes the weight of cakes in the i-th row

Please process to the end of file.

[Technical Specification]

All inputs are integers.

1<=n,m,K<=100

1<= {w_{ij}}<=100

Output
For each case, output an integer in an single line indicates the maximum weight of cake Gorwin can eat.

Sample Input
    
1 1 2 3 2 3 100 1 2 3 4 5 6

Sample Output
    
0 16
Hint
In the first case, Gorwin can’t eat part of cake, so she can’t eat any cake.In the second case, Gorwin walks though below route (1,1)->(2,1)->(2,2)->(2,3). When she passes a grid, she eats up the cake in that grid. Thus the total amount cake she eats is 1+4+5+6=16.

Source
BestCoder Round #42
题目大意转换:从1,1点走到n,m点,每个点(x,y)有一个wi价值,求在总价值不超过k时能得到的最大价值。
思路:对于某个点,我们可以选择要和不要,也就是dfs(x,y,v+a[i][j])和dfs(x,y,v)  并用dp[x][y][v]记录这个状态是否被搜索过。
代码如下:
/* ***********************************************
Author :
Created Time :2015/5/25 16:28:12
File Name :1.cpp
************************************************ */

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 1<<30
#define maxn 10000+10
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << 61;
const
double eps=1e-5;
using namespace
std;

bool
cmp(int a,int b){
return
a>b;
}

int
a[110][110];
int
dir[2][2]={1,0,0,1};
int
dp[110][110][102];//状态
int n,m,k;
int
Max;
void
dfs(int x,int y,int v){
if
(x==n&&m==y){
Max=max(v,Max);
}

if
(dp[x][y][v])return ;
dp[x][y][v]=1;

for
(int i=0;i<2;i++){
int
nx=x+dir[i][0];
int
ny=y+dir[i][1];
if
(nx<=n&&nx>=1&&ny<=m&&ny>=1){
if
(v+a[nx][ny]<=k)dfs(nx,ny,v+a[nx][ny]);
dfs(nx,ny,v);
}
}
}

int
main()
{

#ifndef ONLINE_JUDGE
//freopen("in.txt","r",stdin);
#endif
//freopen("out.txt","w",stdout);
while(cin>>n>>m>>k){
for
(int i=1;i<=n;i++)
for
(int j=1;j<=m;j++)
cin>>a[i][j];
cle(dp);
Max=0;
dfs(1,1,0);
if
(a[1][1]<=k)
dfs(1,1,a[1][1]);
cout<<Max<<endl;
}

return
0;
}

这篇关于BestCoder Round #42(3/4)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1114128

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单,不做解释 C 对于 x y 两个方向,每一个方向至少需要 x / k 向上取整的步数,取最大值。 由于 x 方向先移动,假如 x 方向需要的步数多于 y 方向的步数,那么最后 y 方向的那一步就不需要了,答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>

数据库系统 第42节 数据库索引简介

数据库索引是数据库表中一个或多个列的数据结构,用于加快数据检索速度。除了基础的B-Tree索引,其他类型的索引针对特定的数据类型和查询模式提供了优化。以下是几种不同类型的索引及其使用场景的详细说明和示例代码。 1. 位图索引 (Bitmap Index) 位图索引适用于具有少量不同值的列(例如性别、国家代码等),它使用位图来表示数据,从而提高查询效率。 适用场景:当列中的值域较小,且数据分布

【代码随想录训练营第42期 续Day52打卡 - 图论Part3 - 卡码网 103. 水流问题 104. 建造最大岛屿

目录 一、做题心得 二、题目与题解 题目一:卡码网 103. 水流问题 题目链接 题解:DFS 题目二:卡码网 104. 建造最大岛屿 题目链接 题解:DFS  三、小结 一、做题心得 也是成功补上昨天的打卡了。 这里继续图论章节,还是选择使用 DFS 来解决这类搜索问题(单纯因为我更熟悉 DFS 一点),今天补卡的是水流问题和岛屿问题。个人感觉这一章节题对于刚

MemSQL Start[c]UP 2.0 - Round 1A(构造)

题目链接:http://codeforces.com/problemset/problem/452/A 解题思路: 打个表暴力查找匹配。 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <complex>#include <cstdio>#include <strin

Codeforces Round #281 (Div. 2)A(构造+暴力模拟)

题目链接:http://codeforces.com/problemset/problem/493/A 解题思路: 暴力的判断,分三种情况去判断即可。注意如果之前已经被罚下场后,那么在后面的罚下情况不应该算在输出结果内。 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <co

Codeforces Round #182 (Div. 2)A(水题)

题目链接:http://codeforces.com/contest/302/problem/A 解题思路: 只要通过重新排列使区间内和为0即是1,否则是0. 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <complex>#include <cstdio>#inc