算法学习——带权并查集dls版本
title: 算法学习——带权并查集dls版本categories: - ICPCtags: - nullabbrlink: 4fc43d7adate: 2024-03-16 00:00:00#对于种类并查集主要是考虑清楚到根节点距离分为几类，每一类的意义#有的题目相出d数组的含义才能想到用带权并查集 //find函数需要变化 int find(int x) { if (p[x] != x) { int root = find(p[x]); d[x] += d[p[x]]; p[x] = root; } return...
牛客周赛 Round 51题解
title: 牛客周赛 Round 51题解categories: - ICPCtags: - nullabbrlink: ‘70288513’date: 2024-03-14 00:00:00牛客周赛 Round 51D：题意：给定一个1e6长度的十进制数a和一个1e9范围的b,求解gcdSolution：考虑用python直接做，发现TLE了，python确实比较慢。考虑本题的关键在于gcd算法的本质$gcd(a,b)=gcd(a-b,b)$，所以我们只需要模拟这个发现，我们只需要提前计算a%b即可，然后再用普通gcd就可以。void solve(){ string s; cin>>s; cin>>n; ll res=0; for(auto x:s){ res=res*10+x-'0'; res%=n; } ...
Codeforces Round 891 (Div. 3) 总结
title: Codeforces Round 891 (Div. 3) 总结categories: - ICPCtags: - nullabbrlink: b908d038date: 2024-03-13...
链表
title: 链表categories: - ICPCtags: - nullabbrlink: 2362a8eadate: 2024-03-10 00:00:00链表单链表 void 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]]; ...
CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
title: ‘CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)’categories: - ICPCtags: - nullabbrlink: 823ca4e1date: 2024-03-07 00:00:00看到B官方题解写了一堆，而如果能注意到一些性质，几行就写完了题意：给一个A，B构成的字符串，可以将“AB”翻转成”BA”,问最多可以进行多少次翻转？实际上在手动模拟以后发现，由于题目限制了每个位置只能翻转一次，所以情况简单了不少。只要还没过最后一个B，那么最后一个B之前的所有A就会被反转。真正无效的部分是开头就是B，以及末尾的A，所以我们只需要找到第一个A，最后一个B即可，这两之间的所有位置都会被颠倒 // Problem: B. AB Flipping // Contest: Codeforces - CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) // URL: https://codeforces.com/contest/1896/problem/B //...
最大子段和以及拓展
title: 最大子段和以及拓展categories: - ICPCtags: - nullabbrlink: d90d19c2date: 2024-03-07 00:00:00无限制最长连续的子序列和题目链接 动态规划转移方程dp[i] = max(dp[i-1] + a[i], a[i]); 最终结果在 dp 数组中线性扫描找出最大值： int pos = max_element(dp + 1, dp + 1 + n) - dp; cout << dp[pos] << " "; dp[i] 表示以序列中第 i 个数字结尾的最大子段和。转移方程分析： 如果选择第 i-1 个数，则由 dp[i-1] 转移而来。 如果不选择第 i-1 个数，则只能自己作为一个子段存在，因为必须以第 i...
牛客周赛 Round 51
title: 牛客周赛 Round 51categories: - ICPCtags: - nullabbrlink: c04d35b0date: 2024-03-06 00:00:00牛客周赛 Round 51D：题意：给定一个1e6长度的十进制数a和一个1e9范围的b,求解gcdSolution：考虑用python直接做，发现TLE了，python确实比较慢。考虑本题的关键在于gcd算法的本质$gcd(a,b)=gcd(a-b,b)$，所以我们只需要模拟这个发现，我们只需要提前计算a%b即可，然后再用普通gcd就可以。void solve(){ string s; cin>>s; cin>>n; ll res=0; for(auto x:s){ res=res*10+x-'0'; res%=n; } ...
Codeforces Round 898 (Div. 4)
title: Codeforces Round 898 (Div. 4)categories: - ICPCtags: - nullabbrlink: e2f7c3b1date: 2024-03-03...
输入输出处理
title: 输入输出处理categories: - ICPCtags: - nullabbrlink: e2f7548ddate: 2024-03-02 00:00:001.io优化const 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...
dp优化
title: dp优化categories: - ICPCtags: - nullabbrlink: dc8e27b4date: 2024-03-01 00:00:00dp优化单调队列优化DP 优化方法大杂烩 I. - qAlex_Weiq - 博客园 (cnblogs.com) #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++){ ...