前面两题是c的，跟着别的博客搞错了，后面去蓝桥官网下了真题。后面的正确。
1.标题：换零钞
x星球的钞票的面额只有：100元，5元，2元，1元，共4种。
小明去x星旅游，他手里只有2张100元的x星币，太不方便，恰好路过x星银行就去换零钱。
小明有点强迫症，他坚持要求200元换出的零钞中2元的张数刚好是1元的张数的10倍，
剩下的当然都是5元面额的。
银行的工作人员有点为难，你能帮助算出：在满足小明要求的前提下，最少要换给他多少张钞票吗？
（5元，2元，1元面额的必须都有，不能是0）
---------------------
思路：直接枚举还算列公式推都很快。
package lq2018_gs;
public class t1 {
public static void main(String[] arg) {
for(int q = 1; q < 100; q++) {
for(int y = 1; y < 500; y++) {
if(5 * y + q * 21 == 200) {
System.out.println("q = " + q +"; " + "y = " + y + "; sum = " + (q * 11 + y));
// break;
}
}
}
}
}
/*
* answer:
q = 5; y = 19; sum = 74
*/
2.标题：激光样式
x星球的盛大节日为增加气氛，用30台机光器一字排开，向太空中打出光柱。
安装调试的时候才发现，不知什么原因，相邻的两台激光器不能同时打开！
国王很想知道，在目前这种bug存在的情况下，一共能打出多少种激光效果？
显然，如果只有3台机器，一共可以成5种样式，即：
全都关上（sorry, 此时无声胜有声，这也算一种）
开一台，共3种
开两台，只1种
30台就不好算了，国王只好请你帮忙了。
要求提交一个整数，表示30台激光器能形成的样式种数。
---------------------
思路：直接dfs吧。
package lq2018_gs;
public class t2 {
public static long ans = 0;
public static long N = 30;
public static void main(String[] arg) {
int a[] = new int[30];
dfs(0, 0, a);
System.out.println(ans);
}
public static void dfs(int x, int f, int[] a) {
if(x == N) {
ans++;
// for(int i = 0; i < N; i++) {
// System.out.print(a[i] + " ");
// }
// System.out.println();
return ;
}
if(f == 0) { // 上一次没点，这次可以点或者不点
a[x] = 1;
dfs(x + 1, 1, a);
a[x] = 0;
dfs(x + 1, 0, a);
}
else {
a[x] = 0;
dfs(x + 1, 0, a);
}
}
}
/*
* ans = 2178309
*/
javaB组国赛真题：
1、标题：三角形面积
已知三角形三个顶点在直角坐标系下的坐标分别为：
(2.3, 2.5)
(6.4, 3.1)
(5.1, 7.2)
求该三角形的面积。
注意，要提交的是一个小数形式表示的浮点数。
要求精确到小数后3位，如不足3位，需要补零。
-------------------------------------------------------------------
my code:
package lq2018_gs;
public class t11 {
public static void main(String[] arg) {
double x[] = {2.3, 6.4, 5.1};
double y[] = {2.5, 3.1, 7.2};
// double x[] = {0, 4, 0};
// double y[] = {3, 0, 0}; // test: s = 6
double l[] = new double[3];
l[0] = Math.sqrt((x[0] - x[1]) * (x[0] - x[1]) + (y[0] - y[1]) * (y[0] - y[1]));
l[1] = Math.sqrt((x[0] - x[2]) * (x[0] - x[2]) + (y[0] - y[2]) * (y[0] - y[2]));
l[2] = Math.sqrt((x[2] - x[1]) * (x[2] - x[1]) + (y[2] - y[1]) * (y[2] - y[1]));
double p = (l[0] + l[1] + l[2]) / 2;
double s = Math.sqrt(p * (p - l[0]) * (p - l[1]) * (p - l[2]));
System.out.println(s);
}
}
/*
* answer = 8.795
*/
某位大佬的：https://www.cnblogs.com/xiexinxinlove/p/3708147.html
package lq2018_gs;
import java.util.Scanner;
public class test {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
double x1 = sc.nextDouble();
double y1 = sc.nextDouble();
double x2 = sc.nextDouble();
double y2 = sc.nextDouble();
double x3 = sc.nextDouble();
double y3 = sc.nextDouble();
// if()
double area = Math.abs(((x1*y2+x2*y3+x3*y1)-(y1*x2+y2*x3+y3*x1))/2);
System.out.println(String.format("%.3f", area));
}
}
/*
2.3 2.5
6.4 3.1
5.1 7.2
*/
2、标题：最大乘积
把 1~9 这9个数字分成两组，中间插入乘号，
有的时候，它们的乘积也只包含1~9这9个数字，而且每个数字只出现1次。
比如：
984672 * 351 = 345619872
98751 * 3462 = 341875962
9 * 87146325 = 784316925
...
符合这种规律的算式还有很多，请你计算在所有这些算式中，乘积最大是多少？
注意，需要提交的是一个整数，表示那个最大的积，不要填写任何多余的内容。
（只提交乘积，不要提交整个算式）
--------------------------
思路：就是全排列，然后枚举每个排列结果中乘号的位置，暴力吧，而且会有重复，但是只要最大嘛，不影响结果。
package lq2018_gs;
public class t22 {
public static int[] data = new int[10];
public static int[] vist = new int[10];
public static long max_ans = 0;
public static long N = 9;
public static long CT = 0;
public static void main(String[] args) {
// TODO Auto-generated method stub 362880
dfs(1);
// System.out.println(CT);
System.out.println(max_ans);
}
public static void dfs(int ct) {
if(ct == N + 1) {
CT++;
// for(int i = 1; i <= N; i++) {
// System.out.print(data[i] + " ");
// }
// System.out.println();
for(int i = 1; i <= 8; i++) {
long le = 0, rt = 0;
for(int j = 1; j <= i; j++) {
le = le * 10 + data[j];
}
for(int j = i + 1; j <= 9; j++) {
rt = rt * 10 + data[j];
}
long ans = le * rt;
int temp[] = new int[10];
int f = 1;
while(ans != 0) {
int t = (int) (ans % 10);
if(temp[t] == 1 || t == 0) {
f = 0;
break;
}
temp[t] = 1;
ans /= 10;
}
for(int k = 1; k <= 9; k++) {
if(temp[k] == 0) {
f = 0;
break;
}
}
if(f == 1) {
max_ans = Math.max(max_ans, le * rt);
}
}
return ;
}
for(int i = 1; i <= N; i++) {
if(vist[i] == 0) {
vist[i] = 1;
data[ct] = i;
dfs(ct + 1);
vist[i] = 0;
}
}
}
}
/*
* answer = 839542176
*
*/
3、标题：全排列
对于某个串，比如：“1234”，求它的所有全排列。
并且要求这些全排列一定要按照字母的升序排列。
对于“1234”，应该输出(一共4!=24行)：
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
下面是实现程序，请仔细分析程序逻辑，并填写划线部分缺少的代码。
// 轮换前k个，再递归处理
import java.util.*;
public class A
{
static void permu(char[] data, int cur){
if(cur==data.length-1){
System.out.println(new String(data));
return;
}
for(int i=cur; i<data.length; i++){
char tmp = data[i];
for(int j=i-1; j>=cur; j--) data[j+1] = data[j];
data[cur] = tmp;
permu(data, cur+1);
tmp = data[cur];
__________________________________________ ;
data[i] = tmp;
}
}
static void permu(String x){
permu(x.toCharArray(),0);
}
public static void main(String[] args){
permu("1234");
}
}
请注意：只需要填写划线部分缺少的内容，不要抄写已有的代码或符号。
// for(int j=cur+1; j<=i; j++) data[j-1] = data[j]; for(int j=cur; j<i; j++) data[j] = data[j+1];
4、标题：整理玩具
小明有一套玩具，一共包含NxM个部件。这些部件摆放在一个包含NxM个小格子的玩具盒中，每个小格子中恰好摆放一个部件。
每一个部件上标记有一个0~9的整数，有可能有多个部件标记相同的整数。
小明对玩具的摆放有特殊的要求：标记相同整数的部件必须摆在一起，组成一个矩形形状。
如以下摆放是满足要求的：
00022
00033
44444
12244
12244
12233
01234
56789
以下摆放不满足要求：
11122
11122
33311
111111
122221
122221
111111
11122
11113
33333
给出一种摆放方式，请你判断是否符合小明的要求。
输入
----
输入包含多组数据。
第一行包含一个整数T，代表数据组数。 (1 <= T <= 10)
以下包含T组数据。
每组数据第一行包含两个整数N和M。 (1 <= N, M <= 10)
以下包含N行M列的矩阵，代表摆放方式。
输出
---
对于每组数据，输出YES或者NO代表是否符合小明的要求。
【样例输入】
3
3 5
00022
00033
44444
3 5
11122
11122
33311
2 5
01234
56789
【样例输出】
YES
NO
YES
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
-----
思路：因为是矩形，所以确定矩形，看里面都是一样的不就行了，刚开始以为共dfs搞，发现，还不如直接用两个并列的for循环直接，
找到左上顶点和右下顶点即可。然后就是将处理后的点标记为不一样的，然后还要记录当前已经访问过的数字，每个数字在一起，故
只可能出现一次，否则就不是了。
My code:
package lq2018_gs;
import java.util.Scanner;
public class t4 {
public static int N, M;
public static char[][] map = new char[15][15];
// public static int dx[] = {-1, 1, 0, 0};
// public static int dy[] = {0, 0, 1, -1};
public static void main(String[] arg) {
Scanner cin = new Scanner(System.in);
int t = Integer.parseInt(cin.nextLine().trim());
while(t-- != 0) {
String line = cin.nextLine().trim();
N = Integer.parseInt(line.split(" ")[0]);
M = Integer.parseInt(line.split(" ")[1]);
// System.out.println(N + " " + M);
for(int i = 0; i < N; i++) {
line = cin.nextLine().trim();
map[i] = line.toCharArray();
}
int[] visit = new int[10];
int flag = 1;
for(int i = 0; i < N && flag == 1; i++) {
for(int j = 0; j < M && flag == 1; j++) {
if(map[i][j] != '*' && visit[map[i][j] - '0'] == 0) {
int min_x = i, min_y = j; // 找到小矩形
int max_x = 0, max_y = 0; // 左右对角
char ch = map[i][j];
visit[ch - '0'] = 1;
for(int k = j; k < M; k++) {
if(map[i][k] == ch) {
max_y = k;
}
else {
break;
}
}
for(int k = i; k < N; k++) {
if(map[k][max_y] == ch) {
max_x = k;
}
else {
break;
}
}
for(int a = min_x; a <= max_x; a++) {
for(int b = min_y; b <= max_y; b++) {
if(map[a][b] == ch) {
map[a][b] = '*';
}
else {
flag = 0; // 小矩形内有其他数字，直接错误
break;
}
}
}
}
else if(map[i][j] != '*' && visit[map[i][j] - '0'] == 1) {
flag = 0;
}
}
}
if(flag == 1) {
System.out.println("YES");
}
else {
System.out.println("NO");
}
}
}
}
/*
6
3 5
00022
00033
44444
3 5
12244
12244
12233
2 5
01234
56789
3 5
11122
11122
33311
4 6
111111
122221
122221
111111
3 5
11122
11113
33333
YES
YES
YES
NO
NO
NO
*/
5、标题：版本分支
小明负责维护公司一个奇怪的项目。这个项目的代码一直在不断分支(branch)但是从未发生过合并(merge)。
现在这个项目的代码一共有N个版本，编号1~N，其中1号版本是最初的版本。
除了1号版本之外，其他版本的代码都恰好有一个直接的父版本；即这N个版本形成了一棵以1为根的树形结构。
如下图就是一个可能的版本树：
1
/ \
2 3
| / \
5 4 6
现在小明需要经常检查版本x是不是版本y的祖先版本。你能帮助小明吗？
输入
----
第一行包含两个整数N和Q，代表版本总数和查询总数。
以下N-1行，每行包含2个整数u和v，代表版本u是版本v的直接父版本。
再之后Q行，每行包含2个整数x和y，代表询问版本x是不是版本y的祖先版本。
对于30%的数据，1 <= N <= 1000 1 <= Q <= 1000
对于100%的数据，1 <= N <= 100000 1 <= Q <= 100000
输出
----
对于每个询问，输出YES或NO代表x是否是y的祖先。
【样例输入】
6 5
1 2
1 3
2 5
3 6
3 4
1 1
1 4
2 6
5 2
6 4
【样例输出】
YES
YES
NO
NO
NO
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
-------
思路： 没有想到好的方法，直接并查集的，还不能压缩，网上没有找到好的题解！！！！
package lq2018_gs;
import java.util.Scanner;
public class t5 {
public static int N, Q;
public static int f[] = new int[100005];
public static int g[] = new int[100005];
public static void main(String[] arg) {
Scanner cin = new Scanner(System.in);
for(int i = 1; i < 100005; i++) {
f[i] = i;
g[i] = 1;
}
N = cin.nextInt();
Q = cin.nextInt();
int u, v;
for(int i = 0; i < N - 1; i++) {
u = cin.nextInt();
v = cin.nextInt();
f[v] = u;
}
// 查找
for(int i = 0; i < Q; i++) {
u = cin.nextInt();
v = cin.nextInt();
int x = find(v, u); // v的祖先是不是u
if(1 == x) {
System.out.println("YES");
}
else {
System.out.println("NO");
}
}
}
public static int find(int x, int y) {
if(f[x] == y) {
return 1;
}
if(f[x] == x) {
return 0;
}
return find(f[x], y);
}
}
6、标题：防御力
小明最近在玩一款游戏。对游戏中的防御力很感兴趣。
我们认为直接影响防御的参数为“防御性能”，记作d，而面板上有两个防御值A和B，与d成对数关系，A=2^d，B=3^d（注意任何时候上式都成立）。
在游戏过程中，可能有一些道具把防御值A增加一个值，有另一些道具把防御值B增加一个值。
现在小明身上有n1个道具增加A的值和n2个道具增加B的值，增加量已知。
现在已知第i次使用的道具是增加A还是增加B的值，但具体使用那个道具是不确定的，请找到一个字典序最小的使用道具的方式，使得最终的防御性能最大。
初始时防御性能为0，即d=0，所以A=B=1。
【输入格式】
输入的第一行包含两个数n1,n2，空格分隔。
第二行n1个数，表示增加A值的那些道具的增加量。
第三行n2个数，表示增加B值的那些道具的增加量。
第四行一个长度为n1+n2的字符串，由0和1组成，表示道具的使用顺序。0表示使用增加A值的道具，1表示使用增加B值的道具。输入数据保证恰好有n1个0，n2个1。
【输出格式】
对于每组数据，输出n1+n2+1行，前n1+n2行按顺序输出道具的使用情况，若使用增加A值的道具，输出Ax，x为道具在该类道具中的编号（从1开始）。若使用增加B值的道具则输出Bx。最后一行输出一个大写字母E。
【样例输入1】
1 2
4
2 8
101
【样例输出1】
B2
A1
B1
E
【样例输入2】
3 0
7 11 13
000
【样例输出2】
A1
A2
A3
E
【样例说明】
对于第一组测试数据，操作过程如下：
操作 d A B
初始 0 1 1
B2 2 4 9
A1 3 8 27
B1 log3(29) 2^(log3(29)) 29
可以证明，这个值是最大的。
对于第二组测试数据，可见无论用什么顺序，A最后总为32，即d总为5，B总为243。
【数据规模】
对于20%的数据，字符串长度<=10000；
对于70%的数据，字符串长度<=200000；
对于100%的数据，字符串长度<=2000000，输入的每个增加值不超过2^30。
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
-------------
不会啊啊啊，甚至暴力都无从下手！！！！