最小生成树
假设 nnn 表示图中点数，mmm 表示图中边数。 Prim算法堆优化 时间复杂度 O(nlogn)O(nlogn)O(nlogn)。 核心思想：每次挑一条与当前集合相连的最短边。 code 12345678910111213141516171819202122232425int 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(); if(vis[u])continue;//再出队跳过 vis[u]=1;//标记u已出队 ans+=d[u];...
CCF认证——202109-2 贡献的变化——差分维护，前缀和算答案
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
Codeforces Round 940 (Div. 2) and CodeCraft-23 前四题难度适中，总体还算不错，我想想都能做。E题考察威尔逊和质数筛前缀和算贡献。F题是数据结构，据说很版，还没补。 A题：题意：给出n个木棍，最多组成多少个多边形 Solution：统计各长度木棍的数量，全部贪心成三角形 123456789void 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 [x,y]:mp)ans+=y/3; cout<<ans<<endl;} B:题意：给出n和k，要求把k拆成n个非负整数，希望最大化n个数的或和的二进制的1的数量 ...
int128
1234567891011121314151617181920212223inline 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) { if(x<0)...
Codeforces Round 937 (Div. 4)
Codeforces Round 937 (Div. 4) B题是输出规律图形题，对于这种题不能直接不思考就上去模拟，而应该思考一下数学规律，往往是模意义下的规律。 本题只需要模4以后的结果分为两类，分别讨论即可。对于模4可以利用位运算取出第二位的，这与模2同理。 123456789101112131415161718192021222324252627282930char 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 i=1;i<=2*n;i++){ for(int j=1;j<=2*n;j++){ int...
后缀自动机SAM
后缀自动机SAM 板子： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899struct 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 =...
拓扑排序
1234567891011121314151617181920212223242526272829const 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 >> n >> m; for(int i=0; i<m; i++){ cin...
辛普森积分
自适应辛普森积分 123456789101112131415161718192021const 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 asr(l,m,a)+asr(m,r,b);}int main(){ ...
最大子序列和
题目描述：给定一个序列，数有正有负，你需要选出一个子序列（不能为空）使你得到的和最大，对于选出来的子序列应该满足相邻数之间奇偶性不同，输出可以得到的最大和 没怎么改的std 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#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)
Codeforces Round 859 (Div. 4) 评价：比较简单的一集，简单考察思维和最基础算法 E:交互题。看了oiwiki和codeforces的文章，之前看的abc文章忘了，打算写一篇总结特点和一些典型例题，还了解了其他题型。 Solution：回到本题：只需要利用前缀和优化每次二分答案，从输入里得到我们想要的信息 123456789101112131415161718192021//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 l=1,r=n; while(l<r){ cout<<"?"<<" "; int mid=(l+r)>>1; cout<<mid-l+1<<"...