【深基7.例1】距离函数
题目描述
给出平面坐标上不在一条直线上三个点坐标 ( x 1 , y 1 ) , ( x 2 , y 2 ) , ( x 3 , y 3 ) (x_1,y_1),(x_2,y_2),(x_3,y_3) (x1,y1),(x2,y2),(x3,y3)，坐标值是实数，且绝对值不超过 100.00，求围成的三角形周长。保留两位小数。
对于平面上的两个点 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1),(x_2,y_2) (x1,y1),(x2,y2)，则这两个点之间的距离 d i s = ( x 2 − x 1 ) 2 + ( y 2 − y 1 ) 2 dis=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2} dis=(x2−x1)2+(y2−y1)2
输入格式
输入三行，第 i i i 行表示坐标 ( x i , y i ) (x_i,y_i) (xi,yi)，以一个空格隔开。
输出格式
输出一个两位小数，表示由这三个坐标围成的三角形的周长。
样例 #1
样例输入 #1
0 0
0 3
4 0
样例输出 #1
12.00
提示
数据保证，坐标均为实数且绝对值不超过 100 100 100，小数点后最多仅有 3 3 3 位。
解题思路
- 1）用两点间距离公式计算出三边长度。
- 2）计算并输出周长，记得输出格式为二位小数。
参考代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
double a,b,c,d,e,f;
double s1,s2,s3;
cin>>a>>b>>c>>d>>e>>f;
s1=sqrt((a-c)*(a-c)+(b-d)*(b-d));
s2=sqrt((a-e)*(a-e)+(b-f)*(b-f));
s3=sqrt((c-e)*(c-e)+(d-f)*(d-f));
printf("%.2lf",s1+s2+s3);
return 0;
}
[USACO1.5]八皇后 Checker Challenge
题目描述
一个如下的 6 × 6 6 \times 6 6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。
上面的布局可以用序列 2 4 6 1 3 5 2\ 4\ 6\ 1\ 3\ 5 2 4 6 1 3 5 来描述，第 i i i 个数字表示在第 i i i 行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6 1\ 2\ 3\ 4\ 5\ 6 1 2 3 4 5 6
列号 2 4 6 1 3 5 2\ 4\ 6\ 1\ 3\ 5 2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前
3
3
3 个解。最后一行是解的总个数。
输入格式
一行一个正整数 n n n，表示棋盘是 n × n n \times n n×n 大小的。
输出格式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
样例 #1
样例输入 #1
6
样例输出 #1
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
提示
【数据范围】
对于
100
%
100\%
100% 的数据，
6
≤
n
≤
13
6 \le n \le 13
6≤n≤13。
解题思路
- 1）根据题目要求， 每行只能放一个皇后，每列只能放一个皇后，每一个“/”斜行只能放一个皇后，每一个“\”斜行只能放一个皇后，我们用数组
check来保证每列和每条对角线上只有一个棋子。check[0]储存了棋子的列数，每一次进行ans[line]=i，使check[0][i]标记为已使用。同理check[1]和check[2]储存对角线上的棋子分布情况。- 2）若满足条件，
if((!used[0][i])&&(!used[1][line+i])&&(!used[2][line-i+n]))，即可在此处下棋，将check数组中的相应数值标记为已使用，并对下一行进行深度优先搜索。- 3）输出前三组解。
参考代码
#include<bits/stdc++.h>
using namespace std;
int ans[14],used[3][28]={0},sum=0,n;
int check(int i,int line)
{
if((!used[0][i])&&(!used[1][line+i])&&(!used[2][line-i+n]))
return 1;
return 0;
}
void dfs(int line)
{
if(line>n)
{
sum++;
if(sum>3) return;
else
{
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
printf("\n");
return;
}
}
for(int i=1;i<=n;i++)
{
if(check(i,line))
{
ans[line]=i;
used[0][i]=1; used[1][line+i]=1; used[2][line-i+n]=1;
dfs(line+1);
used[0][i]=0; used[1][line+i]=0; used[2][line-i+n]=0;
}
}
}
int main()
{
scanf("%d",&n);
dfs(1);
printf("%d",sum);
return 0;
}
[NOIP2005 普及组] 采药
题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有 2 2 2 个整数 T T T（ 1 ≤ T ≤ 1000 1 \le T \le 1000 1≤T≤1000）和 M M M（ 1 ≤ M ≤ 100 1 \le M \le 100 1≤M≤100），用一个空格隔开， T T T 代表总共能够用来采药的时间， M M M 代表山洞里的草药的数目。
接下来的 M M M 行每行包括两个在 1 1 1 到 100 100 100 之间（包括 1 1 1 和 100 100 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
样例 #1
样例输入 #1
70 3
71 100
69 1
1 2
样例输出 #1
3
提示
【数据范围】
- 对于 30 % 30\% 30% 的数据， M ≤ 10 M \le 10 M≤10；
- 对于全部的数据， M ≤ 100 M \le 100 M≤100。
解题思路
- 1）简单的01背包问题，直接套板子
参考代码
#include<bits/stdc++.h>
using namespace std;
int dp[1050];
int main()
{
int T,M;
cin>>T>>M;
for(int i=1;i<=M;i++)
{
int t,v;
cin>>t>>v;
for(int j=T;j>=t;j--)
{
dp[j]=max(dp[j],dp[j-t]+v);
}
}
cout<<dp[T];
return 0;
}
[USACO3.1]总分 Score Inflation
题目背景
选手在我们 USACO 的竞赛中的得分越多我们越高兴。
我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。
题目描述
我们可以从几个种类中选取竞赛的题目,这里的一个"种类"是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数。
你的任务是写一个程序来告诉 USACO 的职员,应该从每一个种类中选取多少题目，使得解决题目的总耗时在竞赛规定的时间里并且总分最大。
输入格式
输入的第一行是用空格隔开的两个整数，分别代表竞赛时间 m m m 和题目类 n n n。
第 2 2 2 到第 ( n + 1 ) (n + 1) (n+1) 行，每行两个用空格隔开的整数，第 ( i + 1 ) (i + 1) (i+1) 行的整数 p i , t i p_i, t_i pi,ti 分别代表解决第 i i i 类题得到的分数和需要花费的时间。
既然是某一类题目，那么这一类题目可以重复选择。
输出格式
输出一行一个整数，代表最大的总分。
样例 #1
样例输入 #1
300 4
100 60
250 120
120 100
35 20
样例输出 #1
605
提示
数据规模与约定
对于 100 % 100\% 100% 的数据，保证 1 ≤ n ≤ 1 0 4 1 \leq n \leq 10^4 1≤n≤104， 1 ≤ p i , t i ≤ 1 0 4 1 \leq p_i, t_i \leq 10^4 1≤pi,ti≤104。
解题思路
- 1）简单的完全背包问题，直接套板子
参考代码
#include<bits/stdc++.h>
using namespace std;
long long dp[10200];
int main()
{
int m,n;
cin>>m>>n;
for(int i=1;i<=n;i++)
{
int p,t;
cin>>p>>t;
for(int j=t;j<=m;j++)
{
dp[j]=max(dp[j],dp[j-t]+p);
}
}
cout<<dp[m];
return 0;
}
迷宫
题目描述
给定一个 N × M N \times M N×M 方格的迷宫，迷宫里有 T T T 处障碍，障碍处不可通过。
在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。
输入格式
第一行为三个正整数 N , M , T N,M,T N,M,T，分别表示迷宫的长宽和障碍总数。
第二行为四个正整数 S X , S Y , F X , F Y SX,SY,FX,FY SX,SY,FX,FY， S X , S Y SX,SY SX,SY 代表起点坐标， F X , F Y FX,FY FX,FY 代表终点坐标。
接下来 T T T 行，每行两个正整数，表示障碍点的坐标。
输出格式
输出从起点坐标到终点坐标的方案总数。文章来源：https://www.toymoban.com/news/detail-611893.html
样例 #1
样例输入 #1
2 2 1
1 1 2 2
1 2
样例输出 #1
1
提示
对于 100 % 100\% 100% 的数据， 1 ≤ N , M ≤ 5 1 \le N,M \le 5 1≤N,M≤5， 1 ≤ T ≤ 10 1 \le T \le 10 1≤T≤10， 1 ≤ S X , F X ≤ n 1 \le SX,FX \le n 1≤SX,FX≤n， 1 ≤ S Y , F Y ≤ m 1 \le SY,FY \le m 1≤SY,FY≤m。文章来源地址https://www.toymoban.com/news/detail-611893.html
解题思路
- 1）将能通过的位置赋值为0，将不能通过的位置赋值为1。
- 2）对四个方向进行深度优先搜索。
参考代码
#include <bits/stdc++.h>
using namespace std;
int N,M,T,sx,sy,fx,fy;
int ans;
int map[100][100];
int b[100][100];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
bool check(int x,int y)
{
if(x<1||x>N||y<1||y>M)return false;
if(map[x][y]) return false;
if(b[x][y])return false;
return true;
}
void dfs(int x,int y)
{
if(x==fx&&y==fy)
{
ans++;
return;
}
for(int i=0;i<4;i++)
{
int newx=x+dx[i];
int newy=y+dy[i];
if(check(newx,newy))
{
b[x][y]=1;
dfs(newx,newy);
b[x][y]=0;
}
}
}
int main()
{
cin>>N>>M>>T;
cin>>sx>>sy>>fx>>fy;
int x,y;
while(T--)
{
cin>>x>>y;
map[x][y]=1;
}
dfs(sx,sy);
cout<<ans;
return 0;
}
到了这里，关于百日刷题计划 ———— DAY1的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
