算法学习——带权并查集dls版本
title: 算法学习——带权并查集dls版本 categories: ICPC tags: null abbrlink: 4fc43d7a date: 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: ICPC tags: null abbrlink: ‘70288513’ date: 2024-03-14 00:00:00 牛客周赛 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就可以。 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: ICPC tags: null abbrlink: b908d038 date: 2024-03-13 00:00:00 ...
链表
title: 链表 categories: ICPC tags: null abbrlink: 2362a8ea date: 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: ICPC tags: null abbrlink: 823ca4e1 date: 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:...
最大子段和以及拓展
title: 最大子段和以及拓展 categories: ICPC tags: null abbrlink: d90d19c2 date: 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 51 categories: ICPC tags: null abbrlink: c04d35b0 date: 2024-03-06 00:00:00 牛客周赛 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就可以。 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: ICPC tags: null abbrlink: e2f7c3b1 date: 2024-03-03 00:00:00 由于题目补完才来写总结，导致前面的有的题目都需要重新再看一遍，只好当作复习了。 但考虑到趁热打铁，先看H. #H题： 从小白视角来看乍一看是博弈论，仔细思考以后发现是图论。本题给的是基环树，意识到这一点很重要，这个条件是让本题不是很复杂的关键。n个点n条边且没有重边保证这个联通图中只有一个环。由于瓦能够预测马去哪，当双方在环上时，瓦永远不会被抓到。若开始时瓦不在环上，则瓦的最优策略是找到去环上的最短路，而马的策略尽可能先到环去拦截瓦。 ...
输入输出处理
title: 输入输出处理 categories: ICPC tags: null abbrlink: e2f7548d date: 2024-03-02 00:00:00 1.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 标准库输入输出流之间的同步。 默认情况下，C++...
dp优化
title: dp优化 categories: ICPC tags: null abbrlink: dc8e27b4 date: 2024-03-01 00:00:00 dp优化 单调队列优化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++){ ...