最小生成树
title: 最小生成树 categories: ICPC tags: null abbrlink: 9acb5cb3 date: 2023-12-08 00:00:00 假设 nnn 表示图中点数，mmm 表示图中边数。 Prim算法堆优化 时间复杂度 O(nlogn)O(nlogn)O(nlogn)。 核心思想：每次挑一条与当前集合相连的最短边。 code int ans,cnt; struct edge{int v,w;}; vector<edge> e[N]; int d[N], vis[N]; priority_queue<pair<int,int>> q; bool prim(int s){ for(int i=0;i<=n;i++) d[i]=inf; d[s]=0; q.push({0,s}); while(q.size()){ int u=q.top().second; q.pop(); ...
CCF认证——202109-2 贡献的变化——差分维护，前缀和算答案
title: CCF认证——202109-2 贡献的变化——差分维护，前缀和算答案 categories: ICPC tags: null abbrlink: 4d5e6051 date: 2023-12-03 00:00:00 https://www.acwing.com/problem/content/4010/ http://118.190.20.162/view.page?gpid=T130 脑子一热抱着玩的心态试了一下三分，当然炸了，就当初认识三分了。 正解是考虑p的变化的影响，p变成p+1的时候，答案的值取决于 p属于 相邻递增数对的值域区间 的数量。也可以考虑递减的情况，两种情况只需要考虑一种，对所有数都考虑都考虑那一种就可以了，两种代码都AC了。 分析：如果 a[i]>a[i−1] 意味着当p取到 a[i−1]+1 到 a[i] 之间的值时，非零段+1 使用数组cnt[]，cnt[i]...
Codeforces Round 940 (Div. 2) and CodeCraft-23
title: Codeforces Round 940 (Div. 2) and CodeCraft-23 categories: ICPC tags: null abbrlink: ‘68444399’ date: 2023-11-30 00:00:00 Codeforces Round 940 (Div. 2) and CodeCraft-23 前四题难度适中，总体还算不错，我想想都能做。E题考察威尔逊和质数筛前缀和算贡献。F题是数据结构，据说很版，还没补。 A题：题意：给出n个木棍，最多组成多少个多边形 Solution：统计各长度木棍的数量，全部贪心成三角形 void solve(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; map<int,int>mp; for(int i=1;i<=n;i++)mp[a[i]]++; int ans=0; for(auto...
int128
title: int128 categories: ICPC tags: null abbrlink: bcbd629e date: 2023-11-21 00:00:00 inline void read(__int128 &x) { x=0; int f=1;//判断正负 char ch=getchar();//读入字符 while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') {//是数字就读 x=x*10+ch-'0';//之前结果乘10，加现在读入的 ch=getchar(); } x=x*f;//添上符号返回 } inline void write(__int128 x) { ...
Codeforces Round 937 (Div. 4)
title: Codeforces Round 937 (Div. 4) categories: ICPC tags: null abbrlink: 6af68cd7 date: 2023-11-20 00:00:00 Codeforces Round 937 (Div. 4) B题是输出规律图形题，对于这种题不能直接不思考就上去模拟，而应该思考一下数学规律，往往是模意义下的规律。 本题只需要模4以后的结果分为两类，分别讨论即可。对于模4可以利用位运算取出第二位的，这与模2同理。 char s1='#'; char s2='.'; void solve(){ cin>>n; vector<vector<char>>ans(2*n+1,vector<char>(2*n+1,'0')); //vector<vector<bool>>v(2*n+1,vector<bool>(2*n+1,0)); for(int...
后缀自动机SAM
title: 后缀自动机SAM categories: ICPC tags: null abbrlink: 6f972cc2 date: 2023-11-19 00:00:00 后缀自动机SAM 板子： struct SAM { static constexpr int asz = 26; struct Node { int len; int fail; int cnt = 0; array<int, asz> next; Node() : len{}, fail{}, next{} {} }; vector<Node> t; int tot = 0; SAM() { init(); } void init() { ...
拓扑排序
title: 拓扑排序 categories: ICPC tags: null abbrlink: fb40efc5 date: 2023-11-16 00:00:00 const int N = 100010; int n,m,a,b; vector<int> e[N], tp; int din[N];//入度数组 bool toposort(){ queue<int> q; for(int i = 1; i <= n; i++) if(din[i]==0) q.push(i); while(q.size()){ int x=q.front(); q.pop(); tp.push_back(x); for(auto y : e[x]){ if(--din[y]==0) q.push(y); } } return tp.size() == n; } int main(){ cin...
辛普森积分
title: 辛普森积分 categories: ICPC tags: null abbrlink: 48861cf4 date: 2023-11-15 00:00:00 自适应辛普森积分 const double eps=1e-10; double a,b,c,d,l,r; double f(double x){ //积分函数 return (c*x+d)/(a*x+b); } double simpson(double l,double r){//辛普森公式 return (r-l)*(f(l)+f(r)+4*f((l+r)/2))/6; }//二次函数特性 double asr(double l,double r,double ans){//自适应 //分段simpson，如果划分足够小，低于误差就可以 auto m=(l+r)/2,a=simpson(l,m),b=simpson(m,r); if(fabs(a+b-ans)<eps) return ans; return...
最大子序列和
title: 最大子序列和 categories: ICPC tags: null abbrlink: cf78f348 date: 2023-11-14 00:00:00 题目描述：给定一个序列，数有正有负，你需要选出一个子序列（不能为空）使你得到的和最大，对于选出来的子序列应该满足相邻数之间奇偶性不同，输出可以得到的最大和 没怎么改的std #include <bits/stdc++.h> using namespace std; #define ll long long //# define int long long #define ull unsigned long long #define pii pair<int,int> #define double long double #define baoliu(x, y) cout << fixed << setprecision(y) << x #define endl "\n" const int N = 2e5 +...
Codeforces Round 859 (Div. 4)
title: Codeforces Round 859 (Div. 4) categories: ICPC tags: null abbrlink: 72f3a48 date: 2023-11-11 00:00:00 Codeforces Round 859 (Div. 4) 评价：比较简单的一集，简单考察思维和最基础算法 E:交互题。看了oiwiki和codeforces的文章，之前看的abc文章忘了，打算写一篇总结特点和一些典型例题，还了解了其他题型。 Solution：回到本题：只需要利用前缀和优化每次二分答案，从输入里得到我们想要的信息 //cout.flush()； void solve(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++){ a[i]+=a[i-1]; } int...