AtCoder Beginner Contest 352
title: AtCoder Beginner Contest 352 categories: ICPC tags: null abbrlink: c823ce06 date: 2024-11-27 00:00:00 AtCoder Beginner Contest 352 https://atcoder.jp/contests/abc352
一类链式并查集问题
title: 一类链式并查集问题 categories: ICPC tags: null abbrlink: 1875215d date: 2024-11-23 00:00:00 链接：https://ac.nowcoder.com/acm/contest/69510/G 来源：牛客网 你在一个星球上，外星人amiloac想让你管理一条河流，该河流有xxx段，每两段之间有一个挡板隔开，每一段都有各自的颜色aaa。你需要管理qqq天，每一天你需要做以下的一种操作。 1 l r1\ l\ r1 l r将第lll至rrr段河流的所有未打开的挡板打开。 2 x2\ x2 x询问你第xxx段河流的颜色是什么。 对于任意相邻的两段，它们之间的隔板被打开后的瞬间，河流的颜色会混合变成颜色最深的河流的颜色，aaa越大，颜色越深。 注：隔板打开后，河流的段数不会变。请注意不同寻常的空间限制！ 第一行为两个整数n,q(1≤n≤5⋅105),(1≤q≤5⋅105)n,q(1\le n \le 5 \cdot 10^5),(1\le q\le 5 \cdot...
Codeforces Round 960 (Div. 2)A-E
title: Codeforces Round 960 (Div. 2)A-E categories: ICPC tags: null abbrlink: 73d95a8b date: 2024-11-22 00:00:00 Codeforces Round 960 (Div. 2)A-E A题意：公平博弈。给定一个数组n个数，每个数只能用一次。给一个mxmxmx。每次轮到自己操作的时候就选一个数组里的数，满足a[i]>=mxa[i]>=mxa[i]>=mx,然后令mx=a[i]mx=a[i]mx=a[i].双方轮流做直到一方无法操作，则另一方取胜。 Sol:赛时1min猜了个错解，只看最大值，只看最大值的出现次数，回来发现wa了。如果最大值出现偶数次，但次大值出现奇数次，先手也能win。递归考虑这个过程我们发现只需要统计所有数出现次数的奇偶性。只要出现一个奇数先手就能win，策略是从最大的出现奇数次开的数开始拿。 void solve(){ cin>>n; ...
AtCoder Beginner Contest 367
title: AtCoder Beginner Contest 367 categories: ICPC tags: null abbrlink: 9364694a date: 2024-11-17 00:00:00 AtCoder Beginner Contest 367 待补：ABC 367 G 题解 - spdarkle - 博客园 (cnblogs.com) D.一个湖周围有 NNN 个休息区。 这些休息区按顺时针顺序编号为 111 、 222 、…、 NNN 。 从休息区 iii 顺时针走到休息区 i+1i+1i+1 需要 AiA_iAi 步。(其中休息区 N+1N+1N+1 指的是休息区 111 ）。 从休息区 sss 顺时针走到休息区 ttt （ s≠ts \neq ts=t ）所需的最小步数是 MMM 的倍数。 求 (s,t)(s,t)(s,t)...
不带权并查集——jly
title: 不带权并查集——jly categories: ICPC tags: null abbrlink: a22bffbd date: 2024-11-11 00:00:00 struct DSU { vector<int> f, siz; DSU() {} DSU(int n) { init(n); } void init(int n) { f.resize(n); std::iota(f.begin(), f.end(), 0); siz.assign(n, 1); } int find(int x) { while (x != f[x]) { x = f[x] = f[f[x]]; } return x; } ...
bellman-ford算法理解
title: bellman-ford算法理解 categories: ICPC tags: null abbrlink: 98c51b99 date: 2024-10-25 00:00:00 bellman-ford算法理解 从本题谈起再回归到最短路。本题为限制边数的最短路，是这个算法优势领域的题目。为什么它能解决？ 最外层每循坏一次，就是各点向外走一条边，内层对边的遍历是对所有边进行松弛操作，每次进行该操作时，需要用到备份数组，目的是防止连锁反应，保证每次每个点到起点的距离只能因为上一轮的更新而更新。 若只是求最短路，则外层循坏n-1次。为什么是n-1？ 假如最短路存在，认为没有负环 从上面算法理解可以知道，外层n-1次相当于起点已经走过了n-1条边（bfs到n-1层） 那么从最坏情况考虑，由于已经假设最短路存在，那么其长度应该<=n-1. 假如最短路不存在 而如果n-1条边还没有更新到d[n]，即没有找到一条长度<=n-1的路径从1能到n，说明n可能和1不连通或者图中存在负环 ...
一类适合记忆化搜索的区间dp
title: 一类适合记忆化搜索的区间dp categories: ICPC tags: null abbrlink: 1b068ffa date: 2024-10-25 00:00:00 https://www.luogu.com.cn/problem/P5752 https://codeforces.com/contest/598/problem/E cf这个题考虑dp预处理，状态是三维的，转移是分割方案和所分块需要获得的巧克力数量。最后题目多次询问可以o（1）快速查询的 // Problem: E. Chocolate Bar // Contest: Codeforces - Educational Codeforces Round 1 // URL: https://codeforces.com/contest/598/problem/E // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include...
AtCoder Beginner Contest 320
title: AtCoder Beginner Contest 320 categories: ICPC tags: null abbrlink: 696c39ed date: 2024-10-24 00:00:00 AtCoder Beginner Contest 320 https://atcoder.jp/contests/arc106/tasks/arc106_e
三分法
title: 三分法 categories: ICPC tags: null abbrlink: 7481085d date: 2024-10-22 00:00:00 三分法是二分法的变种，他最基本的用途是求单峰函数的极值点。 三分适用的情况：有唯一的最大值，满足最大值左侧严格单调递增，右侧严格单调递减（或左减右增）。强调严格单调，这样在确定最值是才能判断最值的位置，否则三分法不能缩小左右边界。 三分整数模板 整数的三分可能具有不确定性，可以通过改变while循环的条件while(l+3<r)来缩小范围，再通过小范围暴力更新答案 对于边界的暴力不仅省去了处理边界，甚至常数也有提升，原因未知 凹函数的极小值 int sfmin(){ int l=0,r=1e9; while(l+2<r){ //cerr<<l<<" "<<r<<endl; int m1=(r-l)/3+l; int...
利用优先队列维护序列前k大的和
title: 利用优先队列维护序列前k大的和 categories: ICPC tags: null abbrlink: afb59531 date: 2024-10-19 00:00:00 利用优先队列维护序列前k大的和 https://codeforces.com/contest/1969/problem/D https://sua.ac/wiki/2023-icpc-nanjing/g/ https://qoj.ac/submission/408738 注意排序的技巧 #include <bits/stdc++.h> using namespace std; #define sz(a) int((a).size()) using li = long long; int main() { int t; cin >> t; while (t--) { int n, k; cin >> n >> k; vector<int> a(n),...