爱飞鱼的blog

title: AtCoder Beginner Contest 352categories: - ICPCtags: - nullabbrlink: c823ce06date: 2024-11-27 00:00:00AtCoder Beginner Contest 352https://atcoder.jp/contests/abc352

title: 一类链式并查集问题categories: - ICPCtags: - nullabbrlink: 1875215ddate: 2024-11-23 00:00:00链接：https://ac.nowcoder.com/acm/contest/69510/G来源：牛客网 你在一个星球上，外星人amiloac想让你管理一条河流，该河流有$x$段，每两段之间有一个挡板隔开，每一段都有各自的颜色$a$。你需要管理$q$天，每一天你需要做以下的一种操作。 $1\ l\ r$将第$l$至$r$段河流的所有未打开的挡板打开。 $2\ x$询问你第$x$段河流的颜色是什么。 对于任意相邻的两段，它们之间的隔板被打开后的瞬间，河流的颜色会混合变成颜色最深的河流的颜色，$a$越大，颜色越深。 注：隔板打开后，河流的段数不会变。请注意不同寻常的空间限制！ 第一行为两个整数$n,q(1\le n \le 5 \cdot 10^5),(1\le q\le 5 \cdot 10^5)$，分别表示河流的段数和管理的天数。第二行为$n$个整数$a_i(1\le i\le...

title: Codeforces Round 960 (Div. 2)A-Ecategories: - ICPCtags: - nullabbrlink: 73d95a8bdate: 2024-11-22 00:00:00Codeforces Round 960 (Div. 2)A-EA题意：公平博弈。给定一个数组n个数，每个数只能用一次。给一个$mx$。每次轮到自己操作的时候就选一个数组里的数，满足$a[i]>=mx$,然后令$mx=a[i]$.双方轮流做直到一方无法操作，则另一方取胜。Sol:赛时1min猜了个错解，只看最大值，只看最大值的出现次数，回来发现wa了。如果最大值出现偶数次，但次大值出现奇数次，先手也能win。递归考虑这个过程我们发现只需要统计所有数出现次数的奇偶性。只要出现一个奇数先手就能win，策略是从最大的出现奇数次开的数开始拿。 void solve(){ cin>>n; map<int,int>mp; for(int...

title: AtCoder Beginner Contest 367categories: - ICPCtags: - nullabbrlink: 9364694adate: 2024-11-17 00:00:00AtCoder Beginner Contest 367待补：ABC 367 G 题解 - spdarkle - 博客园 (cnblogs.com) D.一个湖周围有 $N$ 个休息区。这些休息区按顺时针顺序编号为 $1$ 、 $2$ 、……、 $N$ 。从休息区 $i$ 顺时针走到休息区 $i+1$ 需要 $A_i$ 步。(其中休息区 $N+1$ 指的是休息区 $1$ ）。从休息区 $s$ 顺时针走到休息区 $t$ （ $s \neq t$ ）所需的最小步数是 $M$ 的倍数。求 $(s,t)$ 的可能对数。 Sol:注意只能顺时针，所以固定起点的时候，到达任何一个点的路程都是确定的。考虑破环成链，维护%mod意义下的前缀和一个map桶，像滑动窗口维护这个map。但要注意边界，因$a_{i}$表示的是一条边。 void solve() { ...

title: 不带权并查集——jlycategories: - ICPCtags: - nullabbrlink: a22bffbddate: 2024-11-11 00:00:00struct 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; } ...

title: bellman-ford算法理解categories: - ICPCtags: - nullabbrlink: 98c51b99date: 2024-10-25...

title: 一类适合记忆化搜索的区间dpcategories: - ICPCtags: - nullabbrlink: 1b068ffadate: 2024-10-25 00:00:00https://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...

title: AtCoder Beginner Contest 320categories: - ICPCtags: - nullabbrlink: 696c39eddate: 2024-10-24 00:00:00AtCoder Beginner Contest 320 https://atcoder.jp/contests/arc106/tasks/arc106_e

title: 三分法categories: - ICPCtags: - nullabbrlink: 7481085ddate: 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...

title: 利用优先队列维护序列前k大的和categories: - ICPCtags: - nullabbrlink: afb59531date: 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), b(n); ...