WORIA

http://codeforces.com/gym/103202 H. The Boomsday Project   题意：共享单车，每次骑要花费 rrr 元。另外还有 nnn 种租赁方式，每种方式在购买后 did_idi​ 天内有效，在有效期内能免费骑 kik_iki​ 次，购买需要花费 cic_ici​ 元。给出 mmm 条骑车记录，在第 pip_ipi​ 天骑了 qiq_iqi​ 次，问最少花费。1≤n≤500,1≤m≤105,1≤r≤109,1≤di,ki,ci≤109,0≤pi≤109,0≤qi≤3×105,∑i=1mqi≤3×1051\leq n \leq 500, 1 \leq m \leq 10^5, 1 \leq r \leq 10^9,1 \leq d_i, k_i, c_i \leq 10^9,0 \leq p_i \leq 10^9, 0 \leq q_i \leq 3 \times 10^5, \sum_{i=1}^m q_i \leq 3 \times 10^51≤n≤500,1≤m≤105,1≤r≤109,1≤di​,ki​,ci​≤109,0≤pi​≤1 ...

https://ac.nowcoder.com/acm/contest/12548 M - Stone Games   题意：给定一个数组，多次询问，每次询问给定L，R，问最小的，不能由区间 [L,R][L,R][L,R] 中的数求和得到的数值。 主席树 建立一个权值线段树，假设用左子树中的权值能凑出 111 到 XXX 中所有的数，数组中位于右子树的元素和为 SSS，则用整棵树能凑出 111 到 X+SX+SX+S 中所有的数。但是如果 XXX 小于数组中最小的且位于右子树的数-1，则说明一定有数无法被凑出来。这时就找到了答案。 因此对于这棵权值线段树，从权值 1 开始，不断合并右侧兄弟子树，合并前判断是否大于右侧子树最小值-1，这就需要递归右侧子树。所以总的复杂度为 O(Qlog⁡2(109))O(Q\log^2(10^9))O(Qlog2(109))。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include&l ...

https://ac.nowcoder.com/acm/contest/7501 B - Intelligent Robot   题意：k 个线段，二维平面，要从 (sx,sy) 走到 (tx,ty)，不能穿过线段，问最短距离。 线段相交判断+最短路 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include <bits/stdc++.h>#define debug(x) cout << #x << ":\t" << (x) << endl;using namespace std;#define ll long longconst int N = 2e6 + 10;const int INF = 0x3f3f3f3f;c ...

https://ac.nowcoder.com/acm/contest/10272 M - Monster Hunter   题意：给定一棵树，有点权，每个点上有个怪物，击杀节点 u 上的怪物的代价为 u 的点权 + u 的儿子的点权和。初始时可以选择 kkk 个节点，击杀这些点上的怪物，后续就不需要统计它们的代价，并且计算它们父亲上怪物的代价时也不需要考虑已被击杀的节点。接下来从根开始往下击杀怪物，并求代价和。对于每一个 kkk，求最小代价。 树形dp+背包 dp[u][j][1/0]dp[u][j][1/0]dp[u][j][1/0] 表示 uuu 的子树中击杀了 jjj 个，且 uuu 是/否被击杀，的最小代价。 则需要将 jjj 分配给 uuu 的各个儿子以求得最小值。所以需要背包。 遍历每一个儿子，更新dp数组。把一个儿子看成一种物品，每种可以拿多个，代价不同。 还要保证每层循环枚举的范围都是合法的，即不可能枚举到不存在的情况。这样每两个点只会在他们的LCA处被枚举到，复杂度就是 O(n2)O(n^2)O(n2)。 这种分配问题求最小值的应该要首先考虑背包！ 12345678 ...

https://ac.nowcoder.com/acm/contest/9925 H - Rice Arrangement   题意：给定一个有 n 个位置的圆桌，其中 k 个位置上有人，k 个位置上有饭，饭放在桌上的转盘上，每次可以顺时针或逆时针旋转一格，当一碗饭与一个人在同一位置时，这个人可以吃也可以不吃。要求旋转最少次数使得每个人都有饭吃。 枚举+思维 只可能：始终顺时针转，始终逆时针转，先顺时针再逆时针转，先逆时针转再顺时针转。最多只会改变一次方向。 枚举起点，之后的人按顺序吃对应的饭，则需要顺时针转的角度为所有人需要顺时针转的角度的最大值。逆时针类似。 再考虑改变方向的情况。枚举在变成逆时针转之前，顺时针转的角度，那么需求量小于等于这个角度的人都吃到饭了，只剩下大于这个角度的人。他们需要逆时针转的角度为它们 n - 顺时针转的角度的最小值。 先逆时针再顺时针类似。 实现方法非常巧妙，只需要按照顺时针转的角度排序即可，因为排序后，没有吃到饭的人的“顺时针转的角度的最小值”就是下一个值。 需要注意如果顺时针转的角度为 0，逆时针需要转的角度也应该是0，而不是 n。但是这一点在实现 ...

https://www.cometoj.com/contest/18/problems A. 夺宝奇兵   题意：mm的网格上有n类宝藏，每类有两个，给出坐标，需要按1到n，再从n到1的顺序拿取所有宝藏。求最小距离。 相邻两类宝藏直接比较怎么拿距离最近，就直接拿掉，最后n到n距离固定。 123456789101112131415161718192021222324252627#include<bits/stdc++.h>using namespace std;#define ll long longtypedef pair<ll, ll> pii;const int INF = 0x3f3f3f3f;const int maxn = 1e5 + 10;const int mod = 1e9 + 7;int n, m;pii A, B, C, D;ll dis(pii a, pii b) { return abs(a.first - b.first) + abs(a.second - b.second);}ll ans;int main() & ...

https://www.cometoj.com/contest/14/problems D. 精简改良   题意：给定一张无向连通图，要求删除一些边，使得新图仍联通，且任意两点的距离之和最长，求这个距离和。 斯坦纳树 数据范围很小，明显是要状压dp。 如果存在环，一定可以有更好的答案。所以最后的结果一定是一棵生成树。 dp[S][u]dp[S] [u]dp[S][u] 表示在点集 SSS 上，以 uuu 为根的生成树的最优解，此时的点集 SSS 中的答案必定是已经确定的了，即这个生成树上的所有边都不会再在其他地方有任何改变。 枚举 SSS 的子集 TTT ，同时得到 S−TS-TS−T，设为 KKK，则 S=T+KS=T+KS=T+K 。接下来试着把 TTT 和KKK 合并，以得到 SSS ：枚举 KKK 中的点 uuu ，作为合并后的根节点，则从 uuu 向 TTT 中点 vvv 连边，同时加入边 (u,v)(u,v)(u,v) 的贡献，注意，由于上面说的生成树中的边不会再有改变了，所以此时计算贡献应该把全局的贡献都算上，而不仅仅是在点集 SSS 上的贡献。 123456789101 ...

https://www.cometoj.com/contest/7/problems B. 吃豆豆   题意：有 n⋅mn\cdot mn⋅m 个格子，每个格子在 T[i][j]T[i] [j]T[i][j] 的倍数时会出现一颗糖，下一秒马上消失，若此时wls在这个格子上，就能得到一颗糖。问wls从S到T，至少拿到C颗糖，最少时间。 直接bfs搜，每个点可能呆着不动或者上下左右走，所以五个方向拓展，呆着不动的话直接跳到下一次出现糖的时候。 或者dp也一样。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include<bits/stdc++.h>using namespace std;#define ll long longtypedef pair<int, int> pii;const int INF = 0x3f3f3f3f;const int maxn = 1e5 + 10;int n, ...

http://codeforces.com/gym/102501 按难度排序 F. Icebergs   题意：给定几块不相交的多边形，问面积和。 直接抄板子即可，面积由向量叉乘得到，注意得到的是有向面积，可能为负，要绝对值。 123456789101112131415161718192021222324252627282930313233#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const int N = 2e5 + 10;struct Point{ double x, y; Point(double x = 0, double y = 0) :x(x), y(y) { }};typedef Point Vector;Vector operator-(Point A, Point B) { return Vector( ...

https://codeforces.com/gym/102500 按难度排序 I. Inverted Deck   题意：给定一个序列，问能否翻转一个区间后变为非递减。 找到一个尽量大的非递增的区间，把它翻过来。判断结果是否满足非递减。 1234567891011121314151617181920212223#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const int N = 1e6 + 10;int n;int a[N];int main() { scanf("%d", &n); for (int i = 1; i <= n; i++)scanf("%d", &a[i]); int L = INF, R = 0; for (int i = 2; i <= n; i++) { i ...