- 博客(61)
- 收藏
- 关注
RSS订阅原创 LeetCode 每日一题：528. 按权重随机选择
528. 按权重随机选择原题地址题目类型 题意 分析 前缀和 + 二分 时间复杂度 O()O( )O() 代码class Solution { int[] pre; int sum; public Solution(int[] w) { pre = new int[w.length]; pre[0] = w[0]; for (int i = 1, len = w.length; i
2021-08-30 10:03:18
79
原创 Codeforces Round #739 (Div. 3)
套题名称原题地址#题目分数是否ACA800✅B1000✅C2000✅D1800❌E2000❌F2300❌G2400❌H2400❌I2400❌J2400❌K2400❌L2400❌M2400❌N2400❌A. 题目题目类型 题意 分析 时间复杂度 O()O( )O()
2021-08-20 20:48:05
92
原创 Codeforces Round #597 (Div. 2)
Codeforces Round #597 (Div. 2)原题地址#题目分数是否ACAGood ol’ Numbers Coloring1000✅BRestricted RPS1200✅CConstanze’s Machine1400✅DShichikuji and Power Grid1900❌EHyakugoku and Ladders2300❌FDaniel and Spring Cleaning2300❌
2021-08-18 01:18:36
141
原创 Codeforces Round #738 (Div. 2)
Codeforces Round #738 (Div. 2)原题地址#题目分数是否ACAMocha and Math✅BMocha and Red and Blue✅CMocha and Hiking✅D1Mocha and Diana (Easy Version)✅D2Mocha and Diana (Hard Version)❌EMocha and Stars❌A. Mocha and Math
2021-08-17 17:13:09
82
原创 Educational Codeforces Round 77 (Rated for Div. 2)
Educational Codeforces Round 77 (Rated for Div. 2)原题地址#题目分数是否ACAHeating1000✅BObtain Two Zeroes1300✅CInfinite Fence1700❌DA Game with Traps1900❌ETournament2700❌A. Heating题目类型 数学代码 public static void s
2021-08-16 01:52:19
91
原创 Codeforces Round #592 (Div. 2)
Codeforces Round #592 (Div. 2)原题地址#题目分数是否ACAPens and Pencils800✅BRooms and Staircases1000✅CThe Football Season2000✅DPaint the Tree1800❌EMinimizing Difference2000❌FChips2300❌GRunning in Pairs2400❌
2021-08-15 22:33:56
74
原创 Codeforces Round #737 (Div. 2)
Codeforces Round #737 (Div. 2)原题地址#题目分数是否ACAEzzat and Two Subsequences800✅BMoamen and k-subarrays1100✅CMoamen and XOR1700❌DEzzat and Grid2200❌EAssiut Chess2800❌A. Ezzat and Two Subsequences题目类型 思维题意 给
2021-08-15 20:39:12
82
原创 Codeforces Round #516 (Div. 2, by Moscow Team Olympiad)
Codeforces Round #516 (Div. 2, by Moscow Team Olympiad)原题地址#题目分数是否ACAMake a triangle!800✅BEquations of Mathematical Magic1200✅COh Those Palindromes1300✅DLabyrinth1800✅EDwarves, Hats and Extrasensory Abilities1900❌
2021-08-15 19:53:27
82
原创 Educational Codeforces Round 12
Educational Codeforces Round 12原题地址A. Buses Between Cities题意给出 A 市到 B 市和 B 市到 A 市公交车、出发的频率以及需要的时间。判断当坐从 A 市到 B 市的某一辆车时，在到达 B 市的图中遇到的公交车的数量。分析遇到的公交车共有两种在 m 时刻从前出发但未到站在 m 时刻之后出发枚举所有从 B 市出发的车，然后判断是否可以遇到代码 public static void solve() throws IOExcep
2021-08-15 01:19:17
115
原创 Educational Codeforces Round 74 (Rated for Div. 2)
Educational Codeforces Round 74 (Rated for Div. 2)原题地址#题目分数是否ACAPrime Subtraction900✅BKill 'Em All1300✅CStandard Free2play1600✅DAB-string1900❌EKeyboard Purchase2200❌FThe Maximum Subtree2200❌GAdilbek and th
2021-08-14 10:18:50
338
原创 POJ Problem 1195 - Mobile phones
POJ Problem 1195 - Mobile phones原题地址题目类型：二维树状数组题意在一个 S×SS \times SS×S 大小的矩阵中，进行单点修改，子矩阵查询。分析使用二维树状数组。代码static int[][] C;public static void solve() throws IOException { int tt = nextInt(); int S = nextInt(); C = new int[S + 10][S
2021-08-08 08:51:45
86
原创 AcWing Problem 1275 - 最大数
AcWing Problem 1275 - 最大数原题地址题目类型：线段树题意有两种操作：• 添加操作：每次向序列后添加一个数• 询问这个序列中最后 LLL 个数中最大值分析因为每次插入的数与上一次查询有关系所以必须动态在线做这题。求区间最大值可以想到用线段树，起初可认为线段树的叶子节点都为 000，然后每次添加一个数的时候再进行更新并维护最大值。代码static int[] C;public static void solve() throws IOException {
2021-08-08 08:51:19
72
原创 POJ Problem 2299 - Ultra-QuickSort
POJ Problem 2299 - Ultra-QuickSort原题地址题目类型：树状数组、逆序数、离散化题意给定一个序列，求出其中逆序数的个数。分析可以使用归并排序来求也可以使用树状数组来求，结果记得使用 longlonglong。在用树状数组求得时候需要使用离散化。代码static int[] a;static int[] C;static int[] all;static int aLen;public static void solve() throws IOExcep
2021-08-08 08:50:27
106
原创 POJ Problem 2182 - Lost Cows
POJ Problem 2182 - Lost Cows原题地址题目类型：树状数组、二分、标记题意有编号是 1～n1～n1～n 的 nnn 个数字， 2≤n≤80002 \leq n \leq 80002≤n≤8000, 乱序排列，顺序是未知的。对于每个位置的数字，知道排在它前面比它小的数字有多少个。求这个乱序数列的顺序。分析观察发现最后一位数可以直接确定，然后将这个数从 1−n1 - n1−n 的集合中划去，然后再看倒数第二个数，发现这个数应该是剩下的数中第 a[i]+1a[i] + 1a[i
2021-08-08 08:48:47
196
原创 POJ Problem 2352 - Stars
POJ Problem 2352 - Stars原题地址题目类型：树状数组、标记题意：在一个平面中给出一些星星得坐标（输入时按 yyy 递增得顺序给出，如果 yyy 相等则按 xxx 递增给出），定义一个星星的等级为在它左下方星星的数量，即 yyy 小于等于它且 xxx 小于等于它的星星的数量。输出 0～n−10～n-10～n−1 每种等级星星的数量。分析：因为输入是按 yyy 递增的顺序输入的，所以对于当前输入，它的等级就是在它之前的输入中 xxx 比它小的星星的个数。所以这里可以用树状数组对
2021-08-08 08:46:35
62
原创 Kattis Problem - Square Peg in a Round Hole
Kattis Problem - Square Peg in a Round Hole原题地址题目类型：贪心、排序题意有 N 块圆形的地， M 个圆形的屋子和 K 个正方形的屋子。在地上修建屋子时不能触碰地的边界。给出每块地的半径以及圆形屋子的半径和正方形屋子的边长，求最多可以修建多少个屋子。分析可以想到，一个屋子在一块地上可以修建时应使地的半径尽可能小。圆形的屋子则可以直接比较半径，而正方形的屋子所占圆的半径是它的对角线的一半。所以将每个屋子的半径处理出来进行排序，再将地的半径进行排序，然后进
2021-08-06 10:55:32
227
原创 Kattis Problem - Saving For Retirement
Kattis Problem - Saving For Retirement原题地址题意Bob 从 BBB 岁开始直到 BrB_rBr 岁退休，每年存 BsB_sBs 元钱。Alice 现在 AAA 岁，每年可以存 AsA_sAs 元钱。求 Alice 在多少岁时退休存的钱比 Bob 退休时存的钱多。分析Bob 总共存的钱是 Bs∗(Br−B)B_s * (B_r - B)Bs∗(Br−B)，所以 Alice 需要存 Bs∗(Br−B)/As+1B_s * (B_r - B) / A_s
2021-08-06 10:16:27
97
原创 AcWing Problem 241 - 楼兰图腾
AcWing Problem 241 - 楼兰图腾原题地址题目类型：树状数组 + 标记题意分别统计这样的三元组的个数：1.（yay_aya, yby_byb, ycy_cyc）其中 ya>yby_a > y_bya>yb 、yb<ycy_b<y_cyb<yc 、0<a<b<c≤n0 < a < b < c \leq n0<a<b<c≤n2.（yay_aya, yby_byb, ycy_cy
2021-07-29 17:20:39
76
原创 AcWing Problem - 一个简单的整数问题2
AcWing Problem - 一个简单的整数问题2原题地址题目类型：树状数组题意有两种操作：• 查询区间 [l, r] 内的和• 对 [l, r] 内所有数加上 d分析使用两个树状数组来维护代码static int[] a;static long[] C1;static long[] C2;public static void solve() throws IOException { int n = nextInt(); int m = nextInt();
2021-07-29 17:06:18
55
原创 AcWing Problem - 一个简单的整数问题
AcWing Problem - 一个简单的整数问题原题地址题目类型树状数组题意有两种操作：• 求数组中一段区间的和• 修改数组中某一个数分析使用树状数组和差分的思修来维护。时间复杂度 n logn代码static int[] C;static int[] a;public static void solve() throws IOException { int n = nextInt(); int m = nextInt(); init(n)
2021-07-29 17:02:27
62
原创 CodeForces Problem - Segments Removal
CodeForces Problem - Segments Removal原题地址题目类型：链表、Set题意给定一个整数序列，每次选择元素相同的最长的连续的子串然后删除，删除后左右两边的部分会拼接起来，如果有多个这样的子串则选择最左边的。求按照如上规则多少次操作后源串会变为空串。分析首先将连续的子串处理为 num 和 cnt 表示，然后用静态链表存储，并用 TreeSet 保存，使得 set 最后一个元素为长度最长且是最左边得子串。然后模拟执行上面得操作，每次删除一个子串后将其链表中左右两边得节
2021-07-29 16:57:06
63
原创 AcWing Problem1250 - 格子游戏
AcWing Problem1250 - 格子游戏原题地址题目类型：并查集题意在一个 n x n 的点阵中，两个人轮流在相邻的点与点之间连线，当连线出现一个封闭的圈时游戏结束。但是现在游戏进行了很多回合已经无法辨别游戏的结果。给定点阵的大小 n 和 m 次操作，判断游戏的结果，如果结束了则输出结束的回合。分析观察发现，当出现封闭的圈时在连最后一条线时圈中剩余的线都属于一个连通块，所以将已经进行过的操作用并查集维护，连一条线时就将两个顶点放入一个集合，如果在连线时发现两个顶点已经属于一个集合，那
2021-07-29 16:51:05
81
原创 Kattis Problem - Keyboardd
Kattis Problem - Keyboardd原题地址题目类型：字符串、映射题意：有一个键盘，其中部分键坏了，按一次会会在屏幕上输入两次。现在给出正确的输入的字符串 s 和用这个坏键盘输入这个字符串后在屏幕上显示的字符串 t。通过这两个字符串确定出是那些键坏了。分析：因为坏的键按一下会打印两次，若一个键是坏的话则它在 s 中一个其中字符相同的连续的子串长度为 l，那么对应在 t 中其长度就应该是 2 * l。那么就检查 s 中每一个连续相同的子串在 t 中显示的长度是否是 2 * l，如果
2021-07-29 00:33:03
108
原创 Kattis Problem - Planina
Kattis Problem - Planina原题地址题目类型：规律题意：首先平面上有四个点形成的方块，每次进行如下操作：在相邻顶点的中间添加一个点以及在此方块的中心添加一个点。求经过 N 此迭代后点阵中点的数量。分析：枚举观察几个样例后发现点阵边上点的数量的变化规律为 x+(x −1)，而点阵中点的数量则是边长的乘积。因为数据范围较小可以事先打表提升效率(貌似没啥用)。代码：static final int[] TB = {0, 9, 25, 81, 289, 1089, 4225, 1
2021-07-29 00:24:23
90
原创 Kattis Problem - Hot Springs
Kattis Problem - Hot Springs原题地址题目类型：构造题意：重排一个含有 n 个整数的序列，使得所有的 |a_(i−1) − a_i |≤|a_i − a_(i+1) |。分析：先对数组排序。然后考虑最大的差的绝对值是 a_max − a_min, 然后将最大值放在第 n - 1 的位置，将最小值放在第 n 的位置。然后再剩下的数中选择最大值和最小值，按相同的逻辑进行构造。代码：public static void solve() throws IOExcept
2021-07-29 00:12:13
263
原创 Kattis Problem - Jack-O‘-Lantern Juxtaposition
Kattis Problem - Jack-O’-Lantern Juxtaposition原题地址题目类型：数学、排列组合题意：现在有眼睛、鼻子、嘴巴三种设计分别有 N、T、M 种。可以通过随意从中各取一个进行组合得到不同的设计。统计总共有多少种不同的设计。分析：排列组合问题。代码：public static void solve() throws IOException { int N = nextInt(); int T = nextInt(); int M =
2021-07-29 00:08:33
101
原创 Kattis Problem - Sibice
Kattis Problem - Sibice原题地址题目类型：数学题意：在地上散落了一些火柴，每个火柴都有各自的长度，现在需要将它们收集到一个长 h、宽 w 的火柴盒中，判断有哪些火柴可以装进去，哪些不可以装进去。分析：火柴盒可以装的最大长度的火柴是它的斜边的长度，然后用每个火柴和斜边的长度进行比较。代码public static void solve() throws IOException { int n = nextInt(); int w = nextInt();
2021-07-29 00:03:25
109
原创 Kattis Problem - Contest Struggles
Kattis Problem - Contest Struggles原题地址题目类型：数学题意：给出 n 道题难度的平均分 d（一道题难度的分值为[0, 100]），猜测其中 k 道题难度的平均分为 s。判断这个猜测是否正确，如果正确输出剩余题目的平均分，否则输出 impossible。分析：通过 n * d 算出总分数，然后减去 k * s 得到剩余题目难度的总分，然后再除 n - k，判断结果是否在 [0, 100]范围内（输出时注意精度）。代码：public static void
2021-07-28 23:55:46
107
原创 Gym 103117 Problem - Spicy Restaurant
Gym 103117 Problem - Spicy Restaurant原题地址题目类型：搜索、BFS、打表题意：有 n 个火锅店位置为 1～n，每个火锅店都有一个辣度，并且 n 个火锅店之间有 m 条无向边相连。现在有 q 组询问，每次给出一位游客的具体位置，和他能忍受的最大辣度。求出这个游客可以到达的辣度不超过其忍耐限度且途经路径最少的火锅店，并输出最短的路径长度，如果不存在这样的饭店则输出 -1。分析：看到求最短路径很容易想到用 BFS，但是查询有 5e5次，显然不能每次都搜一遍
2021-07-28 23:38:00
302
原创 Kattis Problem - Yoda
Kattis Problem - Yoda原题地址题目类型：模拟题意：给定两个数字，从它们的最低位开始进行比较，该位数字的值严格小于另一方的，则该位的数字会掉落。最终两个数字的值会变为多少。分析：因为是需要每一位都进行比较，所以使用字符串处理会更方便。代码：public static void solve() throws IOException { char[] a = next().toCharArray(); char[] b = next().toCharArray
2021-07-28 22:54:27
102
原创 Kattis Problem - Freckles
Kattis Problem - Freckles原题地址题目类型：最小生成树题意：在纸上有 n 个点（坐标形式给出），可以用钢笔划线将点连接起来。现在需要用钢笔连线使得所有的点都连通，并使用墨水最少，画线使用墨水的值等于线的长度。分析：很明显是要求其最小生成树。在每两个点之间建边，长度为其之间的距离，然后使用 Prim 算法求其最小生成树。使用 Kruskal 算法会超时。代码static double[] x;static double[] y;static double[][] G
2021-07-28 22:45:47
76
原创 洛谷 Problem P1119 - 灾后重建
洛谷 Problem P1119 - 灾后重建原题地址题目类型：最短路径、Floyd题意：在一个有向图中，每个结点只有在时间 t 之后才有效（该节点无效的时候与它相连的边无效），一条边有效IFF与它相连的两个节点都是有效的。现在给出 0～n-1 每个节点生效的时间点。然后给出 q 次询问，每次查询 x 和 y 节点在 t 时刻时的最短路径，如果不存在输出 -1。查询的时间 t 是递增的！分析：最先的想法是每次查询时建图跑 Floyd，但是这样效率无法接受。但是节点的个数很小，且输入和查询的 t
2021-07-28 22:30:00
77
原创 洛谷 Problem P1629 - 邮递员送信
洛谷 Problem P1629 - 邮递员送信原题地址题目类型：最短路径、Dijkstra题意：在一个有向图中，给定一个起点，对于其余的每个点进行从起点走到该点再返回起点的操作，求最终经过的总路程。分析：首先可以想到用 Dijkstra 算法求出从起点到各个点的最短距离，但是到达每个点后还要返回，这个路径应该也是最短的，但因为是有向图我们无法直接求得。但是可以重新反向建图，即将原来的边反向连，然后再用 Dijkstra 算法来求最短路。此时求得的最短路就是所有点走向起点的最短路径。代码s
2021-07-28 22:20:33
82
原创 Kattis Problem - Popular Vote
Kattis Problem - Popular Vote原题地址题意有 n 个候选人，给出每个人获得的投票数，判断谁能获胜。分析先对其进行排序，如果票数最多的和第二多的票数一样则说明没有获胜者，如果最多的票数的 2 倍大于总票数则是 Majority winner 否则是 Minority winner。代码public static void solve() throws IOException { int n = nextInt(); Pair[] a = ne
2021-07-10 09:15:01
84
原创 Kattis Problem - Elementary Math
Kattis Problem - Elementary Math原题连接题意有 n 对整数，每对整数都可以使用 +、-、* 三种运算符进行运算。现在需要为每对整数选择一种运算符，并且保证最终 n 对整数的解都是不同的。分析对于每对数因为都有三种运算符，所以都有三个解，可以将每对数与它的解之间连一条边，则每对数与所有可能解构成一个二分图，然后就可以使用匈牙利算法来进行二分图的最大匹配。如果最后匹配了 n 个则说明存在解，然后根据匹配的结果输出每对数使用的运算符，否则无解。因为操作数比较大，所有要先离
2021-07-09 23:36:59
128
原创 Codeforces Round #724 (Div. 2)
Codeforces Round #724 (Div. 2)原题地址A. Omkar and Bad Story题意当一个数组中任意两个数的绝对值在数组中都存在且每个数都唯一则称这个数组好。现在可以通过向数组中添加任意多个数（数组最终大小不超300），然后判断能否得到一个好数组。分析首先数组中数的大小为 [−200, 200]，所以考虑负数的情况。假设 b < 0 则 |a - b| > a，所以数组会无限增长从而无法得到一个好数组。而正数差的绝对值的范围定在 [0, 100] 范围
2021-07-09 20:18:50
107
原创 Kattis Problem - Island Hopping
Kattis Problem - Island Hopping原题链接题意有 m 个岛，给出每个岛的坐标，在两个岛之间建桥的花费等于两个岛之间的距离。求使所有岛连通所需要建桥的最小花费。分析很明显是要求其最小生成树。在每两个岛之间建边，长度为其之间的距离，然后使用 Kruskal 算法求其最小生成树。代码static int[] fa;public static void solve() throws IOException { int m = nextInt();
2021-07-09 11:14:38
220
原创 Kattis Problem - Soundex
Kattis Problem - Soundex原题链接题意给定 Soundex Code 编码的规则，将输入的字符串转为 Soundex Code 编码。分析模拟即可，注意没有定义 Soundex Code 编码的字符不用处理，连续 Sound Code 编码相同的字符视为一个。代码static final int[] TB = {0, 1, 2, 3, 0, 1, 2, 0, 0, 2, 2, 4, 5, 5, 0, 1, 2, 6, 2, 3, 0, 1, 0, 2, 0, 2};p
2021-07-09 10:21:58
126
原创 Kattis Problem - The Dragon of Loowater
Kattis Problem - The Dragon of Loowater原题链接题意你的王国里有一条 n 个头的恶龙，你希望雇一些骑士把它杀掉（即砍掉所有的头）。村里有 m 个骑士可以雇佣，一个能力值为 x 的骑士可以砍掉恶龙一个直径不超过 x 的头，且需要支付 x 个金币。如何雇佣骑士才能砍掉恶龙所有的头，且需要支付的金币最少？注意，一个骑士只能砍一个头（且不能被雇佣两次）。分析将龙的每一个头的直径和骑士的身高从小到大排序，然后一个一个的砍（能砍的就砍，不能砍的就下一个）。最后判断能否将所
2021-07-09 09:16:03
140
原创 LA 7735 - Pocket Cube
LA 7735 - Pocket Cube原题链接题意给定一个二阶魔方每个面的状态，求能否在一步内将魔方还原。分析根据题目描述得出每个颜色在输入得数组中得下标。然后就是模拟魔方转动的过程并判断是否还原。思考后可以发现，只有六种转动的情况和一种不转的情况（顺时针转动前面的面等价于逆时针转动后面的面），所以以枚举每种情况进行判断。最好用纸折一个立方体，然后将每个颜色对应的下标写上去调参更方便、准确。PS：题目数据貌似有问题，输入的 N 应该比实际的测试数据多一个，用 Java 不做处理是过不了的
2021-07-09 09:12:39
85
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人