---

希望决赛题目不搞我

先挂

---

#1 三角形面积

本题满分: 13分

---

问题描述

已知三角形三个顶点在直角坐标系下的坐标分别为：
(2.3, 2.5)
(6.4, 3.1)
(5.1, 7.2)

求该三角形的面积。

---

答案提交

注意，要提交的是一个小数形式表示的浮点数。
要求精确到小数后3位，如不足3位，需要补零。

---

8.795

---

calcCode：

public class Test {
	
	public static void main(String[] args) {
		Point X = new Point(2.3, 2.5),
			  Y = new Point(6.4, 3.1),
			  Z = new Point(5.1, 7.2);
		double a = Point.distance(X, Y),
			   b = Point.distance(X, Z),
			   c = Point.distance(Y, Z),
			   p = (a + b + c) / 2;
		System.out.printf("%.3f\n", Math.sqrt(p * (p - a) * (p - b) * (p - c)));
	}
	
	static class Point {
		
		double a, b;
		
		Point(double a, double b) {
			this.a = a;
			this.b = b;
		}
		
		static double distance(Point a, Point b) { return Math.sqrt((a.a - b.a) * (a.a - b.a) + (a.b - b.b) * (a.b - b.b)); }
	}
}

海伦公式

---

#2 最大乘积

本题满分: 39分

---

问题描述

把 1~9 这9个数字分成两组，中间插入乘号，
有的时候，它们的乘积也只包含1~9这9个数字，而且每个数字只出现1次。

比如：
984672 * 351 = 345619872
98751 * 3462 = 341875962
9 * 87146325 = 784316925
…

符合这种规律的算式还有很多，请你计算在所有这些算式中，乘积最大是多少？

---

答案提交

注意，需要提交的是一个整数，表示那个最大的积，不要填写任何多余的内容。
（只提交乘积，不要提交整个算式）

---

839542176

---

calcCode：

public class Test {

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        int add = 0, mul = 1, max = 0;
        for (int i = 0; i < 9; i++) {
            add += arr[i];
            mul *= arr[i];
        }
        do
            for (int i = 0, l = 0, r, v, a, m; i < 9; i++) {
                l = l * 10 + arr[i];
                r = 0;
                for (int j = i + 1; j < 9; j++) r = r * 10 + arr[j];
                v = l * r;
                if (v > max) {
                    m = 1; a = 0;
                    do {
                        a += v % 10;
                        m *= v % 10;
                    } while ((v /= 10) > 0);
                    if (m == mul && a == add) max = l * r;
                }
            }
        while (next(arr));
        System.out.print(max);
    }

    static boolean next(int[] a) {
        int i = a.length - 2;
        while (i >= 0 && a[i] > a[i + 1]) i--;
        if (i < 0) return false;
        int j = i + 1, t = a[i];
        while (j < a.length && a[j] > t) j++;
        a[i] = a[j - 1];
        a[j - 1] = t;
        java.util.Arrays.sort(a, i + 1, a.length);
        return true;
    }
}

声明一下，少了一步效验

不优雅，但实用

---

#3 全排列

本题满分: 27分

---

问题描述

对于某个串，比如：“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; j <i; j++) data[j] = data[j+1];

---

#4 整理玩具

时间限制: 1.0s 内存限制: 256.0MB 本题满分: 45 分

---

问题描述

小明有一套玩具，一共包含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代表是否符合小明的要求。

---

测试样例₁

Input：
3
3 5
00022
00033
44444
3 5
11122
11122
33311
2 5
01234
56789

Output：
YES
NO
YES

---

code：

import java.io.InputStream;
import java.io.IOException;
import java.io.PrintWriter;

public class Main {

    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int[][] map = new int[10][10];
        int[] cnt = new int[128];
        int c = in.nextInt();
        while (c-- > 0) {
            for (int i = '0'; i <= '9'; i++) cnt[i] = 0;
            int n = in.nextInt(), m = in.nextInt();
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    cnt[map[i][j] = in.nextChar()]++;
            boolean flag = true;
            agent: for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++) {
                    if (map[i][j] == 0) continue;
                    int col = i + 1, row = j + 1;
                    int val = map[i][j];
                    while (col < n && map[col][j] == val) col++;
                    while (row < m && map[i][row] == val) row++;
                    if ((col - i) * (row - j) != cnt[val]) {
                        flag = false;
                        break agent;
                    }
                    for (int k = i; k < col; k++)
                        for (int g = j; g < row; g++)
                            if (map[k][g] != val) {
                                flag = false;
                                break agent;
                            } else map[k][g] = 0;
                }
            out.println(flag? "YES": "NO");
        }
        out.close();
    }

    static class InputReader {

        InputStream in;
        int next, len;
        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;
        }

        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++];
        }

        int nextChar() {
            int c = getByte();
            while (c <= 32 || c == 127)
                if (-1 == (c = getByte())) return -1;
            return c;
        }

        int nextInt() {
            int n = 0, c = nextChar();
            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 本题满分: 71 分

---

问题描述

小明负责维护公司一个奇怪的项目。这个项目的代码一直在不断分支(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的祖先版本。

---

输出格式

对于每个询问，输出YES或NO代表x是否是y的祖先。

---

测试样例₁

Input：
6 5
1 2
1 3
2 5
3 6
3 4
1 1
1 4
2 6
5 2
6 4

Output：
YES
YES
NO
NO
NO

---

评测用例规模与约定

对于30%的数据，1 <= N <= 1000 1 <= Q <= 1000
对于100%的数据，1 <= N <= 100000 1 <= Q <= 100000

---

code：

import java.io.InputStream;
import java.io.IOException;
import java.io.PrintWriter;

public class Main {
	
	static int[] link;
	
	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int N = in.nextInt(), Q = in.nextInt(), u, v, w;
		link = new int[N + 1];
		while (N-- > 1) {
			u = in.nextInt();
			v = in.nextInt();
			link[v] = u;
		}
		while (Q-- > 0) {
			v = in.nextInt();
			w = in.nextInt();
			if (v == 1)    w = 1;
			else while (w != 1) {
				if (w == v) break;
				w = link[w];
			}
			out.println(w == v? "YES": "NO");
		}
		out.close();
	}
	
	static class InputReader {
		
		InputStream in;
		int next, len;
		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;
		}
		
		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++];
		}
		
		int nextChar() {
			int c = getByte();
			while (c <= 32 || c == 127)
				if (-1 == (c = getByte())) return -1;
			return c;
		}
		
		int nextInt() {
			int n = 0, c = nextChar();
			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 防御力

时间限制: 1.0s 内存限制: 256.0MB 本题满分: 105 分

---

问题描述

小明最近在玩一款游戏。对游戏中的防御力很感兴趣。
我们认为直接影响防御的参数为“防御性能”，记作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。

---

测试样例₁

Input：
1 2
4
2 8
101

Output：
B2
A1
B1
E

Explanation：
操作过程如下：
操作  d         A              B
初始  0	        1              1
B2    2         4              9
A1    3	        8              27
B1   log3(29)   2^(log3(29))   29

可以证明，这个值是最大的。

测试样例₂

Input：
3 0
7 11 13

000

Output：
A1
A2
A3
E

Explanation：
可见无论用什么顺序，A最后总为32，即d总为5，B总为243。 

---

评测用例规模与约定

对于20%的数据，字符串长度<=10000；
对于70%的数据，字符串长度<=200000；
对于100%的数据，字符串长度<=2000000，输入的每个增加值不超过2³⁰。

---

code：

import java.io.InputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;

public class Main {

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n1 = in.nextInt(), n2 = in.nextInt();
        Props[] A = new Props[n1];
        Props[] B = new Props[n2];
        for (int i = 0; i < n1; i++)
            A[i] = new Props(i, in.nextInt());
        for (int i = 0; i < n2; i++)
            B[i] = new Props(i, in.nextInt());
        Arrays.sort(A, new Comparator<Props>() {
            public int compare(Props arg0, Props arg1) {
                return arg0.val == arg1.val? (arg0.id - arg1.id) : (arg0.val - arg1.val);
            }
        });
        Arrays.sort(B, new Comparator<Props>() {
            public int compare(Props arg0, Props arg1) {
                return arg1.val == arg0.val? (arg0.id - arg1.id) : (arg1.val - arg0.val);
            }
        });
        Comparator idcmp = new Comparator<Props>() {
            public int compare(Props arg0, Props arg1) {
                return arg0.id - arg1.id;
            }
        };
        String line = in.nextLine().trim();
        for (int i = 0, a = 0, b = 0, c, high = line.length(); i < high;) {
            int start = i;
            int end = i + 1;
            char key = line.charAt(start);
            while(end < high && line.charAt(end) == key) end++;
            i = end;
            if (end - start == 1) {
                if (key == '0') out.println("A" + (A[a++].id + 1));
                else			out.println("B" + (B[b++].id + 1));
            } else {
                if (key == '0') {
                    Arrays.sort(A, a, c = a + end - start, idcmp);
                    while (a < c)
                        out.println("A" + (A[a++].id + 1));
                } else {
                    Arrays.sort(B, b, c = b + end - start, idcmp);
                    while (b < c)
                        out.println("B" + (B[b++].id + 1));
                }
            }
        }
        out.println("E");
        out.close();
    }

    static class Props {

        int id, val;

        Props(int id, int val) {
            this.id = id;
            this.val = val;
        }
    }

    static class InputReader {

        InputStream in;
        int next, len;
        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;
        }

        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++];
        }

        int getChar() {
            int c = getByte();
            while (c != -1 && (c <= 32 || c == 127)) c = getByte();
            return c;
        }

        int nextInt() {
            int n = 0, c = getChar();
            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;
        }

        String nextLine() {
            StringBuilder res = new StringBuilder();
            int c = getChar();
            while (c != '\n') {
                res.appendCodePoint(c);
                c = getByte();
            }
            return res.toString();
        }
    }
}

---

1. 第几天

2000年的1月1日，是那一年的第1天。
那么，2000年的5月4日，是那一年的第几天？
注意：需要提交的是一个整数，不要填写任何多余内容。

2. 方格计数

如图p1.png所示，在二维平面上有无数个1x1的小方格。

我们以某个小方格的一个顶点为圆心画一个半径为1000的圆。
你能计算出这个圆里有多少个完整的小方格吗？

3. 复数幂

设i为虚数单位。对于任意正整数n，(2+3i)^n 的实部和虚部都是整数。
求 (2+3i)^123456 等于多少？ 即(2+3i)的123456次幂，这个数字很大，要求精确表示。

答案写成 “实部±虚部i” 的形式，实部和虚部都是整数（不能用科学计数法表示），中间任何地方都不加空格，实部为正时前面不加正号。(2+3i)^2 写成: -5+12i，
(2+3i)^5 的写成: 122-597i

4. 测试次数

x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。

x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。

如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。
特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。
如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n

为了减少测试次数，从每个厂家抽样3部手机参加测试。

某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

请填写这个最多测试次数。

5. 快速排序

以下代码可以从数组a[]中找出第k小的元素。

它使用了类似快速排序中的分治算法，期望时间复杂度是O(N)的。

请仔细阅读分析源码，填写划线部分缺失的内容。

#include <stdio.h>

int quick_select(int a[], int l, int r, int k) {
	int p = rand() % (r - l + 1) + l;
	int x = a[p];
	{int t = a[p]; a[p] = a[r]; a[r] = t;}
	int i = l, j = r;
	while(i < j) {
		while(i < j && a[i] < x) i++;
		if(i < j) {
			a[j] = a[i];
			j--;
		}
		while(i < j && a[j] > x) j--;
		if(i < j) {
			a[i] = a[j];
			i++;
		}
	}
	a[i] = x;
	p = i;
	if(i - l + 1 == k) return a[i];
	if(i - l + 1 < k) return quick_select( _____________________________ ); //填空
	else return quick_select(a, l, i - 1, k);
}
	
int main()
{
	int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};
	printf("%d\n", quick_select(a, 0, 14, 5));
	return 0;
}

注意：只填写划线部分缺少的代码，不要抄写已经存在的代码或符号。

6. 递增三元组

给定三个整数数组

A = [A1, A2, … AN],

B = [B1, B2, … BN],

C = [C1, C2, … CN]，

请你统计有多少个三元组(i, j, k) 满足：

1. 1 <= i, j, k <= N`
`2. Ai < Bj < Ck
【输入格式】 
第一行包含一个整数N。
第二行包含N个整数A1, A2, ... AN。
第三行包含N个整数B1, B2, ... BN。
第四行包含N个整数C1, C2, ... CN。

对于30%的数据，1 <= N <= 100  
对于60%的数据，1 <= N <= 1000 
对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000 

【输出格式】
一个整数表示答案
123456789101112
【样例输入】
3
1 1 1
2 2 2
3 3 3

【样例输出】
27 

7. 螺旋折线

如图p1.png所示的螺旋折线经过平面上所有整点恰好一次。

对于整点(X, Y)，我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。

例如dis(0, 1)=3, dis(-2, -1)=9

给出整点坐标(X, Y)，你能计算出dis(X, Y)吗？

【输入格式】
X和Y  

对于40%的数据，-1000 <= X, Y <= 1000  
对于70%的数据，-100000 <= X， Y <= 100000  
对于100%的数据, -1000000000 <= X, Y <= 1000000000  

【输出格式】
输出dis(X, Y)  
123456789
【样例输入】
0 1

【样例输出】
3

8. 日志统计

小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有N行。其中每一行的格式是：

ts id

表示在ts时刻编号id的帖子收到一个"赞"。

现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，小明就认为这个帖子曾是"热帖"。

具体来说，如果存在某个时刻T满足该帖在[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞，该帖就曾是"热帖"。

给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。

【输入格式】
第一行包含三个整数N、D和K。  
以下N行每行一条日志，包含两个整数ts和id。  

对于50%的数据，1 <= K <= N <= 1000  
对于100%的数据，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000  

【输出格式】
按从小到大的顺序输出热帖id。每个id一行。  
123456789
【输入样例】
7 10 2  
0 1  
0 10    
10 10  
10 1  
9 1
100 3  
100 3  

【输出样例】
1  
3  

9. 全球变暖

你有一张某海域NxN像素的照片，".“表示海洋、”#"表示陆地，如下所示：

…
.##…
.##…
…##.
…####.
…###.
…

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

…
…
…
…
…#…
…
…

####请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

【输入格式】
第一行包含一个整数N。  (1 <= N <= 1000)  
以下N行N列代表一张海域照片。  

照片保证第1行、第1列、第N行、第N列的像素都是海洋。  

【输出格式】
一个整数表示答案。
12345678
【输入样例】
7 
.......
.##....
.##....
....##.
..####.
...###.
.......  

【输出样例】
1  

10. 乘积最大

给定N个整数A1, A2, … AN。请你从中选出K个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以1000000009的余数。

注意，如果X<0， 我们定义X除以1000000009的余数是负(-X)除以1000000009的余数。
即：0-((0-x) % 1000000009)

【输出格式】
一个整数，表示答案。
12345678910
【输入样例】
5 3 
-100000   
-10000   
2   
100000  
10000  

【输出样例】
999100009
12345678910
再例如：
【输入样例】
5 3 
-100000   
-100000   
-2   
-100000  
-100000

【输出样例】
-999999829

这是第一次参加蓝桥杯，应该也是最后一次。我参加的B组 JAVA，整体感觉还行吧，只是比赛的时候出了点小意外。本来是下午1点钟结束的，因为提前了两分钟开始，然后到12点五十几的时候就交不了了，导致一个大题白白没交上去，当时心里有点炸。不过也没什么，蓝桥杯这种比赛，就当是玩一下吧。然后就说说题目吧，水平有限，错了见谅。

第一题：

标题：第几天

2000年的1月1日，是那一年的第1天。

那么，2000年的5月4日，是那一年的第几天？

注意：需要提交的是一个整数，不要填写任何多余内容。

这种题...直接口算吧。

我的答案：125

 

第二题 ：

标题：方格计数

如图p1.png所示，在二维平面上有无数个1x1的小方格。




我们以某个小方格的一个顶点为圆心画一个半径为1000的圆。
你能计算出这个圆里有多少个完整的小方格吗？ 

注意：需要提交的是一个整数，不要填写任何多余内容。

比赛的时候以为找到了规律：如果半径为R的话，那么所圈住的小正方形应该是[2 *(R-1)]^2。试了1，2，3都满足，然后就没多想，毕竟才第二个题目。

比赛完了才发现这式子有问题，R>根号2*(R-1)只有在R<4时才成立，唉，当时也没仔细看，就想当然的填了上去。写了个代码跑了一下，发现果然错了，还是太年轻啊...

import java.util.Scanner;

public class 方格计数 {
	static int N = 10000; // 方格图的大小, 10000够大了
	static int X = 5000, Y = 5000; // 圆心坐标
	static double[] l = new double[N]; 
	static double[] r = new double[N];
	static int R, ans = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		R = sc.nextInt();
		for (int i = Y - R; i <= Y + R; i++) {
			l[i] = X - Math.sqrt(R * R - (Y - i) * (Y - i));
			r[i] = Math.min(N, (X << 1) - l[i]);
			if (l[i] < 0) {
				l[i] = 0;
			}
		}
		for (int i = Y - R; i <= Y - 1; i++) {
			int ll = (int) Math.ceil(l[i]), rr = (int) Math.floor(r[i]); 
			ans += rr - ll;
		}
		for (int i = Y; i <= Y + R - 1; i++) {
			int ll = (int) Math.ceil(l[i + 1]), rr = (int) Math.floor(r[i + 1]);
			ans += rr - ll;
		}
		System.out.println(ans);
	}
}

 

我的答案： 3137548

 

 

第三题：

标题：复数幂
设i为虚数单位。对于任意正整数n，(2+3i)^n 的实部和虚部都是整数。
求 (2+3i)^123456 等于多少？ 即(2+3i)的123456次幂，这个数字很大，要求精确表示。
答案写成 "实部±虚部i" 的形式，实部和虚部都是整数（不能用科学计数法表示），中间任何地方都不加空格，实部为正时前面不加正号。(2+3i)^2 写成: -5+12i，
(2+3i)^5 的写成: 122-597i

注意：需要提交的是一个很庞大的复数，不要填写任何多余内容。

这题真的是不想吐槽了，用java大数加快速幂做的，应该是做对了，但是一开始eclipse控制台没显示出来，以为是大数爆了。

代码：

import java.math.BigInteger;

public class 复数幂 {
	public static void main(String[] args) {
		Complex cmp = new Complex(BigInteger.valueOf(2), BigInteger.valueOf(3));
		System.out.println(quickPow(cmp, 123456).toString());
	}
	
	private static Complex quickPow(Complex cmp, int n) {
		if (n == 0) {
			return new Complex(BigInteger.valueOf(1), BigInteger.valueOf(0));
		}
		Complex temp = quickPow(cmp, n / 2);
		temp.multiply(temp);
		if (n % 2 != 0) {
			temp.multiply(cmp);
		}
		return temp;
	}
}

class Complex {
	BigInteger a;  // 实部
	BigInteger b;  // 虚部
	
	public Complex(BigInteger a, BigInteger b) {
		this.a = a;
		this.b = b;
	}
	
	public void multiply(Complex cm) {
		BigInteger tempa = a.multiply(cm.a).subtract(b.multiply(cm.b));
		BigInteger tempb = a.multiply(cm.b).add(b.multiply(cm.a));
		a = tempa;
		b = tempb;
	}
	
	@Override
	public String toString() {
		String aStr = "" + a;
		String bStr = b + "i";
		if (b.compareTo(BigInteger.valueOf(0)) > 0) {
			bStr = "+" + bStr;
		} else if (b.compareTo(BigInteger.valueOf(0)) == 0) {
			bStr = "";
		}
		return aStr + bStr;
	}
}

eclipse控制台输出的结果是--i，不知道是什么鬼，比赛完了才知道把这个--i是一个超长的字符串，所以直接把eclipse输出的--i粘贴到记事本就可以看到结果了。结果就不贴了，太长了，刚刚粘贴的时候浏览器都卡了。反正思路应该不难，如果是c++的话，手写大数应该也还好，然后快速幂就不说了，算法基础。

看一下最右边的滚动滑轮感受一下数字规模。。。

 

第四题：

标题：测试次数
x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。
x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。
如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。
特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。
如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n
为了减少测试次数，从每个厂家抽样3部手机参加测试。
某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？
请填写这个最多测试次数。

注意：需要填写的是一个整数，不要填写任何多余内容。

其实这题在之前碰到过一个差不多的，不过当时没有深究，之前的好像是两个鸡蛋，100层，问最坏情况下最少几次？这个是最坏情况最多几次，我不知道是不是我多想了，比赛的时候二分答案，错了。。。比赛完结合之前的题目又想了一下，递推了一下，算出来19。

我的答案：19

代码：

public class 摔手机 {
	public static void main(String[] args) {
		System.out.println(DroppingPhone(3, 1000));
	}

	private static long DroppingPhone(long phone, long floors) {
		long times = 1;
		while (DroppingMax(phone, times) < floors) {
			++times;
		}
		return times;
	}

	private static long DroppingMax(long phone, long times) {
		if (phone == 1) {
			return times;
		}

		if (phone >= times) {
			return (long) Math.pow(2, times) - 1;
		}

		return DroppingMax(phone, times - 1) + DroppingMax(phone - 1, times - 1) + 1;
	}
}

 

第五题：

标题：快速排序
以下代码可以从数组a[]中找出第k小的元素。  
它使用了类似快速排序中的分治算法，期望时间复杂度是O(N)的。

请仔细阅读分析源码，填写划线部分缺失的内容。

import java.util.Random;
public class Main{
	public static int quickSelect(int a[], int l, int r, int k) {
		Random rand = new Random();
		int p = rand.nextInt(r - l + 1) + l;
		int x = a[p];
		int tmp = a[p]; a[p] = a[r]; a[r] = tmp;
		int i = l, j = r;
		while(i < j) {
                	while(i < j && a[i] < x) i++;
                	if(i < j) {
                        	a[j] = a[i];
                        	j--;
                	}
                	while(i < j && a[j] > x) j--;
                	if(i < j) {
                        	a[i] = a[j];
                        	i++;
                	}
        	}
        	a[i] = x;
        	p = i;
        	if(i - l + 1 == k) return a[i];
        	if(i - l + 1 < k) return quickSelect( _________________________________ ); //填空
        	else return quickSelect(a, l, i - 1, k);	
	}
	public static void main(String args[]) {
		int [] a = {1, 4, 2, 8, 5, 7};
		System.out.println(quickSelect(a, 0, 5, 4));
	}
}

注意：只提交划线部分缺少的代码，不要抄写任何已经存在的代码或符号。

这题也不是什么新题，利用快排的partition思想进行"选择"，是解决这类问题的高效方法，可以把复杂度从O（nlongn）（直接排序求a[k - 1]）降到O（n）（利用快排分组时左边刚好k-1个元素）。注意题目要求是O(n)，这题如果只求运行正确有几种写法，如果不注意直接写partition 的分治可能还是O（nlogn）。

我的答案：a, i + 1, r, k - i + l - 1  

 

-----------------------------------分割线-------------------------------------------

编程题就懒得去码代码了，不太喜欢重复性的劳动，就大致说一下我的思路，菜鸡一只，错了请见谅。。。

 

第六题：

标题：递增三元组
给定三个整数数组
A = [A1, A2, ... AN], 
B = [B1, B2, ... BN], 
C = [C1, C2, ... CN]，
请你统计有多少个三元组(i, j, k) 满足：
1. 1 <= i, j, k <= N  
2. Ai < Bj < Ck  

【输入格式】
第一行包含一个整数N。
第二行包含N个整数A1, A2, ... AN。
第三行包含N个整数B1, B2, ... BN。
第四行包含N个整数C1, C2, ... CN。
对于30%的数据，1 <= N <= 100  
对于60%的数据，1 <= N <= 1000 
对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000 
【输出格式】
一个整数表示答案


【输入样例】
3
1 1 1
2 2 2
3 3 3

【输出样例】
27 

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

这道题的话，比赛的时候为了节省时间直接O(N^3)暴力求解，虽然知道肯定不行，但想着花几分钟拿一部分分还是很划算的，之后有时间再优化，结果做着做着没时间了。下来又想了一下，可以先排序，然后以B数组为标杆，对于B的每一个元素Bi，统计A中比Bi小的元素，C中比Bi大的元素，然后相乘，最后把乘积累加起来。也不知道蓝桥的判题机怎么样，O(nlogn)对于1e5的数据规模，勉勉强强能过。

第七题

标题：螺旋折线


如图p1.pgn所示的螺旋折线经过平面上所有整点恰好一次。  
对于整点(X, Y)，我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。  

例如dis(0, 1)=3, dis(-2, -1)=9  

给出整点坐标(X, Y)，你能计算出dis(X, Y)吗？

 

【输入格式】

 

X和Y 

对于40%的数据，-1000 <= X, Y <= 1000  
对于70%的数据，-100000 <= X， Y <= 100000  
对于100%的数据, -1000000000 <= X, Y <= 1000000000  

【输出格式】
输出dis(X, Y)  

【输入样例】
0 1

【输出样例】

 

3

资源约定：

 

峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

 

 

这题考察的不是算法吧，就是思维，方法应该挺多的。我用的方法是把螺旋折线转变成一个个的同心正方形，像下面这样，

注意转化关系，转化之后就很标准了，非常好算。实在不行，分象限讨论，细心一点，肯定能做出来。

第八题

标题：日志统计
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有N行。其中每一行的格式是：
ts id  
表示在ts时刻编号id的帖子收到一个"赞"。  
现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，小明就认为这个帖子曾是"热帖"。  
具体来说，如果存在某个时刻T满足该帖在[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞，该帖就曾是"热帖"。  
给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。  

 

【输入格式】

 

第一行包含三个整数N、D和K。  
以下N行每行一条日志，包含两个整数ts和id。  

对于50%的数据，1 <= K <= N <= 1000  
对于100%的数据，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000  

【输出格式】
按从小到大的顺序输出热帖id。每个id一行。  

 

 

【输入样例】

 

7 10 2  
0 1  
0 10    
10 10  
10 1  
9 1
100 3  
100 3  

【输出样例】
1  
3  
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

 

这题用的优先队列加hash（或者直接写一个二维的排序也行吧），感觉是没问题，造了几组数据都过了，然而前面说到有一题最后到时间没交，就是这题。。。这题计算点赞量，应该是以每一个点赞时间Ti为为起点，计算[Ti,D)的点赞数（i = 1, 2, 3, ..., n），然后求最大值与K比较。

 

第九题

标题：全球变暖

你有一张某海域NxN像素的照片，"."表示海洋、"#"表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。  
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。  
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。  
【输入格式】

第一行包含一个整数N。  (1 <= N <= 1000)  

以下N行N列代表一张海域照片。  

 

照片保证第1行、第1列、第N行、第N列的像素都是海洋。  
【输出格式】
一个整数表示答案。
【输入样例】
7 
.......
.##....
.##....
....##.
..####.
...###.
.......  
【输出样例】
1  
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

 

这题也是比较简单，几乎就是裸的dfs求联通分量，在求联通分量的时候做个标记，判断这个联通分量（岛屿）中是否存在不临海的陆地，存在的话，这样的联通分量（岛屿）才不会完全消失。

第十题

标题：堆的计数
我们知道包含N个元素的堆可以看成是一棵包含N个节点的完全二叉树。  
每个节点有一个权值。对于小根堆来说，父节点的权值一定小于其子节点的权值。  
假设N个节点的权值分别是1~N，你能求出一共有多少种不同的小根堆吗？  
例如对于N=4有如下3种：

    1
   / \
  2   3
 /
4

    1
   / \
  3   2
 /
4

    1
   / \
  2   4
 /
3

由于数量可能超过整型范围，你只需要输出结果除以1000000009的余数。  
【输入格式】
一个整数N。  
对于40%的数据，1 <= N <= 1000  
对于70%的数据，1 <= N <= 10000  
对于100%的数据，1 <= N <= 100000
【输出格式】
一个整数表示答案。  
【输入样例】
4  
【输出样例】
3
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

这题之前是在哪看到过，（好像是阿里）的面试题。比赛的时候就这道题没做出来，求个组合数就求炸了，乘法逆元想不起来了。这题应该是组合数加DP，之后有时间再看看吧。

 

总结：其实从上一届蓝桥杯开始，题目难度就慢慢上升了。今年的题目除了第一题，之后每一题想拿到满分都不是那么的容易，质量还行吧，摘掉了"暴力杯"的帽子。不过话说回来，蓝桥杯这种题目跟ACM，NOI，IOI这种级别的比赛，完全就是过家家了，蓝桥杯适合我这种菜鸡玩一玩，拿个奖还可以加点分，也挺好哈。

很少在csdn上写东西，也是第一次写这么多。emmm，就先说到这吧，蓝桥杯，再见了（应该不会再见了）。。。

 

-------4月9日更新----------

今天结果出来了，竟然水了个省一，又可以去水一下国赛了...  ps：其实是想着终于能公费去北京旅游了