Codeforces
| # | 提交时间 | 提交者 | 问题 | 语言 | 判题状态 | 时间 | 内存 |
|---|---|---|---|---|---|---|---|
| 270289706 | Jul/13/2024 16:04UTC+8 | 0x22 | E - Novice's Mistake | C++14 (GCC 6-32) | Accepted | 124 ms | 0 KB |
| 270271674 | Jul/13/2024 13:39UTC+8 | 0x22 | D - Test of Love | Python 3 | Accepted | 171 ms | 10200 KB |
| 270269583 | Jul/13/2024 13:19UTC+8 | 0x22 | D - Lunar New Year and a Wander | C++14 (GCC 6-32) | Accepted | 140 ms | 13000 KB |
| 270265069 | Jul/13/2024 12:22UTC+8 | 0x22 | D - Secret Passwords | C++14 (GCC 6-32) | Accepted | 93 ms | 12300 KB |
| 270161836 | Jul/12/2024 18:49UTC+8 | 0x22 | C - K-special Tables | C++14 (GCC 6-32) | Accepted | 93 ms | 1000 KB |
| 270154658 | Jul/12/2024 17:44UTC+8 | 0x22 | C1 - Brain Network (easy) | C++14 (GCC 6-32) | Accepted | 62 ms | 0 KB |
| 270150873 | Jul/12/2024 17:12UTC+8 | 0x22 | B - Mahmoud and Ehab and the bipartiteness | C++14 (GCC 6-32) | Accepted | 171 ms | 15400 KB |
| 270141643 | Jul/12/2024 16:01UTC+8 | 0x22 | B - Plus from Picture | C++14 (GCC 6-32) | Accepted | 62 ms | 300 KB |
| 270133131 | Jul/12/2024 15:05UTC+8 | 0x22 | B - Simple Game | C++14 (GCC 6-32) | Accepted | 78 ms | 0 KB |
| 269952218 | Jul/11/2024 23:07UTC+8 | 0x22 | C - Gorilla and Permutation | C++14 (GCC 6-32) | Accepted | 77 ms | 400 KB |
| 269927226 | Jul/11/2024 22:51UTC+8 | 0x22 | B - Angry Monk | C++14 (GCC 6-32) | Accepted | 93 ms | 800 KB |
| 269898935 | Jul/11/2024 22:36UTC+8 | 0x22 | A - Only Pluses | C++14 (GCC 6-32) | Accepted | 46 ms | 0 KB |
| 269851490 | Jul/11/2024 16:47UTC+8 | 0x22 | D - Array and Operations | C++14 (GCC 6-32) | Accepted | 77 ms | 0 KB |
| 269832328 | Jul/11/2024 14:39UTC+8 | 0x22 | F - Forever Winter | C++14 (GCC 6-32) | Accepted | 109 ms | 0 KB |
| 269828248 | Jul/11/2024 14:06UTC+8 | 0x22 | B - Magic Forest | C++14 (GCC 6-32) | Accepted | 77 ms | 0 KB |
| 269515191 | Jul/09/2024 13:59UTC+8 | 0x22 | C - Nice Garland | C++14 (GCC 6-32) | Accepted | 93 ms | 0 KB |
1618C Array and Operations
动态规划（dp）贪心（greedy）数学（math）*1300
题目大意：必须做完k次操作，每次选两个位置不同的元素x和y，移除这两个元素，把 x/y 加到你的分数里面，问最少可得到的分数是多少
显然要让分数最少，就要让 x/y 尽可能为0
先对数组排序，因为 2k <= n，所以在没有进行操作的情况下，基础分是前 n-2*\k 项的和
接下来 从排序后的数组的后面开始进行操作 需要固定k次操作，排序之后，只有两种情况：
1. 分子等于分母，分数+1
2. 分子小于分母，分数不变
k次操作后即是最优解
862B Mahmoud and Ehab and the bipartiteness
DFS及其变种（dfs and similar）图论（graphs）树形结构（trees）*1300
题目大意：给你一棵树，问给这棵树最多可以加多少边，这棵树仍然是一个二分图
二分图：图中的节点可以分为两个点集u1, u2，对于所有在u1的顶点对其他u1的点都没有边，对于所有在u2的顶点对其他u2的点都没有边
我们使用DFS进行染色法，染成true的在u1，false在u2，开一个col数组记录顶点颜色，a，b分别记录不同颜色节点的数量
循环所有顶点的边，每个顶点它可以添加的最大边数是：它不同颜色集合中的节点数 - 它连接的顶点数
Leetcode
| 最近提交时间 | 题目 | 题目难度 | 提交次数 |
|---|---|---|---|
| 3 天前 | #2970 统计移除递增子数组的数目 I | 简单 | 1 次 |
| 4 天前 | #343 整数拆分 | 中等 | 2 次 |
| 4 天前 | #63 不同路径 II | 中等 | 6 次 |
| 4 天前 | #62 不同路径 | 中等 | 1 次 |
| 4 天前 | #1143 最长公共子序列 | 中等 | 3 次 |
| 4 天前 | #300 最长递增子序列 | 中等 | 3 次 |
| 5 天前 | #3102 最小化曼哈顿距离 | 困难 | 4 次 |
| 5 天前 | #1701 平均等待时间 | 中等 | 15 次 |
| 6 天前 | #238 除自身以外数组的乘积 | 中等 | 9 次 |
| 6 天前 | #724 寻找数组的中心下标 | 简单 | 2 次 |
| 6 天前 | #面试题 02.04 分割链表 | 中等 | 7 次 |
| 6 天前 | #LCR 036 逆波兰表达式求值 | 中等 | 8 次 |
| 7 天前 | #2915 和为目标值的最长子序列的长度 | 中等 | 6 次 |
| 7 天前 | #198 打家劫舍 | 中等 | 4 次 |
| 7 天前 | #70 爬楼梯 | 简单 | 3 次 |
最小化曼哈顿距离
给你一个下标从 0 开始的数组 points ，它表示二维平面上一些点的整数坐标，其中 points[i] = [xi, yi] 。
两点之间的距离定义为它们的 曼哈顿距离
请你恰好移除一个点，返回移除后任意两点之间的 最大 距离可能的 最小 值
最小的曼哈顿距离是 max({xi - xj + yi - yj, xi - xj - yi + yj, - xi + xj + yi - yj, - xi + xj - yi + yj})
我们把所有点的坐标换成 [xi - yi, xi + yi]，经过公式推导，对于所有i，我们得到最小曼哈顿距离：
max(max(xi) - min(xi), max(yi) - min(yi))
那么我们就把问题简化成了模拟。由于点的坐标可能有重复，所以创建两个multiset，分别维护x和y的最值，遍历所有的点，每次删点取最值代入公式即可得到答案。
Pintia
牛客
最优屏障 - https://ac.nowcoder.com/acm/problem/14666?time=1720594276239
单调栈