写在前面：
第8~12届的题目请见 第一篇
第七届
A. 煤球数目
public class Main {
public static void main(String[] args) {
int n = 100;
long now = 1, sum = 1;
for (int i = 2; i <= n; i++)
{
now += i;
sum += now;
}
System.out.println(sum);
}
}
B. 生日蜡烛
public class Main {
public static void main(String[] args) {
for (int i = 1; i <= 100; i++)
{
int sum = 0;
for (int j = i; j <= 100; j++)
{
sum += j;
if(sum == 236)
{
System.out.println(i);
return;
}
if(sum > 236)
{
break;
}
}
}
}
}
C. 凑算式
和带分数差不多，主要区别是这五个数里，每个数的位数都固定了。
一开始的写法，在check里加了有关位数的判断，比较麻烦。
public class Main {
static int N = 10;
static int n, res;
static boolean[] used = new boolean[N];
static int[] st = new int[N];
static int get(int l, int r)
{
int m = 0;
for (int i = l; i <= r; i++)
{
m = m * 10 + st[i];
}
return m;
}
static boolean check(int a, int b, int c, int d, int e)
{
if(a*c*e + b*e + c*d == c*e*n)
{
if(String.valueOf(a).length() == 1 &&
String.valueOf(b).length() == 1 &&
String.valueOf(c).length() == 1 &&
String.valueOf(d).length() == 3 &&
String.valueOf(e).length() == 3)
return true;
}
return false;
}
static void dfs(int u)
{
if(u >= N)
{
for (int i = 1; i <= 5; i++)
for (int j = i + 1; j <= 6; j++)
for (int k = j + 1; k <= 7; k++)
for (int l = k + 1; l <= 8; l++)
{
int a = get(1, i);
int b = get(i + 1, j);
int c = get(j + 1, k);
int d = get(k + 1, l);
int e = get(l + 1, 9);
if(check(a, b, c, d, e)) res++;
}
return;
}
for (int i = 1; i < N; i++)
{
if(!used[i])
{
st[u] = i;
used[i] = true;
dfs(u + 1);
used[i] = false;
st[u] = 0;
}
}
}
public static void main(String[] args) {
n = 10;
dfs(1);
System.out.println(res);
}
}
后来想了想，直接取数组就行了啊。
public class Main {
static int N = 10;
static int n, res;
static boolean[] used = new boolean[N];
static int[] st = new int[N];
static int get(int l, int r)
{
int m = 0;
for (int i = l; i <= r; i++)
{
m = m * 10 + st[i];
}
return m;
}
static boolean check(int a, int b, int c, int d, int e)
{
if(a*c*e + b*e + c*d == c*e*n) return true;
return false;
}
static void dfs(int u)
{
if(u >= N)
{
int a = get(1,1);
int b = get(2,2);
int c = get(3,3);
int d = get(4,6);
int e = get(7,9);
if(check(a, b, c, d, e)) res++;
return;
}
for (int i = 1; i < N; i++)
{
if(!used[i])
{
st[u] = i;
used[i] = true;
dfs(u + 1);
used[i] = false;
st[u] = 0;
}
}
}
public static void main(String[] args) {
n = 10;
dfs(1);
System.out.println(res);
}
}
D、E都是填空题，不写了
F. 方格填数
注意boolean数组没必要弄重复
还有，看清题干，res++要放对位置。
import java.util.Arrays;
public class Main {
static int N = 20;
static int n = 10;
static long res;
static boolean[][] g = new boolean[N][N]; //是否相邻
static int[] st = new int[N];
static boolean[] used = new boolean[N];
static void dfs(int u)
{
if(u > n)
{
boolean flag = true;
for (int i = 1; i <= 10; i++)
for (int j = i + 1; j <= 10; j++)
{
if(g[i][j]) //所有相邻的情况
{
if(Math.abs(st[i] - st[j]) == 1)
{
flag = false;
break;
}
}
}
if(flag) res++;
return;
}
for (int i = 0; i <= 9; i++)
{
if(!used[i])
{
st[u] = i;
used[i] = true;
dfs(u + 1);
used[i] = false;
st[u] = -1;
}
}
}
public static void main(String[] args) {
Arrays.fill(st, -1);
/*
* g[1][2] = g[1][4] = g[1][5] = g[1][6] = true; g[2][1] = g[2][3] = g[2][5] =
* g[2][6] = g[2][7] = true; g[3][2] = g[3][6] = g[3][7] = true; g[4][1] =
* g[4][5] = g[4][8] = g[4][9] = true; g[5][1] = g[5][2] = g[5][4] = g[5][6] =
* g[5][8] = g[5][9] = g[5][10] = true; g[6][1] = g[6][2] = g[6][3] = g[6][5] =
* g[6][7] = g[6][9] = g[6][10] = true; g[7][2] = g[7][3] = g[7][6] = g[7][10] =
* true; g[8][4] = g[8][5] = g[8][9] = true; g[9][4] = g[9][5] = g[9][6] =
* g[9][8] = g[9][10] = true; g[10][5] = g[10][6] = g[10][7] = g[10][9] = true;
*/
g[1][2] = g[1][4] = g[1][5] = g[1][6] = true;
g[2][3] = g[2][5] = g[2][6] = g[2][7] = true;
g[3][6] = g[3][7] = true;
g[4][5] = g[4][8] = g[4][9] = true;
g[5][6] = g[5][8] = g[5][9] = g[5][10] = true;
g[6][7] = g[6][9] = g[6][10] = true;
g[7][10] = true;
g[8][9] = true;
g[9][8] = g[9][10] = true;
dfs(1);
System.out.println(res);
}
}
G. 剪邮票
和七段码有点像
import java.util.Arrays;
public class Main {
static int N = 20;
static int n = 12;
static long res;
static boolean[][] g = new boolean[N][N]; //是否相邻
static int[] st = new int[N];
static int[] p = new int[N];
static boolean[] used = new boolean[N];
static int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
static void dfs(int u)
{
if(u > 5)
{
for (int i = 1; i <= 12; i++) p[i] = i;
for (int i = 1; i <= 5; i++)
for (int j = 1; j <= 5; j++)
{
int max = Math.max(st[i], st[j]);
int min = Math.min(st[i], st[j]);
if(g[min][max])
{
int a = find(min), b = find(max);
if(a != b) p[a] = b;
}
}
int t = 0;
for (int i = 1; i <= 5; i++)
{
if(p[st[i]] == st[i]) t++;
if(t > 1) return;
}
if(t == 1)
{
// for (int i = 1; i <= 5; i++) System.out.print(st[i]+" ");
// System.out.println();
res++;
}
return;
}
for (int i = 1; i <= 12; i++)
{
if(!used[i])
{
st[u] = i;
used[i] = true;
dfs(u + 1);
used[i] = false;
st[u] = -1;
}
}
}
public static void main(String[] args) {
Arrays.fill(st, -1);
g[1][2] = g[1][5] = true;
g[2][3] = g[2][6] = true;
g[3][4] = g[3][7] = true;
g[4][8] = true;
g[5][6] = g[5][9] = true;
g[6][7] = g[6][10] = true;
g[7][8] = g[7][11] = true;
g[8][12] = true;
g[9][10] = true;
g[10][11] = true;
g[11][12] = true;
dfs(1);
//由于排列组合，会有重复情况，不要
System.out.println(res / 5 / 4 / 3 / 2);
}
}
H. 四平方和
暴力就可以AC
y总的做法对Java不太友好，就不放在这里了。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
n = Integer.parseInt(input[0]);
for(int a = 0; a * a <= n; a++)
for(int b = a; a * a + b * b <= n; b++)
for(int c = b; a * a + b * b + c * c <= n; c++)
{
int d2 = n - a * a - b * b - c * c;
int d = (int) Math.sqrt(d2);
if(d2 >= c * c && d * d == d2)
{
System.out.println(a+" "+b+" "+c+" "+d);
return;
}
}
}
}
I. 取球博弈
太复杂了，不会。
J. 压缩变换
暴力 TLE 50分
这里用了map记录数字最后一次出现的位置。
如果用数组存的话，需要开很大，官网评测机会运行错误，很怪。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
public class Main {
static int N = 100010;
static int n;
static int[] a = new int[N];
static int[] b = new int[N];
static HashSet<Integer> hs = new HashSet<>();
static HashMap<Integer,Integer> map = new HashMap<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
n = Integer.parseInt(input[0]);
input = br.readLine().split(" ");
for (int i = 1; i <= n; i++)
{
a[i] = Integer.parseInt(input[i - 1]);
if(map.get(a[i]) == null)
{
b[i] = -a[i];
map.put(a[i], i);
}
else
{
hs.clear();
for(int j = map.get(a[i]) + 1; j < i; j++)
{
hs.add(a[j]);
}
b[i] = hs.size();
map.put(a[i], i); //别忘记更新最后出现的位置
}
}
for (int i = 1; i <= n; i++) System.out.print(b[i]+" ");
}
}
I. 交换瓶子 (C++组)
1.每次交换，必然会有两种结果：把一个环分裂成两个，把一个环合并成一个。
2.初始的时候，一共有k个环，希望把它变成n个环。每次操作最多只能增加1个环，所以最少需要n-k次操作，也必然存在这种方案。
3.开一个布尔数组，随便找一个点遍历，把它所有能到的点找出来，也就是这个环上的点全找出来，找完之后说明找到了一个环，再让计数器+1，再接着找下一个点。
例如：3找在第3个位置上的瓶子，也就是2。变成代码就是 j = b[j]。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 10010;
static int n;
static int[] b = new int[N];
static boolean[] st = new boolean[N];
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
n=Integer.parseInt(input[0]);
input=br.readLine().split(" ");
for (int i = 1; i <= n; i ++ ) b[i] = Integer.parseInt(input[i-1]);
int cnt = 0;
for (int i = 1; i <= n; i ++ )
if (!st[i])
{
cnt ++ ;
for (int j = i; !st[j]; j = b[j])
st[j] = true;
}
System.out.println(n-cnt);
}
}
J. 最大比例 (C++组)
还是有点不明白，就贴几个题解，以后回来看看。
题解1
题解2
第六届
A. 三角形面积
用矩形面积减去三个角的直角三角形面积即为该三角形面积。
B. 立方变自身
根据题意,55的三次方为6位数,即使每一位为9,每位相加最高只能为54,所以从55以后的数不可能满足条件,只需要循环前54个数。
public class Main {
static int res;
public static void main(String[] args) {
int n = 55;
for (int i = 1; i <= n; i++)
{
int a = i * i * i;
String s = String.valueOf(a);
int sum = 0;
for (int j = 0; j < s.length(); j++)
{
sum += s.charAt(j) - '0';
}
if(sum == i) res++;
}
System.out.println(res);
}
}
C. 三羊献瑞
三羊献瑞 祥瑞生辉 气
A B C D E D F G H
EDFG + ABCD = ABFDH
5467 1234 12648
import java.util.Arrays;
public class Main {
static int N = 20;
static int[] st = new int[N];
static boolean[] used = new boolean[N];
static void dfs(int u)
{
if(u > 8)
{
if(st[1] != 0 && st[5] != 0) //四、五位数，所以三个数的首位都不为0
{
int a = st[5]*1000+st[4]*100+st[6]*10+st[7];
int b = st[1]*1000+st[2]*100+st[3]*10+st[4];
int c = st[1]*10000+st[2]*1000+st[6]*100+10*st[4]+st[8];
if(a + b == c)
{
System.out.println(b);
}
}
return;
}
for (int i = 0; i <= 9; i++)
{
if(!used[i])
{
st[u] = i;
used[i] = true;
dfs(u + 1);
used[i] = false;
st[u] = -1;
}
}
}
public static void main(String[] args) {
Arrays.fill(st, -1);
dfs(1);
}
}
D、E都是代码补全题，不写了。
F. 加法变乘法
public class Main {
public static void main(String[] args) {
for (int i = 1; i <= 49; i++)
for (int j = i + 1; j <= 49; j++)
{
if(1225 - i - (i + 1) - j - (j + 1) + i * (i + 1) + j * (j + 1) == 2015)
{
System.out.println(i);
// System.out.println(i + " " + j);
}
}
}
}
G. 牌型种数
public class Main {
static int res, sum; //res是方案数，sum为当前手牌数
static void dfs(int u) //u是当前牌的种类 (1~K)
{
if (sum > 13 || u > 13) return; //如果手牌数超过13张 或 牌的点数大于13 则返回
if (sum == 13) //如果手牌数刚好够13张，说明刚好满足一组方案，res++并且返回上一层
{
res++;
return;
}
for (int i = 0; i <= 4; i++) //对于每个牌种，可以有五种选择，不拿或者拿1~4张
{
sum += i; //对于每种选择 累加到小明的 手牌数当中
dfs(u + 1); //对于他的每种选择都往下搜索，直到不能再往下走为止
sum -= i; //每次回溯的时候，都需要把他刚才的选择给撤回
}
}
public static void main(String[] args) {
dfs(0); //初始状态为0 当第一次进入dfs时候，第一个for循环里面是dfs(1) 此时代表的是 对牌种1的五种选择进行 dfs
System.out.println(res);
}
}
H. 饮料换购
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
int n; //瓶盖个数
n=Integer.parseInt(input[0]);
// n/3向下取整 = 换的饮料的数量
// n%3 = 换完后剩下的瓶盖的数量
int res = n;
while (n >= 3) //不是0
{
res += n / 3; //多喝多少瓶
n = n / 3 + n % 3; //喝了的+盖的数量
}
System.out.println(res);
}
}
I. 垒骰子
DFS会TLE，不过能得37分
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int MOD = (int) (1e9+7);
static int n, m;
static int[] op = new int[10]; // 骰子对应的面
static boolean[][] con = new boolean[10][10]; // 是否冲突
static void init()
{
op[1] = 4; op[4] = 1;
op[2] = 5; op[5] = 2;
op[3] = 6; op[6] = 3;
}
static long dfs(int up, int cnt)
{
//第一个骰子不动，计算其余n-1个骰子。所以到n个的时候就停止。
//除第一层外底层筛子都有四个面可选，所以cnt==n时ans要+4 (这里是return 1，后面乘4了)
if (cnt == n) return 1;
long ans = 0;
for (int i = 1; i <= 6; i++)
{
int down = op[up];
if (con[down][i] || con[i][down]) continue;
ans = (ans + 4 * dfs(i, cnt + 1)) % MOD;
}
return ans;
}
public static void main(String[] args) throws IOException {
init();
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
n = Integer.parseInt(input[0]);
m = Integer.parseInt(input[1]);
for (int i = 0; i < m; ++i) {
int a, b;
input=br.readLine().split(" ");
a = Integer.parseInt(input[0]);
b = Integer.parseInt(input[1]);
con[a][b] = true;
con[b][a] = true;
}
long ans = 0;
for (int i = 1; i <= 6; ++i) {
//横向可以随便转，第一层也有四个面可选，所以最后要乘以4
ans = (ans + 4 * dfs(i, 1)) % MOD;
}
System.out.println(ans);
}
}
J. 生命之树
dfs 50分
树形DP，无向树，求连通块的最大值。
一般用递归(DFS)来做，每次算一下子树的根结点的值是多少，一般用儿子的结点算。
ArrayList模拟树，虽然比数组慢一点，但方便。
java 限制递归最大一万层，递归深度太深导致栈溢出，这没办法。
而且官网的部分数据与题意不符，很怪。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main {
//无向树，点数十万，边数两倍
static int N = 100010;
static int n;
static int[] w = new int[N]; //每个点的权值
static ArrayList<Integer>[] g = new ArrayList[N];
//数据范围10^6，一共10^5个点。所以最大10^11，会暴int
static long[] f = new long[N]; //状态数组
static void dfs(int u, int father)
{
f[u] = w[u]; //首先包括子树根节点u的权值
//枚举u的所有儿子
for(int i = 0; i < g[u].size(); i++)
{
int j = g[u].get(i);
if(j != father)
{
dfs(j, u);
f[u] += Math.max(0, f[j]);
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
n = Integer.parseInt(input[0]);
for(int i = 0;i <= n;i++) g[i] = new ArrayList<Integer>(); //ArrayList数组必须先初始化
input=br.readLine().split(" ");
for (int i = 1; i <= n; i ++ ) w[i] = Integer.parseInt(input[i-1]);
for (int i = 0; i < n - 1; i ++ ) //n个结点，n-1条边
{
int a, b;
input=br.readLine().split(" ");
a = Integer.parseInt(input[0]);
b = Integer.parseInt(input[1]);
g[a].add(b);
g[b].add(a);
}
//从结点1开始。由于无向边，需要避免往回搜。第二个参数是从哪个点下来的(父节点)。
dfs(1, -1);
long res = f[1]; //所有结点最大值
for (int i = 2; i <= n; i ++ ) res = Math.max(res, f[i]);
if(res > 0) System.out.println(res);
else System.out.println(0);
}
}
y总写法
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
//无向树，点数十万，边数两倍
static int N = 100010, M = N * 2;
static int n;
static int[] w = new int[N]; //每个点的权值
static int idx; //邻接表
static int[] h = new int[N], e = new int[M], ne = new int[M];
//数据范围10^6，一共10^5个点。所以最大10^11，会暴int
static long[] f = new long[N]; //状态数组
static void add(int a, int b)
{
e[idx] = b; ne[idx] = h[a]; h[a] = idx ++ ;
}
static void dfs(int u, int father)
{
f[u] = w[u]; //首先包括子树根节点u的权值
//枚举u的所有儿子
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j != father) //j不是往回搜的
{
dfs(j, u);
f[u] += Math.max((long)0, f[j]); //小于0的不加。(long)可以不加。
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
n = Integer.parseInt(input[0]);
Arrays.fill(h, -1);
input=br.readLine().split(" ");
for (int i = 1; i <= n; i ++ ) w[i] = Integer.parseInt(input[i-1]);
for (int i = 0; i < n - 1; i ++ ) //n个结点，n-1条边
{
int a, b;
input=br.readLine().split(" ");
a = Integer.parseInt(input[0]);
b = Integer.parseInt(input[1]);
add(a, b); add(b, a); //无向图，双向边
}
//从结点1开始。由于无向边，需要避免往回搜。第二个参数是从哪个点下来的(父节点)。
dfs(1, -1);
long res = f[1]; //所有结点最大值
for (int i = 2; i <= n; i ++ ) res = Math.max(res, f[i]);
System.out.println(res);
}
}
A. 奖券数目 (C++组)
public class Main {
public static void main(String[] args) {
int res = 0;
for (int i = 10000; i <= 99999; i++)
{
if(String.valueOf(i).indexOf('4') == -1) res++;
}
System.out.println(res);
}
}
B. 星系炸弹 (C++组)
用Date和Calendar都实现了一遍
Excel解法
import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.Date;
public class Main {
public static void main(String[] args) {
//月份别忘记减1
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
Date date = new Date(114, 11 - 1, 9 + 1000);
String ans = sdf.format(date);
System.out.println(ans);
Calendar calendar = Calendar.getInstance();
calendar.set(2014, 11 - 1, 9 + 1000);
String ans2 = sdf.format(calendar.getTime());
System.out.println(ans2);
}
}
H. 移动距离 (C++组)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
int w, m, n;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
w=Integer.parseInt(input[0]);
m=Integer.parseInt(input[1]);
n=Integer.parseInt(input[2]);
m --; n -- ; //全部-1，下标从0开始。这样求行号列号好求
int x1 = m / w, x2 = n / w; //行号
int y1 = m % w, y2 = n % w; //列号
if (x1 % 2 == 1) y1 = w - 1 - y1;
if (x2 % 2 == 1) y2 = w - 1 - y2;
System.out.println(Math.abs(x1 - x2) + Math.abs(y1 - y2));
}
}
第五届
A. 武功秘籍
带走的页数（80,81）（82,83）（84,85）（86,87）（88,89）（90,91）（92,93）
答案：7
B. 切面条
自己画个图找规律
发现每次相加的都是2的整数次幂
n 0 1 2 3 4
sum 2 3 5 9 17
public class Main {
public static void main(String[] args) {
int n = 10, sum = 2;
for (int i = 1; i <= n; i++)
{
sum += Math.pow(2, i - 1);
}
System.out.println(sum);
}
}
C. 猜字母
public class Main {
public static String Method(String s)
{
StringBuilder sb = new StringBuilder();
for(int i = 0,t = s.length(); i < t; i++)
{
if(i % 2 == 1) //原序列的偶数在现序列为奇数
{
sb.append(s.charAt(i));
}
}
return sb.toString(); //返回删除后的字符串
}
public static void main(String[] args)
{
String s = "abcdefghijklmnopqrs";
String str = "";
for(int i = 1; i <= 106; i++)
{
str += s;
}
int n = str.length();
while(n != 1) //只剩下最后一个字符时跳出循环
{
str = Method(str); //Method方法返回的是删除掉奇数位置后的字符串
n = str.length(); //n为删除掉奇数位置后的字符串长度
}
System.out.println(str); //输出最后一个字符
}
}
F. 奇怪的分式
注意使用对角相乘
public class Main {
public static void main(String[] args) {
int sum = 0;
for (int a = 1; a < 10; a++)
for (int b = 1; b < 10; b++)
for (int c = 1; c < 10; c++)
for (int d = 1; d < 10; d++)
if (a != b && c != d
&& a * c * (b * 10 + d) == b * d * (a * 10 + c))
{
sum++;
}
System.out.println(sum);
}
}
G. 扑克序列
这种全排列DFS要记住
import java.util.TreeSet;
public class Main {
static TreeSet<String> set = new TreeSet<>(); //treeset内元素不可重复其有序
static char[] poker = "AA223344".toCharArray();
static void test()
{
String s = new String(poker);
if(s.lastIndexOf('A') - s.indexOf('A')!=2) return;
if(s.lastIndexOf('2') - s.indexOf('2')!=3) return;
if(s.lastIndexOf('3') - s.indexOf('3')!=4) return;
if(s.lastIndexOf('4') - s.indexOf('4')!=5) return;
set.add(s);
}
static void dfs(int k)
{
if(k == poker.length)
{
test();
return;
}
for(int i = k, len = poker.length; i < len; i++)
{
char c = poker[i]; poker[i] = poker[k]; poker[k] = c;
dfs(k + 1);
c = poker[i]; poker[i] = poker[k]; poker[k] = c;
}
}
public static void main(String[] args) {
dfs(0);
for(String s: set)
{
System.out.println(s);
}
}
}
H. 分糖果
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
public class Main {
static int N = 110;
static int n, res;
static int[] a = new int[N];
static int[] b = new int[N];
static HashSet<Integer> hs = new HashSet<>();
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
n = Integer.parseInt(input[0]);
input=br.readLine().split(" ");
for (int i = 1; i <= n; i++)
{
a[i] = Integer.parseInt(input[i - 1]);
b[i] = a[i] / 2;
}
while(true)
{
for (int i = 1; i <= n; i++)
{
if(i + 1 <= n) a[i] = b[i] + b[i + 1];
else a[i] = b[i] + b[1];
}
for (int i = 1; i <= n; i++)
{
if(a[i] % 2 == 1)
{
a[i]++;
res++;
}
b[i] = a[i] / 2;
}
hs.clear();
for (int i = 1; i <= n; i++)
{
hs.add(a[i]);
}
if(hs.size() == 1) break;
}
System.out.println(res);
}
}
I. 地宫取宝
DFS TLE 42分
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int MOD = 1000000007;
static int N = 60;
static int n, m, k, res;
static int[][] c = new int[N][N];
static int[] dx = {0,1};
static int[] dy = {1,0};
static void dfs(int x, int y, int u, int max)
{
if(x > n || y > m || u > k) return;
if(x == n && y == m) //最后一格也有取不取两种情况
{
if(u == k) res = (res + 1) % MOD;
if(u + 1 == k && c[x][y] > max) res = (res + 1) % MOD;
return;
}
for (int i = 0; i < 2; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
dfs(nx, ny, u, max);
if(c[x][y] > max) //不能用if(Math.max(c[x][y], max) == c[x][y])，因为可能这俩会相等
{
dfs(nx, ny, u + 1, c[x][y]);
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
n=Integer.parseInt(input[0]);
m=Integer.parseInt(input[1]);
k=Integer.parseInt(input[2]);
for (int i = 1; i <= n; i++)
{
input=br.readLine().split(" ");
for (int j = 1; j <= m; j++)
{
c[i][j] = Integer.parseInt(input[j - 1]);
}
}
dfs(1,1,0,-1); //价值可能为0，所以max初值为-1
System.out.println(res % MOD);
}
}
DP
//摘花生+最长上升子序列的组合
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 55, MOD = 1000000007;
static int n, m, k; //k个物品
static int[][] w = new int[N][N]; //价值
/*f(i,j,k,c) 是指取了这个宝物之后的状态(倒着想)
i j 坐标
k 当前取多少个
c 最后取得一件的价值是多少*/
static int[][][][] f = new int[N][N][13][14]; //状态(方案数！) (0~12 13个数(0代表不拿)、-1~12(-1是初始化)->0~13 14个数)
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
n=Integer.parseInt(input[0]);
m=Integer.parseInt(input[1]);
k=Integer.parseInt(input[2]);
for (int i = 1; i <= n; i ++ )
{
input=br.readLine().split(" ");
for (int j = 1; j <= m; j ++ )
{
w[i][j]=Integer.parseInt(input[j-1]);
w[i][j] ++ ; //把所有价值都+1，原因在下面。
}
}
//初始化：选第一个和不选第一个
f[1][1][1][w[1][1]] = 1;
//"如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它" 所以必须是严格升序
//又因为价值范围是0~12，这样第一个物品不取的情况不好初始化，C没法填。(如果填0，就拿不起后面价值=0的物品了)
//所以应该初始化成f[1][1][0][-1] = 1; 但由于下标不能为负，所以把所有C都+1。从0开始就变成从1开始了。
//因为我们记录的是方案数，只关心各个物品之间的大小关系，具体数值不影响答案。所以这种处理后面也不需要改回来。
f[1][1][0][0] = 1;
for (int i = 1; i <= n; i ++ ) //循环所有状态
for (int j = 1; j <= m; j ++ )
{
if (i == 1 && j == 1) continue; //特判，已经初始化过了。其实不加这句话也可以
for (int u = 0; u <= k; u ++ ) //枚举个数k
for (int v = 0; v <= 13; v ++ ) //枚举最后一件物品的价值c 0也是一个合法取值，表示“当前没有取任何物品”。
{
//其实这里的意思是四种情况加起来，但由于模的数非常大，三倍的Mod就爆了，所以最多两个数相加再取模(int是2*10^9)
f[i][j][u][v] = (f[i][j][u][v] + f[i - 1][j][u][v]) % MOD; //这句只写一个也行 f[i][j][u][v] = (f[i - 1][j][u][v]) % MOD;
f[i][j][u][v] = (f[i][j][u][v] + f[i][j - 1][u][v]) % MOD;
if (u > 0 && v == w[i][j]) //因为要取，所以u>0，即个数>0。v==w[i][j]是因为取完之后是c
{
//这个判断里面的循环的c'是枚举的我所取物品中最后一个的数目，c是一定小于w[i][j]的。
for (int c = 0; c < v; c ++ ) //循环c'<c c'用c表示
{
f[i][j][u][v] = (f[i][j][u][v] + f[i - 1][j][u - 1][c]) % MOD;
f[i][j][u][v] = (f[i][j][u][v] + f[i][j - 1][u - 1][c]) % MOD;
}
}
}
}
int res = 0;
//由题意，n m k固定，所以只根据价值循环一遍，把方案数加起来就可以。
//f[n][m][k][0]表示什么物品都没拿，它的值是0，所以从1开始循环和从0开始循环是不影响结果的。
for (int i = 0; i <= 13; i ++ ) res = (res + f[n][m][k][i]) % MOD;
System.out.println(res);
}
}
J. 矩阵翻硬币
太难了，不会。
A. 啤酒和饮料 (C++组)
public class Main {
public static void main(String[] args) {
for(int i = 1; i <= 82.3 / 1.9; i++) //i啤酒 j饮料
for(int j = 0; j < i ; j++)
if(i * 19 + j * 23 == 823) System.out.println(j);
}
}
C. 李白打酒 (C++组)
public class Main {
static int res;
//分别表示 店 花 酒量 位置 最后一个位置表示
static void dfs(int a, int b, int sum, int u, int flag)
{
if(u == 15)
{
if(a == 5 && b == 10 && sum == 0 && flag == 0)
{
res++;
}
return;
}
dfs(a + 1, b, sum * 2, u + 1, 1);
dfs(a, b + 1, sum - 1, u + 1, 0);
}
public static void main(String[] args) {
dfs(0, 0, 2, 0, 0);
System.out.println(res);
}
}
D. 史丰收运算 (C++组)
没看懂，可以再看看 题解
G. 六角填数 (C++组)
import java.util.Arrays;
public class Main {
static int N = 20;
static int[] st = new int[N];
static boolean[] used = new boolean[N];
static void dfs(int u)
{
if(u > 12)
{
if(st[1] == 1 && st[2] == 8 && st[12] == 3)
{
int line1 = st[1]+st[3]+st[6]+st[8];
int line2 = st[1]+st[4]+st[7]+st[11];
int line3 = st[8]+st[9]+st[10]+st[11];
int line4 = st[2]+st[3]+st[4]+st[5];
int line5 = st[2]+st[6]+st[9]+st[12];
int line6 = st[5]+st[7]+st[10]+st[12];
if(line1==line2&&line2==line3&&line3==line4&&line4==line5&&line5==line6)
System.out.println(st[6]);
}
return;
}
for (int i = 1; i <= 12; i++)
{
if(!used[i])
{
st[u] = i;
used[i] = true;
dfs(u + 1);
used[i] = false;
st[u] = -1;
}
}
}
public static void main(String[] args) {
Arrays.fill(st, -1);
dfs(1);
}
}
H. 蚂蚁感冒
两只蚂蚁相撞，虽然题目说是180°掉头，但可以等价转换为方向不变，穿过去了。
假设第一只感冒蚂蚁是向右的，则其它蚂蚁：
1.右边所有向左的一定感染
2.左边向左、右边所有向右的安全。
3.左边向右的要分情况看看：
如果第一只感冒蚂蚁的右边有向左的蚂蚁，则会被感染。
没有的话，就安全。
所以统计1 3两种情况的蚂蚁数量就可以
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 55;
static int n;
static int[] x = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
n=Integer.parseInt(input[0]);
input=br.readLine().split(" ");
for (int i = 0; i < n; i ++ ) x[i]=Integer.parseInt(input[i]);
int left = 0, right = 0; // 分别表示左边向右走的蚂蚁数量，和右边向左走的蚂蚁数量
for (int i = 1; i < n; i ++ )
if (Math.abs(x[i]) < Math.abs(x[0]) && x[i] > 0) left ++ ;
else if (Math.abs(x[i]) > Math.abs(x[0]) && x[i] < 0) right ++ ;
if (x[0] > 0 && right == 0 || x[0] < 0 && left == 0) System.out.println(1);
else System.out.println(left + right + 1);
}
}
J. 小朋友排队 (C++组)
第四届
A. 世纪末的星期
import java.util.Calendar;
import java.util.Date;
public class Main {
public static void main(String[] args) {
for (int i = 1999;; i += 100)
{
Calendar calendar = Calendar.getInstance();
calendar.setTime(new Date(i - 1900, 12 - 1, 31)); //月份要减1
if (calendar.get(Calendar.DAY_OF_WEEK) - 1 == 0) //1是星期日，7是星期六。减1就能对应上0~6
{
System.out.println(i);
return;
}
}
}
}
B. 马虎的算式
import java.util.Arrays;
public class Main {
static int N = 10;
static int res;
static int[] st = new int[N];
static boolean[] used = new boolean[N];
static void check()
{
int num1 = st[1] * 10 + st[2];
int num2 = st[3] * 100 + st[4] * 10 + st[5];
int num3 = st[1] * 100 + st[4] * 10 + st[2];
int num4 = st[3] * 10 + st[5];
if(num1 * num2 == num3 * num4) res++;
}
static void dfs(int u)
{
if(u > 5)
{
check();
return; //别忘记写return，不然结果不对。
}
for (int i = 1; i <= 9; i++)
{
if(!used[i])
{
used[i] = true;
st[u] = i;
dfs(u + 1);
st[u] = -1;
used[i] = false;
}
}
}
public static void main(String[] args) {
Arrays.fill(st, -1);
dfs(1);
System.out.println(res);
}
}
C. 振兴中华
仔细看看矩阵，其实就是最基础的“走方格” DFS
也可以用DP做，见这篇 文章
public class Main {
static int n = 4, m = 5, res;
static void dfs(int x, int y)
{
if(x > 4 || y > 5) return;
if(x == 4 && y == 5)
{
res++;
return;
}
dfs(x + 1, y);
dfs(x, y + 1);
}
public static void main(String[] args) {
dfs(1, 1);
System.out.println(res);
}
}
D. 黄金连分数
这篇 题解 写的非常好。
G. 错误票据
1.”\s+” - 匹配任意空白字符(没用上)
2.Arrays.sort(int[] a, int fromIndex, int toIndex)
这种形式是对数组部分排序，也就是对数组a的下标从fromIndex到toIndex-1的元素排序，注意：下标为toIndex的元素不参与排序哦！
3.这题的输入确实很蛋疼，不过Java问题不大
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 10010; //100*100最多有10000个数
static int[] a = new int[N];
public static void main(String[] args) throws IOException {
int cnt;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
cnt=Integer.parseInt(input[0]);
int start = 0;
while (cnt -- >0)
{
input=br.readLine().split(" ");
for(int i=0;i<input.length;i++)
{
a[i+start] = Integer.parseInt(input[i]);
}
start += input.length;
}
Arrays.sort(a,0,start);
int res1 = 0, res2 = 0;
//从第二个数(下标为1)开始扫描，比较与前1个数的关系
for (int i = 1; i < start ; i ++ )
if (a[i] == a[i - 1]) res2 = a[i]; // 重号
else if (a[i] >= a[i - 1] + 2) res1 = a[i] - 1; // 断号
System.out.println(res1+" "+res2);
}
}
H. 幸运数
内存超限+TLE 50分
可以看这篇 题解
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 1000010;
static int n, m, res;
static int[] a = new int[N];
public static void lucky(int[] arr, int k)
{
int cnt = 1;
int[] b = new int[N];
for (int i = 1; i < arr.length; i++)
{
if(i % k != 0) b[cnt++] = arr[i];
}
// for (int i = 1; i < 10; i++) System.out.println(b[i]);
a = b.clone();
}
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
n = Integer.parseInt(input[0]);
m = Integer.parseInt(input[1]);
for (int i = 1; i < m; i++) a[i] = i;
lucky(a, 2); //先把2删了
int now = 2;
while(true)
{
int take = a[now];
if(take == 0) break;
lucky(a, take);
now++;
}
for(int num : a)
{
if(num > m) break;
if(num > n && num < m) res++;
}
System.out.println(res);
}
}
I. 带分数
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
//朴素法：枚举全排列、枚举位数、判断等式是否成立
public class Main {
static int N=10;
static int n;
static int res;
static boolean[] used = new boolean[N];
static int[] state = new int[N];
static int get(int l,int r) //求解分割过后的数值大小
{
int m=0;
for(int i=l;i<=r;i++)
{
m=m*10+state[i];
}
return m;
}
static boolean check(int a,int b,int c) //判断数值是否满足条件
{
if(n*c-a*c==b) return true; //由 n=a+b/c 变形的等式
return false;
}
static void dfs(int u)
{
if(u>=N)//已经完成全排列，用双重循环将全排列划分为三个数字
{
for(int i=1;i<=7;i++) //因为要分三段，第一段最大是1~7。
{
for(int j=i+1;j<=8;j++) //第二段最大是2~8。
{
int a=get(1,i); //分别将此时a b c的数值表示出来
int b=get(i+1,j);
int c=get(j+1,9);
if(check(a,b,c)) res++; //判断是否符合题目条件
}
}
return;
}
for(int i=1;i<N;i++) //dfs求排列型递归
{
if(!used[i])
{
state[u]=i;
used[i]=true;
dfs(u+1);
used[i]=false;
state[u]=0;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
n=Integer.parseInt(input[0]);
dfs(1);
System.out.println(res);
}
}
J. 连号区间数
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 10010, INF = 100000000; //每个数都在1~10000，所以最值比这大就行
static int n;
static int[] a = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
n=Integer.parseInt(input[0]);
input=br.readLine().split(" ");
for (int i = 0; i < n; i ++ )
{
a[i] = Integer.parseInt(input[i]);
}
int res = 0;
//枚举的同时算最值
for (int i = 0; i < n; i ++ ) // 枚举区间左端点
{
int minv = INF, maxv = -INF;
//第二层，每次循环的时候，区间里只加了一个数，所以最值只计算新的数就可以了。
for (int j = i; j < n; j ++ ) // 枚举区间右端点
{
minv = Math.min(minv, a[j]);
maxv = Math.max(maxv, a[j]);
if (maxv - minv == j - i) res ++ ;
}
}
System.out.println(res);
}
}
A. 高斯日记 (C++组)
Excel大法只支持1970年以后的日期。
不过可以把题干中的日期延后200年，最后再减去就行，但要注意2000年是个闰年，而1800不是。
答案是1799-07-16，加200年后没超过2000，所以就不用再算2000年闰年的影响了。
C. 第39级台阶 (C++组)
public class Main {
static int res;
static void dfs(int u, int step)
{
if(u > 39) return;
if(u == 39)
{
if(step % 2 == 0) res++;
return;
}
dfs(u + 1, step + 1);
dfs(u + 2, step + 1);
}
public static void main(String[] args) {
dfs(0, 0);
System.out.println(res);
}
}
H. 翻硬币 (C++组)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 110;
static int n;
static char[] start = new char[N], end = new char[N];
static void turn(int i)
{
if (start[i] == '*') start[i] = 'o';
else start[i] = '*';
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
start = br.readLine().toCharArray();
end = br.readLine().toCharArray();
n = start.length;
int res = 0;
for (int i = 0; i < n - 1; i ++ ) //最后一列不按(因为和倒二效果一样)
if (start[i] != end[i])
{
turn(i); turn(i + 1);
res ++ ;
}
System.out.println(res);
}
}
佬 关注你了hh
大工程啊
省一第三名，真的很谢谢老哥你
哥，决赛见respect
哪个省啊，我没进决赛😂
浙江h h h
跟着老哥走，见证大佬的诞生hhh
不是大佬😂，努力学习中~