2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛
链接:https://ac.nowcoder.com/acm/contest/118/B
来源:牛客网
题目描述
喜爱ACM的PBY同学遇到了一道数学难题,已知底数n,请你帮他准确的计算出结果a = nπ(n的π次方),结果保留小数点后x位。
输入描述:
第一行是一个整数t,表示测试实例的个数; 然后是t行输入数据,每行包含两个正整数n和x,表示底数和保留位数。 (1 <= t <= 100,1 <= n <= 500,1 <= x <= 6)
输出描述:
对于每组输入数据,分别输出结果a,每个输出占一行。
示例1
输入
3 1 3 7 6 9 1
输出
1.000 451.807873 995.0
题解:保存精度的水题,wa了一个小时,学习了大佬的printf用法。
枚举精度的:
#include<bits/stdc++.h>
using namespace std;
#define M_PI 3.14159265358979323846
typedef long long int ll;
vector<int> v;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,x;
cin>>n>>x;
double sum=(double)pow(n,M_PI);
if(x==1)
{
printf("%.1f\n",sum);
}
else if(x==2)
{
printf("%.2f\n",sum);
}
else if(x==3)
{
printf("%.3f\n",sum);
}
else if(x==4)
{
printf("%.4f\n",sum);
}
else if(x==5)
{
printf("%.5f\n",sum);
}
else if(x==6)
{
printf("%.6f\n",sum);
}
}
return 0;
}
大佬的:
#include <stdio.h>
#include <bits/stdc++.h>
#define fst first
#define sed second
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
int main()
{
int T;
cin >> T;
while (T--)
{
int n, x;
cin >> n >> x;
char s[] = "%.0f\n";
s[2] = '0' + x;
printf(s, pow(n, acos(-1)));
}
return 0;
}
链接:https://ac.nowcoder.com/acm/contest/118/F
来源:牛客网
题目描述
《扫雷》是一款大众类的益智小游戏,于1992年发行。游戏目标是在最短的时间内根据点击格子出现的数字找出所有非雷格子,同时避免踩雷,踩到一个雷即全盘皆输。当某个位置为数字的时,代表它周围的八连通区域中有对应数量的雷。
kirai获取了简化版扫雷(没有标记雷的小旗)的后台数据(后台数据包括所有数字和雷的位置),转换为一个n*m(1≤n, m≤500)的矩阵并对格子类型做了如下标记:
雷被标记为'*';
点开的空白区域标记为'0';
未点开的空白区域标记为'.';
数字1~8代表周围有多少雷;
kirai非常笨,他希望你帮他完成这样的任务:
给定k(1≤k≤min(可扫位置数, 10))个位置坐标和扫雷游戏的后台数据,输出点开指定位置序列后游戏的结果,初始时游戏中没有点开任何位置。
注:数据保证扫雷过程中不会重复点击已扫位置。
输入描述:
输入样例有多组,全部是正整数。首先输入样例组数T(T≤10)。 接下来输入T组数,每组数据第一行包括四个正整数n,m,k(1≤n, m≤500, 1≤k≤min(可扫位置数, 10))分别表示地图的行、列数和即将点开的位置数。紧接着是一个n*m的矩阵,代表扫雷的后台数据,。 矩阵后是k个整数对xi, yi(1≤i≤k, 1≤xi≤n, 1≤yi≤m),表示依次点开的位置。
输出描述:
如果某一步踩到雷,输出"Game over in step x"(不包括引号",表示第x步踩中雷);未踩到雷则根据扫雷的游戏规则更新,并输出最后一步结束后显示给kirai的矩阵。
示例1
输入
1 5 5 3 2*11* *2111 22... *1... 11... 1 1 3 3 1 2
输出
Game over in step 3
说明
2.... ..... ..... ..... ..... 2.... .2111 .2000 .1000 .1000 Game over in step 3
题解:DFS暴力八个方向判断一下是否满足显示的条件,注意需要全部接收完数据。(又自闭一个小时的bug)
#include<bits/stdc++.h>
using namespace std;
char mp[505][505];
char mp1[505][505];
int mp2[505][505];
int x1[10]={1,-1,0,0,1,1,-1,-1};
int y111[10]={0,0,1,-1,1,-1,1,-1};
int n,m,k;
void dfs(int x,int y)
{
for(int i=0;i<9;i++)
{
int xx=x1[i]+x;
int yy=y111[i]+y;
if(xx>=1 && xx<=n && yy>=1 && yy<=m&&!mp2[xx][yy])
{
mp2[xx][yy]=1;
if(mp[xx][yy]=='.')
{
mp1[xx][yy]='0';
dfs(xx,yy);
}
else
mp1[xx][yy]=mp[xx][yy];
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
getchar();
memset(mp2,0,sizeof(mp2));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%c",&mp[i][j]);
mp1[i][j]='.';
}
getchar();
}
int temp=1,q=0;
while(k--)
{
int x,y;
scanf("%d%d",&x,&y);
if(!q)
{
if(mp[x][y]=='*')
{
q=temp;
}
else if(mp[x][y]>='0'&&mp[x][y]<='9')
{
mp1[x][y]=mp[x][y];
mp2[x][y]=1;
}
else
{
mp1[x][y]='0';
dfs(x,y);
}
temp++;
}
}
if(q==0)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
printf("%c",mp1[i][j]);
}
cout<<endl;
}
}
else
{
printf("Game over in step %d\n",q);
}
}
return 0;
}
链接:https://ac.nowcoder.com/acm/contest/118/J
来源:牛客网
题目描述
现在萌新要乘船度过一条河,这条河宽为s米。
现已知船相对于水的速度为v1,水流的速度为v2。
由于萌新想到达起点的正对岸,所以他会一直调整船行驶的方向朝向正对岸。
你的任务是计算萌新将用多少时间度过这条河;若他不能到达起点的正对岸,输出“Infinity”。
输入描述:
第一行输入一个整数n,表示测试用例数; 接下来n行,每行输入三个整数s、v1、v2。 其中,1≤n≤1000,0≤s≤100, 0≤v1,v2≤100。
输出描述:
输出一个实数,你的任务是计算萌新将用多少时间度过这条河(保留10位小数);若他不能到达起点的正对岸,输出“Infinity”。
示例1
输入
3 2 2 2 2 4 3 5 6 5
输出
Infinity 1.1428571429 2.7272727273
题解:积分,把两个速度分解一下,联立方程组求解,得到t = s * v1 /(v1*v1 - v2*v2) 。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int s,v1,v2;
scanf("%d%d%d",&s,&v1,&v2);
if(s == 0)
{
printf("%.10lf\n",0.0);
}
else if(v1 <= v2)
{
printf("Infinity\n");
}
else
{
double ans = (v1*s)*1.0/(v1*v1-v2*v2);
printf("%.10lf\n",ans);
}
}
return 0;
}
链接:https://ac.nowcoder.com/acm/contest/118/C
来源:牛客网
题目描述
艺术家通常要通过颜料的混合得到某种他想要的但又不是从工厂里面生产出来的原始的那种颜料。为了简便起见, 我们假设每种颜料都可以分成是红绿两个分量的数值指标, 即每种颜料都可以用红绿在其中占据的百分比来表示。艺术家从工厂拿回了三种不同颜料分别是(x1%红,y1%绿), (x2%红,y2%绿),(x3%红,y3%绿), 问艺术家是否能够调出自己想要的颜料(x0%红,y0%绿)?
输入描述:
八个整数:x0,y0,x1,y1,x2,y2,x3,y3。(0 < xi, yi < 100)
输出描述:
输出Yes如果可以调出, 否则输出No
示例1
输入
2 3 1 1 3 3 2 4
输出
Yes
说明
一份颜料一, 一份颜料二, 一份颜料三混合即可。
备注:
输入数据有多组! 输入数据有多组! 输入数据有多组!
题解:这题居然与计算几何有关,判断 它是只要给出的点,在三角内部即可。
用面积判断点是否在三角形内部。
向量公式算面积:S=|(x1-x3)*(y2-y3)-(x2-x3)*(y1-y3)|/2
大佬的代码:
/*********************
Author Ms. Wen
Date 2018/5/5
解题思路:
这个题目当时没写出来,它是只要给出的点,在三角内部即可。
因为对于(x1,y1),(x2,y2),其连线上的任意一点都可以构成。
同理(x1,y1),(x3,y3),其连线上的任意一点都可由这两点分量
构成。线段上的任意点又可和线段上的任意点相连,其中间的点
又可以被构成。则只要给出的点在三角形内即可。很巧妙,当时
真的没想到和三角形与点的位置这个知识点扯上关系。
***************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
#define eps 1e-5
using namespace std;
int Area(int x1,int y1,int x2,int y2,int x3,int y3) {
int area = x1*y2 + x2*y3 + x3*y1 - x1*y3 - x2*y1 - x3*y2;
return abs(area);
}
bool check(int x0,int y0,int x1,int y1,int x2,int y2,int x3,int y3) {
int area1 = Area(x0,y0,x1,y1,x2,y2);
int area2 = Area(x0,y0,x1,y1,x3,y3);
int area3 = Area(x0,y0,x2,y2,x3,y3);
int sum = Area(x1,y1,x2,y2,x3,y3);
if(area1+area2+area3 == sum) {
return true;
}
return false;
}
int main() {
int x0,y0,x1,y1,x2,y2,x3,y3;
while(~scanf("%d%d%d%d%d%d%d%d",&x0,&y0,&x1,&y1,&x2,&y2,&x3,&y3)) {
if(check(x0,y0,x1,y1,x2,y2,x3,y3)) {
printf("Yes\n");
}
else {
printf("No\n");
}
}
return 0;
}