不定期更细中。。。。。。
声明1：由于js的问题导致VIEW CODE按钮只能点“I”附近才能展开代码
声明2：为了排版的美观，所有的解释以及需要留意的地方我都放在代码中了
声明3：以下所有代码均是已经AC的，请各位放心食用
杂项1
ST表
//交LG的话记得加快读~~~
#include<bits/stdc++.h>
using namespace std;
int n,m,f[5000005][20];//f[i][j]为从i开始(2^j)-1的最大值
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>f[i][0];
}
for(int k=1;k<=20;k++){
for(int i=1;i<=n-(1<<k)+1;i++){
f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);//将区间拆成两半[i,i+2^j-1]和[i+2^(j-1),j-1]
}
}//如果是先枚举i那么在f[1][2]的时候会不知道f[2][1]的值
for(int i=1;i<=m;i++){
int le,ri;cin>>le>>ri;
int t=log(ri-le+1)/log(2);//换底公式即log以2为ri-le+1的对数，找到最大的k
printf("%d\n",max(f[le][t],f[ri-(1<<t)+1][t]));//左右两半区间查询
//记得+1如1~5:log2(5)=2,f[1][2]为1~4的max而后半段要2~5，5-2^2=1所以要加1！！！
}
}
线段树1
#include<bits/stdc++.h>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[100005];
struct node{
ll sum,add;
ll l,r;
}t[1000005];
ll read(){
ll x=0;char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
void build(ll p,ll l,ll r){
t[p].l=l,t[p].r=r;
if(l==r){t[p].sum=a[l];return ;}
ll mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
void spread(ll p){
if(t[p].add){
t[p*2].sum+=(ll)t[p].add*(t[p*2].r-t[p*2].l+1);//ll!!!
t[p*2+1].sum+=(ll)t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
t[p*2].add+=t[p].add;//别忘了
t[p*2+1].add+=t[p].add;
t[p].add=0;
}
}
void add(ll p,ll l,ll r,ll k){
if(t[p].l>=l&&t[p].r<=r){
t[p].add+=k;
t[p].sum+=(ll)k*(t[p].r-t[p].l+1);//不要忘了
return ;
}
spread(p);
ll mid=(t[p].l+t[p].r)>>1;//记得是在这个节点记录的区间的中点
if(l<=mid)add(p*2,l,r,k);//注意是l<=mid否则当修改区间横跨了mid时就不会进行任何操作
if(r>mid)add(p*2+1,l,r,k);
t[p].sum=t[p*2].sum+t[p*2+1].sum;//还要记得修改sum
}
ll ask(ll p,ll l,ll r){
if(t[p].l>=l&&t[p].r<=r){
return t[p].sum;
}
spread(p);
t[p].sum=t[p*2].sum+t[p*2+1].sum;
ll mid=(t[p].r+t[p].l)>>1;
ll val=0;
if(l<=mid)val+=ask(p*2,l,r);
if(r>mid)val+=ask(p*2+1,l,r);
return val;
}
int main(){
cin>>n>>m;
for(ll i=1;i<=n;i++){
a[i]=read();
}
build(1,1,n);
for(ll i=1;i<=m;i++){
ll ty=read();
if(ty==1){
ll cn=read(),cm=read(),cw=read();
add(1,cn,cm,cw);
}
else {
ll cn=read(),cm=read();
cout<<ask(1,cn,cm)<<endl;
}
}
}
线段树2
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,a[1000005],mod;
struct node{
ll sum,l,r,mu,add;
}t[1000005];
ll read(){
ll x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
void build(ll p,ll l,ll r){
t[p].l=l,t[p].r=r;t[p].mu=1;
if(l==r){t[p].sum=a[l]%mod;return ;}
ll mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}
void spread(ll p){
t[p*2].sum=(ll)(t[p].mu*t[p*2].sum+((t[p*2].r-t[p*2].l+1)*t[p].add)%mod)%mod;
t[p*2+1].sum=(ll)(t[p].mu*t[p*2+1].sum+(t[p].add*(t[p*2+1].r-t[p*2+1].l+1))%mod)%mod;
t[p*2].mu=(ll)(t[p*2].mu*t[p].mu)%mod;
t[p*2+1].mu=(ll)(t[p*2+1].mu*t[p].mu)%mod;
t[p*2].add=(ll)(t[p*2].add*t[p].mu+t[p].add)%mod;
t[p*2+1].add=(ll)(t[p*2+1].add*t[p].mu+t[p].add)%mod;
t[p].mu=1,t[p].add=0;
}
void add(ll p,ll l,ll r,ll k){
if(t[p].l>=l&&t[p].r<=r){
t[p].add=(t[p].add+k)%mod;
t[p].sum=(ll)(t[p].sum+k*(t[p].r-t[p].l+1))%mod;//只要加上增加的就好
return ;
}
spread(p);
t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
ll mid=(t[p].l+t[p].r)>>1;
if(l<=mid)add(p*2,l,r,k);
if(mid<r)add(p*2+1,l,r,k);
t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}
void mu(ll p,ll l,ll r,ll k){
if(t[p].l>=l&&t[p].r<=r){
t[p].add=(t[p].add*k)%mod;//比较重要的一步,add要在这里乘上k,因为后面可能要加其他的数而那些数其实是不用乘k的
t[p].mu=(t[p].mu*k)%mod;
t[p].sum=(t[p].sum*k)%mod;
return ;
}
spread(p);
t[p].sum=t[p*2].sum+t[p*2+1].sum;
ll mid=(t[p].l+t[p].r)>>1;
if(l<=mid)mu(p*2,l,r,k);
if(mid<r)mu(p*2+1,l,r,k);
t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}
ll ask(ll p,ll l,ll r){
if(t[p].l>=l&&t[p].r<=r){
return t[p].sum;
}
spread(p);
ll val=0;
ll mid=(t[p].l+t[p].r)>>1;
if(l<=mid)val=(val+ask(p*2,l,r))%mod;
if(mid<r)val=(val+ask(p*2+1,l,r))%mod;
return val;
}
int main(){
cin>>n>>m>>mod;
for(int i=1;i<=n;i++){
a[i]=read();
}
build(1,1,n);
for(int i=1;i<=m;i++){
int ty=read();
if(ty==1){
ll cn=read(),cm=read(),cw=read();
mu(1,cn,cm,cw);
}else if(ty==2){
ll cn=read(),cm=read(),cw=read();
add(1,cn,cm,cw);
}else {
ll cn=read(),cm=read();
cout<<ask(1,cn,cm)<<endl;
}
}
}
悬线法
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1005][1005],l[1005][1005],r[1005][1005],up[1005][1005];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char ch;cin>>ch;
if(ch=='F')a[i][j]=1;
r[i][j]=l[i][j]=j,up[i][j]=1;
}
}
for(int i=1;i<=n;i++){
for(int j=2;j<=m;j++){
if(a[i][j]==a[i][j-1]&&a[i][j]==1)l[i][j]=l[i][j-1];
}
for(int j=m-1;j>=1;j--){
if(a[i][j]==a[i][j+1]&&a[i][j]==1)r[i][j]=r[i][j+1];
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i>1&&a[i][j]==a[i-1][j]&&a[i][j]==1){//是>1才进去但是i=1时还是要做的
r[i][j]=min(r[i][j],r[i-1][j]);
l[i][j]=max(l[i][j],l[i-1][j]);
up[i][j]=up[i-1][j]+1;
}
ans=max(ans,(r[i][j]-l[i][j]+1)*up[i][j]);
}
}
cout<<ans;
}
哈夫曼树
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
priority_queue<pair<int,int> >dui;
signed main(){
cin>>n>>m;int w;
for(int i=1;i<=n;i++){
cin>>w;
dui.push(make_pair(-w,-1));
}
while((dui.size()-1)%(m-1))dui.push(make_pair(-0,-1));//最后一次合并要满足=0 因为每次合并要减少k-1个节点要将n个节点合并成1个
//题解里的解释：因为每次都是将k个节点合并为1个（减少k-1个），一共要将n个节点合并为1个，如果（n-1）%（k-1）！=0 则最后一次合并时不足k个。也就表明了最靠近根节点的位置反而没有被排满，因此我们需要加入k-1-（n-1）%（k-1）个空节点使每次合并都够k个节点（也就是利用空节点将其余的节点挤到更优的位置上）。
int ans=0;
while(dui.size()>=m){
int re=0,h=-0;
for(int i=1;i<=m;i++){
int x=dui.top().first,y=dui.top().second;dui.pop();
re+=x;
h=min(h,y);
}
ans+=re;
dui.push(make_pair(re,h-1));
}
cout<<-ans<<endl<<-dui.top().second-1;
}
LIS
#include<bits/stdc++.h>
using namespace std;
int n,a[100005],f[100005];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];f[i]=0x7ffffff;
}
int len=0;f[0]=0;
for(int i=1;i<=n;i++){
if(f[len]<a[i])f[++len]=a[i];
else {
int l=1,r=len;
while(l<r){
int mid=(l+r)>>1;
if(a[i]<f[mid])r=mid;//因为要将a[i]插入到f中，且插入位置保证f[mid]>=a[i]，所以>a[i]也可能是答案
else l=mid+1;
}
f[l]=a[i];
}
}
cout<<len;
}
LCS
#include<bits/stdc++.h>
using namespace std;
int n,f[100001],a[100001],b[100001],ma[100001];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];ma[a[i]]=i,f[i]=0x7fffffff;
}
for(int i=1;i<=n;i++)cin>>b[i];
f[0]=0;
int len=0;
for(int i=1;i<=n;i++){
if(f[len]<ma[b[i]])f[++len]=ma[b[i]];//比队尾还大
else {
int l=1,r=len;
while(l<r){
int mid=(l+r)>>1;
if(f[mid]<ma[b[i]])l=mid+1;
else r=mid;
}
f[l]=ma[b[i]];
}
}
cout<<len;
}
/*由于数据过大我们在时间和空间上都不能像下面那样做
那怎么办呢
我们发现既然是1到n的排列 那我们就可以把A离散化 这样我们就可以得到B在A序列中的编号
如果我们找到了一段编号序列的子序列，他是单调递增的，那么就表明对应元素在A和B中是从前往后排列的
这就是我们要的答案
差点忘了说 找这段单调递增的序列其实就是LIS哦
*/
#include<bits/stdc++.h>
using namespace std;
int n,m,a[2005],b[2005],f[2005][2005];
inline int read(){
register int x=0;register char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
int main(){
freopen("lcis.in","r",stdin);
freopen("lcis.out","w",stdout);
cin>>n>>m;
for(register int i=1;i<=n;++i){
a[i]=read();
}
for(register int i=1;i<=m;++i){
b[i]=read();
}
register int maxn=0;
for(register int i=1;i<=n;++i){
for(register int j=1;j<=m;++j){
if(a[i]==b[j]){
for(register int k=1;k<j;++k){
f[i][j]=max(f[i][j],f[i][k]+1);
}
maxn=max(maxn,f[i][j]);
}else f[i][j]=f[i-1][j];
}
}
cout<<maxn<<endl;
}
/*
fij表示到ai和bj的位置且ai必选
*/
LCIS
#include<bits/stdc++.h>
using namespace std;
int n,m,a[505],b[505],g[505][505],f[505][505];
void path(int i,int j){
if(j==0)return ;
path(g[i][j],j-1);
if(g[i][j]!=i){
printf("%d ",a[i]);
}
}
int main(){
cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
cin>>m;for(int j=1;j<=m;j++)cin>>b[j];
int maxn=0,x=0,y=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i]==b[j]){
f[i][j]=1;
for(int k=1;k<i;k++){
if(a[k]<a[i]){
if(f[i][j]<f[k][j-1]+1){//如果是f[k][j]由于a[1~i]与b[j]不匹配所以这样是错的
f[i][j]=f[k][j-1]+1;
g[i][j]=k;
}
}
}
if(maxn<f[i][j]){maxn=f[i][j],x=i,y=j;}
}else{
f[i][j]=f[i][j-1];
g[i][j]=i;
}
}
}
cout<<maxn<<endl;
path(x,y);
cout<<endl;
}
/*
输出的递归函数path应有两个参数(i,j),表示当前在数组A中位置是i,在数组B中位置是j.
我们沿着f[i][j]转移时的路径递归,也就是path(i-1,g[i][j]).
若g[i][j]==j,则说明这里是没有增加LCIS长度的转移,
应该沿着f[i][j]转移时的路径继续递归,但不输出.直到g[i][j]!=j就输出B[j].
*/
后序遍历
#include<bits/stdc++.h>
using namespace std;
char q[1000005],z[1000005];
int len;
int find(char k){
for(int i=1;i<=len;i++)if(q[i]==k)return i;
}
void dfs(int l1,int r1,int l2,int r2){
int m=find(z[r2]);
cout<<q[m];
if(m>l1)dfs(l1,m-1,l2,r2-r1+m-1);//有左子树
if(r1>m)dfs(m+1,r1,l2+m-l1,r2-1);
}
//r2-(r1-m+1)
//r2-r1+m-1
//l2+(m-r1)
//l2+m-r1
int main(){
scanf("%s",q+1);scanf("%s",z+1);
len=strlen(q+1);
dfs(1,len,1,len);
}
后缀表达式
#include<bits/stdc++.h>
using namespace std;
char a[1005];
int sum,k;
stack <int> stk;
int main()
{
gets(a);
for(int i=0;a[i]!='@';i++)
{
if(a[i]=='.')
{
sum=0,k=1;
for(int j=i-1;j>=0&&a[j]>='0'&&a[j]<='9';j--) sum=sum+(a[j]-48)*k,k*=10;
stk.push(sum);
continue;
}
if(a[i]>='0'&&a[i]<='9') continue;
sum=stk.top();
stk.pop();
if(a[i]=='+') sum=stk.top()+sum;
if(a[i]=='-') sum=stk.top()-sum;
if(a[i]=='*') sum=stk.top()*sum;
if(a[i]=='/') sum=stk.top()/sum;
stk.pop();
stk.push(sum);
}
printf("%d",stk.top());
return 0;
}
中缀表达式转后缀表达式
#include<bits/stdc++.h>
#define M 10007
using namespace std;
int n;
char ss[10000005];
stack<char>dui;
int main(){
cin>>n;
scanf("%s",ss +1);
string s=".";
for(int i=1;i<=n;i++){
if(ss[i]=='('||ss[i]=='*'){
dui.push(ss[i]);
}
if(ss[i]=='+'){
while(dui.size()&&dui.top()=='*'){//直到找到优先级更低的符号
s+=dui.top();
dui.pop();
}
dui.push('+');
}
if(ss[i]==')'){
while(dui.size()&&dui.top()!='('){
s+=dui.top();
dui.pop();
}
dui.pop();
}
if(ss[i]!='('&&ss[i]!=')'){
s+='.';
}
}
while(dui.size())s+=dui.top(),dui.pop();
cout<<s<<endl;
}
/*
8
+*+(*+)*
下面的话来自题解区：
转换过程需要用到栈，具体过程如下：
1）如果遇到操作数，我们就直接将其输出。
2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。
3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。
4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。
5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。
备注：本题中我们用一个"."来代表数字。扫描整个表达式（读入的字符串），如果当前位置不是括号（既不是左括号也不是右括号），就在后缀表达式里填一个"."表示这里应有一个数字。
*/
科学的整数二分模板
int l=0,r=1e6+1,mid,mem;
while(l<=r){
mid=l+r>>1;
if(check(mid)) l=mid+1,mem=mid;
else r=mid-1;
}
return mem;
小数二分
double l=1,r=2000;
while(r-l>1e-5){
double mid=(l+r)/2;
if(check(mid)){
l=mid;
}else{
r=mid;
}
}
printf("%d\n",r);
逆序对
#include<iostream>
using namespace std;
long long t[1000005],ans=0;
long long n,a[1000005];
void merge(int l,int r){//归并大法
if(l==r)
return;
int mid=(l+r)/2;
merge(l,mid);//用分治的思想，先分离，再合并
merge(mid+1,r);
int i=l,j=mid+1,p=l;
while(i<=mid&&j<=r){
if(a[i]>a[j]){
t[p++]=a[j++];
ans+=mid-i+1;//此时两边都是排好序了的，当前面的序列中有一个数大于后面的一个数时，前面序列中剩下的数都大于这个数，共mid-i+1个
}
else
t[p++]=a[i++];
}
while(i<=mid)
t[p++]=a[i++];//把序列中剩下的数存入t
while(j<=r)
t[p++]=a[j++];
for(i=l;i<=r;i++)
a[i]=t[i];//t中的数要回到a中
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
merge(1,n);//调用merge
cout<<ans<<endl;
return 0;
}
树状数组1
#include<bits/stdc++.h>
using namespace std;
int n,m,a[5000005],sum[5000005];
int read(){
int x=0;char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
int lowbit(int x){return x&(-x);}
void add(int x,int k){while(x<=n)sum[x]+=k,x+=lowbit(x);}
int getsum(int x){
int re=0;
while(x!=0){
re+=sum[x];
x-=lowbit(x);
}
return re;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)add(i,a[i]);
int ty,x,y;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&ty,&x,&y);
if(ty==1)add(x,y);
else cout<<getsum(y)-getsum(x-1)<<endl;
}
}
/*
单点修改区间查询
*/
树状数组2
#include<bits/stdc++.h>
using namespace std;
int n,m,a[500005],sum[500005];
int lowbit(int x){return x&(-x);}
void add(int x,int k){while(x<=n)sum[x]+=k,x+=lowbit(x);}
int getsum(int x){int re=0;while(x)re+=sum[x],x-=lowbit(x);return re;}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
int ty,x,y,k;
for(int i=1;i<=m;i++){
cin>>ty;
if(ty==1){
cin>>x>>y>>k;
add(x,k);
add(y+1,-k);
}else {
cin>>x;
cout<<a[x]+getsum(x)<<endl;
}
}
}
/*
区间修改单点查询
我们不可能一个个去修改
于是考虑差分
想到这问题迎刃而解
区间修改时只需修改x和y+1即可
最后求个sum+a[x]即为答案
*/
O(1)快速乘
int qmul(int x,int y,int mod){
return (x*y-(long long)((long double)x/mod*y)*mod+mod)%mod;
}
二进制gcd
inline ll gcd(ll a,ll b){
if(a==0)return b;
if(b==0)return a;
if(!(a&1)&&!(b&1))return 2*gcd(a>>1,b>>1);
else if(!(a&1))return gcd(a>>1,b);
else if(!(b&1))return gcd(a,b>>1);
else return gcd(abs(a-b),min(a,b));
}
杂项2
A*
#include<bits/stdc++.h>
using namespace std;
int lim,mp[10][10];
const int n=5;
const int dx[10]={0,1,1,-1,-1,2,2,-2,-2};
const int dy[10]={0,2,-2,2,-2,1,-1,1,-1};
const int st[7][7]={
{0,0,0,0,0,0},
{0,1,1,1,1,1},
{0,0,1,1,1,1},
{0,0,0,2,1,1},
{0,0,0,0,0,1},
{0,0,0,0,0,0}
};
int diff(){
int re(0);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(mp[i][j]!=st[i][j])++re;
}
}
return re;
}
bool ans;
bool pen(int x,int y){
if(x<1||x>n||y<1||y>n)return 0;
return 1;
}
void dfs(int dep,int x,int y){
if(ans)return ;
if(dep==lim){//必须是==,否则就成正常的搜索了......
if(!diff()){
ans=1;
printf("%d\n",lim);
}
return ;
}
for(int i=1;i<=8;i++){
int xx=x+dx[i],yy=y+dy[i];
if(pen(xx,yy)){
swap(mp[x][y],mp[xx][yy]);
int now=diff();
if(now+dep<=lim)dfs(dep+1,xx,yy);
swap(mp[x][y],mp[xx][yy]);
}
}
}
int main(){
int tt;
cin>>tt;
while(tt--){
int stax,stay;
char ch;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>ch;
if(ch=='*')stax=i,stay=j,mp[i][j]=2;
else mp[i][j]=ch-'0';
}
}
if(!diff()){printf("-1\n");continue;}
for(lim=1;lim<=15;lim++){
dfs(0,stax,stay);
}
if(!ans)printf("-1\n");
ans=0;
}
}
数论类
线性基
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll p[55],a,n,ans;
void merge(ll k){
for(int i=55;i>=0;i--){//>=0!!!!!!!!
if(!(k>>i))continue;
if(!p[i]){p[i]=k;break;}
k^=p[i];//消去最高位，后面的1不管，这也是为什么线性基不唯一——shuixirui
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;
merge(a);
}
for(int i=55;i>=0;i--){
if((ans^p[i])>ans)ans^=p[i];
}
cout<<ans;
}
//如果要查询某个数是否能被该线性基表出可以把该数转成二进制
//对于每一位如果为1就XORp[i]如果最后结果为0则可以被表出
裴蜀定理
//裴蜀定理内容ax+by=c,x∈Z*,y∈Z*成立的充要条件是gcd(a,b)∣c,Z* 表示正整数集。
//扩展到求ax+by=c 的最小非负 c,显然 c 要满足 (a,b)|c,所以 c 取 (a,b)是最小的。
#include<bits/stdc++.h>
using namespace std;
int n,a,ans;
int gcd(int a,int b){
if(!b)return a;
return gcd(b,a%b);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){cin>>a;a>0?(a*=1):(a*=(-1));ans=gcd(ans,a);}
cout<<ans;
}
并查集
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[200005];
int find(int k){
while(fa[k]!=k)k=fa[k]=fa[fa[k]];//循环版找爸爸
return k;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
int cn,cm,cz;
cin>>cn>>cm>>cz;
int a=find(cm),b=find(cz);
if(cn==1){
if(a>b)fa[a]=b;//按序号大小合并
else fa[b]=a;
}else{
if(a==b)cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
}
}
快速排序
#include<bits/stdc++.h>
using namespace std;
int n,a[100005];
int read(){
int x=0;char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
void quick_sort(int l,int r){
if(l>=r)return ;
int mid=a[(l+r)>>1],i=l,j=r;
while(i<=j){
while(a[i]<mid)++i;//不能加‘=’不然会T
while(a[j]>mid)--j;
if(i<=j){//要特判
swap(a[i],a[j]);
++i,--j;//注意注意
}
}
if(l<j)quick_sort(l,j);//!!!
if(r>i)quick_sort(i,r);//!!!
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
a[i]=read();
}
quick_sort(1,n);
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
}
素数筛
#include<bits/stdc++.h>
using namespace std;
int n,m,prime[100000005],ji;
bool bo[10000005];
int main(){
cin>>n>>m;
for(int i=2;i<=n;i++){
if(!bo[i])prime[++ji]=i;//不能加括号！！！，每次都要更新！！！
for(int j=1;i*prime[j]<=n;j++){//记得是prime[j]*i,i和j换个位置
bo[i*prime[j]]=1;
if(i%prime[j]==0)break;//期中有其他因子的时候就退出来
}
}
bo[1]=bo[0]=1;
for(int i=1;i<=m;i++){
int cn;cin>>cn;
if(bo[cn])cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
}
//当你n特别大比如1e12时我们可以这么求出这个数可以被分解成多少个质数：
#include<bits/stdc++.h>
using namespace std;
long long read()
{
long long x=0,f=1;
char c=getchar();
while((c<'0'||c>'9')&&c!='-')c=getchar();
if(c=='-')f=-1,c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
long long T,n,ans;
int main(){
T=read();
while(T--){
n=read();
ans=0;
for(long long i=2;i*i<=n;++i)
while(!(n%i)){
n/=i;
ans++;
}
if(n>1)ans++;
if(ans==2)printf("Bob\n");
else printf("Alice\n");
}
return 0;
}
快速幂
#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long m,n,mod;
ll quick(ll x,int y){//快速幂
ll res=1;
while(y){
if(y&1)res=(ll)res*x%mod;
x=(ll)x*x%mod; y>>=1;
}return res;
}
int main(){
cin>>m>>n>>mod;
cout<<m<<"^"<<n<<" mod "<<mod<<"="<<quick(m,n)%mod;
}
或者你也可以这么写 下面是我早期写的版本
#include<iostream>
using namespace std;
long long b,p,k;
long long mod(long long x)
{
if(x==0) return 1%k;
long long y=x,s;
bool bo=y%2;
y/=2;
s=mod(y);
s*=s%k;
if(bo==1) s*=b;
return s%k;
}
int main(){
cin>>b>>p>>k;
cout<<b<<"^"<<p<<" mod "<<k<<"="<<mod(p);
}
三分法
#include<bits/stdc++.h>
#define eps 1e-6
using namespace std;
int n;
double l,r,a[20];
double f(double x){//秦九昭定理
double s=0;
for(int i=1;i<=n+1;i++)s=s*x+a[i];//巧妙的操作
return s;
}
int main(){
cin>>n>>l>>r;
for(int i=1;i<=n+1;i++)cin>>a[i];//特别注意有n+1个值
while(r-l>=eps){
double k=(r-l)/3.0;
double mid1=l+k,mid2=r-k;
if(f(mid1)>f(mid2))r=mid2;
else l=mid1;
}
printf("%.5lf",l);
}
矩阵快速幂
#include <bits/stdc++.h>
#define ll long long
#define m 1000000007
using namespace std;
inline ll gi(){
register char ch=getchar();register ll x=0;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
ll n,k;
struct node {
ll mat[100][100];
}add,a,ans,mu,e,qk;
inline node mul(node x,node y){
node mem=qk;
for(register int i=1;i<=n;i++){
for(register int j=1;j<=n;j++){
for(register int h=1;h<=n;h++){
mem.mat[i][j]=(mem.mat[i][j]+x.mat[i][h]*y.mat[h][j])%m;//记得加上原来的
}
}
}
return mem;
}
inline void quick(ll k){
ans=e;
while(k){
if(k&1)ans=mul(ans,mu);
mu=mul(mu,mu);
k>>=1;
}
}
int main(){
cin>>n>>k;
for(register int i=1;i<=n;i++){
for(register int j=1;j<=n;j++){
mu.mat[i][j]=a.mat[i][j]=gi();
}
}
for(ll i=1;i<=n;i++){
e.mat[i][i]=1;
}
quick(k);
for(register int i=1;i<=n;i++){
for(register int j=1;j<=n;j++){
printf("%lld ",ans.mat[i][j]);
}
printf("\n");
}
return 0;
}
乘法逆元1
//法1(递推法)
#include<bits/stdc++.h>
using namespace std;
long long n,p,inv[3000001];
int main(){
cin>>n>>p;
inv[1]=1;
for(int i=2;i<=n;i++){
inv[i]=(p-p/i)*inv[p%i]%p;
}
for(int i=1;i<=n;i++)printf("%d\n",inv[i]);
}
/*
递推求inv的解释：
设p=k*i+r;
则有k*i+r≡0(mod p)
为了把r^(-1)剥离出来两边同乘i^(-1)*r^(-1)
得到r^(-1)=-k*r^(-1);
k=p/i,r^(-1)=inv[p%i];
此时我们注意到这样乘起来是负数
所以我们用p减去他
*/
//法2(扩展欧几里得法)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,p,inv[3000001],x,y;
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){x=1,y=0;return ;}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
int main(){
cin>>n>>p;
for(int i=1;i<=n;i++){
exgcd(i,p,x,y);
x=(p+x%p)%p;
cout<<x<<endl;
}
}
/*
a*x≡c(mod p)
令t=x^(-1)
我们要求的就是
x*t≡1(mod p)
于是我们有
x*t+p*y=1
求t即可
*/
//法3(快速幂)
//即x^(p-2);
//由于这个方法只适用于x与p互质的情况，exgcd不仅比他快还适用所有情况 这里就不在赘述
乘法逆元2
//明天就考试了，这是题解，有时间补锅
#include<cstdio>
#include<cctype>
typedef long long LL;
int n,k,md,pre[5000005],suf[5000005],a[5000005];
int readint(){
int x=0;char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
inline int Inv(const int p){
if(p==1)return 1;
return((LL)(md-md/p)*Inv(md%p)%md);
}
int main(){
n=readint(),md=readint(),k=readint();
int ans=0;
for(register int i=*pre=suf[n+1]=1;i<=n;++i)
pre[i]=(LL)pre[i-1]*(a[i]=readint())%md;
for(register int i=n;i;--i)
suf[i]=(LL)suf[i+1]*a[i]%md;
for(register int i=1,j=k;i<=n;++i,j=(LL)j*k%md)
ans=(ans+(LL)j*pre[i-1]%md*suf[i+1])%md;
printf("%lld",ans*(LL)Inv(pre[n])%md);
return 0;
}
NIM游戏
#include<bits/stdc++.h>
using namespace std;
int t,n;
int main(){
cin>>t;
while(t--){
cin>>n;
int ans=0;
for(int i=1;i<=n;i++){
int ci;
cin>>ci;
ans^=ci;
}
if(ans)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
中国剩余定理
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100005],b[100005];
void exgcd(int aa,int bb,int &x,int &y){
if(!bb){x=1,y=0;return ;}
exgcd(bb,aa%bb,y,x);
y-=aa/bb*x;
}
int ksc(int aa,int bb,int mod){
int re=0;
while(bb){
if(bb&1)re=(re+aa)%mod;
bb>>=1,aa=(aa+aa)%mod;
}
return re;
}
void crt(){
int ans=0;
for(int i=1;i<=n;i++){
int mi=m/b[i],x,y;
exgcd(mi,b[i],x,y);//求出mi的逆元
ans=(ans+ksc(ksc(x,mi,m)%m,a[i],m)%m)%m;
}
ans=(ans%m+m)%m;
cout<<ans;
}
signed main(){
cin>>n;m=1;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){cin>>b[i];a[i]=(a[i]%b[i]+b[i])%b[i];m*=b[i];}//吧a转换成正数并计算m
crt();
}
/*
对于sum{ai*mi*mi^(-1)}的解释
xi≡ai*mi*mi^(-1)(mod bi)
xj≡aj*mj*mj^(-1)(mod bj)
当循环到j时由于mj=b1*b2*...*bj-1*bj+1*...*bn
故sum之后即为答案
*/
高斯消元
#include<bits/stdc++.h>
using namespace std;
double f[4005][4005],ans[400];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n+1;j++){
cin>>f[i][j];
}
}
for(int i=1;i<=n;i++){
int r=0;
for(int j=i;j<=n;j++)
if(fabs(f[r][i])<fabs(f[j][i]))//fabs返回实数的绝对值
r=j;
if(!r){
printf("No Solution");//找不到最大值即此列全为０
return 0;
}
swap(f[i],f[r]);//交换行骚操作～～～
double chu=f[i][i];//就是此列最大的那个关键元，那整列被放到第ｉ行
for(int j=i;j<=n+1;j++)f[i][j]/=chu;//是i~n+1!，第１～ｉ为０，本行除以这个关键元
for(int j=i+1;j<=n;j++){//枚举行数
chu=f[j][i];//当前行的关键元,要消去,且必须用中间变量（不然在后面的for里面值会被修改）
for(int k=i;k<=n+1;k++){//枚举列数，是i~n+1
f[j][k]-=f[i][k]*chu;//f[i][k]为这一列第一个，用关键元所在行对应列的来消此列其他值
// if(f[j][k]==-0)f[j][k]=0;
}
}
}
ans[n]=f[n][n+1];//因为是阶梯型矩阵，最后一行的第n+1个数就是xn的值
for(int i=n;i>=1;i--){//倒着枚举！
ans[i]=f[i][n+1];//本行结果初始化为第n+1个数
for(int j=i+1;j<=n;j++){
ans[i]-=ans[j]*f[i][j];//ans[j]中已经存放了xj的答案，乘本行第ｊ个再减去就是xi的值
}
}
for(int i=1;i<=n;i++)
printf("%.2lf\n",ans[i]);
}
康托展开
//这也是题解，有时间再补锅
#include <iostream>
#include <cstdio>
#define MOD (998244353)
using namespace std;
int n,a[1000000];
int c[1000001]={};
inline int lowbit(int x){
return x&(-x);
}
inline void modify(int p){
while(p<=n){
++c[p];
p+=lowbit(p);
}
return;
}
inline int ask(int p){
int s=0;
while(p){
s+=c[p];
p-=lowbit(p);
}
return s;
}
inline void readInt(int &x){
char c;
while((c=getchar())<'0' || c>'9');
x=(c^48);
while('0'<=(c=getchar()) && c<='9'){
x=x*10+(c^48);
}
return;
}
int fac[1000000]={1,1};
int main(){
int i,s=0;
readInt(n);
for(i=0;i<n;++i){
readInt(a[i]);
}
for(i=2;i<1000000;++i){
fac[i]=(long long)fac[i-1]*i%MOD;
}
for(i=0;i<n;++i){
s=(s+(long long)fac[n-1-i]*(a[i]-1-ask(a[i]-1))%MOD)%MOD;
modify(a[i]);
}
printf("%d\n",(s+1)%MOD);
return 0;
}
欧拉定理
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int n,mod,phi,k;
bool bo;
int quick(int a,int b){
int res=a,ans=1;
while(b){
if(b&1)ans=(long long)ans*res%mod;//要加ll...
res=(long long)res*res%mod;
b>>=1;
}
return ans%mod;
}
int main(){
cin>>n>>mod;
n%=mod;
int x=phi=mod;//等于mod...
for(int i=2;i*i<=x;i++){
if(x%i==0){
phi=phi/i*(i-1);
while(x%i==0)x/=i;
}
}if(x>1){phi=phi/x*(x-1);}
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){
k=(k<<1)+(k<<3)+(ch^48);
ch=getchar();
if(k>=phi)bo=1,k%=phi;//>=&&%phi...
}
if(k>=phi)bo=1,k%=phi;
if(bo)k+=phi;
printf("%d",quick(n,k));
}
Pollard-Rho算法
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll ans=1;
inline ll quick(ll x,ll p,ll mod){
ll ans=1;
while(p){
if(p&1)ans=ans*x%mod;
x=x*x%mod; p>>=1;
}
return ans;
}
inline bool mr(ll x,ll p){
if(quick(x,p-1,p)!=1)return 0;
ll y=p-1,z;
while(!(y&1)){
y>>=1; z=quick(x,y,p);
if(z!=1&&z!=p-1)return 0;
return 1;
}return 1;
}
inline bool prime(ll p){ if(p<2)return 0;
if(p==2||p==3||p==5||p==11||p==101)return 1;
return mr(2,p)&&mr(3,p)&&mr(5,p)&&mr(11,p)&&mr(101,p);
}
inline ll Abs(ll x){return x<0?-x:x;}
inline ll gcd (ll a,ll b){
register ll t;
while (b){
t=a%b;
a=b;
b=t;
}
return a;
}
inline ll rho(ll p){
ll x,y,z,c,g; int i,j;
while(1){
x=y=rand()%p; c=rand()%p;
z=1; i=0; j=1;
while(++i){
x=((__int128)x*x+c)%p;
z=(__int128)z*Abs(y-x)%p;
if(x==y)break;
if(z==0){
g=gcd(Abs(y-x),p);
if(g>1)return g;
break;
}
if(!(i%127)||i==j){
g=gcd(z,p);
if(g>1)return g;
if(i==j)y=x,j<<=2;
}
}
}
}
inline void find(ll x){
if(x<=ans)return ;
if(prime(x)){ans=x;return ;}
ll p=rho(x);
while(x%p==0)x/=p;
find(p); find(x);
}
int main(){
int t;cin>>t;
srand(time(0));
while(t--){
ll n; ans=1;
cin>>n; find(n);
if(ans==n){puts("Prime");continue;}
printf("%lld\n",ans);
}
}
图类
负环
#include<bits/stdc++.h>
using namespace std;
int tt,n,m,head[100005],ji,dis[100005],cnt[100005];
int read(){
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
struct node{
int next,yuan,w;
}ed[1000005];
void add(int p,int q,int quan){
ed[++ji].next=head[p];
ed[ji].yuan=q;
ed[ji].w=quan;
head[p]=ji;
}
bool huan;
queue<int>dui;//队列就行了
void spfa(){
while(dui.size())dui.pop();
dui.push(1);
dis[1]=0;//0号节点到根节点的距离为0
while(dui.size()){
int x=dui.front();dui.pop();
for(int i=head[x];i;i=ed[i].next){
int y=ed[i].yuan,l=dis[x]+ed[i].w;
if(dis[y]>l){
dis[y]=l;
++cnt[y];
dui.push(y);
if(cnt[y]>=n){huan=1;return;}//>=n!!!
}
}
}
}
int main(){
cin>>tt;
while(tt--){
cin>>n>>m;
memset(head,0,sizeof(head));
memset(ed,0,sizeof(ed));
memset(dis,127,sizeof(dis));
memset(cnt,0,sizeof(cnt));
ji=0,huan=0;
for(int i=1;i<=m;i++){
register int cn=read(),cm=read(),cw=read();
if(cw<0)add(cn,cm,cw);
else add(cm,cn,cw),add(cn,cm,cw);
}
spfa();
if(huan)cout<<"YE5"<<endl;
else cout<<"N0"<<endl;
}
return 0;
}
Dij
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int m,n,s,ji,head[200005],dis[200005];
bool bo[200005];
struct node{
int w,next,yuan;
}ed[200005];
void add(int p,int q,int quan)
{
ed[++ji].w=quan;
ed[ji].yuan=q;
ed[ji].next=head[p];
head[p]=ji;
}
priority_queue < pair < int , int > > dui;//注意怎么写
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int cm,cn,cs;
scanf("%d%d%d",&cm,&cn,&cs);
add(cm,cn,cs);
}
for(int i=1;i<=n;i++)dis[i]=0x7fffffff;//注意是只有初始化
dis[s]=0;
dui.push(make_pair(0,s));//注意make_pair怎么写,内容是什么
while(!dui.empty()){//注意有括号
int x=dui.top().second;//括号
dui.pop();
if(bo[x])continue;//记得判断重复
bo[x]=1;
for(int j=head[x];j;j=ed[j].next){
int y=ed[j].yuan,l=dis[x]+ed[j].w;
if(dis[y]>l){
dis[y]=l;
dui.push(make_pair(-dis[y],y));//是-dis[y]
}
}
}
for(int i=1;i<=n;i++)printf("%d ",dis[i]);
return 0;
}
spfa
#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int read(){
int x=0;char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
int head[200005],ji,dis[200005];
struct node{
int next,yuan,w;
}ed[5000005];
void add(int p,int q,int quan){
ed[++ji].next=head[p];
ed[ji].yuan=q;
ed[ji].w=quan;
head[p]=ji;
}
bool bo[1000005];
queue<int>dui;
void spfa(){
dui.push(s);bo[s]=1;
for(int i=1;i<=n;i++)dis[i]=0x7fffffff;dis[s]=0;
while(dui.size()){
int x=dui.front();dui.pop();
bo[x]=0;
for(int i=head[x];i;i=ed[i].next){
int y=ed[i].yuan,l=ed[i].w+dis[x];
if(dis[y]>l){
dis[y]=l;
if(!bo[y]){//注意注意spfa与dij最大的额就是bo的位置
//dij每个点只会更新一次spfa可能会多次更新
bo[y]=1;
dui.push(y);
}
}
}
}
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int cn=read(),cm=read(),cw=read();
add(cn,cm,cw);
}
spfa();
for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
}
tarjan
#include<bits/stdc++.h>
using namespace std;
int n,m,head[100005],ji,sum,ans,mem;
struct node{
int next,yuan;
}ed[100005];
void add(int p,int q){
ed[++ji].next=head[p];
ed[ji].yuan=q;
head[p]=ji;
}
int dfn[100005],low[100005];
stack<int>dui;//必须用stack!!!队列是先进先出
bool bo[100005];
void tarjan(int k){
mem=0;
low[k]=dfn[k]=++ji;
dui.push(k);bo[k]=1;
for(int i=head[k];i;i=ed[i].next){
int y=ed[i].yuan;
if(!dfn[y]){
tarjan(y);
low[k]=min(low[k],low[y]);
}else {
if(bo[y]){
low[k]=min(low[k],low[y]);
}
}
}
if(dfn[k]==low[k]){
bo[k]=0;
int x=dui.top();
while(x!=k&&dui.size()){
bo[x]=0;
dui.pop();
x=dui.top();
++mem;
}
dui.pop();
if(mem>0)++ans;//因为题目说了构成联通块的牛的数量要>=2
mem=0;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int cn,cm;
cin>>cn>>cm;
add(cn,cm);
}
ji=0;
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
cout<<ans;
}
SCC
#include<bits/stdc++.h>
using namespace std;
int n,m,dfn[1000005],low[1000005],col[1000005],sum,si[1000005],out[1000005];
struct node{
int next,yuan;
}ed[1000005];
int head[10000105],ji;
void add(int p,int q){
ed[++ji].next=head[p];
ed[ji].yuan=q;
head[p]=ji;
}
bool bo[1000005];
stack<int>dui;
void tarjan(int k){
low[k]=dfn[k]=++ji;
dui.push(k);
bo[k]=1;
for(int i=head[k];i;i=ed[i].next){
int y=ed[i].yuan;
if(!dfn[y]){
tarjan(y);
low[k]=min(low[k],low[y]);
}else {
if(bo[y]){
low[k]=min(low[k],low[y]);
}
}
}
if(dfn[k]==low[k]){
si[++sum]=1;
col[k]=sum;
bo[k]=1;
while(dui.top()!=k){
col[dui.top()]=sum;
bo[dui.top()]=0;
si[sum]++;//与正常tarjan相比就是这里和上面col不同，si是统计每个块里面有多少个元素
dui.pop();
}
dui.pop();
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int cn,cm;cin>>cn>>cm;
add(cn,cm);
}ji=0;
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i);
}
}
//到这里强连通分量已经算完啦
//后面只是题目要求。。。
/*
具体解释参考 恨妹不成穹 的解释：
但如果有多个点出度为0，那么它们都当不了明星（它们没有受到对方的爱慕—>它们没有受到所有牛的爱慕）
得出结论:
1.缩点后，若只有一个出度为0的点，那么明星牛的个数即那个强连通分量包含的点的个数；
2.缩点后，若有多个出度为0的点或无出度为0的点，那么明星牛的个数即为0。
*/
for(int i=1;i<=n;i++){
for(int j=head[i];j;j=ed[j].next){
int y=ed[j].yuan;
if(col[i]!=col[y])++out[col[i]];
}
}
int cun=0,ans=0;
for(int i=1;i<=sum;i++){
if(!out[i]){//
++cun;
ans+=si[i];
}
if(cun>=2){
cout<<"0"<<endl;
return 0;
}
}
cout<<ans;
}
缩点
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005];
int read(){
int x=0;char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
int headEd[100005],ji,head[100005];
struct node{
int next,yuan,w;
}Ed[1000005],ed[100005];
void add(int p,int q){
ed[++ji].next=head[p];
ed[ji].yuan=q;
head[p]=ji;
}
void addEd(int p,int q){
Ed[++ji].next=headEd[p];
Ed[ji].yuan=q;
headEd[p]=ji;
}
int dfn[100005],low[100005],scc[100005],sum[100005],col;
stack<int>sta;
bool bo[100005];
void tarjan(int k){
low[k]=dfn[k]=++ji;
sta.push(k);bo[k]=1;
for(int i=headEd[k];i;i=Ed[i].next){
int y=Ed[i].yuan;
if(!dfn[y]){
tarjan(y);
low[k]=min(low[k],low[y]);
}else {
if(bo[y]){
low[k]=min(low[k],low[y]);
}
}
}
if(dfn[k]==low[k]){
++col;
scc[k]=col,bo[k]=0;
sum[col]=a[k];
while(sta.top()!=k){
scc[sta.top()]=col;
bo[sta.top()]=0;
sum[col]+=a[sta.top()];
sta.pop();
}
sta.pop();
}
}
int mem[100005][3],jied,in[100005],dis[100005];
queue<int>dui;
void topo(){
for(int i=1;i<=n;i++)dis[i]=sum[i];
while(dui.size()){
int x=dui.front();
dui.pop();
for(int i=head[x];i;i=ed[i].next){
int y=ed[i].yuan;
--in[y];
dis[y]=max(dis[y],dis[x]+sum[y]);
if(!in[y]){
dui.push(y);
}
}
}
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
int cn,cm;
for(int i=1;i<=m;i++){
cn=read(),cm=read();
addEd(cn,cm);
mem[++jied][1]=cn,mem[jied][2]=cm;
}
ji=0;
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
//step2:build!
ji=0;
for(int i=1;i<=m;i++){
int x=mem[i][1],y=mem[i][2];
if(scc[x]!=scc[y]){
add(scc[x],scc[y]);
++in[scc[y]];
}
}
for(int i=1;i<=n;i++)if(!in[i])dui.push(i),dis[i]=sum[i];
topo();
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,dis[i]);
}
cout<<ans;
}
LCA
#include<bits/stdc++.h>
using namespace std;
int n,m,root,f[500005][25];
struct node{
int next,yuan;
}ed[5000005];
int head[500005],ji,de[500005];
inline int read(){
register int x=0;char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
inline void add(int p,int q){
ed[++ji].next=head[p];
ed[ji].yuan=q;
head[p]=ji;
}
inline void dfs(int k,int ste){
for(int j=1;j<=20;j++){//因为不一定编号小的就是编号大的 的祖先所以要在dfs时预处理f
f[k][j]=f[f[k][j-1]][j-1]; //还有，f预处理必须放在dfs前面，因为后面的儿子会要用到这个f
}
for(register int i=head[k];i;i=ed[i].next){
register int y=ed[i].yuan;
if(!de[y]){
de[y]=ste;
f[y][0]=k;
dfs(y,ste+1);
}
}
}
inline int lca(int p,int q){
if(de[p]>de[q])swap(p,q);
for(register int i=20;i>=0;i--){
if(de[f[q][i]]>=de[p])q=f[q][i];//记得是>=!!!
}
if(p==q)return p;
for(register int i=20;i>=0;i--){
if(f[p][i]!=f[q][i]){
p=f[p][i],q=f[q][i];
}
}
return f[p][0];
}
int main(){
cin>>n>>m>>root;
for(register int i=1;i<n;i++){
register int cn=read(),cm=read();
add(cn,cm);add(cm,cn);
}
de[root]=1;
dfs(root,2);
for(register int i=1;i<=m;i++){
register int cn=read(),cm=read();
printf("%d\n",lca(cn,cm));//cout->printf 2.7s->1.7s
}
}
最小生成树
#include<bits/stdc++.h>
using namespace std;
struct tree{
int yuan,next,w;
}ed[200005];
int m,ji,n,head[200005],ans,fa[200005];
bool cmp(tree a,tree b){
return a.w<b.w;//是<
}
int find(int k){
while(k!=fa[k])k=fa[k]=fa[fa[k]];
return k;
}
void kruskal(){
sort(ed+1,ed+n+1,cmp);
for(int i=1;i<=n;i++){
int x=find(ed[i].next),y=find(ed[i].yuan);
if(x==y)continue;
if(x>y){
fa[y]=x;
}
else
fa[x]=y;
ans+=ed[i].w;
if(++ji==m-1)return ;//n-1即可
}
}
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>ed[i].next>>ed[i].yuan>>ed[i].w;//无需链式钱向星，否则yuan不对
}
for(int i=1;i<=m;i++)fa[i]=i;
ji=0;
kruskal();
cout<<ans;
}
分层图
//然而放的并不是分层图的做法
//放的是Dij或spfa+DP的做法,貌似比分层图正解还快???
//首先是Dij版的
#include<bits/stdc++.h>
using namespace std;
int n,m,k,f[100005][30];
int read(){
int x=0;char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
int head[1000005],ji;
struct node{
int next,yuan,w;
}ed[1000005];
void add(int p,int q,int quan){
ed[++ji].next=head[p];
ed[ji].yuan=q;
ed[ji].w=quan;
head[p]=ji;
}
struct no{
int dis,x,now;
bool operator > (const no& bb)const{return dis<bb.dis;}
bool operator < (const no& bb)const{return dis>bb.dis;}//重中之重,重载运算符(直接变成小跟堆)
};
priority_queue< no >dui;
bool bo[100005][30];
void dij(){
memset(f,127,sizeof(f));
f[1][0]=0;
dui.push(no{0,1,0});
while(dui.size()){
int x=dui.top().x,now=dui.top().now;
dui.pop();
if(bo[x][now])continue;
bo[x][now]=1;
for(int i=head[x];i;i=ed[i].next){
int y=ed[i].yuan;
if((!bo[y][now])&&f[y][now]>f[x][now]+ed[i].w){
f[y][now]=f[x][now]+ed[i].w;
dui.push(no{f[y][now],y,now});
}
if((!bo[y][now+1])&&now<k&&f[y][now+1]>f[x][now]){
f[y][now+1]=f[x][now];
dui.push(no{f[y][now+1],y,now+1});
}
}
}
}
int main(){
n=read(),m=read(),k=read();
for(int i=1;i<=m;i++){
int cn=read(),cm=read(),cw=read();
add(cn,cm,cw);
add(cm,cn,cw);
}
dij();
cout<<f[n][k]<<endl;
return 0;
}
//spfa版(当然比Dij慢多了)
#include<bits/stdc++.h>
using namespace std;
int n,m,k,f[100005][30];
int read(){
int x=0;char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
int head[1000005],ji;
struct node{
int next,yuan,w;
}ed[1000005];
void add(int p,int q,int quan){
ed[++ji].next=head[p];
ed[ji].yuan=q;
ed[ji].w=quan;
head[p]=ji;
}
queue<pair<int,int> >dui;
bool bo[100005][30];
void spfa(){
memset(f,127,sizeof(f));
dui.push(make_pair(1,0));
bo[1][0]=1,f[1][0]=0;
while(dui.size()){
int x=dui.front().first,now=dui.front().second;
dui.pop();
bo[x][now]=0;
for(int i=head[x];i;i=ed[i].next){
int y=ed[i].yuan;
if(f[y][now]>f[x][now]+ed[i].w){
f[y][now]=f[x][now]+ed[i].w;
if(!bo[y][now]){
bo[y][now]=1;
dui.push(make_pair(y,now));
}
}
if(now<k&&f[y][now+1]>f[x][now]){
f[y][now+1]=f[x][now];
if(!bo[y][now+1]){
bo[y][now+1]=1;
dui.push(make_pair(y,now+1));
}
}
}
}
}
int main(){
n=read(),m=read(),k=read();
for(int i=1;i<=m;i++){
int cn=read(),cm=read(),cw=read();
add(cn,cm,cw);
add(cm,cn,cw);
}
spfa();
int ans=0x7fffffff;
for(int i=0;i<=k;i++)ans=min(ans,f[n][i]);
cout<<ans<<endl;
return 0;
}
STL类
堆
#include<bits/stdc++.h>
using namespace std;
int n;
priority_queue<int,vector<int>,greater<int> >dui;
int main(){
cin>>n;
for(register int i=1;i<=n;++i){
register int ty;cin>>ty;
if(ty==1){
cin>>ty;
dui.push(ty);
}
else if(ty==2){
cout<<dui.top()<<endl;
}else{
dui.pop();
}
}
}
字符串类
manacher
//注意此算法求的是回文串，必须是连续的一段序列
//而回文序列则不必连续
#include<bits/stdc++.h>
using namespace std;
char s[31000005];
int r[31000005],len;//r是包括自己向右扩展的最大半径
int main(){
s[0]=s[1]='#';len=2;
while(cin>>s[len]){
s[++len]='#';++len;
}
--len;//在每个字符之间插板子
r[0]=r[1]=r[2]=1;
int maxr=2,pos=0,ans=0;
for(int i=3;i<=len;i++){//必须一个一个更新 因为可能答案是关于‘#’对称的。。。
if(i<maxr){
r[i]=min(r[(pos<<1)-i],maxr-i);//两种情况
}else r[i]=1;
for(;s[i-r[i]]==s[i+r[i]];++r[i]);//左右拓展
if(maxr<i+r[i])pos=i,maxr=i+r[i];
ans=max(ans,r[i]);
}
cout<<ans-1;//半径减去‘#’的个数
}
KMP
#include<bits/stdc++.h>
using namespace std;
int n,m,lena,lenb,nex[1000005];
char a[1000005],b[1000005];
int main(){
scanf("%s%s",a+1,b+1);
lena=strlen(a+1);
lenb=strlen(b+1);
int j=0;
for(int i=2;i<=lenb;i++){
while(j&&b[i]!=b[j+1])j=nex[j];
if(b[i]==b[j+1])++j;
nex[i]=j;
}
j=0;
for(int i=1;i<=lena;i++){
while(j&&b[j+1]!=a[i])j=nex[j];
if(b[j+1]==a[i])++j;
if(j==lenb){cout<<i-lenb+1<<endl;j=nex[j];}
}
for(int i=1;i<=lenb;i++)cout<<nex[i]<<" ";
return 0;
}
字符串hash
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull n,a[100005];
char s[100005];
ull mod=20190816170251;
ull base=131;
ull ha(int len){
ull ans=0;
for(int i=0;i<len;i++){
ans=(ans*base+(ull)s[i])%mod+19260817;//别问为什么是这个数,问就禁言
}
return ans;
}
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%s",s);
a[i]=ha(strlen(s));
}
int ans=1;
sort(a+1,a+n+1);
for(int i=1;i<n;i++){
if(a[i]!=a[i+1])
ans++;
}
printf("%d",ans);
}
/*
字符串hash的原理:
比如abcde
则
ha[1]=a
ha[2]=ab
ha[3]=abc
ha[4]=abcd
ha[5]=abcde
倒过来hash:
ha[1]=e
ha[2]=ed
ha[3]=edc
ha[4]=edcb
ha[5]=edcba
所以如果要取出'cba'的子串
则要用ha[5]-ha[2]*(base^(5-2))
*/
高精度
高精度加法
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 1000000
using namespace std;
char d[maxn],e[maxn];
int a[maxn],b[maxn],c[maxn];
int main(){
scanf("%s%s",&d,&e);
int lena=strlen(d),lenb=strlen(e),lenc=lena>lenb?lena:lenb,jin=0;
for(int i=0;i<lena;i++){
a[lena-i]=d[i]-48;
}
for(int i=0;i<lenb;i++){
b[lenb-i]=e[i]-48;
}
for(int i=1;i<=lenc;i++){
c[i]=a[i]+b[i]+jin;
jin=c[i]/10;
c[i]%=10;
}
lenc++;
c[lenc]=jin;
while(!c[lenc]&&lenc>1){
lenc--;
}
for(int i=lenc;i>=1;i--)printf("%d ",c[i]);
return 0;
}
高精度减法
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 1000000
using namespace std;
char d[maxn],e[maxn];
int a[maxn],b[maxn],c[maxn],f[maxn];
int main(){
scanf("%s%s",&d,&e);
if(strcmp(d,e)==0){
cout<<"0";
return 0;
}
int lena=strlen(d),lenb=strlen(e);
for(int i=0;i<lena;i++){
a[lena-i]=d[i]-48;
}
while(!a[lena]){
lena--;
}
for(int i=0;i<lenb;i++){
b[lenb-i]=e[i]-48;
}
while(!b[lenb]){
lenb--;
}
int lenc=lena>lenb?lena:lenb;
if(memcmp(a,b,lenc)<0&&lena==lenb||(lena<lenb)){
memcpy(f,a,sizeof(a)); memcpy(a,b,sizeof(b)); memcpy(b,f,sizeof(f));
cout<<"-";
int t=lena;
lena=lenb;
lenb=t;
}
lenc=lena>lenb?lena:lenb;
for(int i=1;i<=lenc;i++){
if(a[i]-b[i]<0){
a[i]+=10;
a[i+1]--;
}
c[i]=a[i]-b[i];
}
lenc++;
while(!c[lenc]&&lenc>1){
lenc--;
}
for(int i=lenc;i>=1;i--)printf("%d ",c[i]);
return 0;
}
高精度乘法
#include<iostream>
#include<cstring>
using namespace std;
int a[2005],b[2005],c[2005];
char a1[2005],b1[2005];
int main(){
scanf("%s%s",&a1,&b1);
int lena=strlen(a1),lenb=strlen(b1);
for(int i=0;i<lena;i++) a[lena-i]=a1[i]-'0';
for(int i=0;i<lenb;i++) b[lenb-i]=b1[i]-'0';
for(int i=1;i<=lenb;i++){
int jin=0;
for(int j=1;j<=lena;j++){
c[i+j-1]=a[j]*b[i]+jin+c[i+j-1];
jin=c[i+j-1]/10;
c[i+j-1]%=10;
}
c[lena+i]=jin;
}
int lenc=lena+lenb;
while(!c[lenc]&&lenc>1)lenc--;
for(int i=lenc;i>=1;i--)printf("%d ",c[i]);
return 0;
}
高精除以低精（附带出输出余数）
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int a[2005],b,c[2005],jin;
char a1[2005];
int main(){
scanf("%s",&a1);
cin>>b;
int lena=strlen(a1);
for(int i=0;i<lena;i++) a[i+1]=a1[i]-'0';//记得是从前往后处理
for(int i=1;i<=lena;i++){
c[i]=(jin*10+a[i])/b;
jin=(jin*10+a[i])%b;
}
int lenc=1;
while(!c[lenc]&&lenc<lena)lenc++;
for(int i=lenc;i<=lena;i++)printf("%d",c[i]);
cout<<endl<<jin;
return 0;
}
//jin取的是前面的余数，把前面的余数拼到后面一起除
排序
选择排序
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int a[99999999],n;
void swap(int &l,int &k){
int t=l;
l=k;
k=t;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
int ji=i;
for(int j=i+1;j<=n;j++){
if(a[j]<a[ji])ji=j;
}
if(ji!=i)
// {//或者这样也行
// int t=a[i];
// a[i]=a[ji];
// a[ji]=t;
// }
swap(a[i],a[ji]);//要传址调用
}
cout<<endl;
for(int i=1;i<=n;i++)
printf("%d ",a[i]);
return 0;
}
正版冒泡
#include<iostream>
#include<cstdio>
using namespace std;
int a[99999999],n;
int main(){
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=n-1;i>=1;i--){
for(int j=0;j<=i;j++){
if(a[j]>a[j+1]) swap(a[j],a[j+1]);
}
}
for(int i=1;i<=n;i++)printf("%d ",a[i]);
return 0;
}
盗版冒泡
#include<iostream>
#include<cstdio>
using namespace std;
int a[99999999],n;
int main(){
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
// for(int i=1;i<=n;i++)cout<<a[i]<<" ";
for(int i=1;i<=n;i++){
// int ji=0;
for(int j=i+1;j<=n;j++){
if(a[i]>a[j]) swap(a[i],a[j]);
}
}
for(int i=1;i<=n;i++)printf("%d ",a[i]);
return 0;
}
插排
#include<iostream>
#include<cstdio>
using namespace std;
int a[99999999],n,i,j;
void yi(int p,int q)
{
for(int h=q;h>p;h--)a[h]=a[h-1];
}
int main(){
cin>>n;
for( i=1;i<=n;i++)scanf("%d",&a[i]);
for( i=2;i<=n;i++){//a[i]为需要插入的数
for( j=i-1;j>=1;j--)//寻找插入点
if(a[j]<a[i])break;
if(j!=i-1){//需要将a[i]插入a[j]后
int temp=a[i];
yi(j+1,i);
a[j+1]=temp;
}
}
cout<<endl;
for(i=1;i<=n;i++)printf("%d ",a[i]);
return 0;
}
桶排
#include<iostream>
#include<cstdio>
using namespace std;
int a[99999999],n,ji;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&ji);
a[ji]++;
}
for(int i=0;i<=n;i++){
while(a[i]){
printf("%d ",i);
a[i]--;
}
}
return 0;
}
三数取中+插排版 快排
#include<iostream>
#include<cstdio>
using namespace std;
int a[99999999],n;
void cha(int p,int q)//p<q
{
int f,g;
for( f=p;f<=q;f++){
for( g=f-1;g>=p;g++)if(a[g]<a[f])break;
if(g!=f-1){
int temp=a[f];
for(int s=f;s>g;s--)a[s]=a[s-1];
a[g+1]=temp;
}
}
}
void quick(int le,int ri)
{
if(le>=ri)return;
if(ri-le>=10)cha(le,ri);
int t=(le+ri)/2,mid,x=le,y=ri;
if(a[le]<a[t]){
if(a[t]>a[ri]){
int w=a[t];
a[t]=a[ri];
a[ri]=w;
}
}
if(a[le]>a[t]){
int w=a[t];
a[t]=a[le];
a[le]=w;//a[le]<a[t]
if(a[t]>a[ri]){
int w=a[t];
a[t]=a[ri];
a[ri]=w;
}
}
mid=a[t];
do{
while(a[x]<mid)x++;
while(a[y]>mid)y--;
if(x<=y){
int w=a[x];
a[x]=a[y];
a[y]=w;
x++;
y--;
}
}while(x<=y);
if(le<y)quick(le,y);
if(x<ri)quick(x,ri);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
quick(1,n);
for(int i=1;i<=n;i++)printf("%d ",a[i]);
}
return 0；
归并排序
#include<iostream>
#include<cstdio>
using namespace std;
int a[99999999],b[99999999],n;
void gui(int le,int ri)
{
if(le==ri)return;
int mid=(le+ri)/2,x=le,y=mid+1,k=le;
gui(le,mid);
gui(mid+1,ri);
while(x<=mid&&y<=ri){
if(a[x]<a[y]){
b[k++]=a[x++];
}
else{
b[k++]=a[y++];
}
}
while(x<=mid){
b[k++]=a[x++];
}
while(y<=ri){
b[k++]=a[y++];
}
for(int g=le;g<=ri;g++)a[g]=b[g];
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
gui(1,n);
for(int i=1;i<=n;i++)printf("%d ",a[i]);
return 0;
}
测试数据生成器
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;
int main(){
freopen("testdata.in","w",stdout);
srand((unsigned)time(NULL));
for(int i=1;i<=10000;i++)
printf("%d ",rand());
return 0；
}