爱飞鱼的blog

#对于种类并查集主要是考虑清楚到根节点距离分为几类，每一类的意义 #有的题目相出d数组的含义才能想到用带权并查集 1234567891011//find函数需要变化int find(int x){ if (p[x] != x) { int root = find(p[x]); d[x] += d[p[x]]; p[x] = root; } return p[x];} #在查询过程中遇到两个不连通的点，需要合并操作，我们需要注意维护距离 123456789if(find(l)!=find(r)){//1.a[f[l]]=a[l]-d[l]2.a[f[r]]=a[r]-d[r]//现在要维护的是d[f[l]];//最终应该满足3.x=d[f[l]]=a[f[l]]-a[f[r]];//4.a[j]-a[r]=x;//将124代入3解得d[f[l]];d[f[l]]=x-d[l]+d[r];f[f[l]]=f[r];//不能颠倒顺序，先维护距离再移动根}

牛客周赛 Round 51 D：题意：给定一个1e6长度的十进制数a和一个1e9范围的b,求解gcd Solution：考虑用python直接做，发现TLE了，python确实比较慢。考虑本题的关键在于gcd算法的本质gcd(a,b)=gcd(a−b,b)gcd(a,b)=gcd(a-b,b)gcd(a,b)=gcd(a−b,b)，所以我们只需要模拟这个发现，我们只需要提前计算a%b即可，然后再用普通gcd就可以。 1234567891011void solve(){ string s; cin>>s; cin>>n; ll res=0; for(auto x:s){ res=res*10+x-'0'; res%=n; } cout<<gcd(res,n)<<endl;} ...

一段时间没打比赛，整个节奏没找到，对于会的问题代码实现的不够顺畅，对于看起来不会的问题总是有种先入为主的算法恐惧，其实不是算法不会，而是思维和灵性不够 c题是构造题，不难想到最小值出现次数一定是最多的，最小值具有的性质是相对位置不影响出现次数，对出现次数排序让整个问题清晰，想到这点整个问题便可以实现。 但这题非常坑的点题面说了构造的数组需要在-1e9到1e9之间，对于最后段可以随意构造的数组要注意只能构造成已经给出的数中的最大值，而不是最大值+1，不然很容易造数据hack，使你构造的数组中出现1e9+1 没出d是最值得反思的，只是一个简单的不等式代数移项就可以让整个题目豁然开朗，却因为对于题目背景描述而直接放弃。 赛后目前补了e和f，e题只有排序后才能让问题变得清晰，将数学推导式整体写出来再合并就可以发现只需要用前缀和就可以维护，这告诉我们看问题不能点到点的去看，一段一段的去看会有惊喜 f题的韦达定理很显然，核心在于对于解的所有情况的讨论和一元二次方程精度问题（普遍说sqrt精度很差）。对于sqrt可以直接自己写二分或用sqrtl? ...

链表 单链表 1234567891011121314151617181920212223242526272829303132333435void solve() { int n; cin >> n; int idx = 0; vector<int> nex(n + 1), e(n + 1); nex[0] = -1; int &head = nex[0]; auto insert = [&](int x, int k) { // 在地址为k的数后插入x idx++; nex[idx] = nex[k]; e[idx] = x; nex[k] = idx; }; auto del = [&](int k) { // 删除地址为k的数 nex[k] = nex[nex[k]]; }; for (int i = 1; i <= n; i++)...

看到B官方题解写了一堆，而如果能注意到一些性质，几行就写完了 题意：给一个A，B构成的字符串，可以将“AB”翻转成"BA",问最多可以进行多少次翻转？ 实际上在手动模拟以后发现，由于题目限制了每个位置只能翻转一次，所以情况简单了不少。 只要还没过最后一个B，那么最后一个B之前的所有A就会被反转。真正无效的部分是开头就是B，以及末尾的A，所以我们只需要找到第一个A，最后一个B即可，这两之间的所有位置都会被颠倒 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061// Problem: B. AB Flipping// Contest: Codeforces - CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)// URL: https://codeforces.com/contest/1896/problem/B// Memory...

无限制最长连续的子序列和 题目链接 动态规划转移方程 1dp[i] = max(dp[i-1] + a[i], a[i]); 最终结果在 dp 数组中线性扫描找出最大值： 12int pos = max_element(dp + 1, dp + 1 + n) - dp;cout << dp[pos] << " "; dp[i] 表示以序列中第 i 个数字结尾的最大子段和。 转移方程分析： 如果选择第 i-1 个数，则由 dp[i-1] 转移而来。 如果不选择第 i-1 个数，则只能自己作为一个子段存在，因为必须以第 i 个数结尾。 优化：记录子段端点 在题目中，还需要给出具体是哪段子段和最大（即左端点和右端点）。 初始方法：先求出最大值，再排序所有符合最大值的子段，按题目要求取左端和右端尽可能小的子段。 优化方法：在线性扫描时维护最大值，同时更新左右端点。 有长度限制最长连续的子序列和 类型：单调队列优化 DP 题目描述 给定一个长度为 n 的序列 a，找出其中元素总和最大且长度不超过 m 的连续子区间。 ...

牛客周赛 Round 51 D：题意：给定一个1e6长度的十进制数a和一个1e9范围的b,求解gcd Solution：考虑用python直接做，发现TLE了，python确实比较慢。考虑本题的关键在于gcd算法的本质gcd(a,b)=gcd(a−b,b)gcd(a,b)=gcd(a-b,b)gcd(a,b)=gcd(a−b,b)，所以我们只需要模拟这个发现，我们只需要提前计算a%b即可，然后再用普通gcd就可以。 1234567891011void solve(){ string s; cin>>s; cin>>n; ll res=0; for(auto x:s){ res=res*10+x-'0'; res%=n; } cout<<gcd(res,n)<<endl;} ...

由于题目补完才来写总结，导致前面的有的题目都需要重新再看一遍，只好当作复习了。 但考虑到趁热打铁，先看H. #H题： 从小白视角来看乍一看是博弈论，仔细思考以后发现是图论。本题给的是基环树，意识到这一点很重要，这个条件是让本题不是很复杂的关键。n个点n条边且没有重边保证这个联通图中只有一个环。由于瓦能够预测马去哪，当双方在环上时，瓦永远不会被抓到。若开始时瓦不在环上，则瓦的最优策略是找到去环上的最短路，而马的策略尽可能先到环去拦截瓦。 ...

1.io优化 1234const char endl = '\n'; //另外，请使用'\n'而不是 endl ，因为endl默认会增加刷新操作，而导致输出缓冲失效，降低效率。cin.tie(0);ios::sync_with_stdio(false); cin.tie(0) 和 ios::sync_with_stdio(false) 是 C++ 中用于优化输入输出的语句。 cin.tie(0) 的作用是取消 cin 与 cout 的绑定，默认情况下，当使用 cin 进行输入操作时，会先执行 cout 的缓冲输出。使用 cin.tie(0) 可以将 cin 和 cout 解绑，让它们可以独立地进行操作，从而提高输入输出的效率。 ios::sync_with_stdio(false) 则是取消 C++ 标准库输入输出流和 C 标准库输入输出流之间的同步。 默认情况下，C++ 标准库的输入输出流与 C 标准库的输入输出流是同步的，这就意味着在混合使用 C++ 的 cin/cout 和 C 的 scanf/printf...

dp优化 单调队列优化DP 优化方法大杂烩 I. - qAlex_Weiq - 博客园 (cnblogs.com) 123456789101112131415161718192021222324#include <iostream>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;const int N=1e5+10;int n,k,q[N];LL w[N],f[N],sum;int main(){ cin>>n>>k; k++; // for(int i=1;i<=n;i++) cin>>w[i],sum+=w[i]; int h=1,t=0; LL s=1e18; for(int i=1;i<=n;i++){ while(h<=t && f[q[t]]>=f[i-1]) t--; q[++t]=i-1; ...