今日训练学习"/>
今日训练学习
试题 算法训练 活雷锋
提交此题 评测记录
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
寻找“活雷锋”：经过警察叔叔的走访调查，知道了“活雷锋”每次做完好事后，别人问起他的名字时，他总是说自己是“雷锋16”，而他家的门上也写着数字“16”。你能通过这个线索找到“活雷锋”的家吗？
输入格式
输入4行5列的数字，查找16
输出格式
输出1行，如果有16就输出‘yes'，没有就输出’no'。
样例输入
一个满足题目要求的输入范例。
例：
1 2 3 4 5
2 3 4 5 6
21 3 3 4 6
2 4 5 6 16
样例输出
与上面的样例输入对应的输出。
例：
yes
数据规模和约定
输入数据中每一个数的范围。
例：0<n,m<1000000。
思路：双重循环
#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(){
int a[4][5],i,j;
for(i=0;i<4;i++)
{
for(j=0;j<5;j++)
cin>>a[i][j];
}
for(i=0;i<4;i++)
{
for(j=0;j<5;j++)
{
if(a[i][j]==16)
{
cout<<"yes";
return 0;
}
}
}
cout<<"no";
return 0;
}
试题 算法训练 勇士和地雷阵
提交此题 评测记录
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
勇士们不小心进入了敌人的地雷阵（用n行n列的矩阵表示，'*'表示某个位置埋有地雷，'-'表示某个位置是安全的），他们各自需要在规定的步数（一步代表走到和当前位置相邻的位置）内绕开地雷到达出口（第一行第一格，即坐标为（0,0）的位置）才能完成任务，告诉你每个勇士的位置（x，y）和规定的步数s，请你判断每个勇士能否顺利完成任务（1代表“能”，-1代表“不能”）。
输入格式
输入数据的第一行为一个整数n；第二行至第n+1行是n行n列地雷阵的矩阵表示（见输入样例）；第n+2行至最后一行每行是一个勇士的位置x、y和到达出口规定的最大步数s，三个整数间用空格隔开。
输出格式
按顺序输出对每个勇士是否能顺利完成任务的判断（1代表“能”，-1代表“不能”），对每个勇士的判断占一行。
样例输入
5
-----
--*--
-**--
-**--
*-*--
0 1 1
0 4 3
1 1 3
1 4 2
2 0 3
3 0 4
3 3 2
4 1 3
样例输出
1
-1
1
-1
1
1
-1
-1
数据规模和约定
1≤n≤500，0≤x≤n-1，0≤y≤n-1，1≤s≤500
思路：
由于所有点的终点始终为 (0, 0),所以,可以在终点用宽度搜索算法,求出终点到每个点的距离.
之后再读取点的数据,根据 当前的点到终点的距离 与 能动的步数 来比较即可知道答案
链接：
#include <iostream>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=510;
int n;
char g[N][N];
int dist[N][N];
int dx[4]={-1,0,1,0};//移动
int dy[4]={0,1,0,-1};
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void bfs(int a,int b)
{
queue<PII> store;
store.push({a,b});
dist[a][b]=0;
while(store.size())
{
pair<int,int> temp=store.front();
store.pop();
for(int i=0;i<4;i++)
{
int nx=temp.x+dx[i];
int ny=temp.y+dy[i];
if(nx<0||nx>n-1||ny<0||ny>n-1)
continue;
if(dist[nx][ny]!=0)
continue;
if(g[nx][ny]=='*')
continue;
dist[nx][ny]=dist[temp.x][temp.y]+1;
store.push({nx,ny});
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++)
cin>>g[i];
bfs(0,0);
int x,y,z;
while(cin>>x>>y>>z)
{
if(x==0&&y==0)
cout<<1<<endl;
else
if(dist[x][y]!=0&&dist[x][y]<=z)
cout<<1<<endl;
else
cout<<-1<<endl;
}
return 0;
}
试题 算法训练 强力党逗志芃
提交此题 评测记录
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
逗志芃励志要成为强力党，所以他将身上所以的技能点都洗掉了重新学技能。现在我们可以了解到，每个技能都有一个前提技能，只有学完了前提技能才能学习当前的技能（有一个最根本的技能不需要前提技能）。学习每个技能要消耗一个技能点，然后可以获得这个技能的威力值。由于逗志芃要陪妹子，所以他希望你教他如何点技能使得威力值最大从而成为强力党。
输入格式
第一行两个数n，m表示有n个技能和m个技能点。第二行有n个数，第i个数表示第i个技能的威力值。
之后的n-1行，每行两个数x,y，表示y技能的前提技能是x，也就是说先学第x个技能才能学弟y个技能。
输出格式
一个数，最大的威力值。
样例输入
3 2
1 10 20
1 2
1 3
样例输出
21
数据规模和约定
0<n,m<=200, 技能的威力值不超过200。
思路：链接：
#include <iostream>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int N=210;
int n,m;
int q[N];
int h[N],e[N],ne[N],idx;
int dp[N][N],res=0;//以i为根节点，总花费的点数不超过j的最大方案，伤害的最大值
bool st[N];//是否有前驱
void add(int x,int y)
{
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}
void dfs(int u)
{
for(int i=h[u];i!=-1;i=ne[i])//循环物品组
{
int son=e[i];
dfs(son);
for(int j=m-1;j>=0;j--)//循环剩余的点数
for(int k=0;k<=j;k++)//循环决策
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[son][k]);
}
//将当前的节点1
for(int i=m;i>=1;i--)
dp[u][i]=dp[u][i-1]+q[u];
dp[u][0]=0;
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)//读取每个节点的值
cin>>q[i];
for(int i=1;i<n;i++)//读取节点之间的关系
{
int x,y;
cin>>x>>y;
add(x,y);//x为y的父节点
st[y]=true;
}
int root;//寻找根节点
for(int i=1;i<=n;i++)
if(st[i]==false)
{
root=i;
break;
}
dfs(root);
cout<<dp[root][m]<<endl;
return 0；
}
更多推荐
今日训练学习
发布评论