爱飞鱼的blog

AtCoder Beginner Contest 352 https://atcoder.jp/contests/abc352

链接：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 10^5)n,q(1≤n≤5⋅105),(1≤q≤5⋅105)，分别表示河流的段数和管理的天数。 第二行为nnn个整数ai(1≤i≤n),(1≤ai≤109)a_i(1\le i\le n),(1\le a_i\le...

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，策略是从最大的出现奇数次开的数开始拿。 12345678910void solve(){ cin>>n; map<int,int>mp; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)mp[a[i]]++; bool...

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) 的可能对数。 Sol:注意只能顺时针，所以固定起点的时候，到达任何一个点的路程都是确定的。考虑破环成链，维护%mod意义下的前缀和一个map桶，像滑动窗口维护这个map。但要注意边界，因aia_{i}ai​表示的是一条边。 12345678910111213141516171819202122232425262728293031void solve() { cin >> n >> m; ...

123456789101112131415161718192021222324252627282930313233343536373839struct 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; } bool same(int x, int y) { return...

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不连通或者图中存在负环 ...

https://www.luogu.com.cn/problem/P5752 https://codeforces.com/contest/598/problem/E cf这个题考虑dp预处理，状态是三维的，转移是分割方案和所分块需要获得的巧克力数量。最后题目多次询问可以o（1）快速查询的 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273// 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...

AtCoder Beginner Contest 320 https://atcoder.jp/contests/arc106/tasks/arc106_e

三分法是二分法的变种，他最基本的用途是求单峰函数的极值点。 三分适用的情况：有唯一的最大值，满足最大值左侧严格单调递增，右侧严格单调递减（或左减右增）。强调严格单调，这样在确定最值是才能判断最值的位置，否则三分法不能缩小左右边界。 三分整数模板 整数的三分可能具有不确定性，可以通过改变while循环的条件while(l+3<r)来缩小范围，再通过小范围暴力更新答案 对于边界的暴力不仅省去了处理边界，甚至常数也有提升，原因未知 凹函数的极小值 123456789101112131415int sfmin(){ int l=0,r=1e9; while(l+2<r){ //cerr<<l<<" "<<r<<endl; int m1=(r-l)/3+l; int m2=r-(r-l)/3; if(cal(m1)>cal(m2))l=m1; else r=m2; } int ans=cal(l); for(int...

利用优先队列维护序列前k大的和 https://codeforces.com/contest/1969/problem/D https://sua.ac/wiki/2023-icpc-nanjing/g/ https://qoj.ac/submission/408738 注意排序的技巧 123456789101112131415161718192021222324252627282930313233343536373839#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); for (auto& x : a) cin >> x; ...