2022百度之星程序设计大赛 - 初赛 - 第一场
BD202201洞穴
题目
怪诞小镇的森林里有一个奇怪的洞穴群。
这个洞穴群包括 n 个洞穴（从 1 到 n 编号）。
每个洞穴中有若干岔路通向其他的洞穴，每条岔路都有一个长度。
日志3上记录了这个洞穴群的一个特点：任意两个洞穴间仅存在一条路径。
此外，日志的主人还在日志3上写下了任意两个洞穴间的距离。
现在小度想要知道这个洞穴群中，哪两个洞穴间存在岔路。
格式
输入格式
多组样例输入，第一行一个整数 T 表示数据组数。
每组数据包括 n+1 行。
第一行一个数字 n 表示洞穴的个数
之后 n 行每行 n 个整数，第 x 行的第 y 个整数 disx,y 表示洞穴 x 和洞穴 y 间的距离。
输出格式
对于每个样例，首先输出一行一个整数 k，表示洞穴群中存在 k 条岔路。
之后 k 行输出 k 个二元组 (x,y)，表示洞穴 x 和洞穴 y 间有一条直接连通的岔路。
请按照 (x,y) 递增的顺序输出：即 x 不同时先输出 x 较小的 (x,y)；x 相同时先输出 y 较小的 (x,y)。
数据范围
T≤10，1≤n≤100，disx,y≤105
样例
输入
1
5
0 1 2 3 3
1 0 1 2 2
2 1 0 3 3
3 2 3 0 4
3 2 3 4 0
输出
4
1 2
2 3
2 4
2 5
题解
任意两个洞穴间仅存在一条路径，说明答案是连通树。
没错，这题就是最小生成树kruskal-算法的板子。
结论：kruskal 算法不选择的边都能通过前面选的边组合形成。
kruskal 算法从权值最小的距离开始选，遇到第一条不选的边，如果这条边不是通过组合形成，则这两构成的边由于树的性质必然会破坏前面的一条边，导致要花费更多边去维护被破坏边的两个点的距离，而树的边数量是固定的。所以第一个不选的边能通过前面选的边组合形成。把第一个不选的边(组合形成)当成一条边，递推即可得到答案。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer cin = new StreamTokenizer(br);
static PrintWriter out = new PrintWriter(System.out);
static int nextInt() throws Exception {
cin.nextToken();
return (int) cin.nval;
}
static String next() throws Exception {
cin.nextToken();
return cin.sval;
}
static double nextDouble() throws Exception {
cin.nextToken();
return cin.nval;
}
public static void main(String[] args) throws Exception {
int cnt = nextInt();
while (cnt --> 0) {
int n = nextInt();
int[][] g = new int[n * n - n][3];
int[][] res = new int[n * n - n][];
p = new int[n + 1];
int idx = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
nextInt();
}
for (int j = i + 1; j <= n; j++) {
g[idx][0] = i;
g[idx][1] = j;
g[idx++][2] = nextInt();
}
p[i] = i;
}
Arrays.sort(g, 0, idx, (o1, o2) -> {
return o1[2] - o2[2];
});
int ridx = 0;
for (int i = 0; i < idx; i++) {
int[] v = g[i];
if (find(v[0]) != find(v[1])) {
p[find(v[0])] = find(v[1]);
res[ridx++] = v;
}
}
Arrays.sort(res, 0, ridx, (o1, o2) -> {
if (o1[0] == o2[0]) {
return o1[1] - o2[1];
}
return o1[0] - o2[0];
});
out.println(ridx);
for (int i = 0; i < ridx; i++) {
out.println(res[i][0] + " " + res[i][1]);
}
out.flush();
}
}
static int[] p;
static int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
BD202202小度养小猫
没有vip做不了这题，代码不保证一定正确。
题目
小度养了n只小猫，他每天按时给这n只小猫喂食，即第iii分钟他将给第i只小猫喂食。
但是他今天突然有事出去，前k分钟他不能给这些小猫喂食，而只能在第k+1 ~ k+n分钟喂食。
现在要求：今天的喂食顺序可以不同于之前的顺序，但是第iii只小猫今天吃食的时间不能早于自己之前吃食的时间i。
如果第i只小猫今天在第ti分钟吃食，那么它会产生(ti2−i2)∗ci的不满意度。
现在满足要求的前提下，请确定一个喂食顺序使不满意度之和最小并求出这个最小值（注：同一时间只能喂一只小猫）。
格式
输入格式
第一行两个正整数n,k表示小猫的数量和小度不能喂食的时间 。
第二行n个整数c1,c2,…,cn表示第i个小猫不满意度的系数。
输出格式
共一行输出一个数代表最小不满意度之和。
数据范围
1 ≤ k ≤ n ≤ 105, k ≤ 5*104,ci ≤ 104
答案保证在long long范围内。
样例
输入
5 2
4 2 1 10 2
输出
136
题解
经典的贪心+并查集维护天数的板子。
−i2∗ci不变，要使ti2∗ci最大，则按ci大到小排序后，每次选择能选的最小的ti即可。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer cin = new StreamTokenizer(br);
static PrintWriter out = new PrintWriter(System.out);
static int nextInt() throws Exception {
cin.nextToken();
return (int) cin.nval;
}
static String next() throws Exception {
cin.nextToken();
return cin.sval;
}
static double nextDouble() throws Exception {
cin.nextToken();
return cin.nval;
}
public static void main(String[] args) throws Exception {
int n = nextInt(), k = nextInt();
int[][] c = new int[n + 1][2];
p = new int[n + 2];
long res = 0;
for (int i = 1; i <= n; i++) {
c[i][0] = i;
c[i][1] = nextInt();
res -= (long) i * i * c[i][1];
}
for (int i = 0; i < p.length; i++) {
p[i] = i;
}
Arrays.sort(c, 1, c.length, (o1, o2) -> o2[1] - o1[1]);
for (int i = 1; i <= n; i++) {
int di = c[i][0];
int ci = c[i][1];
int sub = di - k;
if (sub < 1) {
sub = 1;
}
int day = find(sub);
p[day] = find(day + 1);
day += k;
res += (long) day * day * ci;
}
System.out.println(res);
}
static int[] p;
static int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
BD202203简单题
题目
小度喜欢单调序列。一天，小度得到了一个序列，他决定把这个序列拆分成两个序列：一个是（非严格)上升序列，一个是（非严格）下降序列。小度猪脑过载了，你能帮帮他吗？
已知一个正整数序列a1…an，你需要判断能否将a序列恰好划分成两个非空子序列（a序列中的每个元素属于且仅属于其中一个子序列），使得一个是（非严格)上升序列，另一个是（非严格）下降序列。
格式
输入格式
输入的第一行为一个整数n，表示序列长度。
输入第二行为n个整数ai。
输出格式
输出仅一行，如果存在合法的划分方案，输出”yes”（不含引号），否则输出”no”（不含引号）。
数据范围
n ≤ 105, 1 ≤ ai ≤ 109
样例
输入
6
1 1 4 5 1 4
输出
yes
题解
动态规划即可，f0[i]表示把a[i]添加进递增序列时，递减序列的限制。f1[i]表示把a[i]添加进递减序列时，递增序列的限制.。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer cin = new StreamTokenizer(br);
static PrintWriter out = new PrintWriter(System.out);
static int nextInt() throws Exception {
cin.nextToken();
return (int) cin.nval;
}
static String next() throws Exception {
cin.nextToken();
return cin.sval;
}
static double nextDouble() throws Exception {
cin.nextToken();
return cin.nval;
}
public static void main(String[] args) throws Exception {
int n = nextInt();
int[] f0 = new int[n + 1];
int[] f1 = new int[n + 1];
int[] a = new int[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = nextInt();
}
Arrays.fill(f0, 0);
Arrays.fill(f1, Integer.MAX_VALUE);
f0[0] = Integer.MAX_VALUE;
f1[0] = 0;
for (int i = 1; i <= n; i++) {
a[0] = 0;
if (a[i] >= a[i - 1]) {
f0[i] = f0[i - 1];
}
if (a[i] >= f1[i - 1]) {
a[0] = Integer.MAX_VALUE;
f0[i] = Math.max(f0[i], a[i - 1]);
}
a[0] = Integer.MAX_VALUE;
if (a[i] <= a[i - 1]) {
f1[i] = f1[i - 1];
}
if (a[i] <= f0[i - 1]) {
a[0] = 0;
f1[i] = Math.min(f1[i], a[i - 1]);
}
}
System.out.println(f1[n] != Integer.MAX_VALUE || f0[n] != 0 ? "yes" : "no");
}
}