A~F 小白月赛94>  我的自动WA机又出手了, 狠狠掉分 A 九宫格 读入,按位置输出即可 import java.io.*; public class Main { public static void main(String[] args) throws Exception { int[] a = new int[10]; for (int i = 1; i < 10; i++) a[i] = I(); String s = S(); for (char ch : s.toCharArray()) pw.print(a[ch - '0']); pw.flush(); } s...

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的方案数 (i,j)位置由(i-1,j)和(i,j-1)两个位置转移而来: (1) map(i,j)==0 dp[i][j][k1][k2]=dp[i-1][j][k1-1][k2]+dp[i][j-1][k1-1][k2] // k1=p处需要特判 (2) map(i,j)==1 dp[i][j][k1][k2...

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==y%3 当某人没数字可选时,他就输了 */ static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535); static StreamTokenizer st = new StreamTokenizer(bf); s...

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, 如果z>x且z>y,则变化量一定是正的, 所以全部加到同一个数上是最优解 先经过操作1 如果此时b-a是3的倍数, 则可以全部加到第三个数上, 答案为sum^2 如果此时b-a不是3的倍数, 那么会变为0 1 sum-1 (如果余2可以调整为1), 答案为 (sum-1)^2 + 1^2...

最短路  import java.util.*; public class Main { private static List<int[]>[] graph; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), m = sc.nextInt(); graph = new ArrayList[n + 1];//编号从1开始 Arrays.setAll(graph, k -> new ArrayList<>()); fo...

! 某些代码为提交区的转载 A 互质对数位和 - 容斥原理  import java.util.*; public class Main { /* 求 sum{ sum{ F(j) | j=1->i } | i=1->n } 其中F(j)表示j的数位和 */ /** 贡献法, 计算i的贡献, 即F[i] * 数量 数量 = i后面与i互质的数的个数 = (n-i) - i后面不与i互质的数个数 <p> i后面不与i互质的数个数 可以 枚举i的质因子集 假设枚举出的质因子集相乘为mul, 则 i~n上有 (n-i) / mul 个mul的倍数, 即有 (n-i) / mu...

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

E 小红的平行四边形 平行四边形ABCD面积 = 向量AB × 向量AC 用哈希表先把可以组成平行四边形的边存一起, 然后配对计算面积 可以组成平行四边形的边满足以下条件: (1) 两边平行 → 斜率相等 (2) 两边长度相等 (满足这两个条件, 另外两边一定是平行的) import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { int n = I(); long[][] points = new long[n][2]; f...

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

我邻接表开n+1, 可以过45%, 然后爆索引越界, 开200001能AC import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { int n = I(); int m = I(); List<int[]>[] g = new ArrayList[200001]; // List<int[]>[] g = new ArrayList[n+1]; // 这里用n+1,只能过45%, 下面的建图爆索引...

有趣的区间 x是奇数 ⇔ x的二进制最低位为1 A[l] | ...|A[r]为奇数 ⇔ A[l~r]至少有一个数是奇数 设以A[i]为右端点, 考虑它的左端点(<=i)能取哪些位置: (1) 如果A[i]为奇数, 左端点可以随便取, 因为包含了A[i]这个奇数, 有i+1个 (2) 如果A[i]为偶数, 设上一个奇数在last, 那么[0,last]都可以取, 因为包含了A[last]这个奇数, 有last+1个 所以用一个变量记录最近的奇数位置, 从前往后遍历统计即可  import java.io.*; import java.math.BigInteger; import jav...

小A买彩票 暴力枚举 枚举四种彩票的数量, 统计不亏本情况即可 (1) 总情况: 有 4^n = 2^(2n) = 1<<(2n) 种 (2) 数量分别为a,b,c,d时: 不亏本条件: -2a-b+0c+d>=0, d>=2a+b 该情况数量: 根据排列组合原理有 n! / (a! * b! * c! * d!)种, 累加求和  最后gcd约分输出即可 import java.math.BigInteger; import java.util.Scanner; public class Main { static BigInteger[] A = new BigInt...

B 咖啡坤 题目梳理 S[1] = COFFEE S[2] = CHICKEN S[n] = S[n-2] + S[n-1] 对于给定的n和k,求S[n]的第k位~第k+10位  思路: 记 L[n]为S[n]的长度, 则有L[n] = L[n-2] + L[n-1] 因为S[n]是由前两项拼接而来: 如果 k <= L[n-2]: 那么S[n]只需要看前面的一段S[n-2], 问题就变为了 n-2和k 如果 k > L[n-2]: 那么就是求后面的S[n-1]的第k-L[n-2]位, 问题就变为了 n-1和k-L[n-2]  转移方程: 所以定义f(n,k)为S[n]的第k个字符...

D 韩信点兵 性质: 给定整数 a 和 b , 对 a 加上 b 的任意倍数, a % b 的结果不变 => 如果 x 满足约束 x % a = b , 则 x + ka 也满足约束 => 方程 x % a = b, 特解 x = x0 的通解为 x = x0 + ka   令 x[i] 为满足前i个约束的解的最小值 X[i] 为满足前i个约束的解的通解 Lcm[i]=lcm(a[0],a[1],,...,a[i]) 只考虑前i个约束的通解: X[i] = x[i] + k1 * Lcm[i] 考虑第i+1个约束: X[i+1] = x[i+1] + k2 * Lcm[i+1] =...