绝迹的星

题解

/ 注册

全部文章 / 题解（共11篇）

题解 | # 2021江西ICPC省赛 #

A 01矩阵 - dp 题意: 给定一个 n * m 的01矩阵, 从(1,1)开始, 只能向右或向下, 问走到(n,m), 且路径上至少p个0,q个1的方案数有多少根据题目我们很容易就可以定义出一个dp做法 dp[i][j][k1][k2]: 走到(i,j), 有k1个0,k2个1的方案数 (...

Java Python3 数学模拟博弈论 LRU缓存

2024-05-24

1 267

题解 | #G 选数博弈#

G 选数博弈 import java.io.*; import java.util.*; public class Main { /* n个数, 每次A先选择1个数x, B需要选择1一个数字y, 然后从n个数中移除x和y y需要满足 |x-y|<=3 或 x%3=...

Java 博弈论

2024-05-22

2 226

题解 | #A Special Adjustment Method#

A Special Adjustment Method (1) 操作1 a b c → 0 b-a c+2a (a<b<c) (2) 操作2 a b c → a+2 b-1 c-1 → a b-3 c-3 x,y,z -> x-1,y-1,z+2的变化量为 4z-2x-2y+6...

Python3 数学

2024-05-22

2 200

题解 | #最短路#

最短路 import java.util.*; public class Main { private static List<int[]>[] graph; public static void main(String[] args) { Sc...

Java spfa

2024-05-22

1 219

题解 | #数列互质#

数列互质莫队模版使用哈希表维护区间中每个数的出现次数, 区间指针移动后遍历出现次数求互质个数 import java.io.*; import java.util.*; public class Main { static BufferedReader bf = new Buffe...

Java 哈希表计数莫队

2024-05-20

1 224

题解 | #E 小红的平行四边形#

E 小红的平行四边形平行四边形ABCD面积 = 向量AB × 向量AC 用哈希表先把可以组成平行四边形的边存一起, 然后配对计算面积可以组成平行四边形的边满足以下条件: (1) 两边平行 → 斜率相等 (2) 两边长度相等 (满足这两个条件, 另外两边一定是平行的) import java.io...

几何枚举哈希表

2024-05-20

5 353

题解 | #B-旅行#

B-旅行题意: 给定图, 求 max{ 任取三个点(起点 → 中转 → 终点)的最短路径长度 } 起点 → 中转 → 终点 ⇔ (中转 → 点1) + (中转 → 点2) 枚举中转点c, dijkstra求出c到其他点的最短距离, 在这些最短距离中选择两个最大的即可 import java.i...

图最短路枚举

2024-05-19

1 228

题解 | #有趣的区间#

有趣的区间 x是奇数 ⇔ x的二进制最低位为1 A[l] | ...|A[r]为奇数 ⇔ A[l~r]至少有一个数是奇数设以A[i]为右端点, 考虑它的左端点(<=i)能取哪些位置: (1) 如果A[i]为奇数, 左端点可以随便取, 因为包含了A[i]这个奇数, 有i+1个 (2) 如...

枚举数学脑筋急转弯

2024-05-17

1 186

题解 | #小A买彩票#

小A买彩票暴力枚举枚举四种彩票的数量, 统计不亏本情况即可 (1) 总情况: 有 4^n = 2^(2n) = 1<<(2n) 种 (2) 数量分别为a,b,c,d时: 不亏本条件: -2a-b+0c+d>=0, d>=2a+b 该情况数量: 根据排列组合原理有 n...

数学枚举概率与统计

2024-05-17

1 219

题解 | #D 韩信点兵#

D 韩信点兵性质: 给定整数 a 和 b , 对 a 加上 b 的任意倍数, a % b 的结果不变 => 如果 x 满足约束 x % a = b , 则 x + ka 也满足约束 => 方程 x % a = b, 特解 x = x0 的通解为 x = x0 + ka 令 x[i]...

Java 数学

2024-05-14

2 251