第十五届蓝桥杯C/C++学B组（解）
则时间*速率=路程t*dx = 2px ,t*dy = 2qy,令一式/二式，得p/q= y/x*dx/dy = y*dx/x*dy ，利用gcd（求两个数的最大公约数）对分式p,q进行约分，进而得到约分后的p,q 则利用时间t=2px/dx,总路程 = t*(sqrt(15^2+17^2))针对前进的方向进行分解为x,y方向，去求解运动返回到左上角的时间，有了时间，即可利用时间来计算总路程，假设
目录
1.握手问题
解题思路一
数学方法
50个人互相握手 （49+1）*49/2 ，减去7个人没有互相握手（6+1）*6/2
答案：1204
解题思路二
思路：
模拟
将50个人从1到50标号，对于每两个人之间只握一次手，我们可以将问题转化为每个人只主动和标号比他大的人握一次手，那么标号为 1 的人，需要主动握 49 次，标号为 2 的人，需要主动握 48 次，以此类推，标号为 i 的人需要主动握 50 - i 次。（这边强烈建议 I 人往后排）
经过上述流程，我们即可得到不加限制条件下的总握手次数为 1 + 2 + ... + 48 + 49 = 1225
接下来我们来处理限制条件，我们假设相互之间没有握手的这七个人为标号 1 ~ 7 的七个人，那么如果他们之间有相互握手的话，根据前述流程可得他们之间握手次数为 1 + 2 + ... + 6 = 21
用总次数减去多余握手次数（前七个人间相互握手次数）即得到限制条件下的握手次数，即为 1204
可用代码实现求和、求差过程
package 十五届;
public class Min {
public static void main(String[] args) {
int ans = 0;
for (int i = 1; i <= 50; i++) {
for (int j = i+1; j <= 50; j++) {
//排除掉7人的情况
if(!(i>=1&&i<=7 && j>=1&&j<=7)){
ans++;
}
}
}
System.out.println(ans);
}
}2.小球反弹
解题思路：
针对前进的方向进行分解为x,y方向，去求解运动返回到左上角的时间，有了时间，即可利用时间来计算总路程，假设 x方向走了p个来回，y方向走了q个来回，经过了时间t，小球第一次回到原点
则时间*速率=路程 t*dx = 2px ,t*dy = 2qy,令一式/二式，得p/q= y/x*dx/dy = y*dx/x*dy ，利用gcd（求两个数的最大公约数）对分式p,q进行约分，进而得到约分后的p,q 则利用时间t=2px/dx,总路程 = t*(sqrt(15^2+17^2))
package 十五届;
import static java.lang.Math.sqrt;
public class 小球反弹 {
public static void main(String[] args) {
int x = 343720;
int y = 233333;
int dx = 15;
int dy = 17;
int p = y * dx;
int q = x * dy;
int g = gcd(p, q);
p /= g;
q /= g;
int t = 2 * p * x / dx;
double ans = t * sqrt(15 * 15 + 17 * 17);
//d答案输出两位小数
System.out.printf("%.2f", ans);
}
public static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}答案：1100325199.77
3.好数
解题思路
首先排除掉末位数，可以优化复杂度，满足条件后 在进一步检查偶数位是否为偶数，奇数位是否为奇数
package 十五届;
import java.util.Scanner;
public class 好数 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int ans = 0;
for (int i = 1; i <= n; i++) {
//局部优化：过滤数值结尾不符合条件的情况
if (i % 10 % 2 == 0) continue;
if (check(i)) ans++;//判断是否为好数
}
System.out.println(ans);
}
//检查x是否为好数
public static boolean check(int x) {
int cnt = 1; //记录位数
while (x > 0) {
int b = x % 10;
if (cnt % 2 == 1) {//是奇数位并且不是奇数
if (b % 2 != 1) return false;
} else if (b % 2 != 0) {//是偶数位并且不是偶数
return false;
}
cnt++;
x /= 10;
}
return true;
}
}4.R格式
解题思路：
本题考察利用数组模拟高精度，
package 十五届;
import java.util.Scanner;
public class 高精度 {
public static void main(String[] args) {
int[] a = new int[(int) (2e3 + 10)];
String s = "";
int n = 0;
Scanner scanner = new Scanner(System.in);
s = scanner.nextLine();
n = scanner.nextInt();
StringBuffer stringBuffer = new StringBuffer(s);
stringBuffer.reverse();//反转字符串
int pos = s.indexOf('.');
stringBuffer.delete(pos, pos + 1);//把小数点删除，方便后续计算
int len = s.length();
for (int i = 0; i < len; i++) {
a[i + 1] = stringBuffer.charAt(i) - '0';
}
//高精度*低精度模板
for (int i = 1; i <= n; i++) {
//顺序扫描每一位，均*2
for (int j = 1; j <= len; j++) {
a[j] = a[j] * 2;
}
//再次扫描。处理进位和最高位
for (int j = 1; j <= len; j++) {
if (a[j] >= 10) {
a[j + 1]++;
a[j] %= 10;
if (j == len) len++;
}
}
}
//处理小数点后的第一位，进行四舍五入
if (a[pos] >= 5) {
a[pos + 1]++;
}
//倒序打印
for (int i = len; i >= pos+1; i--) {
System.out.print(a[i]);
}
}
}第四题：宝石组合
题解：
1.先对宝石的 “闪亮度” 进行排序，从小到大排列。
2.枚举所有可能的三种宝石组合，可以采用三重循环来实现，其中第一个循环选择第一种宝石，第二个循环选择第二种宝石，第三个循环选择第三种宝石。
3.对于每种组合，计算它们的精美程度。精美程度可以定义为三种宝石的乘积除以它们的最小公倍数。最小公倍数可以通过最大公约数来求得。
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<utility>
using namespace std;
int gcd(int a,int b){
if(!b)
return a;
return gcd(b,a%b);
}
int lcm(int a,int b){
return a/gcd(a,b)*b;
}
void Solution()
{
int n;
cin>>n;
vector<int>g(n);
for(int &a:g)
cin>>a;
sort(g.begin(),g.end());
int a=0,b=0,c=0;
int maxx=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(j!=i)
{
for(int k=0;k<n;k++){
if(k!=j&&k!=i)
{
int q,w,e,r;
q=lcm(g[i],g[j]);
w=lcm(g[i],g[k]);
e=lcm(g[j],g[k]);
r=lcm(q,g[k]);
int tem=g[i]*g[j]*g[k]*r/q/w/e;
if(tem>maxx){
maxx=tem;
a=g[i];
b=g[j];
c=g[k];
}
}
}
}
}
}
cout<<a<<' '<<b<<' '<<c;
return;
}
int main()
{
Solution();
return 0;
}
5: 数字接龙（15分）
问题描述
小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为N × N N × NN×N 的格子棋盘上展开，其中每一个格子处都有着一个0... K − 1 0 ... K − 10...K−1之间的整数。游戏规则如下：
从左上角( 0 , 0 ) (0, 0)(0,0) 处出发，目标是到达右下角( N − 1 , N − 1 ) (N − 1,N − 1)(N−1,N−1) 处的格子，每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。
对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列要满足：0 , 1 , 2 , . . . , K − 1 , 0 , 1 , 2 , . . . , K − 1 , 0 , 1 , 2 , . . . 0,1,2, ... , K − 1, 0, 1,2, ... ,K − 1, 0, 1, 2, ...0,1,2,...,K−1,0,1,2,...,K−1,0,1,2,...。
途中需要对棋盘上的每个格子恰好都经过一次（仅一次）。
路径中不可以出现交叉的线路。例如之前有从( 0 , 0 ) (0, 0)(0,0) 移动到( 1 , 1 ) (1, 1)(1,1)，那么再从( 1 , 0 ) (1, 0)(1,0) 移动到( 0 , 1 ) (0, 1)(0,1) 线路就会交叉。
为了方便表示，我们对可以行进的所有八个方向进行了数字编号，如下图2 22 所示；因此行进路径可以用一个包含0...7 0... 70...7 之间的数字字符串表示，如下图1 11是一个迷宫示例，它所对应的答案就是：41255214 4125521441255214。
现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径，输出字典序最小的那一个；如果不存在任何一条路径，则输出− 1 −1−1。
输入格式
第一行包含两个整数N NN、K KK。
接下来输入N NN 行，每行N NN 个整数表示棋盘格子上的数字。
输出格式
输出一行表示答案。如果存在答案输出路径，否则输出− 1 −1−1。
样例输入
3 3
0 2 0
1 1 1
2 0 2
样例输出
41255214
样例说明
行进路径如图1 11 所示。
评测用例规模与约定
对于80 % 80\%80% 的评测用例，1 ≤ N ≤ 5 1 ≤ N ≤ 51≤N≤5
对于100 % 100\%100% 的评测用例，1 ≤ N ≤ 10 , 1 ≤ K ≤ 10 1 ≤ N ≤ 10, 1 ≤ K ≤ 101≤N≤10,1≤K≤10
思路
dfs
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
private static final int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
private static final int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
private static int n, k;
private static boolean[][] st = new boolean[101][101];
private static boolean[][][][] ss = new boolean[11][11][11][11];
private static int[][] a = new int[101][101];
private static ArrayList<String> s = new ArrayList<>();
public static void dfs(int x, int y, String q) {
if (x == n - 1 && y == n - 1) {
if (q.length() == n * n - 1) {
s.add(q);
}
return;
}
for (int i = 0; i < 8; i++) {
int ax = x + dx[i], ay = y + dy[i];
if (ax < 0 || ay < 0 || ax >= n || ay >= n) continue;
if ((a[ax][ay]) != (a[x][y] + 1) % k) continue;
if (!st[ax][ay] && i % 2 == 0) {
st[ax][ay] = true;
char qq = (char) ('0' + i);
dfs(ax, ay, q + qq);
st[ax][ay] = false;
} else if (!st[ax][ay] && i % 2 == 1 && !ss[x][y][ax][ay]) {
st[ax][ay] = true;
char qq = (char) ('0' + i);
if (i == 1) {
ss[x - 1][y][ax + 1][ay] = true;
ss[ax + 1][ay][x - 1][y] = true;
}
if (i == 3 || i == 5) {
ss[x + 1][y][ax - 1][ay] = true;
ss[ax - 1][ay][x + 1][y] = true;
}
dfs(ax, ay, q + qq);
st[ax][ay] = false;
if (i == 1) {
ss[x - 1][y][ax + 1][ay] = false;
ss[ax + 1][ay][x - 1][y] = false;
}
if (i == 3 || i == 5) {
ss[x + 1][y][ax - 1][ay] = false;
ss[ax - 1][ay][x + 1][y] = false;
}
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
k = scanner.nextInt();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = scanner.nextInt();
}
}
String q = "";
st[0][0] = true;
dfs(0, 0, q);
if (s.isEmpty()) {
System.out.println(-1);
} else {
Collections.sort(s);
System.out.println(s.get(0));
}
}
}
6: 爬山（20分）
思路
贪心，维护一个堆，哪个魔法减少的更多就取哪个。
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int p = scanner.nextInt();
int q = scanner.nextInt();
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // 大顶堆
for (int i = 0; i < n; i++) {
int temp = scanner.nextInt();
pq.offer(temp);
}
while (p != 0 && q != 0) {
int cur = pq.poll();
if ((int) Math.sqrt(cur) < (int) (cur / 2)) {
p--;
cur = (int) Math.sqrt(cur);
} else {
q--;
cur = (int) (cur / 2);
}
pq.offer(cur);
}
while (p != 0) {
int cur = pq.poll();
p--;
cur = (int) Math.sqrt(cur);
pq.offer(cur);
}
while (q != 0) {
int cur = pq.poll();
q--;
cur = (int) (cur / 2);
pq.offer(cur);
}
long ans = 0;
while (!pq.isEmpty()) {
ans += pq.poll();
}
System.out.println(ans);
}
}
7：拔河（20分）
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
long n = Long.parseLong(br.readLine());
long[] num = new long[1010];
long[] pre = new long[1010];
TreeSet<Long> mset = new TreeSet<>();
String[] input = br.readLine().split(" ");
for (int i = 1; i <= n; i++) {
num[i] = Long.parseLong(input[i - 1]);
pre[i] = pre[i - 1] + num[i];
}
for (int l = 1; l <= n; l++) {
for (int r = l + 1; r <= n; r++) {
mset.add(pre[r] - pre[l]);
}
}
long res = 999999999;
for (int r = 1; r < n; r++) {
for (int l = 0; l < r; l++) {
long val = pre[r] - pre[l];
Long ceil = mset.ceiling(val);
if (ceil != null) {
res = Math.min(res, Math.abs(ceil - val));
}
Long floor = mset.floor(val);
if (floor != null) {
res = Math.min(res, Math.abs(floor - val));
}
}
for (int i = r + 1; i <= n; i++) {
mset.remove(pre[i] - pre[r]);
}
}
bw.write(res + "\n");
bw.flush();
bw.close();
br.close();
}
}
为武汉地区的开发者提供学习、交流和合作的平台。社区聚集了众多技术爱好者和专业人士，涵盖了多个领域，包括人工智能、大数据、云计算、区块链等。社区定期举办技术分享、培训和活动，为开发者提供更多的学习和交流机会。
更多推荐
22
0- 0
已为社区贡献1条内容
所有评论(0)