【深基7.例1】距离函数
题目描述
输入格式
输入三行，第 i行表示坐标 ( x i , y i )，以一个空格隔开。
输出格式
输出一个两位小数，表示由这三个坐标围成的三角形的周长。
样例 #1
样例输入 #1
0 0 0 3 4 0
样例输出 #1
12.00
提示
数据保证，坐标均为实数且绝对值不超过 100，小数点后最多仅有 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的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。
上面的布局可以用序列 2 4 6 1 3 5 来描述，第 i ii 个数字表示在第 i 行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 3个解。最后一行是解的总个数。
输入格式
一行一个正整数 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 % 的数据，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个整数 T（1 ≤ T ≤ 1000）和 M （1 ≤ M ≤ 100 ），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
接下来的 M行每行包括两个在 1到 100之间（包括 1和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
样例 #1
样例输入 #1
70 3 71 100 69 1 1 2
样例输出 #1
3
提示
【数据范围】
对于 30 % 30\%30% 的数据，M ≤ 10
对于全部的数据，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 mm 和题目类 n nn。
第 2到第 ( n + 1 ) 行，每行两个用空格隔开的整数，第 ( i + 1 )行的整数 p i , t i分别代表解决第 i类题得到的分数和需要花费的时间。
既然是某一类题目，那么这一类题目可以重复选择。
输出格式
输出一行一个整数，代表最大的总分。
样例 #1
样例输入 #1
300 4 100 60 250 120 120 100 35 20
样例输出 #1
605
提示
数据规模与约定
解题思路
- 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 方格的迷宫，迷宫里有 T处障碍，障碍处不可通过。
在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。
输入格式
第一行为三个正整数 N , M , T，分别表示迷宫的长宽和障碍总数。
第二行为四个正整数 S X , S Y , F X , F Y SX,SY代表起点坐标，F X , F Y 代表终点坐标。
接下来 T行，每行两个正整数，表示障碍点的坐标。
输出格式
输出从起点坐标到终点坐标的方案总数。
样例 #1
样例输入 #1
2 2 1 1 1 2 2 1 2
样例输出 #1
1
提示
解题思路
- 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; }
