第十四届蓝桥杯省赛Java大学A组题解 第十四届蓝桥杯省赛Java大学A组题解
目录
A特殊日期
题目:
题解:
使用LocalDate对日期进行枚举,统计满足条件的日期数量即可
public static void main(String[] args) {
LocalDate start = LocalDate.of(1900, 1, 1);
LocalDate end = LocalDate.of(9999, 12, 31);
int ans = 0;
while (start.isBefore(end)) {//枚举日期
int y = start.getYear(), m = start.getMonthValue(), d = start.getDayOfMonth();
if (isEqual(y, m, d)) {//判断是否满足条件
ans++;
}
start = start.plusDays(1);
}
System.out.println(ans);//70910
}
private static boolean isEqual(int y, int m, int d) {
int count = 0;
while (y > 0) {
count += y % 10;
y /= 10;
}
while (m > 0) {
count -= m % 10;
m /= 10;
}
while (d > 0) {
count -= d % 10;
d /= 10;
}
return count == 0;
}最终答案为
70910
B与或异或
题目:
题解:
深搜枚举所有情况,统计最后结果为1的方案数
part1 - 全排列:
要从该层的值推导出下一层的值, 需要枚举门的全部选择方案
/**
对门进行全情况枚举,0表示与门,1表示或门,2表示异或门
@param oper 结果存储
@param start 当前要枚举的门编号
@param end 要枚举的门数量
@param stack 存储当前枚举的情况
*/
static void All(List oper, int start, int end, Stack stack) {
if (start == end) {
oper.add(new ArrayList(stack));
return;
}
for (int i = 0; i < 3; i++) {
stack.push(i);
All(oper, start + 1, end, stack);
stack.pop();
}
}part2 - 深搜:
定义int dfs(int[]arr)表示初始输入为arr时,最终结果为1的方案数,令n为arr的长度
- 当n为1时判断是否为1即可
- 当n大于1时,需要生成一个门的全排列(长度为n-1) , 对于每一个全排列创建一个新的数组newArr(长度为n-1, 其值由arr与门的排列生成). 那么dfs(arr)可以表示为 Sum(dfs(newArr))
static int dfs(int[] arr) {
int n = arr.length;
if (n == 1) return arr[0] == 1 ? 1 : 0;
//生成长度为n-1的门的情况枚举
List oper = new ArrayList();
All(oper, 0, n - 1, new Stack());
int res = 0;
for (List op : oper) {
//每个排列生成一个长度为n-1的新数组
int[] newArr = new int[n - 1];
for (int i = 0; i < n - 1; i++) {
int o = op.get(i);
if (o == 0) {
newArr[i] = arr[i] & arr[i + 1];
} else if (o == 1) {
newArr[i] = arr[i] | arr[i + 1];
} else {
newArr[i] = arr[i] ^ arr[i + 1];
}
}
res += dfs(newArr);//dfs(arr)=Sum(dfs(newArr))
}
return res;
}最后调用dfs(new int[]{1,0,1,0,1})输出即可
答案为
30528
C平均
题目:
题解:
n是10的倍数,每个数的出现次数都相等, 一个数修改成任意数都是等代价的, 我们只需要关心哪些数大于n/10即可,什么数少了多少个不需要管,因为多的数必须修改,而修改成哪个数并不重要
贪心: 假如数字1有是多余, 更改数字1的代价有 {a,b,c,..}, 那么肯定是选择最小的一个代价去修改才是最优解. 所以对于多余的数字,需要找到修改它的代价集,选择最小的代价
基于以上,可以使用优先级队列存储一个数代价集,方便获取它的最小代价,然后还需要用HashMap构建数字到它的代价集的映射
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
HashMap map = new HashMap();//数字->优先级队列(代价集),代价升序排列
int[] count = new int[10];//计数
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int num = sc.nextInt(), b = sc.nextInt();
map.computeIfAbsent(num, k -> new PriorityQueue()).offer(b);
count[num]++;
}
int ans = 0;
for (int i = 0; i < 10; i++) {
int more = count[i] - n / 10;//数字i的多余个数
Queue queue = map.get(i);
for (int j = 0; j < more; j++) {//修改p个数字i
ans += queue.poll();//挑最小代价进行修改
}
}
System.out.println(ans);
sc.close();
}D棋盘
题目:
题解:
解1 - 暴力:
创建n*n的二维数组,每次操作对(x1,y1)至(x2,y2)的区域的数进行取反,操作完后打印即可
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] arr = new int[n][n];
int m = sc.nextInt();
for (int i = 0; i < m; i++) {
//对(x1,y1)至(x2,y2)的区域的数进行取反
int x1 = sc.nextInt() - 1, y1 = sc.nextInt() - 1, x2 = sc.nextInt() - 1, y2 = sc.nextInt() - 1;
for (int x = x1; x 解2 - 前缀和差分(TODO):
正解应该是使用前缀和差分达到每次操作O(1)的时间复杂度, 但是没想到暴力直接过了, 那我也懒得写了, 需要这个解法的私信戳我, 我更一下
E互质数个数
题目:
题解:
part1 - 欧拉函数:
令E(x)表示[1,x]上与x互质数的个数
欧拉函数有以下两个常用公式:
- E(a^b) = E(a) * a^(b-1)
- E(k) = k * ∏(1 - 1/pi) 其中pi是k的质因子
所以套用公式1得 E(a^b) % MOD = E(a) * pow( a, b-1 ) % MOD
其中E(a)的求解可以使用公式2, pow(a,b-1)可以使用快速幂算法
part2 - E(a) :
暴力: 要求出a的质因数, 最简单的做法就是从i=2开始枚举,如果i是质数且a%i==0, 则找到一个质因数.
素数筛法: 从第一个质数i=2开始枚举, 如果i是a的因数, 那么将a不断除以2, 直到a%2!=0, 筛掉了所有a中2的倍数的因子, i=3时也是如此, i=4时因为已经被2筛掉了, 所以i不是a的因数了,可以直接跳过
举一些例子:
实际上不需要全部枚举,只需要枚举到sqrt(a)即可
因为sqrt(a)*sqrt(a)<=a, 不可能存在两个大于sqrt(a)的质因数, 所以如果a存在一个大于sqrt(a)的质因数k, 那么经过操作后, a的值就等于k, 如果不存在, 那么最后a的值会等于1, 所以只需要做一个a是否等于1的判断即可
static long E(long a) { // E(a) = a * ∏(1 - 1/pi)
long p = a;
long res = a;
int sq = (int) Math.sqrt(a);
for (int i = 2; i part3 - 快速幂:
快速幂算法求x^n % MOD , 这里介绍二进制快速幂算法
先看一个例子(我还没想好怎么讲):
也就是说对指数n进行二进制拆分, 从最低位开始取, 如果是1, 那么该项需要乘, 其中要乘的数为底数, 底数初始为base=x, 每次取n的二进制时需要将base平方
static long pow(long x, long n) { //x^n
long ans = 1;
while (n != 0) {
if ((n & 1) == 1) ans = (ans * x) % MOD;//最低位为1,则需要乘
x = (x * x) % MOD;//底数平方
n >>= 1;
}
return ans;
}总体代码:
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a = sc.nextLong(), b = sc.nextLong();
System.out.println(E(a) * pow(a, b - 1) % MOD); //E(a^b)=E(a)*a^(b-1)
}
static long E(long a) { // E(a) = a * ∏(1 - 1/pi)
long p = a;
long res = a;
int sq = (int) Math.sqrt(a);
for (int i = 2; i >= 1;
}
return ans;
}F阶乘的和
题目:
题解:
将A从低到高排列, m=A1时一定满足要求, 因为 A1! % m! = 0, 而A2!、A3!...都含有因子A1!, 则Sum(Ai!) % m! = 0
当 m=A2 (A1!=A2) 时一定不满足要求, 因为 A1! 中不含 A2项, 所以一定无法整除m!
比如 2!、3!、4!, 当m=2时, (2!+3!+4!)/m!=1+3+4*3可以整除, 当m=3时, (2!+3!+4!)/m!=1/3+1+4不能整除
如果A1==A2呢, 每3个2! 可以提升为1个3! (3个二星融合1个3星[doge]), 每4个3!可以提升为1个, 即 n个k! 可以融合为 n/(k+1)个(k+1)! , 其中n是k+1的倍数, 只需要经过层层融合后, 最小一个A就是答案
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//将数据存储到优先级队列中,按A的值进行排序
HashMap map = new HashMap();//A_Value->A_Count
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int num = sc.nextInt();
map.put(num, map.getOrDefault(num, 0) + 1);
}
Queue queue = new PriorityQueue((Comparator.comparingInt(o -> o[0])));//[A,A的个数]
for (Map.Entry entry : map.entrySet()) {
queue.offer(new int[]{entry.getKey(), entry.getValue()});
}
//计算答案
int ans = queue.peek()[0];//第一个最小值一定能整除
while (!queue.isEmpty()) {
int[] p = queue.poll();
int A_Value = p[0], A_Count = p[1];//A_Value有A_Count个
if (A_Count % (A_Value + 1) != 0) {//不能完全融合,最后剩余的最小的A一定就是当前A,后面不需要融合了
break;
}
//该项A可以完全融合为A+1
int[] next = queue.peek();
if (next == null || next[0] != A_Value + 1) {//不是连续的A项,需要新建这个A项
next = new int[]{A_Value + 1, A_Count / (A_Value + 1)};
queue.offer(next);
} else {//连续A项,直接在它原数量上增加
next[1] += A_Count / (A_Value + 1);
}
ans++;//融合是从A_Value->V_Value+1,所以ans的增加一定也是连续的
}
System.out.println(ans);
sc.close();
}G小蓝的旅行计划
题目:
题解:
贪心:
假如说现在不考虑油箱的容量(油箱容量无限), 那么最优的策略是 先闷着头往前开, 在发现开不到下一个站点时, 回头看哪个加油站还有油加(如果没有油可以加了, 返回-1), 有多个选择的情况下肯定是选一个最便宜的加油站加油, 加到能走到下一个加油站为止, 并统计花的钱.
public static void main(String[] args){// 9AC 1WR
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();//n个站点,最大容量m
int cost = 0;//当前最小消耗
int curr = m;//当前油量
Queue queue = new PriorityQueue(Comparator.comparingInt(a -> a[0]));//[油价,剩余可加的油量]按油价排序
for (int i = 0; i < n; i++) {
int distance = sc.nextInt();// 到下一个站点的消耗
if (curr >= distance) {// 可以直接走到下一个站点
curr -= distance;
} else {// 走不到下一站
int need = distance - curr;// 需要加need升油, 只加need升,不多加,下次出发时再加
while (need > 0) {
if (queue.isEmpty()) { // 还需要加油,但是没油可加了
System.out.println(-1);
return;
}
int[] data = queue.poll();// 取已到达过的,还能加油的,最便宜的站点加油
if (data[1] > need) { // 有超出的油,加need升,剩余的放回队列
data[1] -= need;
cost += need * data[0];
need = 0;
queue.offer(data);
} else {// 全部加
cost += data[1] * data[0];
need -= data[1];
}
}
curr = 0;
}
// 到达下一个站点,加油机会存入队列
int co = sc.nextInt();// 油价
int maxAdd = sc.nextInt();// 最多加的油量
queue.offer(new int[]{co, maxAdd});
}
System.out.println(cost);
}这个代码已经能拿到90分了
线段树:
现在考虑油箱容量有上限m, 令 limit[i] 表示加油站i的最大加油量, rest[i] 表示到达加油站i的剩余容量
那么在加油站i的最大加油量就等于 min( m-rest[i], limit[i] )
对于之前的贪心算法, 假设现在准备从加油站i-1出发前往下一个加油站i, 但是油量不足, 在i前面的加油站j是最便宜的加油站. 如果直接在加油站j加k升油, 这会导致 rest [ j ~ i-1 ] 都会增加k, 这个操作可能会超出油箱上限, 所以如果想在加油站j加油, 需要求出 rest [ j ~ i-1 ] 的最大值maxOil, 能加的油量就是 min(m - maxOil, limit[j])
对于频繁的区间查询、区间更新的问题, 一般使用线段树/树状数组, 所以可以使用线段树来维护rest数组, 目的是快速地查询 rest [ j ~ i-1 ] 的最大值
static int M = 200001;
static int[] distance = new int[M];// 开往下一个站点的距离
static int[] limit = new int[M];// 加油站的加油上限
static int[] cost = new int[M];// 加油站的加油花费
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
for (int i = 1; i o.cost)));
SegmentTree tree = new SegmentTree();
int curr = m;//当前油量
for (int i = 1; i H太阳
题目:
题解:
极角排序:
首先为了方便计算, 把太阳移到原点处, 这样所有的线段都会位于三四象限, 我们把线段的左端点称为起点,右端点称为终点
如果从x的负半轴开始逆时针转180°, 对线段的端点进行扫描, 在遇到线段起点时, 我们可以把线段的y轴加入有序集合set中, 当遇到线段终点时, 将其从集合中移除, 这样就表示出了一条线段的覆盖范围.
有序集合set提供了一个重要信息, 正在被扫描的线段中,最上面的线段是哪一条,令其为set.first.
令ans[i]表示线段i能被照射到, 当遇到某线段端点时, 取被正在扫描的最上面的线段i, 则ans[i]=true
下面举个例子演示执行过程:
(第一个扫描到的线段肯定能被照到,特殊处理ans)首先扫描到线段1的左端点,set为null, 将线段1添加到set中
然后扫描到线段2的左端点,取set.first=线段1, 将线段1标记为true, 将线段2加入set中,它的y轴低于线段1,所以排在线段1后面
扫描线段1的右端点, set.first依然是线段1,重复刚才的操作, 因为是右端点,那么线段1的覆盖范围就结束了,将线段1从set中移除
扫描线段4的左端点, 取set.first=线段2,将线段2标记为true, 线段4加入set
扫描线段4的右端点, 取set.first=线段2,将线段2标记为true, 线段4从set中移除
扫描线段3的左端点, 取set.first=线段2, 将线段2标记为true, 线段3加入set
扫描线段2的右端点, 取set.first=线段3,将线段3标记为true, 线段2从set中移除
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long X = sc.nextInt(), Y = sc.nextInt();
Node[] a = new Node[2 * n + 1];//0位置不存储数据
for (int i = 1; i {//按斜率排序,(从左到右)
long l = aa.x * bb.y - aa.y * bb.x;
if (l > 0) return -1;
if (l == 0) return 0;
return 1;
});
TreeSet s = new TreeSet(((o1, o2) -> Math.toIntExact(o1.y - o2.y)));//按y轴坐标排序
boolean[] ans = new boolean[n + 1];//ans[i]表示编号为i的线段可以被照到
a[0] = new Node(0, 1, 0, 0);
for (int i = 1; i I高塔
题目
题解
不会,dfs过了5个点,15个超时,数据有点大, 不好做, 数组我都开不出来, 写出来了我再回来更
static int MOD = 998244353;
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int Int() {
try {
st.nextToken();
} catch (Exception ignored) {
}
return (int) st.nval;
}
static long Long() {
try {
st.nextToken();
} catch (Exception ignored) {
}
return (long) st.nval;
}
public static void main(String[] args) {
n = Int();
long m = Long();
A = new int[n];
for (int i = 0; i < n; i++) A[i] = Int();
System.out.println(f(0, m));
}
static int[] A;
static int n;
/**
当前进行到了第i回合,剩余remain点能量的方案数
*/
static long f(int i, long remain) {
if (i == n || remain == 0) return 1;
long ans = 0;
for (long Ci = 1; Ci J反异或01串
题目:
题解:
0是可以随便添加的, 而1不能随便添加, 所以我们的目的是使用反异或凑1出来
- 反异或操作最多能使用一次
- 仅有1^0可以得到1
- 一个字符串s反异或后一定是一个回文串
假如T中有一串字符是101101, 这是一个偶数长度的回文串, 那么我们只需要对101000做反异或, 101000 ^ 000101 = 101101, 就可以将后半部分变为101, 本来需要4个1, 现在只需要一半
所以, 如果我们找到T中1最多的一个回文串, 假设有x个1, 那么这个回文串我们只需要添加x/2个1, 然后添加适当的0, 进行反异或就可以得到这个回文串
另外中心为1的一个奇数长度回文串, 比如1101011, 它不能使用反异或操作凑1, 因为1^1=0, 取110100进行反异或的话, 会将中心值变为0, 110100 ^ 001011 = 1100011与最终的结果就不符了
所以, 寻找T中最多1的且中心值不为1的回文子串, 假设有x个1, 这x个1只需要添加一半, 答案为count(T,1) - x / 2
对于求回文串可以使用中心拓展算法, 枚举回文串的中心点(可以是一个字符,也可以是两个字符),然后尝试向外拓展, 直到不能拓展,即可找到以中心点为中心的最长的回文串, 我们需要的是最多1的回文串, 最长和最多1并不是很冲突, 只需要在拓展时记录一下1的个数即可,如果1更多则最后更新答案
public static void main(String[] args) {
//最多1的回文01串,如果是中心是1的奇数长度串,则无效
Scanner sc = new Scanner(System.in);
char[] T = sc.next().toCharArray();
int len = T.length;
longestPalindrome(T);//求1最多的回文01串,[left,right]
int count = 0;
for (int i = 0; i < left; i++) {
if (T[i] == '1') count++;
}
for (int i = right + 1; i < len; i++) {
if (T[i] == '1') count++;
}
System.out.println(count + count1);
}
static int left, right, count1;
static void longestPalindrome(char[] chars) {
left = -1;
right = -1;
count1 = 0;
for (int i = 0; i < chars.length - 1; i++) {
//中心拓展算法
if (chars[i] != '1') extend(chars, i, i);//一个字符作为中心点
extend(chars, i, i + 1);//两个字符作为中心点
}
}
static void extend(char[] chars, int i, int j) {
// 选择一个中间点,向两边查找
int count = 0;
while (i >= 0 & j < chars.length && chars[i] == chars[j]) {
if (chars[i] == '1') count++;
i--;
j++;
}
//直到不是回文,退出循环
i++;
j--;
if (count > count1) {//记录最多1的区间
left = i;
right = j;
count1 = count;
}
}