第八届蓝桥杯 2017年国赛真题 (Java 大学C组)
·
希望决赛题目不搞我
先挂
#1 数位和
本题满分: 15分
问题描述
数学家高斯很小的时候就天分过人。一次老师指定的算数题目是：1+2+…+100。
高斯立即做出答案：5050!
这次你的任务是类似的。但并非是把一个个的数字加起来，而是对该数字的每一个数位作累加。
这样从1加到100的“和”是：901
从10加到15是：21，也就是：1+0+1+1+1+2+1+3+1+4+1+5，这个口算都可以出结果的。
按这样的“加法”，从1加到1000是多少呢？ 请通过浏览器提交该结果。
当然，我们并不期望你能像高斯一样，发现数字背后深奥的秘密，只要请计算机帮忙，一切都easy!
答案提交
注意：你需要提交的是一个整数，不要填写任何多余的内容（比如：说明性文字）
13501
calcCode：
public class Test {
public static void main(String[] args) {
int res = 0;
for (int i = 1, n = 1; i <= 1000; n = ++i)
do res += n % 10;
while (0 < (n /= 10));
System.out.println(res);
}
}
优雅
不懂就问，为什么填空题不提交个代码算它个优雅分
#2 数字划分
本题满分: 31分
问题描述
w星球的长老交给小明一个任务：
1,2,3…16 这16个数字分为两组。
要求：
这两组数字的和相同，
并且，两组数字的平方和也相同，
并且，两组数字的立方和也相同。
请你利用计算机的强大搜索能力解决这个问题。
并提交1所在的那个分组的所有数字。
这些数字要从小到大排列，两个数字间用一个空格分开。
即类似：1 4 5 8 … 这样的答案。
答案提交
注意，只提交这一组数字，不要填写任何多余的内容。
1 4 6 7 10 11 13 16
calcCode：
import java.util.*;
public class Test {
static int n = 16, sum, pow2sum, pow3sum;
static int[] pow2, pow3;
public static void main(String[] args) {
pow2 = new int[n];
pow3 = new int[n];
for (int i = 0, v = 1; i < n; i++, v++) {
sum += v;
pow2sum += pow2[i] = v * v;
pow3sum += pow3[i] = v * pow2[i];
}
Deque<Integer> path = new ArrayDeque();
sum /= 2;
pow2sum /= 2;
pow3sum /= 2;
dfs(0, 0, 0, 0, path);
}
static void dfs(int cur, int val, int val2, int val3, Deque<Integer> path) {
if (cur == n) {
if (val == sum && val2 == pow2sum && val3 == pow3sum) System.out.println(path);
} else {
dfs(cur + 1, val, val2, val3, path);
path.addLast(cur + 1);
dfs(cur + 1, val + cur + 1, val2 + pow2[cur], val3 + pow3[cur], path);
path.removeLast();
}
}
}
深搜杯
#3 树形显示
本题满分: 23分
问题描述
对于分类结构可以用树形来形象地表示。比如：文件系统就是典型的例子。
树中的结点具有父子关系。我们在显示的时候，把子项向右缩进（用空格，不是tab），并添加必要的连接线，以使其层次关系更醒目。
下面的代码就是为了这个目的的，请仔细阅读源码，并填写划线部分缺少的代码。
import java.util.*;
class MyTree
{
private Map<String, List<String>> map_ch = new HashMap<String, List<String>>();
private Map<String,String> map_pa = new HashMap<String,String>();
public void add(String parent, String child)
{
map_pa.put(child, parent);
List<String> lst = map_ch.get(parent);
if(lst==null){
lst = new ArrayList<String>();
map_ch.put(parent, lst);
}
lst.add(child);
}
public String get_parent(String me){
return map_pa.get(me);
}
public List<String> get_child(String me){
return map_ch.get(me);
}
private String space(int n)
{
String s = "";
for(int i=0; i<n; i++) s += ' ';
return s;
}
private boolean last_child(String x){
String pa = map_pa.get(x);
if(pa==null) return true;
List<String> lst = map_ch.get(pa);
return lst.get(lst.size()-1).equals(x);
}
public void show(String x){
String s = "+--" + x;
String pa = x;
while(true){
pa = map_pa.get(pa);
if(pa==null) break;
s = ___________________________________ ; // 填空
}
System.out.println(s);
}
public void dfs(String x){
show(x);
List<String> lst = map_ch.get(x);
if(lst==null) return;
for(String it: lst){
dfs(it);
}
}
}
public class TreeView
{
public static void main(String[] args)
{
MyTree tree = new MyTree();
tree.add("root", "dog");
tree.add("root", "cat");
tree.add("root", "duck");
tree.add("dog", "AAdog");
tree.add("dog", "BBdog");
tree.add("dog", "CCdog");
tree.add("AAdog", "AAdog01");
tree.add("AAdog", "AAdog02");
tree.add("cat", "XXcat");
tree.add("cat", "YYcat");
tree.add("XXcat","XXcat-oo");
tree.add("XXcat","XXcat-qq");
tree.add("XXcat-qq", "XXcat-qq-hahah");
tree.add("duck", "TTduck");
tree.add("TTduck", "TTduck-001");
tree.add("TTduck", "TTduck-002");
tree.add("TTduck", "TTduck-003");
tree.add("YYcat","YYcat.hello");
tree.add("YYcat","YYcat.yes");
tree.add("YYcat","YYcat.me");
tree.dfs("root");
}
}
对于题目中的测试数据，输出结果:
答案提交
注意，只填写划线部分缺少的代码，不要抄写已有的代码或符号。
(last_child(pa)? "": "|") + space(pa.length()) + s
#4 小数第n位
时间限制: 1.0s 内存限制: 256.0MB 本题满分: 47 分
问题描述
我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。
如果我们把有限小数的末尾加上无限多个0，它们就有了统一的形式。
本题的任务是：在上面的约定下，求整数除法小数点后的第n位开始的3位数。
输入格式
一行三个整数：a b n，用空格分开。a是被除数，b是除数，n是所求的小数后位置（0<a,b,n<1000000000）
输出格式
一行3位数字，表示：a除以b，小数后第n位开始的3位数字。
测试样例1
Input：
1 8 1
Output：
125
测试样例2
Input：
1 8 3
Output：
500
测试样例3
Input：
282866 999000 6
Output：
914
code：
import java.io.IOException;
import java.io.InputStream;
public class Main {
static long mod;
public static void main(String[] args) {
InputReader in = new InputReader(System.in);
long a = in.nextInt(), b = in.nextInt(), n = in.nextInt();
mod = b * 1000;
System.out.printf("%03d", ((a % mod) * pow(10, n + 2) % mod) / b);
}
static long pow(long a, long n) {
a %= mod;
if (n == 0) return 1;
if (n == 1) return a;
if ((n & 1) == 0)
return pow(a * a, n / 2) % mod;
return (pow(a * a, n / 2) * a) % mod;
}
static class InputReader {
private InputStream in;
private int next, len;
private byte[] buff;
InputReader(InputStream in) { this(in, 8192); }
InputReader(InputStream in, int buffSize) {
this.buff = new byte[buffSize];
this.next = this.len = 0;
this.in = in;
}
private int getByte() {
if (next >= len)
try {
next = 0;
len = in.read(buff);
if (len == -1) return -1;
} catch (IOException e) {
e.fillInStackTrace();
}
return buff[next++];
}
private int split() {
int c = getByte();
while (c <= 32 || c == 127) c = getByte();
return c;
}
public int nextInt() {
int n = 0, c = split();
boolean flag = true;
if (c == '-') {
c = getByte();
flag = false;
}
while (c >= '0'&& c <='9') {
n = n * 10 + (c & 0xf);
c = getByte();
}
return flag? n: -n;
}
}
}
快速幂
#5 分考场
时间限制: 1.0s 内存限制: 256.0MB 本题满分: 79 分
问题描述
n个人参加某项特殊考试。
为了公平，要求任何两个认识的人不能分在同一个考场。
求是少需要分几个考场才能满足条件。
输入格式
第一行，一个整数n(1<n<100)，表示参加考试的人数。
第二行，一个整数m，表示接下来有m行数据
以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。
输出格式
一行一个整数，表示最少分几个考场。
测试样例1
Input：
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
Output：
4
测试样例2
Input：
5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Output：
5
code：
import java.io.IOException;
import java.io.InputStream;
public class Main {
static int room[];
static boolean[][] link;
static int res = 0x3F3F3F3F, n;
public static void main(String[] args) {
InputReader in = new InputReader(System.in);
n = in.nextInt();
room = new int[n + 1];
int m = in.nextInt(), v ,w;
link = new boolean[n + 1][n + 1];
while (m-- > 0) {
v = in.nextInt();
w = in.nextInt();
link[v][w] = link[w][v] = true;
}
dfs(1, 0);
System.out.print(res);
}
static void dfs(int cur, int k) {
if (k >= res) return;
if (cur > n) res = res < k? res: k;
else {
agent: for (int i = 0; i < k; i++) {
for (int j = 1; j < cur; j++)
if (link[cur][j] && room[j] == i)
continue agent;
room[cur] = i;
dfs(cur + 1, k);
}
dfs(cur + 1, (room[cur] = k) + 1);
}
}
static class InputReader {
private InputStream in;
private int next, len;
private byte[] buff;
InputReader(InputStream in) { this(in, 8192); }
InputReader(InputStream in, int buffSize) {
this.buff = new byte[buffSize];
this.next = this.len = 0;
this.in = in;
}
private int getByte() {
if (next >= len)
try {
next = 0;
len = in.read(buff);
if (len == -1) return -1;
} catch (IOException e) {
e.fillInStackTrace();
}
return buff[next++];
}
private int split() {
int c = getByte();
while (c <= 32 || c == 127) c = getByte();
return c;
}
public int nextInt() {
int n = 0, c = split();
boolean flag = true;
if (c == '-') {
c = getByte();
flag = false;
}
while (c >= '0'&& c <='9') {
n = n * 10 + (c & 0xf);
c = getByte();
}
return flag? n: -n;
}
}
}
#6 合根植物
时间限制: 2.0s 内存限制: 256.0MB 本题满分: 105 分
问题描述
w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
输入格式
第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。
接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)
接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。
格子的编号一行一行，从上到下，从左到右编号。
比如：5 * 4 的小格子，编号：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
输出格式
输出一个整数，表示合根植物的个数
测试样例1
Input：
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
Output：
5
code：
import java.io.IOException;
import java.io.InputStream;
import java.util.HashSet;
import java.util.Set;
public class Main {
static int[] link;
public static void main(String[] args) {
InputReader in = new InputReader(System.in);
int n = in.nextInt(), m = in.nextInt(), k = in.nextInt();
int size = n * m + 1, v, w;
link = new int[size];
for (int i = 1; i < size; i++)
link[i] = i;
while (k-- > 0) {
v = find(in.nextInt());
w = find(in.nextInt());
if (v != w) link[v] = w;
}
Set<Integer> set = new HashSet();
for (int i = 1; i < size; i++)
set.add(find(i));
System.out.print(set.size());
}
static int find(int x) { return x == link[x]? x: (link[x] = find(link[x])); }
static class InputReader {
private InputStream in;
private int next, len;
private byte[] buff;
InputReader(InputStream in) { this(in, 8192); }
InputReader(InputStream in, int buffSize) {
this.buff = new byte[buffSize];
this.next = this.len = 0;
this.in = in;
}
private int getByte() {
if (next >= len)
try {
next = 0;
len = in.read(buff);
if (len == -1) return -1;
} catch (IOException e) {
e.fillInStackTrace();
}
return buff[next++];
}
private int split() {
int c = getByte();
while (c <= 32 || c == 127) c = getByte();
return c;
}
public int nextInt() {
int n = 0, c = split();
boolean flag = true;
if (c == '-') {
c = getByte();
flag = false;
}
while (c >= '0'&& c <='9') {
n = n * 10 + (c & 0xf);
c = getByte();
}
return flag? n: -n;
}
}
}
简单的并查集，作为一道压轴题显然是不够看的
综合来看17年题目是最简单的
希望今年能像该年一样运气好
更多推荐
0
0- 0
已为社区贡献8条内容
所有评论(0)