写在前面：
这算是二刷省赛题了，因为之前一刷的时候参考了很多资料，所以这次想独立做一遍。
在四月九日考试前我会尽量把4 ~ 12届的绝大部分题目都做完。
第十二届第一场
A. ASC
public class Main {
public static void main(String[] args) {
System.out.println('L' - 'A' + 65);
}
}
B. 卡片
import java.util.Arrays;
public class Main {
static int[] num = new int[11];
public static void main(String[] args) {
Arrays.fill(num, 2021);
boolean flag = false;
for (int i = 1; i < 10000; i++) {
int t = i;
while(t>0)
{
num[t%10] -- ;
if(num[t%10] < 0) //不能写 == 0
{
flag = true;
break;
}
t/=10;
}
if(flag)
{
System.out.println(i - 1);
break;
}
}
}
}
C. 直线
注意：要把int类型赋值给double类型的时候，必须强制类型转换为(double)
class Line
{
double k, b;
Line(double k, double b) {
this.k = k;
this.b = b;
}
}
public class Main {
static int N = 2000000;
static int cnt;
static Line[] line = new Line[N];
public static void main(String[] args) {
int n = 20, m = 21;
for (int x1 = 0; x1 < n; x1++)
for (int y1 = 0; y1 < m; y1++)
for (int x2 = 0; x2 < n; x2++)
for (int y2 = 0; y2 < m; y2++)
{
if(x1 == x2) continue;
//y1 = k * x1 + b
//y2 = k * x2 + b
//y1 - y2 = k * (x1 - x2)
double k = (double)(y1 - y2) / (x1 - x2); //必须转double!!!
double b = y1 - k * x1;
boolean flag = true;
for (int i = 0; i < cnt; i++)
{
if(Math.abs(line[i].k - k) < 1e-8 && Math.abs(line[i].b - b) < 1e-8)
flag = false;
}
if(flag)
{
line[cnt++] = new Line(k, b);
}
}
System.out.println(cnt + n);
}
}
D. 货物摆放
import java.util.ArrayList;
public class Main {
//直接书写的数字是int型，太大。需要加个L转换一下
static long n = 2021041820210418L;
static long res;
static ArrayList<Long> d = new ArrayList<Long>();
public static void main(String[] args) {
for (long i = 1; i * i <= n; i++)
{
if(n % i == 0)
{
d.add(i);
if(i != n / i) d.add(n / i); //别写到判断语句外面
}
}
for(long a : d)
for(long b : d)
for(long c : d)
{
if(a * b * c == n) res++;
}
System.out.println(res);
}
}
E. 路径
gcd、图的存储、spfa算法都要好好背背。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N = 2200, M = N * 50;
static int n, idx;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int[] w = new int[M];
static int[] dist = new int[N];
static boolean[] st = new boolean[N];
static int gcd(int a, int b)
{
return b != 0 ? gcd(b, a % b) : a;
}
static void add(int a, int b, int c)
{
w[idx] = c; e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
static void spfa() // 求1号点到n号点的最短路距离
{
Arrays.fill(dist, 0x3f3f3f3f); //初始化所有点的距离为最大值
dist[1] = 0; //1号点到1号点的距离为0
Queue<Integer> q = new LinkedList<Integer>();
q.offer(1); //把1号点放入队列。
st[1] = true; //存储当前点是否在队列当中。防止队列当中存储重复点。
while(q.size() > 0)
{
int t = q.poll();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) //更新t的所有邻边
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if(!st[j]) // j不在队列中，才把j插入进去。防止重复插入
{
q.offer(j);
st[j] = true;
}
}
}
}
}
public static void main(String[] args) {
n = 2021;
Arrays.fill(h, -1);
for (int i = 1; i <= n; i++)
for (int j = Math.max(1, i - 21); j <= Math.min(n, i + 21); j++)
{
int d = gcd(i, j);
add(i, j, i * j / d); //最小公倍数
}
spfa();
System.out.println(dist[n]);
}
}
F. 时间显示
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static long n;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
n = Long.parseLong(input[0]);
n /= 1000;
n %= 24 * 60 * 60; //去掉所有整天
long h = n / 3600;
long m = n % 3600 / 60;
long s = n % 60;
System.out.println(String.format("%02d", h) +":"+ String.format("%02d", m) +":"+ String.format("%02d", s));
}
}
G. 最少砝码
参考了这篇 题解
以为是DFS或者DP，但发现根本没法做。
看了题解才知道是找规律，这也太难找了吧。
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]);
if(n == 1)
{
System.out.println(1);
return;
}
int start = 0, end = (int) Math.pow(3, 0);
for (int i = 0; ; i++)
{
start += (int) Math.pow(3, i);
end += (int) Math.pow(3, i + 1);
if(n >= start + 1 && n <= end)
{
System.out.println(i + 2);
return;
}
}
}
}
H. 杨辉三角形
y总的做法没看懂，就直接暴力了。
WA 40分
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
n*(n+1)/2 = 1+2+…+n
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 1000; //不能到10000，会内存超限，0分
static int n;
static int[][] num = new int[N][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 i = 1; i < N; i++)
{
for (int j = 1; j <= i; j++)
{
if(j == 1 || j == i) num[i][j] = 1;
else num[i][j] = num[i-1][j] + num[i-1][j-1];
if(num[i][j] == n)
{
System.out.println((i-1)*i/2 +j);
return;
}
}
}
}
}
I. 双向排序
暴力 TLE 60分
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
public class Main {
static int N = 100010;
static int n, m;
static Integer[] a = new Integer[N]; //必须用Integer数组才能逆序
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 <= n; i++) a[i] = i;
while(m-- > 0)
{
input = br.readLine().split(" ");
int p = Integer.parseInt(input[0]);
int q = Integer.parseInt(input[1]);
if(p == 0) Arrays.sort(a, 1, q + 1, Collections.reverseOrder()); //逆向排序
else Arrays.sort(a, q, n + 1);
}
for (int i = 1; i <= n; i++) System.out.print(a[i]+" ");
}
}
J. 括号序列
太难了不会做
G. 砝码称重（C++组）两种做法
DFS TLE 50分
注意看好dfs里的下标。
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;
static int[] w = new int[N];
static HashSet<Integer> hs = new HashSet<Integer>();
static void dfs(int u, int sum)
{
if(u > n) return;
if(sum > 0) hs.add(sum); //根据题意，<= 0的不要。
dfs(u + 1, sum + w[u + 1]); //放右边
dfs(u + 1, sum); //不放
dfs(u + 1, sum - w[u + 1]); //放左边
}
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++) w[i] = Integer.parseInt(input[i - 1]);
dfs(0, 0);
System.out.println(hs.size());
}
}
背包DP 满分
注意偏移量，以及不同情况的存在条件。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
public class Main {
//j的取值其实是 -m ~ +m，因为数组下标不能为负，所以所有第二维偏移到0 ~ 2m。B是偏移量。
static int N = 110;
static int M = 200010;
static int B = M / 2;
static int n, m;
static int[] w = new int[N];
static boolean[][] f = new boolean[N][M];
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++)
{
w[i] = Integer.parseInt(input[i - 1]);
m += w[i]; //所有砝码总重量
}
f[0][B] = true; //一个物品都没有，总和是0是可以的。(f[0][0] 需要加上偏移量B)
for (int i = 1; i <= n; i++)
for (int j = -m; j <= m; j++)
{
f[i][j + B] = f[i - 1][j + B]; //不选 (这种情况一定存在)
if(j + w[i] <= m) f[i][j + B] |= f[i - 1][j + w[i] + B]; //放右边 (注意存在条件)
if(j - w[i] >= -m) f[i][j + B] |= f[i - 1][j - w[i] + B]; //放左边 (注意存在条件)
}
int res = 0; //最后看看 f(n, 1 ~ m) 有多少个非空就可以了。
for (int i = 1; i <= m; i++)
{
if(f[n][i + B]) res++;
}
System.out.println(res);
}
}
第十二届第二场
A. 求余 1
2021 % 20 = 1
B. 双阶乘 59375
public class Main {
public static void main(String[] args) {
int n = 2021, ans = 1;
while(n > 0) //for (int i = 1; i <= 2021; i += 2) 也行
{
ans = (ans * n) % 100000;
n-=2;
}
System.out.println(ans);
}
}
C. 格点 15698
public class Main {
static long res;
public static void main(String[] args) {
for (int x = 1; x <=2021; x++)
for (int y = 1; x * y <=2021; y++)
res++;
System.out.println(res);
}
}
D. 整数分解 691677274345
我参考别人做的
一个数分解成五个正整数之和第四和第五个数只有remain - 1种情况 (用笔模拟一下就知道了)
public class Main {
public static void main(String[] args) {
int n = 2021;
long res = 0;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
for(int k = 1;k <= n;k++)
{
int remain = n - i - j - k;
if(remain <= 1) break;
res += (remain-1);
}
System.out.println(res);
}
}
y总的隔板法 思路真不错
一个方程的解都可以转换为一个放隔板的方式。反过来也是一样。所以原方程正整数的解等于这样摆放隔板的方案数。
一共有2021-1=2020个空，要从中挑4个位置放隔板，所以是 组合数 C(2020, 4) = 2020*2019*2018*2017/(1*2*3*4)
public class Main {
public static void main(String[] args) {
long res = 1;
for (int i = 2020, j = 1; j <= 4; i --, j ++ )
res = res * i / j;
System.out.println(res);
}
}
E. 城邦 4046
并查集+最小生成树 因为是填空题，所以可以用稍慢的Prim算法，用并查集实现。(当然Kruskal更好，但代码多)
import java.util.ArrayList;
class Edge
{
int a,b,c; //c是边权
Edge(int a, int b, int c) {
this.a = a;
this.b = b;
this.c = c;
}
}
public class Main {
static int N = 2030, M = N * N / 2; //边数M = C(n, 2) ，这里没用上
static int n = 2021, m;
static int[] p = new int[N]; //并查集
static ArrayList<Edge> e = new ArrayList<>(); //用数组的话就是e[M]
static int find(int x) // 并查集
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
static int get(int x, int y) //算边权
{
int res = 0;
while (x != 0 || y != 0) //只要有一个不为0就循环，都为0才退出!
{
int a = x % 10, b = y % 10;
if (a != b) res += a + b;
x /= 10; y /= 10;
}
return res;
}
public static void main(String[] args) {
for (int i = 1; i <= n; i ++ ) p[i] = i; //初始化并查集
for (int i = 1; i <= n; i ++ )
for (int j = i + 1; j <= n; j ++ )
{
e.add(new Edge(i, j, get(i, j)));
m++; //任意两个城邦之间，都有一座桥直接连接。
}
e.sort((o1, o2)->{
return o1.c - o2.c; //按边权从小到大排序
});
int res = 0;
for (int i = 0; i < m; i ++ ) //m其实就是e.size()，用后者更好
{
int a = e.get(i).a, b = e.get(i).b, c = e.get(i).c;
if (find(a) != find(b))
{
res += c;
p[find(a)] = find(b); //加到一个集合
}
}
System.out.println(res);
}
}
F. 特殊年份
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int cnt;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input;
for(int i=0;i<5;i++)
{
input = br.readLine();
if(input.charAt(1)-input.charAt(3) == -1 && input.charAt(0) == input.charAt(2)) cnt++;
}
System.out.println(cnt);
}
}
G. 小平方
注意：除法运算会有精度损失的问题，可以转换为等价的乘法运算。用int类型做除法的时候要特别注意！
写i * i % n * 2 < n 不写 i * i % n < n / 2 避免处理浮点数 写右边的会报错。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int n, res;
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 v = 1; v < n; v++)
{
if(2 * ((v * v) % n) < n) res++;
}
System.out.println(res);
}
}
H. 完全平方数 两种做法
暴力 WA 能过5/10个数据
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static long n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
n = Long.parseLong(input[0]);
for(int i=1;i<=n;i++)
{
if((long)Math.sqrt(i*n) - Math.sqrt(i*n) == 0)
{
System.out.println(i);
return;
}
}
}
}
y总满分做法
n * x = m ^ 2
m是完全平方数意味着m里任何质因子的次数都是偶数。因为次数为偶数的质因子才能分成两份。反过来也是如此。
这个问题就等价于，给一个数n，n最少乘多少可以使n里面每个质因子的次数等于偶数。
所以这题做法是，把n分解质因数，看一下次数，把所有次数为奇数的质因子乘起来，就是答案。
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(" ");
long n = Long.parseLong(input[0]);
long res = 1;
//1不是质因子。从最小的质因子2开始枚举。注意数据范围，不能用int
for (long i = 2; i * i <= n; i ++ )
if (n % i == 0) //求质因子i的次数
{
int s = 0;
while (n % i == 0)
{
s ++;
n /= i;
}
if (s % 2 == 1) res *= i; //s是奇数就乘
}
if (n > 1) res *= n; //可能还有一个质因子(唯一一个大于根号n)，次数是1，乘上。
System.out.println(res);
}
}
I. 负载均衡
1.由于是从前往后枚举所有起点，因此可以用一个堆或者优先队列去维护整个过程。
2.每次算ai之前，需要先把所有执行完的区间，即所有终点在当前起点之前的区间删掉
3.这是每次找最小值并删除的操作，所以用堆(优先队列)来维护：找到当前还没被删的区间里面右端点最小的一个。如果比当前起点还小，就删掉这个区间。
4.只要堆顶元素能删，就一直删，直到堆顶元素的终点大于当前起点。
5.Java由于不能用PII，每次都要重写比较器，有点麻烦。还有，队列数组的每个元素，即每个队列，都必须先初始化才行。
6.部分代码参考 https://www.cnblogs.com/wei-jing/p/10806236.html
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
static int N = 200010;
static int n, m; //计算机数量 任务数量
static int[] s = new int[N]; //每个计算机的算力
static PriorityQueue<int[]>[] q = new PriorityQueue[N]; //[0]结束时间，[1]所需算力。
//小根堆。因为要用数组元素的[0]比较大小，所以需要定义比较器。
static Comparator<int[]> cmp = new Comparator<int[]>()
{
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
};
public static void main(String[] args) throws IOException {
for (int i = 0; i < N; i++)
{
q[i] = new PriorityQueue<>(cmp); //队列数组的每个元素都需要初始化。同时比较器cmp在此指定。
}
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
n = Integer.parseInt(input[0]);
m = Integer.parseInt(input[1]);
input = br.readLine().split(" ");
for (int i = 1; i <= n; i ++ ) s[i] = Integer.parseInt(input[i-1]);
while (m -- >0)
{
int a, b, c, d;
input = br.readLine().split(" ");
a = Integer.parseInt(input[0]);
b = Integer.parseInt(input[1]);
c = Integer.parseInt(input[2]);
d = Integer.parseInt(input[3]);
//队列不空，且第一个元素的终点<=当前任务开始时刻
//也就是说第一个元素的截止时间只要比当前任务晚，就退出。
while (q[b].size() > 0 && q[b].peek()[0] <= a)
{
s[b] += q[b].poll()[1]; //恢复算力，并删除堆顶
}
if (s[b] < d) System.out.println("-1"); //先判断算力是否充足
else //加入新任务
{
int[] task = {a + c, d};
q[b].add(task);
s[b] -= d; //减掉算力
System.out.println(s[b]);
}
}
}
}
J. 国际象棋 两种做法
DFS TLE 能过10/20个数据
自己写的时候忘记考虑不放马的情况，也没考虑某个点能同时被多匹马攻击的情况。我反思。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 10, M = 110;
static int MOD = 1000000007;
static int n, m, k, res;
//注意：x， y这个点可能同时被多匹马攻击到，所以不能用boolean数组，否则不好恢复现场!
static int[][] g = new int[N][M];
static int[] dx = {1,1,-1,-1,2,2,-2,-2};
static int[] dy = {2,-2,2,-2,1,-1,1,-1};
static void dfs(int x, int y, int u)
{
if(u == k) //先计算方案数
{
res = (res + 1) % MOD;
return;
}
if(y >= m) //再判定是否出界
{
y = 0;
x++;
}
if(x >= n) return;
dfs(x, y + 1, u); //(x, y)不放马，u不加1。 不要忘记这种情况。
if(g[x][y] == 0) //(x, y)如果可以放马，就放马
{
g[x][y]++;
for(int i = 0; i < 8; i++) //标记所有(x, y)能攻击的位置，数量++
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
g[a][b]++;
}
dfs(x, y + 1, u + 1); //放马后u+1
for(int i = 0; i < 8; i++) //恢复现场
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
g[a][b]--;
}
g[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]);
dfs(0,0,0); //从(0, 0)，0个马开始
System.out.println(res % MOD);
}
}
y总的状态压缩 满分答案
1.由N小M大，想到状态压缩DP
2.从上往下放马，只会和前两行有关系。因为只有前两行才能调过来。所以只需要把上一行和上上行记下来就可以了
3.f(i, a, b, j) 前i行放了j个马，第i-1行状态为a，第i行状态为b。每个状态是01串表示放没放。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
//1 << 6是 1×2^6 1000000
static int N = 110, M = 1 << 6, K = 21, MOD = (int) (1e9 + 7);
static int n, m, k;
static int[][][][] f = new int[N][M][M][K];
static int get_count(int x) //求二进制数里面有多少个1
{
int res = 0;
while (x > 0)
{
res ++ ;
x -= x & -x;
}
return res;
}
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]);
f[0][0][0][0] = 1; //初始状态，前面都是0，一个马都没有。
for (int i = 1; i <= m; i ++ ) //枚举所有状态
for (int a = 0; a < 1 << n; a ++ )
for (int b = 0; b < 1 << n; b ++ )
{
//a和(b向左移两位)、b和(a向左移两位) 有重合的话，会攻击，不能放这里。下面的c也是。
if ((a & (b << 2)) != 0 || (b & (a << 2)) != 0) continue;
for (int c = 0; c < 1 << n; c ++ )
{
if ((c & (a << 2)) != 0 || (a & (c << 2)) != 0) continue;
if ((c & (b << 1)) != 0 || (b & (c << 1)) != 0) continue;
int t = get_count(b); //减去b上的马
for (int u = t; u <= k; u ++)
f[i][a][b][u] = (f[i][a][b][u] + f[i - 1][c][a][u - t]) % MOD;
}
}
int res = 0;
for (int i = 0; i < 1 << n; i ++ )
for (int j = 0; j < 1 << n; j ++ )
res = (res + f[m][i][j][k]) % MOD;
System.out.println(res);
}
}
第十一届第一场
A. 解密
public class Main {
static String s1 = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
static String s2 = "yxmdacikntjhqlgoufszpwbrevYXMDACIKNTJHQLGOUFSZPWBREV";
public static void main(String[] args) {
//注意这是加密后的，我们要求加密前的
String str = "EaFnjISplhFviDhwFbEjRjfIBBkRyY"; //EaFn
int len = str.length();
for (int i = 0; i < len; i++)
{
int index = s2.indexOf(str.charAt(i));
System.out.print(s1.charAt(index));
}
}
}
B. 纪念日
Date类还挺好用的。
import java.util.Date;
public class Main {
public static void main(String[] args) {
//为什么要用21和120的原因
//int y = year + 1900;
Date date1 = new Date(21, 7, 23, 12, 0, 0);
Date date2 = new Date(120, 7, 1, 12, 0, 0);
long date1Time = date1.getTime();
long date2Time = date2.getTime();
System.out.println((date2Time-date1Time) / (1000 * 60));
}
}
C. 合并检测
参考了这篇博客写的
感觉成数学问题了。
D. 分配口罩
暴力DFS
public class Main {
public static int[] mask =
{9090400, 8499400, 5926800, 8547000, 4958200,
4422600, 5751200, 4175600, 6309600, 5865200,
6604400, 4635000, 10663400, 8087200, 4554000};
static int res = Integer.MAX_VALUE; //初始化为最大值
static void dfs(int a, int b, int u)
{
if(u == 15)
{
res = Math.min(res, Math.abs(a - b));
return;
}
dfs(a + mask[u], b, u + 1);
dfs(a, b + mask[u], u + 1);
}
public static void main(String[] args) {
dfs(0, 0, 0);
System.out.println(res);
}
}
E. 斐波那契数列最大公约数
注意：斐波那契数列在五十项左右爆int，一百项左右爆long，所以要用大整数类去做。
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
BigInteger[] num = new BigInteger[2030];
num[1] = num[2] = BigInteger.ONE;
for (int i = 3; i <= 2020; i++)
{
num[i] = num[i - 1].add(num[i - 2]);
}
BigInteger ans = num[2020].gcd(num[520]);
System.out.println(ans);
}
}
(注意接下来五道编程题都没有经过评测机，不保证拿满分)
F. 分类计数
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();
int up = 0, low = 0, num = 0;
for(int i = 0; i < input.length(); i++)
{
if(input.charAt(i) >= 'A' && input.charAt(i) <= 'Z') up++;
else if (input.charAt(i) >= 'a' && input.charAt(i) <= 'z') low++;
else if(input.charAt(i) >= '0' && input.charAt(i) <= '9') num++;
}
System.out.println(up);
System.out.println(low);
System.out.println(num);
}
}
G. 八次求和
在乘法里面取模好像是对结果没影响的。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int n, MOD = 123456789;
static long res;
static long getEight(int num)
{
long result = num;
for (int i = 0; i < 7; i++)
{
result = ((result % MOD) * (num % MOD)) % MOD;
}
return result;
}
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 = 1; i <= n; i++)
{
res = (res + getEight(i)) % MOD;
}
System.out.println(res);
}
}
H. 字符串编码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 200010;
static int[] num = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
int len = input.length();
for (int i = 0; i < len; i++) //转为int数组
{
num[i] = input.charAt(i) - '0';
}
String s1 = "0ABCDEFGHIJKLMNOPQRSTUVWXYZZ"; //把位置0占了，后面好计算
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; i++)
{
if(num[i] == 1 || num[i] == 2 && i + 1 < len && num[i + 1] <= 6)
{
sb.append(s1.charAt(num[i] * 10 + num[i + 1]));
i++; //多用了一个，所以多走一步。
}
else //num[i] > 2 || num[i] == 2 && (i + 1 >= len || num[i + 1] > 6)
{
sb.append(s1.charAt(num[i]));
}
}
System.out.println(sb.toString());
}
}
I. BST插入节点问题
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main {
static int N = 10010;
static int n, k;
static ArrayList<Integer>[] list = new ArrayList[N];
static int[] w = new int[N];
public static void main(String[] args) throws IOException {
for (int i = 0; i < N; i++) list[i] = new ArrayList<Integer>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
n = Integer.parseInt(input[0]);
k = Integer.parseInt(input[1]);
for (int i = 1; i <= n; i++)
{
input = br.readLine().split(" ");
int p = Integer.parseInt(input[0]);
w[i] = Integer.parseInt(input[1]);
list[p].add(i);
}
if(list[k].size() == 2) System.out.println(0);
else if(list[k].size() == 0) System.out.println(-1);
else // == 1
{
int ans = Math.abs(w[k] - w[list[k].get(0)]) - 1; //别忘记减1
System.out.println(ans);
}
}
}
j. 网络分析
并查集+暴力 TLE 能过7/10个数据
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 10010;
static int n, m;
static int[] p = new int[N];
static int[] w = new int[N];
static int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
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 <= n; i++) p[i] = i;
for (int i = 0; i < m; i++)
{
input = br.readLine().split(" ");
int choice = Integer.parseInt(input[0]);
int a = Integer.parseInt(input[1]);
int b = Integer.parseInt(input[2]);
if(choice == 1)
{
p[find(a)] = find(b);
}
else
{
for (int j = 1; j <= n; j++)
{
if(find(j) == find(a)) w[j] += b;
}
}
}
for (int i = 1; i <= n; i++) System.out.print(w[i]+" ");
}
}
y总做法 (合并时不创建新点) 说实话没怎么看懂
参考
https://www.acwing.com/solution/content/15945/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 10010;
static int n, m;
static int[] p = new int[N], d = new int[N];
static int find(int x)
{
if (p[x] == x || p[p[x]] == p[x]) return p[x];
int r = find(p[x]);
d[x] += d[p[x]];
p[x] = r;
return r;
}
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 <= n; i ++ ) p[i] = i;
while (m -- >0)
{
int t, a, b;
input = br.readLine().split(" ");
t = Integer.parseInt(input[0]);
a = Integer.parseInt(input[1]);
b = Integer.parseInt(input[2]);
if (t == 1)
{
a = find(a); b = find(b);
if (a != b)
{
d[a] -= d[b];
p[a] = b;
}
}
else
{
a = find(a);
d[a] += b;
}
}
for (int i = 1; i <= n; i ++ )
if (i == find(i)) System.out.print(d[i]+" ");
else System.out.print(d[i] + d[find(i)]+" ");
}
}
A. 跑步训练 (C++组)
public class Main {
public static void main(String[] args) {
int n = 10000;
int i = 0;
while(n > 0)
{
if(n >= 600 && i % 2 == 0)
{
n -= 600;
}
if(i % 2 == 1)
{
n += 300;
if(n < 600)
{
i++;
break;
}
}
i++;
}
System.out.println(i * 60 + n * 60 / 600);
}
}
D. REPEAT程序、E. 矩阵 (C++组)
太难了，不会，以后来看看
可以参考这两篇题解
题解1
题解2
F. 整除序列 (C++组)
注意：10^18 用long
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(" ");
long n = Long.parseLong(input[0]);
while(n>0)
{
System.out.print(n+" ");
n/=2;
}
}
}
G. 解码
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));
char[] str = br.readLine().toCharArray();
for (int i = 0; i < str.length; i++) {
if(str[i]-'0' >=0 && str[i]-'0' <=9)
{
for (int j = 0; j < str[i]-'0'-1; j++) {
System.out.print(str[i-1]);
}
}
else System.out.print(str[i]);
}
}
}
H. 走方格 (C++组) 两种做法
DFS 能过9/10个数据
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 35;
static int n,m,sum;
static int[] dx = {0,1};
static int[] dy = {1,0};
static void dfs(int row,int col)
{
if(row > n || col > m) return;
if(row == n && col == m)
{
sum++;
return;
}
for (int i = 0; i < 2; i++)
{
int x = row + dx[i];
int y = col + dy[i];
if(x % 2 + y % 2 != 0)
{
dfs(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]);
dfs(1,1);
System.out.println(sum);
}
}
y总的DP
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 40;
static int n, m;
static int[][] f = new int[N][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]);
m=Integer.parseInt(input[1]);
f[1][1] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if(i == 1 && j == 1) continue;
if(i % 2 == 1 || j % 2 == 1)
{
f[i][j] = f[i-1][j] + f[i][j-1];
}
}
System.out.println(f[n][m]);
}
}
I. 整数拼接 (C++组) 两种做法
暴力 只能过4/11个数据
通过大整数的特判能多过1个数据，但仍会TLE
大整数参考
https://blog.csdn.net/weixin_39779975/article/details/112839219
https://blog.csdn.net/wcy8733996wcy/article/details/104436407/
https://blog.csdn.net/zhongkelee/article/details/52289163
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class Main {
static int N = (int) (1e5 + 10);
static int n,k,sum;
static String[] num = new String[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]);
k = Integer.parseInt(input[1]);
BigInteger kk = new BigInteger(Integer.toString(k)); //必须输入k之后再初始化，不然等于0了
input = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
num[i] = input[i];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if(i!=j)
{
if(num[i].equals("1000000000") && num[j].equals("1000000000"))
{
//数据范围10^9，10位数字，两个拼接在一起是20位数字
//long类型到9*10^19 (2^64 -1)，所以long就爆了。
BigInteger t = new BigInteger(num[i]+num[j]);
//[0]是商 [1]是余数
//小于则返回-1，等于则返回0，大于则返回1
if(t.divideAndRemainder(kk)[1].compareTo(BigInteger.ZERO) == 0) sum++;
}
else
{
long t = Long.parseLong(num[i]+num[j]);
if(t % k == 0) sum++;
}
}
}
}
System.out.println(sum);
}
}
y总做法 有点难想
参考
https://www.acwing.com/solution/content/43755/
https://www.acwing.com/solution/content/35561/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class Main {
static int N = 100010;
static int n, m;
static int[] a = new int[N];
//哈希表，存(某个数 * 10 ^ i)% k == j的数量。
//i:0~10,因为题目中给出的最大数是10^9，拼接时第一位1也加进去，所以会扩大10^10倍
static int[][] s = new int[11][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]);
m=Integer.parseInt(input[1]);
input = br.readLine().split(" ");
for (int i = 0; i < n; i ++ ) a[i] = Integer.parseInt(input[i]);
for (int i = 0; i < n; i ++ )
{
long t = a[i] % m;
for (int j = 0; j < 11; j ++ )
{
s[j][(int) t] ++ ;
t = t * 10 % m;
}
}
long res = 0;
for (int i = 0; i < n; i ++ )
{
long t = a[i] % m; //求a[i]的余数
int len = String.valueOf(a[i]).length();
res += s[len][(int) ((m - t) % m)];
long r = t;
while (len -- >0) r = r * 10 % m; //求a[j]的余数，同上面的预处理求法一样
if (r == (m - t) % m) res -- ; //判重
}
System.out.println(res);
}
}
第十一届第二场
A. 门牌制作 624
public class Main {
static int res;
public static void main(String[] args) {
for (int i = 1; i <= 2020; i++)
{
int num = i;
while(num >0)
{
if(num % 10 == 2) res++;
num /= 10;
}
}
System.out.println(res);
}
}
B. 寻找2020 16520
就硬暴力
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int n = 300, m = 300; //m其实就是input.length()
static long res;
static int[][] g = new int[1000][1000];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input;
for (int i = 0; i < n; i++)
{
input = br.readLine();
for (int j = 0; j < m; j++)
{
g[i][j] = input.charAt(j) - '0';
}
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m - 3; j++)
{
if(g[i][j] == 2 && g[i][j + 1] == 0 && g[i][j + 2] == 2 && g[i][j + 3] == 0) res++;
}
}
for(int j = 0; j < m; j++)
{
for(int i = 0; i < n - 3; i++)
{
if(g[i][j] == 2 && g[i + 1][j] == 0 && g[i + 2][j] == 2 && g[i + 3][j] == 0) res++;
}
}
for(int i = 0; i < n - 3; i++)
{
for(int j = 0; j < m - 3; j++)
{
if(g[i][j] == 2 && g[i + 1][j + 1] == 0 && g[i + 2][j + 2] == 2 && g[i + 3][j + 3] == 0) res++;
}
}
System.out.println(res);
}
}
C. 蛇形填数 761
多画一些，找规律
public class Main {
static int n = 20, res = 1;
public static void main(String[] args) {
for (int i = 1; i <= n - 1; i++)
{
res += 4 * i;
}
System.out.println(res);
}
}
D. 七段码 80
DFS 参考了这篇 题解
public class Main {
static int N = 10;
static boolean[] st = new boolean[N]; //亮不亮
static boolean[][] g = new boolean[N][N]; //邻接矩阵
static int[] p = new int[N]; //并查集
static int res = 0;
static int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
static void dfs(int u)
{
if(u > 7)
{
for (int i = 1; i <= 7; i++) p[i] = i; //初始化并查集
for(int i = 1; i <= 7; i++)
for(int j = 1; j <= 7; j++)
{
//如果i和j联通而且i和j是同时亮着的,则将i和j并为一个集合
if(g[i][j] && st[i] && st[j])
{
int a = find(i), b = find(j);
if(a != b) p[a] = b;
}
}
int t = 0; //计算点亮的所有总共有多少个连通块
for (int i = 1; i <= 7; i++)
{
if(p[i] == i && st[i]) t++;
}
if(t == 1) res++; //如果仅有一个连通，则说明符合题意，可行
return;
}
st[u] = true; //开灯
dfs(u + 1);
st[u] = false; //不开灯
dfs(u + 1);
}
public static void main(String[] args) {
/*
连边建图，e[i][j]==1表示i和j相邻
a b c d e f g
1 2 3 4 5 6 7
a bf
b acg
c bdg
d ce
e dfg
f aeg
g bcef
*/
g[1][2] = g[1][6] = true;
g[2][1] = g[2][3] = g[2][7]=true;
g[3][2] = g[3][4] = g[3][7]=true;
g[4][3] = g[4][5] = true;
g[5][4] = g[5][6] = g[5][7]=true;
g[6][1] = g[6][5] = g[6][7]=true;
g[7][2] = g[7][3] = g[7][5] = g[7][6] = true;
dfs(1);
System.out.println(res);
}
}
E. 排序 jonmlkihgfedcba
参考了这篇 文章
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int v, n, remain;
static char[] c = new char[30];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
v = Integer.parseInt(input[0]);
for (int i = 1; i < v; i++)
{
if(i * (i - 1) > 2 * v)
{
n = i;
break;
}
}
remain = n * (n - 1) / 2 - v;
for (int i = 1; i <= n; i++)
{
c[i] = (char) ('a' + (n - i));
}
for (int i = remain + 1; i >= 2; i--)
{
char t = c[i];
c[i] = c[i - 1];
c[i - 1] = t;
}
for (int i = 1; i <= n; i++)
{
System.out.print(c[i]);
}
}
}
F. 成绩分析
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int n, max = -Integer.MAX_VALUE, min = Integer.MAX_VALUE, sum;
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++)
{
input = br.readLine().split(" ");
int num = Integer.parseInt(input[0]);
max = Math.max(max, num);
min = Math.min(min, num);
sum += num;
}
System.out.println(max);
System.out.println(min);
double avg = (double)sum / n; //别忘记转类型
System.out.println(String.format("%.2f", avg)); //不是%.2d
}
}
G. 单词分析
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 30, max = -Integer.MAX_VALUE;
static int[] cnt = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
char[] input = br.readLine().toCharArray();
int len = input.length;
for (int i = 0; i < len; i++)
{
int index = input[i] - 'a' + 1;
cnt[index]++;
max = Math.max(max, cnt[index]);
}
for (int i = 1; i <= 26; i++) //小于等于26，而不是len
{
if(cnt[i] == max)
{
System.out.println((char)('a' + i - 1));
System.out.println(cnt[i]);
return;
}
}
}
}
H. 数字三角形
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 110;
static int n;
static int[][] g = new int[N][N];
static int[][] f = new int[N][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 i = 1; i <= n; i++)
{
input = br.readLine().split(" ");
for (int j = 1; j <= i; j++)
{
g[i][j] = Integer.parseInt(input[j - 1]);
}
}
//范围最小是0，所以可以不写
for (int i = 1; i <= n; i++) Arrays.fill(f[i], -Integer.MAX_VALUE);
f[1][1] = g[1][1];
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++)
{
f[i][j] = g[i][j] + Math.max(f[i - 1][j], f[i - 1][j - 1]);
}
//多画几个找规律：n是奇数时，一定会走到中间那个数；n是偶数时，会走到中间两个数，所以取一个最大值。
if(n % 2 == 1) System.out.println(f[n][n / 2 + 1]);
else
{
int ans = Math.max(f[n][n / 2], f[n][n / 2 + 1]);
System.out.println(ans);
}
}
}
I. 子串分值和
暴力 TLE 60分
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
public class Main {
static int N = 100010;
static int[] s = new int[N];
static long res;
static HashSet<Character> hs= new HashSet<>(); //char的封装类型
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
char[] str = br.readLine().toCharArray();
int start = 0, len = str.length;
while(true)
{
for(int i = start;i < len; i++)
{
hs.add(str[i]);
res += hs.size();
}
start++;
hs.clear();
if(start >= len) break;
}
System.out.println(res);
}
}
正确写法100分，很难想。参考了一篇写的很好的题解
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
public class Main {
static int N = (int) (1e5+10);
static char[] s = new char[N];
static long f[] = new long[N]; //预处理会爆int
static int[] last = new int[30];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
s = ("0"+br.readLine()).toCharArray(); //把第一个字符占了
int n = s.length - 1;
long ans = 0;
//预处理没有任何重复的情况；
for(int i=1;i<=n-i+1;i++) f[i] = f[n-i+1] = (n-i+1)*(long)i; //注意乘的时候一定要转long
//统计总贡献，并去重
for(int i = 1;i<=n;i++)
{
int t = s[i]-'a';
if(last[t] == 0)
{ //判断有无重复部分
ans += f[i];
}
else
{
ans += f[i] - f[i] / i*last[t]; //减去重复部分；
}
last[t] = i; //记录当前字母最后出现位置
}
System.out.println(ans);
}
}
j. 装饰珠
太复杂了，不会。
B. 既约分数 (C++组)
public class Main {
static long res;
static int gcd(int a, int b)
{
return b != 0 ? gcd(b, a % b) : a;
}
public static void main(String[] args) {
for (int i = 1; i <= 2020; i++)
for (int j = 1; j <= 2020; j++)
{
if(gcd(i, j) == 1) res++;
}
System.out.println(res);
}
}
D. 跑步锻炼 (C++组)
这种处理年份的方式挺好用的。
public class Main {
static int[] M = {0,31,28,31,30,31,30,31,31,30,31,30,31};
public static void main(String[] args) {
int y = 2000, m = 1, d = 1, w = 6, ans = 2; //第一天先算上
while(true)
{
if(y % 400 == 0 || y % 4 == 0 && y % 100 != 0) M[2] = 29;
else M[2] = 28;
d++;
w = (w + 1) % 7; //w为0为星期天
if(d > M[m])
{
d = 1;
m++;
}
if(m > 12)
{
m = 1;
y++;
}
if(d == 1 || w == 1) ans++;
ans++;
if(y == 2020 && m == 10 && d == 1) //在每个循环的最后判断一下比较好
{
System.out.println(ans);
return;
}
}
}
}
G. 回文日期 (C++组)
也可以用StringBulider类reverse字符串，也能满分，但会慢好几倍。
题干中的89991231只是输入的最大值，而不是输出结果的最大值，所以根本不需要加这个限制。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int[] days = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
static boolean check_valid(int year, int month, int day)
{
if(year % 400 == 0 || year % 4 == 0 && year % 100 != 0)
{
days[2] = 29;
}
else days[2] = 28;
if(month <= 0 || month > 12) return false; //小于等于
if(day <= 0 || day > days[month]) return false; //小于等于
return true;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int start = Integer.parseInt(input[0]);
boolean flag = true;
for (int i = 1000; i <= 9999; i++)
{
int date = i, x = i;
for (int j = 0; j < 4; j++) //扩展为回文
{
date = date * 10 + x % 10;
x /= 10;
}
int month = date % 10000 / 100;
int day = date % 100;
if(date >= start + 1 && check_valid(i, month, day))
{
if(flag)
{
System.out.println(date);
flag = false;
}
if((i / 100 == i % 100) && (i / 1000 != i % 10))
{
System.out.println(date);
return;
}
}
}
}
}
I. 平面切分 (C++组)
参考了一篇写的很好的题解
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.TreeSet;
public class Main {
static int n, res = 1; //本来就有一部分
static double a, b;
static Comparator<double[]> cmp = new Comparator<double[]>() {
@Override
public int compare(double[] o1, double[] o2) {
if(o1[0] != o2[0])
{
if(o1[0] - o2[0] >0) return 1;
if(o1[0] - o2[0] <0) return -1;
}
else if(o1[1] != o2[1])
{
if(o1[1] - o2[1] >0) return 1;
if(o1[1] - o2[1] <0) return -1;
}
return 0;
//double的comparator不能像之前那样直接return
//if(o1[0] != o2[0]) return (int)(o1[0] - o2[0]);
//return (int)(o1[1] - o2[1]);
}
};
static TreeSet<double[]> set1 = new TreeSet<>(cmp);
static TreeSet<double[]> set2 = new TreeSet<>(cmp);
static void compute(double a, double b)
{
set2.clear();
double x, y; //交点坐标
for(double[] p : set1) //枚举的是斜率、边距，而不是点！
{
if(a != p[0])
{
x = (p[1] - b) / (a - p[0]);
y = a * x + b;
set2.add(new double[]{x, y});
}
}
res += set2.size();
}
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]);
while(n-- >0)
{
input = br.readLine().split(" ");
a = Double.parseDouble(input[0]);
b = Double.parseDouble(input[1]);
int size1 = set1.size();
set1.add(new double[]{a, b});
if(size1 < set1.size()) //不是重边，数目必+1
{
res++;
compute(a, b);
}
}
System.out.println(res);
}
}
第十届
A. 组队 490
手动算吧，不麻烦。但是要注意一个队员只能选中一次。
B. 不同子串 100
只要没有重复的，都用set做，很舒服。
注意 i 和 j 位置要写对。犯了好几次错误导致死循环了，我反思。
import java.util.HashSet;
public class Main {
static String str = "0100110001010001";
static HashSet<String> hs = new HashSet<String>();
public static void main(String[] args) {
for (int i = 0; i < str.length(); i++)
for (int j = i; j < str.length(); j++)
{
hs.add(str.substring(i, j + 1)); //substring会截到第二个参数-1
}
System.out.println(hs.size());
}
}
C. 数列求值 4659
注意运算过程只和每个数的后四位有关系，所以要取模，不然long都会爆。
public class Main {
static long[] num = new long[30000000];
static long[] num2 = new long[30000000];
//法二：递归，但递归不了一万以上层。
static long f(int i)
{
if(num2[i] != 0) return num2[i];
if(i <= 3) return 1;
else return num2[i] = (f(i - 1) % 10000 + f(i - 2) % 10000 + f(i - 3) % 10000) % 10000;
}
public static void main(String[] args)
{
//法一：递推
num[1] = num[2] = num[3] = 1;
for(int i = 4; i <= 20190324; i++)
{
num[i] = num[i - 1] + num[i - 2] + num[i - 3];
num[i] %= 10000; //必须取模，不然不够存
}
System.out.println(num[20190324]);
//System.out.println(f(20193024));
}
}
D. 数的分解
用indexof()做，就很舒服。
但要注意，因为取到的数字“各不相同”，而且顺序不影响，所以这三个数各自的范围要注意。
public class Main {
public static void main(String[] args) {
int res = 0;
for (int i = 1; i <= 2019; i++)
for (int j = i + 1; j <= 2019; j++)
{
int k = 2019 - i - j;
if(k <= j) continue; //还有等于的情况也不能要，切记
int sumi = String.valueOf(i).indexOf('2') + String.valueOf(i).indexOf('4');
int sumj = String.valueOf(j).indexOf('2') + String.valueOf(j).indexOf('4');
int sumk = String.valueOf(k).indexOf('2') + String.valueOf(k).indexOf('4');
if(sumi + sumj + sumk == -6) res++;
}
System.out.println(res);
}
}
E. 迷宫 答案太长了
和 走迷宫 这道题大同小异。
注意：因为BFS迷宫是逆序找通路的，最后输出的答案也必须逆序输出。
DLRU的遍历顺序不能变，还有题干输入也有些刁钻，需要注意。
另外，分享一下在网上看到的 Excel大法
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class Pair
{
int x, y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int N = 52;
static int n, m;
static int[][] map = new int[N][N];
static int[][] d = new int[N][N];
static Pair[][] pre= new Pair[N][N];
static Queue<Pair> q = new LinkedList<Pair>();
static int dx[] = {1, 0, 0, -1};
static int dy[] = {0, -1, 1, 0};
static int idx;
static char[] ans = new char[1510];
static void bfs()
{
q.offer(new Pair(0, 0));
while(q.size() >0)
{
Pair now = q.poll();
for (int i = 0; i < 4; i++)
{
int x = now.x + dx[i], y = now.y + dy[i];
if(x < 0 || x >= n || y < 0 || y >= m) continue;
if(map[x][y] == 1 || d[x][y] != 0) continue;
d[x][y] = d[now.x][now.y] + 1;
pre[x][y] = new Pair(now.x, now.y);
q.offer(new Pair(x, y));
}
}
int x = n - 1, y = m - 1;
/*
D 1,0
L 0,-1
R 0,1
U -1,0
*/
while(x != 0 || y != 0) //不是并且
{
Pair temp = pre[x][y];
int prex = pre[x][y].x, prey = pre[x][y].y;
if(x - prex == 1) ans[idx] = 'D';
else if (x - prex == -1) ans[idx] = 'U';
else if(y - prey == -1) ans[idx] = 'L';
else if(y - prey == 1) ans[idx] ='R';
idx ++;
x = prex; //别忘了回溯
y = prey;
}
}
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 = 0; i < n; i++)
{
input = br.readLine().split(" ");
for (int j = 0; j < input[0].length(); j++) map[i][j] = input[0].charAt(j) - '0'; //char转int
}
bfs();
for(int i = idx -1; i >=0; i--) System.out.print(ans[i]);
}
}
F. 特别数的和
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int n, res;
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 = 1; i <= n; i++)
{
String num = String.valueOf(i);
int sum = num.indexOf('2') + num.indexOf('0') + num.indexOf('1') + num.indexOf('9');
if(sum > -4) res += i;
}
System.out.println(res);
}
}
G. 外卖店优先级
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, m, T;
static int[] score = new int[N], last = new int[N];
static boolean[] st = new boolean[N]; //是否在优先缓存
static ArrayList<int[]> order = new ArrayList<>();
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]);
T=Integer.parseInt(input[2]);
for (int i = 0; i < m; i ++ )
{
input = br.readLine().split(" ");
int ts = Integer.parseInt(input[0]);
int id = Integer.parseInt(input[1]);
order.add(new int[]{ts, id});
}
order.sort((o1,o2)->{
if (o1[0] != o2[0]) return o1[0] - o2[0];
return o1[1] - o2[1];
});
for (int i = 0; i < m;)
{
int j = i;
//把没有订单的情况统一到，下一次有订单的时刻处理，然后最后的一段到T时刻处理。
//当id相等时，时刻增加。因为同一时刻会有很多个订单，一次处理一批相同的订单。
//不能写order.get(j) == order.get(i)，或者equal
while (j < m && order.get(j)[1] == order.get(i)[1]) j ++ ;
int t = order.get(i)[0], id = order.get(i)[1], cnt = j - i; //(j - 1) - i + 1
i = j;
score[id] -= t - last[id] - 1;
if (score[id] < 0) score[id] = 0;
if (score[id] <= 3) st[id] = false; // 以上处理的是t时刻之前的信息
score[id] += cnt * 2;
if (score[id] > 5) st[id] = true;
last[id] = t;
}
for (int i = 1; i <= n; i ++ )
if (last[i] < T) //T时刻没有订单
{
score[i] -= T - last[i]; //注意这里不用-1
if (score[i] <= 3) st[i] = false;
}
int res = 0;
for (int i = 1; i <= n; i ++ )
{
if(st[i]) res++;
}
System.out.println(res);
}
}
H. 人物相关性分析
TLE 能过9/10个数据
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Main {
static int k, res;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
k = Integer.parseInt(input[0]);
String s = br.readLine();
List<Integer> Alice = new ArrayList();
List<Integer> Bob = new ArrayList();
StringBuilder tem = new StringBuilder();
int len = s.length();
for(int i = 0; i < len; i++)
{
if(!(Character.isLetter(s.charAt(i)))) //相当于把分好的一段拿出来判断
{
String str = tem.toString();
if(str.equals("Alice")) Alice.add(i - tem.length());
if(str.equals("Bob")) Bob.add(i - tem.length());
tem.delete(0, tem.length());
}
else //是字母就加入
{
tem.append(s.charAt(i));
}
}
for (int i = 0; i < Alice.size(); i++)
for (int j = 0; j < Bob.size(); j++)
{
//别忘记单词本身还有长度，我们要算的是两者之间的距离
if(Alice.get(i) < Bob.get(j))
{
if(Bob.get(j) - Alice.get(i) - 5 <= k) res++;
}
else
{
if(Alice.get(i) - Bob.get(j) - 3 <= k) res++;
}
}
System.out.println(res);
// long res = 0;
// int n = Alice.size();
// int m = Bob.size();
// int l = 0, r = m - 1 ;
// for(int i = 0; i < n; i++)
// {
// while(l < m && Bob.get(l) < Alice.get(i) - k -3 ) l++;
//
// r = l;
//
// while(r < m && Bob.get(r) <= Alice.get(i) + 5 + k ) r++;
//
// if(r - l > 0) res += r - l;
// }
// System.out.println(res);
}
}
I. 后缀表达式
1.树的后序遍历就是表达式
2.初步考虑时，我们想的是尽可能减负数，加正数
3.后来发现，如果有减号的话，可以通过加括号，变成1~m+n个减号，同样加号也是。
4.至少一个减号和加号，减的话尽可能减最小值，加的话尽可能加最大值
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 200010;
static int n, m;
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]);
m=Integer.parseInt(input[1]);
int k = n + m + 1;
input=br.readLine().split(" ");
for (int i = 0; i < k; i ++ ) a[i] = Integer.parseInt(input[i]);
long res = 0;
//m等于0，即全是加号，并且没法产生减号，所以else中的情况就不适用了，需要特判。
//而n=0，即全是减号的情况就没影响，因为减号可以产生加号。
if (m == 0)
{
for (int i = 0; i < k; i ++ ) res += a[i];
}
else
{
Arrays.sort(a, 0, k); // 也可以不排序，找出最大值和最小值即可
res = a[k - 1] - a[0];
for (int i = 1; i < k - 1; i ++ ) res += Math.abs(a[i]); //必须加绝对值
}
System.out.println(res);
}
}
J. 灵能传输
太难了不会做
B. 年号字串 (C++组)
这道题实际上就是进制转换，将10进制转换为26进制。
想把对应的数字转换成对应的字母，(char)('A' + i - 1),这里就将数字i转换成了对应的第i个字母（i = 1~26）
另外，如果不会做可以拖动Excel
public class Main {
public static void main(String[] args) {
int n = 2019; //52
char a;
StringBuilder res = new StringBuilder();
while(n > 0)
{
if(n % 26 == 0) //1~25都能映射，但 %26=0，需要特判
{
res.append('Z');
n = n / 26 - 1;
}
else
{
a = (char)('A' + n % 26 - 1);
res = res.append(a);
n /= 26;
}
}
System.out.println(res.reverse().toString());
}
}
G. 完全二叉树的权值 (C++组)
注意：+、-运算符的优先级高于<< >>位移运算符
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 100010;
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 = 1; i <= n; i ++ )
{
a[i] = Integer.parseInt(input[i-1]);
}
//s最坏情况下是几万个大小在 −10^5∼10^5 的数的和，可能会溢出int。
long maxs = (long) -1e18; //-10^18
int depth = 0;
//求从i开始，长度是 2^(d-1) 即 1 << d - 1 的总和。
for (int d = 1, i = 1; i <= n; i *= 2, d ++ )
{
long s = 0;
//j <= n 是因为最后一层可能不全
for (int j = i; j < i + (1 << d - 1) && j <= n; j ++ )
s += a[j];
if (s > maxs)
{
maxs = s;
depth = d;
}
}
System.out.println(depth);
}
}
H. 等差数列 (C++组)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 100010;
static int[] a = new int[N];
static int gcd(int a, int b) //欧几里得算法!
{
return b != 0 ? gcd(b, a % b) : a;
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
int n = Integer.parseInt(input[0]);
input=br.readLine().split(" ");
for (int i = 0; i < n; i ++ ) a[i] = Integer.parseInt(input[i]);
Arrays.sort(a, 0, n);
int d = 0;
for (int i = 1; i < n; i ++ ) d = gcd(d, a[i] - a[0]);
if (d == 0) System.out.println(n); //说明是常数数列，直接输出数量。
else System.out.println((a[n - 1] - a[0]) / d + 1); //等差数列求项数的公式, 是a[n-1]而不是a[n]
}
}
第九届
A. 第几天
打开电脑日历数 125
B. 方格计数
对1/4的正半轴圆进行暴力枚举每个方格，这里我们可以转换下关注点，用右上角的点代表一个方格。
public class Main {
static int d = 1000;
static long res;
public static void main(String[] args) {
//求的是完整的小方格，看图，不能从0开始枚举
for (int i = 1; i <= d; i++)
for (int j = 1; j <= d; j++)
{
if(i * i + j * j <= d * d) res++;
}
System.out.println(res * 4);
}
}
C. 复数幂
答案的长度实在是太长了，以至于控制台都打不出来，输出到文件里了。
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) throws FileNotFoundException {
//(a+bi)*(c+di) = (a*c - b*d) + (a*d + b*c)i
BigInteger a = BigInteger.valueOf(2);
BigInteger b = BigInteger.valueOf(3);
BigInteger c = BigInteger.valueOf(2);
BigInteger d = BigInteger.valueOf(3);
for (int i = 1; i <= 123456; i++)
{
BigInteger A = a.multiply(c).subtract(b.multiply(d));
BigInteger B = a.multiply(d).add(b.multiply(c));
a = A;
b = B;
}
// PrintStream out = System.out;
// System.setOut(out); //输入到控制台里
PrintStream ps = new PrintStream(new File("ans.txt")); //默认在项目的路径
System.setOut(ps); //输出在ans.txt里
if(b.compareTo(BigInteger.valueOf(-1)) == -1) System.out.println(a.toString() + b.toString() + "i");
else System.out.println(a + "+" + b + "i");
}
}
D. 测试次数
DP问题不好想，这篇 题解 写的非常好
E. 快速排序
看这篇 题解
F. 递增三元组
1.暴力三重循环会超时，不过在蓝桥好像能拿62分
2.前缀和这个做法必须保证 每个数比较小
3.思路：先枚举B，AC的取值只和B有关系，AC之间没限制。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 100010;
static int n;
static int[] a = new int[N], b = new int[N], c = new int[N];
static int[] as = new int[N]; // as[i]表示在A[]中有多少个数小于b[i]
static int[] cs = new int[N]; // cs[i]表示在C[]中有多少个数大于b[i]
static int[] cnt = new int[N], s = 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]);
//前缀和中由于有 -1 这个操作(s[i - 1])，
//因此在做前缀和的时候尽可能把所有数变成从1开始的数，这样能少处理一些边界情况。
//在这道题里，前缀和是和数值有关系的，数据范围是0~10^5，因为看的是相对大小，所以+1不影响。
input=br.readLine().split(" ");
for (int i = 0; i < n; i ++ )
{
a[i] = Integer.parseInt(input[i]);
a[i]++;
}
input=br.readLine().split(" ");
for (int i = 0; i < n; i ++ )
{
b[i] = Integer.parseInt(input[i]);
b[i]++;
}
input=br.readLine().split(" ");
for (int i = 0; i < n; i ++ )
{
c[i] = Integer.parseInt(input[i]);
c[i]++;
}
//求as[]
for (int i = 0; i < n; i ++ ) cnt[a[i]] ++ ;
// 求cnt[]的前缀和。+1后a[i]都>0，所以从1开始循环
// 是N而不是n，是因为a[i]数值可能会很大，但不会超过N
for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i];
for (int i = 0; i < n; i ++ ) as[i] = s[b[i] - 1];
//求cs[]之前 先把俩数组清空
Arrays.fill(cnt, 0); //memset(cnt, 0, sizeof cnt);
Arrays.fill(s, 0); //memset(s, 0, sizeof s);
for (int i = 0; i < n; i ++ ) cnt[c[i]] ++ ;
for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i];
for (int i = 0; i < n; i ++ ) cs[i] = s[N - 1] - s[b[i]];
//枚举每个b[i]，因为三元组最多是有n^3，可能会爆int。
long res = 0;
//因为每个数都可能有10^5，俩书相乘就是10^10。可能大于2*10^9。所以用转换。
//每个Bj枚举的结果中，有多少个Ai满足要求，多少个Ck满足要求，再相乘，就是方案个数。
for (int i = 0; i < n; i ++ ) res += (long)as[i] * cs[i];
System.out.println(res);
}
}
G. 螺旋折线
优雅解决版：最外层右上角点为4k^2，求一下到这个点的曼哈顿距离就行了
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 x=Integer.parseInt(input[0]);
int y=Integer.parseInt(input[1]);
long k = Math.max(Math.abs(x), Math.abs(y));
if(x >= y) System.out.println(4 * k * k + Math.abs(x - k) + Math.abs(y - k));
else if(x < y) System.out.println(4 * k * k - Math.abs(x - k) - Math.abs(y - k));
}
}
H. 日志统计
1.双指针相当于一个长度为d-1的滑动窗口在移动，当logs[i].x - logs[j].x >= d，这时候超出了临界，所以尾部要裁剪掉，所以cnt[logs[i].y]--，相当于舍弃掉尾部的记录，同时j++,缩小窗口的宽度以符合要求。
2.简而言之 i 在前面跑 j 在后面跟
3.用class和用int[]的耗时差别不是很大，class能快几十毫秒
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
class Logs
{
int time,id;
Logs(int time, int id) {
this.time = time;
this.id = id;
}
}
public class Main {
static int N = 100010;
static int n, d, k;
static ArrayList<Logs> logs = new ArrayList<>();
static int[] cnt = 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]);
d=Integer.parseInt(input[1]);
k=Integer.parseInt(input[2]);
for (int i = 0; i < n; i ++ )
{
input=br.readLine().split(" ");
int time=Integer.parseInt(input[0]);
int id=Integer.parseInt(input[1]);
logs.add(new Logs(time, id)); //类数组不能直接赋值，必须new！
}
logs.sort((o1,o2)->{ //必须写 != ，写 < 答案不对
if(o1.time != o2.time) return o1.time - o2.time;
else return o1.id - o2.id;
});
for (int i = 0, j = 0; i < n; i ++ )
{
int id = logs.get(i).id;
cnt[id] ++ ;
while (logs.get(i).time - logs.get(j).time >= d) //用if不对
{
cnt[logs.get(j).id] -- ;
j ++ ;
}
if (cnt[id] >= k) st[id] = true; //曾是热帖
}
for (int i = 0; i <= 100000; i ++ ) //并不知道id范围，所以全遍历一遍。
if (st[i])
System.out.println(i);
}
}
I. 全球变暖
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N = 1010;
static int n, res;
static char[][] g = new char[N][N];
static boolean[][] st = new boolean[N][N];
static Queue<int[]> q = new LinkedList<int[]>();
static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, 1, -1};
static boolean bfs(int i, int j)
{
int total = 0, bound = 0; //所有单元的数量和边界的数量
q.offer(new int[]{i, j}); //入队
st[i][j] = true; //标记访问过
while(q.size() >0)
{
int[] point = q.poll();
total ++;
boolean is_bound = false;
for (int k = 0; k < 4; k++) //判断当前点是否是边界，并把相邻的陆地加入到队列。
{
int x = point[0] + dx[k], y = point[1] + dy[k];
if(x < 0 || x >= n || y < 0 || y >= n) continue;
if(st[x][y]) continue; //访问过的陆地
if(g[x][y] == '.')
{
is_bound = true;
continue;
}
q.offer(new int[]{x, y});
st[x][y] = true;
}
if(is_bound) bound ++;
}
return total == bound;
}
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] = br.readLine().toCharArray();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
if(!st[i][j] && g[i][j] == '#') //未访问过并且是陆地，则广搜整块大陆。
{
if(bfs(i, j)) res++; //整块大陆全是边界，答案+1
}
}
System.out.println(res);
}
}
J. 堆的计数
不会做
B.明码 (C++组)
题出的很有创意，下次不要这么出了。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input;
int x, y;
while(true)
{
input = br.readLine().split(" ");
for (int i = 0; i < input.length; i += 2)
{
x = Integer.parseInt(input[i]);
y = Integer.parseInt(input[i + 1]);
//转为二进制
String xx = Integer.toBinaryString(x);
String yy = Integer.toBinaryString(y);
//补零，同时防止暴int
String fx = String.format("%08d", new BigInteger(xx));
String fy = String.format("%08d", new BigInteger(yy));
//输出，防止负数转成的二进制过长。
for (int j = fx.length() - 8; j < fx.length(); j++)
{
if(fx.charAt(j) == '0') System.out.print(" ");
else System.out.print("*");
}
for (int j = fy.length() - 8; j < fy.length(); j++)
{
if(fy.charAt(j) == '0') System.out.print(" ");
else System.out.print("*");
}
System.out.println();
}
}
}
}
C. 乘积尾零 (C++组)
参考了这篇 题解
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;
int n = 10;
int sum5 = 0, sum2 = 0;
for (int i = 0; i < n; i++)
{
input = br.readLine().split(" ");
for (int j = 0; j < n; j++)
{
int num = Integer.parseInt(input[j]);
while(num % 5 == 0)
{
sum5++;
num /= 5;
}
while(num % 2 == 0)
{
sum2++;
num /= 2;
}
}
}
System.out.println(Math.min(sum5, sum2));
}
}
J. 乘积最大 (C++组)
之前写的 题解 ，还是有点没搞明白。
第八届
A. 购物单
各项相乘求和
B. 纸牌三角形
参考了这篇 题解
public class Main {
static int n, res;
static int[] path = new int[10];
static boolean[] st = new boolean[10];
static void dfs(int u)
{
if(u == n)
{
int A = path[0] + path[1] + path[2] + path[3];
int B = path[3] + path[4] + path[5] + path[6];
int C = path[6] + path[7] + path[8] + path[0];
if(A == B && B == C) res++;
return;
}
for (int i = 1; i <= n; i++)
{
if(!st[i])
{
path[u] = i;
st[i] = true;
dfs(u + 1);
st[i] = false;
path[u] = 0;
}
}
}
public static void main(String[] args) {
n = 9;
dfs(0);
System.out.println(res / 3 / 2);
}
}
C. 承压计算
参考了这篇 题解
记得最后通过max和min转成电子称的单位。
输入：
7
5 8
7 8 8
9 2 7 2
8 1 4 9 1
8 1 8 8 4 1
7 9 6 1 4 5 4
5 6 5 5 6 9 5 6
5 5 4 7 9 3 5 5 1
7 5 7 9 7 4 7 3 3 1
4 6 4 5 5 8 8 3 2 4 3
1 1 3 3 1 6 6 5 5 4 4 2
9 9 9 2 1 9 1 9 2 9 5 7 9
4 3 3 7 7 9 3 6 1 3 8 8 3 7
3 6 8 1 5 3 9 5 8 3 8 1 8 3 3
8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9
8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4
2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9
7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6
9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3
5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9
6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4
2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4
7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6
1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3
2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8
7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9
7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6
5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 50;
static int n = 30;
static double[][] a = new double[N][N];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input;
for (int i = 1; i <= n; i++)
{
if(i <= n - 1)
{
input = br.readLine().split(" ");
for (int j = 1; j <= i; j++)
{
a[i][j] = Double.parseDouble(input[j - 1]);
a[i][j] += a[i - 1][j - 1] / 2 + a[i - 1][j] / 2;
}
}
else
{
for (int j = 1; j <= i; j++)
{
a[i][j] += a[i - 1][j - 1] / 2 + a[i - 1][j] / 2;
}
}
}
double min = Double.MAX_VALUE, max = -Double.MAX_VALUE;
for (int i = 1; i <= n; i++)
{
max = Math.max(max, a[30][i]);
min = Math.min(min, a[30][i]);
}
//System.out.println("max="+max+" min="+min);
System.out.println(2086458231 / min * max);
}
}
D. 魔方状态
不会
E. 取数位
f(x/10,k)
F. 最大公共子串
a[i-1][j-1]+1
G. 日期问题
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
static boolean check_valid(int year, int month, int day)
{
if (month == 0 || month > 12) return false;
if (day == 0) return false;
if (month != 2)
{
if (day > days[month]) return false;
}
else
{
int leap = 0;
if(year % 100 != 0 && year % 4 == 0 || year % 400 == 0) leap = 1; //注意!0
if (day > 28 + leap) return false;
}
return true;
}
public static void main(String[] args) throws IOException {
int a, b, c;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split("/");
a=Integer.parseInt(input[0]);
b=Integer.parseInt(input[1]);
c=Integer.parseInt(input[2]);
for (int date = 19600101; date <= 20591231; date ++ )
{
int year = date / 10000, month = date % 10000 / 100, day = date % 100;
if (check_valid(year, month, day))
{
if (year % 100 == a && month == b && day == c || // 年/月/日
month == a && day == b && year % 100 == c || // 月/日/年
day == a && month == b &&year % 100 == c) // 日/月/年
System.out.println(year+"-"+String.format("%02d", month)+"-"+String.format("%02d", day));
}
}
}
}
H. 包子凑数
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 10010; //经验值
static int[] a = new int[110];
static boolean[][] f = new boolean[110][N];
static int gcd(int a, int b)
{
return b!=0 ? gcd(b, a % b) : a;
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
int n = Integer.parseInt(input[0]);
int d = 0;
for (int i = 1; i <= n; i ++ )
{
input=br.readLine().split(" ");
a[i] = Integer.parseInt(input[0]);
d = gcd(d, a[i]);
}
if (d != 1) System.out.println("INF");
else
{
f[0][0] = true; //边界：一个物品都没有，总共的和为0，合法。
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < N; j ++ )
{
f[i][j] = f[i - 1][j]; //第一项一定存在
if (j >= a[i]) f[i][j] |= f[i][j - a[i]]; //第二项不一定存在，用“或”
}
int res = 0; //统计的是前n个物品当中，不能用1-N凑出来的数的个数
for (int i = 0; i < N; i ++ )
if (!f[n][i])
res ++ ;
System.out.println(res);
}
}
}
1.最大公约数不是1，那就有无限个凑不出来的；是1，则凑不出来的数是有限个。
2.根据裴蜀定理(视频里的证明，有点复杂)，只要最大公约数是1，就一定有解。
3.根据经验，这道题问的是1到1万(经验值)之间，不能被A1~An凑出来的数字的个数是多少
4.补充：
完全背包：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
多重背包：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
5.本题本质是完全背包问题(因为无限笼)。 把总和(要凑的数)看成背包容量。把每一个数Ai看成物品的体积、
6.状态计算：第i件物品选1、2 … 最多选⌊j/i⌋个。
7.完全背包的最终公式，和01背包的唯一区别：01背包是f(i-1, j-A)，完全背包是f(i,j-A)
8.因为第i层的第j个状态，只依赖于第i层自身和第i-1层，所以可以变成一维数组，进行空间优化。(不过还是得先把二维的写出来，一维的不好理解)
9.用“或”的原因：属性是是否为空，只看有没有就可以。
优化空间版
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 10010; //经验值
static int[] a = new int[110];
static boolean[] f = new boolean[N];
static int gcd(int a, int b)
{
return b!=0 ? gcd(b, a % b) : a;
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] input=br.readLine().split(" ");
int n = Integer.parseInt(input[0]);
int d = 0;
for (int i = 1; i <= n; i ++ )
{
input=br.readLine().split(" ");
a[i] = Integer.parseInt(input[0]);
d = gcd(d, a[i]);
}
if (d != 1) System.out.println("INF");
else
{
f[0] = true; //边界：一个物品都没有，总共的和为0，合法。
for (int i = 1; i <= n; i ++ ) //01背包的话从大到小循环
for (int j = a[i]; j < N; j ++ )
f[j] |= f[j - a[i]]; //j-a[i]比j小，先算出来。
int res = 0; //统计的是前n个物品，不能用1-N凑出来的数的个数
for (int i = 0; i < N; i ++ )
if (!f[i])
res ++ ;
System.out.println(res);
}
}
}
I. 分巧克力
关于二分:
如果想找最小值(左端点)，就用 r=mid
如果想找最大值(右端点)，就用 l=mid
最后结果 l 和 r 都一样
二分两个模板:
/*
* 小巧克力边长 a 一定在 1 – 100000 之间。
答案即为：在 1 – 100000 之间找到一个最大的数，
使得所有的 (w[i]/a) * (h[i]/a) 之和大于要求的数量 k。
使用二分法找到a的最大取值即为答案。
* */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 100010;
static int n, k;
static int[] h = new int[N], w = new int[N];
static boolean check(int mid)
{
int res = 0;
for (int i = 0; i < n; i ++ )
{
//每一大块可以分成的边长为mid的巧克力数量
//不能写成: num +=((w[i]h[i])/(lenlen));；
//因为整数除法存在小数截取，(4 / 3) * (4 / 3) = 1 而 (4* 4) / (3 * 3) = 0
//即乘积的下取整跟下取整的乘积不一样。
res += (h[i] / mid) * (w[i] / mid);
if (res >= k) return true;
}
return false;
}
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]);
k=Integer.parseInt(input[1]);
for (int i = 0; i < n; i ++ )
{
input=br.readLine().split(" ");
h[i]=Integer.parseInt(input[0]);
w[i]=Integer.parseInt(input[1]);
}
int l = 1, r = 100000;
while (l < r) //注意没有等于
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
System.out.println(r);
}
}
J. K倍区间
前缀和+枚举区间长度 暴力做法 28分
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 100010;
static int n, k, res;
static int[] a = new int[N];
static long[] s = new long[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]);
k = Integer.parseInt(input[1]);
for (int i = 1; i <= n; i++)
{
input = br.readLine().split(" ");
a[i] = Integer.parseInt(input[0]);
s[i] = s[i - 1] + a[i];
}
//要先循环区间长度，再循环左端点，再算右端点。
for (int len = 1; len <= n; len++)
{
for (int i = 1; i + len - 1 <= n; i ++ )
{
int j = i + len - 1;
if((s[j] - s[i - 1]) % k == 0) res++;
}
}
System.out.println(res);
}
}
y总做法
用哈希表存一下前面所有数模k的每种余数有多少个。因为值域小，开个数组就行。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 100010;
static int n, k;
static long[] s = new long[N], cnt = new long[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]);
k = Integer.parseInt(input[1]);
for (int i = 1; i <= n; i ++ )
{
input = br.readLine().split(" ");
s[i] = Long.parseLong(input[0]);
s[i] += s[i - 1];
}
long res = 0;
cnt[0] = 1; //先将s0放进去
for (int i = 1; i <= n; i ++ )
{
res += cnt[(int) (s[i] % k)];
cnt[(int) (s[i] % k)] ++ ;
}
System.out.println(res);
}
}
B. 等差素数列 (C++组)
import java.util.Arrays;
public class Main {
static int N = 10010;
static boolean[] prime = new boolean[N];
public static void main(String[] args) {
Arrays.fill(prime, true); //初始化，全为素数。
prime[0] = prime[1] = false;
for(int i = 2; i < N; i++)
for(int j = 2; j * j <= i; j++) //<=才行
{
if(i % j == 0)
{
prime[i] = false;
break;
}
}
// 枚举公差
for(int d = 1; d <= 300; d++)
{
for(int i = 2; i < N; i++)
{
boolean flag = true;
for (int j = 0; j < 10; j++)
{
//必须判断越界
if(i + j * d >= N || prime[i + j * d] == false)
{
flag = false;
break;
}
}
if(flag)
{
System.out.println(d);
return;
}
}
}
}
}
D. 方格分割 (C++组)
看这篇 题解
分享的字数到上限了，后续见 第二篇
tql 考试前 都跟你了 Orz
哈哈，一起加油！