蓝桥杯2015国赛javaB组题目详解
第一题 一步之遥
题目描述
从昏迷中醒来，小明发现自己被关在X星球的废矿车里。矿车停在平直的废弃的轨道上。
他的面前是两个按钮，分别写着“F”和“B”。
小明突然记起来，这两个按钮可以控制矿车在轨道上前进和后退。按F，会前进97米。按B会后退127米。
透过昏暗的灯光，小明看到自己前方1米远正好有个监控探头。
他必须设法使得矿车正好停在摄像头的下方，才有机会争取同伴的援助。
或许，通过多次操作F和B可以办到。
矿车上的动力已经不太足，黄色的警示灯在默默闪烁...每次进行 F 或 B 操作都会消耗一定的能量。
小明飞快地计算，至少要多少次操作，才能把矿车准确地停在前方1米远的地方。
请填写为了达成目标，最少需要操作的次数。输出格式
输出一个整数表示答案代码
public class 蓝桥杯2016一步之遥 {
public static void main(String[] args) {
int a,b;
for(int i=0;;i++){
if((i*97)%127==1){
a=i;
b=(i*97)/127;
break;
}
}
System.out.println(a+b);
}
}
第二题 凑平方数
题目描述
把0~9这10个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。
比如：0, 36, 5948721
再比如：
1098524736
1, 25, 6390784
0, 4, 289, 15376等等...
注意，0可以作为独立的数字，但不能作为多位数字的开始。
分组时，必须用完所有的数字，不能重复，不能遗漏。
如果不计较小组内数据的先后顺序，请问有多少种不同的分组方案？输出格式
输出一个整数表示答案代码
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class 蓝桥杯2016凑平方数 {
public static void main(String[] args) {
List<Long> num = new ArrayList<>();
//得到范围内所有的平方数
for(long i=0;i*i<=9876543210l;i++){
long midi = i*i;
//剔除有（0-9）重复数字的平方数
if(isAlone(midi)){
num.add(midi);
// System.out.println(midi);
}
}
//进行排列组合
dfs(num,0,0);
System.out.println(count);
}
static int count =0;
static ArrayList<String> list = new ArrayList<>();
public static void dfs(List<Long> mylist,int curlength,int cur){
if(curlength==10){
//关键判断，根据长度为10并且没有重复数字可以唯一确定其为所求组合之一
StringBuilder sb = new StringBuilder();
for(String s:list){
//每一个符合length=10条件的组合拼接在一起
sb.append(s);
}
//进行重复判断
if(isAlone(sb.toString())){
//确定符合 加一
count++;
// for(String s:list){
// System.out.print(s+" ");
// }
// System.out.println();
}
}else if(curlength>10){
return;
}
//排列组合
for(int i=cur;i<mylist.size();i++){
String str = String.valueOf(mylist.get(i));
if(!list.contains(str)){
list.add(str);
dfs(mylist,curlength+str.length(),i+1);
list.remove(list.size()-1);
}
}
}
//重载isAlone
public static Boolean isAlone(Long num) {
String s = String.valueOf(num);
char[] ch = s.toCharArray();
Set<Character> set = new HashSet<>();
for(char c:ch){
if(!set.add(c)){
return false;
}
}
return true;
}
public static Boolean isAlone(String s) {
char[] ch = s.toCharArray();
Set<Character> set = new HashSet<>();
for(char c:ch){
if(!set.add(c)){
return false;
}
}
return true;
}
}
第三题 机器人塔
题目描述
X星球的机器人表演拉拉队有两种服装，A和B。
他们这次表演的是搭机器人塔。
类似：
A
B B
A B A
A A B B
B B B A B
A B A B B A
队内的组塔规则是：
A 只能站在 AA 或 BB 的肩上。
B 只能站在 AB 或 BA 的肩上。
你的任务是帮助拉拉队计算一下，在给定A与B的人数时，可以组成多少种花样的塔。
输入一行两个整数 M 和 N，空格分开（0<M,N<500）,分别表示A、B的人数，保证人数合理性。
要求输出一个整数，表示可以产生的花样种数。输入
输入一行两个整数 M 和 N，空格分开（0<M,N<500）,分别表示A、B的人数，保证人数合理性。输出
要求输出一个整数，表示可以产生的花样种数。样例输入
1 2样例输出
3代码(注释解析)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class 蓝桥杯2016机器人塔 {
public static void main(String[] args) {
int numa,numb;
Scanner sc = new Scanner(System.in);
numa = sc.nextInt();
numb = sc.nextInt();
sc.close();
int num = numa+numb;
//最后一行数量
int lastlength = ((int) (Math.sqrt(1+8*num))-1)/2;
//从最后一行开始往前推进
//A=0;B=1
int[] ab ={0,1};
dfs(lastlength, numa, numb, ab);
System.out.println(count);
}
static int count=0;
static ArrayList<Integer> dlist = new ArrayList<>();
//对最后一行进行排列组合
public static void dfs(int lastlength,int numa,int numb,int[] ab) {
if(dlist.size()==lastlength){
//对每种情况进行判断
if(check(dlist, numa, numb)){
count++;
}
return;
}
for(int i=0;i<ab.length;i++){
dlist.add(ab[i]);
dfs(lastlength, numa, numb, ab);
dlist.remove(dlist.size()-1);
}
}
//判断在该末行情况下所唯一确定的机器人塔所用的a的数量和b的数量是否合规
public static Boolean check(List<Integer> mylist,int cura ,int curb) {
if(mylist.size()==0&&cura==0&&curb==0){
return true;
}else if(mylist.size()==0&&(cura!=0||curb!=0)){
return false;
}
ArrayList<Integer> list = new ArrayList<>();
int mya=cura;
int myb=curb;
for(int i:mylist){
if(i==0){
mya-=1;
}else if(i==1){
myb-=1;
}
}
for(int i=0;i<mylist.size()-1;i++){
if(mylist.get(i)==mylist.get(i+1)){
list.add(0);
}else{
list.add(1);
}
}
return check(list, mya, myb);
}
}
第四题 广场舞
题目描述
LQ市的市民广场是一个多边形，广场上铺满了大理石的地板砖。
地板砖铺得方方正正，就像坐标轴纸一样。
以某四块砖相接的点为原点，地板砖的两条边为两个正方向，一块砖的边长为横纵坐标的单位长度，则所有横纵坐标都为整数的点都是四块砖的交点（如果在广场内）。
广场的砖单调无趣，却给跳广场舞的市民们提供了绝佳的参照物。每天傍晚，都会有大批市民前来跳舞。
舞者每次都会选一块完整的砖来跳舞，两个人不会选择同一块砖，如果一块砖在广场边上导致缺角或者边不完整，则没人会选这块砖。（广场形状的例子参考下图）
现在，告诉你广场的形状，请帮LQ市的市长计算一下，同一时刻最多有多少市民可以在广场跳舞。
输入格式
输入的第一行包含一个整数n，表示广场是n边形的（因此有n个顶点）。
接下来n行，每行两个整数，依次表示n边形每个顶点的坐标（也就是说广场边缘拐弯的地方都在砖的顶角上。
数据保证广场是一个简单多边形。输出格式
输出一个整数，表示最多有多少市民可以在广场跳舞。输入样例
5
3 3
6 4
4 1
1 -1
0 4输出样例
7思路
通过四个极值可以判断出大致的遍历范围
关键是如何判断点是否在多边形内部
这里是采用射线法
奇数交点为内部
偶数交点为外部
还要考虑边界条件，射线过顶点以及点在边界上等等。代码（我的代码只能通过百分之五十的测试样例，然后就超内存了（= 。=）
import java.util.ArrayList;
import java.util.Scanner;
public class 蓝桥杯2016广场舞 {
public static void main(String[] args) {
int count=0;
Scanner sc = new Scanner(System.in);
int N= sc.nextInt();
ArrayList<Node> mylist = new ArrayList<>();
for(int i=0;i<N;i++){
mylist.add(new Node(sc.nextInt(),sc.nextInt()));
}
sc.close();
int xmax=Integer.MIN_VALUE;
int xmin=Integer.MAX_VALUE;
int ymax=Integer.MIN_VALUE;
int ymin=Integer.MAX_VALUE;
for(Node node:mylist){
if(node.x>xmax){
xmax=node.x;
}
if(node.x<xmin){
xmin=node.x;
}
if(node.y>ymax){
ymax=node.y;
}
if(node.y<ymin){
ymin=node.y;
}
}
ArrayList<ArrayList<Node>> graph = new ArrayList<>();
for(int j=ymax;j>=ymin;j--){
ArrayList<Node> newList = new ArrayList<>();
for(int i=xmin;i<=xmax;i++){
newList.add(new Node(i, j));
}
graph.add(newList);
}
for(int i=0;i<graph.size()-1;i++){
for(int j=0;j<graph.get(i).size()-1;j++){
if(check(mylist, graph.get(i).get(j))&&check(mylist, graph.get(i+1).get(j))&&check(mylist, graph.get(i).get(j+1))&&check(mylist, graph.get(i+1).get(j+1))){
count++;
}
}
}
System.out.println(count);
}
//射线看奇偶
public static Boolean check(ArrayList<Node> myList,Node testNode) {
Boolean jiaodian = false;
for(int i=0;i<myList.size()-1;i++){
int x1=myList.get(i).x;
int x2=myList.get(i+1).x;
int y1=myList.get(i).y;
int y2=myList.get(i+1).y;
if(i==myList.size()-1){
x2=myList.get(0).x;
y2=myList.get(0).y;
}
//多种情况
//点在边界上
//射线过端点
if(((y2-testNode.y)*(testNode.x-x1)==(testNode.y-y1)*(x2-testNode.x))&&((testNode.y<=y1&&testNode.y>=y2)||(testNode.y>=y1&&testNode.y<=y2))){
// System.out.println(testNode.x+" "+testNode.y);
return true;
}
if(((y1<testNode.y)!=(y2<testNode.y))&&((testNode.y-y1)*(x2-x1)/(y2-y1)+x1>testNode.x)){
jiaodian=!jiaodian;
}
}
return jiaodian;
}
static class Node{
int x,y;
public Node(int x,int y){
this.x = x;
this.y = y;
}
}
}
