树转序列
-
DFS序/dfn 按dfs遍历得到的序列
性质:节点子树在dfn区间 -
欧拉序1
-
欧拉序2:遍历经过的点记录一遍
性质:lca为区间节点深度最小
压位高精度 加乘低精除模板
#include<bits/stdc++.h>
using namespace std;
int N=4,M=1e4;
void print(vector<int> vec){cout<<vec.back();for(int i=vec.size()-2;i>=0;i--)printf("%04d",vec[i]);cout<<"\n";
}
vector<int> add(vector<int> a,vector<int> b){vector<int>c;for(int i=0,t=0;i<(int)a.size()||i<(int)b.size()||t;i++){if(i<(int)a.size())t+=a[i];if(i<(int)b.size())t+=b[i];c.push_back(t%M);t/=M;}return c;
}
vector<int> mul(vector<int> a,vector<int> b){vector<int>c(a.size()+b.size()+1);for(int i=0;i<(int)a.size();i++){for(int j=0;j<(int)b.size();j++){c[i+j]+=a[i]*b[j];c[i+j+1]+=c[i+j]/M;c[i+j]%=M;}}int i=c.size()-1;while(c[i]==0)c.pop_back(),i--;return c;
}
vector<int> div(vector<int> a, int b) {vector<int> c;int r=0;for (int i = a.size() - 1; i >= 0; i--) {r = r * M + a[i];c.push_back(r / b);r %= b;}reverse(c.begin(), c.end());while (c.size() > 1 && c.back() == 0) c.pop_back();return c;
}
vector<int>stovec(string s){vector<int>vec;for(int i=s.size()-1;i>=0;i-=N){int st=max(0,i-N+1),len=i-st+1;vec.push_back(stoi(s.substr(st,len)));}return vec;
}string a,b;
signed main()
{cin>>a>>b;vector<int>vec1=stovec(a),vec2=stovec(b);print(add(vec1,vec2));print(mul(vec1,vec2));print(div(vec1,2));return 0;
}
例题
输入\(N\),求\(\sqrt[5]{N}(1\leqslant N\leqslant 10^{2000})\)
二分加压位高精
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
string n;
int N=4,M=1e4;
void print(vector<int> vec){cout<<vec.back();for(int i=vec.size()-2;i>=0;i--)printf("%04d",vec[i]);cout<<"\n";
}
vector<int> add(vector<int> a,vector<int> b){vector<int>c;for(int i=0,t=0;i<(int)a.size()||i<(int)b.size()||t;i++){if(i<(int)a.size())t+=a[i];if(i<(int)b.size())t+=b[i];c.push_back(t%M);t/=M;}return c;
}
vector<int> mul(vector<int> a,vector<int> b){vector<int>c(a.size()+b.size()+1);for(int i=0;i<(int)a.size();i++){for(int j=0;j<(int)b.size();j++){c[i+j]+=a[i]*b[j];c[i+j+1]+=c[i+j]/M;c[i+j]%=M;}}int i=c.size()-1;while(c[i]==0)c.pop_back(),i--;return c;
}
vector<int> div(vector<int> a, int b) {vector<int> c;int r=0;for (int i = a.size() - 1; i >= 0; i--) {r = r * M + a[i];c.push_back(r / b);r %= b;}reverse(c.begin(), c.end());while (c.size() > 1 && c.back() == 0) c.pop_back();return c;
}
vector<int>stovec(string s){vector<int>vec;for(int i=s.size()-1;i>=0;i-=N){int st=max(0,i-N+1),len=i-st+1;vec.push_back(stoi(s.substr(st,len)));}return vec;
}
bool bigger(vector<int> a, vector<int> b) {if (a.size() != b.size()) return a.size() > b.size();for (int i = a.size() - 1; i >= 0; i--) {if (a[i] != b[i]) return a[i] > b[i];}return 0;
}signed main(){freopen("10.in","r",stdin);freopen("sqrt5.out","w",stdout);cin>>n;vector<int>vn=stovec(n);string l="1",r="1";for(int i=1;i<=int(n.size()/5)+1;i++)r+="0";vector<int>vl=stovec(l),vr=stovec(r);while(bigger(vr,vl)){vector<int> mid=div(add(vl,vr),2),mid5;mid5=mul(mid,mid),mid5=mul(mid5,mid5);mid5=mul(mid5,mid);// print(vl);// print(vr);if(bigger(mid5,vn)||mid5==vn){vr=mid;}else{vl=add(mid,stovec("1"));}}print(vl);return 0;
}
01串反转问题trick
策略:分奇偶,反转奇
给\(S_1和S_2\),每次将\(S_{1,i}和S_{1,i+1}\)反转,\(S_1=S_2\)的最小步数
将\(S_1和S_2\)奇数位反转,得到\(S'_1和S'_2\),在\(S'_1和S'_2\)上求交换\(S'_{1,i}和S'_{1,i+1}\)得到\(S'_2\)最小步数即可
相邻反转->交换
例题:AT_TKPPC6_2_B,P10367
矩阵乘法优化Floyd
Floyd可加矩阵乘法
例题:P6190,P2886
线段交转括号序列trick
abc424_f
把线段两端点当左右括号
切比雪夫/曼哈顿距离
\(A(x_1,y_1),B(x_2,y_2)\)
切比雪夫距离\(|AB|=max(|x_2-x_1|,|y_2-y_1|)\)
曼哈顿距离\(|AB|==|x_2-x_1|+|y_2-y_1|\)
曼哈顿坐标\(=>\)切比雪夫坐标
\((x,y)=>(x+y,x-y)\)
切比雪夫坐标\(=>\)曼哈顿坐标
\((x,y)=>(\frac{x+y}{2},\frac{x-y}{2})\)
判断奇数圈用二分图
裴蜀定理
若\(a,b\)是整数,且\(gcd(a,b)=d\)，那么对于任意的整数\(x,y,ax+by\)都一定是\(d\)的倍数，特别地，一定存在整数\(x,y\)，使\(ax+by=d\)成立。
若\(gcd(a,b)=1\),一定存在整数\(x,y\)，使\(ax+by=1\)成立
例题:CF510D Fox And Jumping
整除分块
求\(\sum^{i=n-1}_{i=1}\lfloor\frac{n}{i}\rfloor\)
观察到\(\lfloor\frac{n}{i}\rfloor\)在\(k\)的某些连续区间内取值是相同的。我们可以按照\(\lfloor\frac{a}{i}\rfloor\)的值\(k\)对\(b\in[2,n-1]\)进行分块。对于每一个\(k\)，计算对应区间内\(b\)的长度，然后将区间长度与该\(k\)的贡献相乘，累加到答案中。
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int n,ans;
int main() {cin>>n;int left=2;while(left<n){int k=n/left;int righ=min(n/k+1,n);ans+=(righ-left)*k;left=righ;}cout<<ans;return 0;
}
随机排列
std::vector<int> nums = {1, 2, 3, 4, 5};
std::random_shuffle(nums.begin(), nums.end()); // 随机打乱
统计一的个数
__builtin_popcount(num)
枚举子集
for(int s2=s1&(s1-1);s2;s2=s1&(s2-1))
快读快写模板
#include <bits/stdc++.h>
using namespace std;
struct IO{
#define MAXSIZE (1<<20)
#define isdigit(x)(x>='0'&&x<='9')
#define read_type int
#define write_type long long
char buf[MAXSIZE],*p1,*p2;char pbuf[MAXSIZE],*pp;IO():p1(buf),p2(buf),pp(pbuf){}~IO(){fwrite(pbuf,1,pp-pbuf,stdout);}char gc(){if(p1==p2)p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin);return p1==p2?' ':*p1++;}void read(read_type&x){bool neg=false;x=0;char ch=gc();for(;!isdigit(ch);ch=gc())if(ch=='-')neg=true;if(neg)for(;isdigit(ch);ch=gc())x=x*10+('0'-ch);else for(;isdigit(ch);ch=gc())x=x*10+(ch-'0');}void read(char*s){char ch=gc();for(;isspace(ch);ch=gc());for(;!isspace(ch);ch=gc())*s++=ch;*s=0;}void read(char&c){for(c=gc();isspace(c);c=gc());}void push(const char&c){if(pp-pbuf==MAXSIZE)fwrite(pbuf,1,MAXSIZE,stdout),pp=pbuf;*pp++=c;}void write(write_type x){bool neg=false;if(x<0){neg=true;push('-');}static int sta[40];int top=0;do{sta[top++]=x%10;x/=10;}while(x);if(neg)while(top)push('0'-sta[--top]);else while(top)push('0'+sta[--top]);}void write(write_type x,char lastChar){write(x),push(lastChar);}}io;
int n;
long long ans;
int main() {io.read(n);for(int i=1;i<=n;i++){int a;io.read(a);ans+=a;}io.write(ans,'\n');return 0;
}
对拍
#include<bits/stdc++.h>
using namespace std;
int main()
{while (1) //一直循环，直到找到不一样的数据{system("data.exe > in.txt");system("baoli.exe < in.txt > baoli.txt");system("std.exe < in.txt > std.txt");if (system("fc std.txt baoli.txt")) //当 fc 返回 1 时，说明这时数据不一样break; //不一样就跳出循环}return 0;
}