NOIP板子
NOIP板子
FIRST lucas（卢卡斯）
#include
#include
#include
using namespace std;
int T,n,m,p;
long long a[100005],b[100005];
long long lucas(int x,int y)
{if(x SECOND fast_pow（快速幂）
#include
#include
#define ll long long
using namespace std;
ll a,b,mod;
ll pow(ll x,ll y)
{int a=1;x%=mod;a%=mod; //注意1 0 1这组数据 while(y){if(y%2)a*=x;x*=x;x%=mod;a%=mod;y>>=1; }return a;
}
int main()
{cin>>a>>b>>mod;cout<#include
#include
#define ll long long
using namespace std;
ll n,k,mod=1e9+7;//开long long
struct AC
{ll data[101][101];
}a,f;
AC work(AC x ,AC y)
{AC c; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)c.data[i][j]=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)c.data[i][j]=c.data[i][j]%mod+x.data[i][k]*y.data[k][j]%mod;return c;
}
AC fast_pow(AC x,ll mi)
{AC ans=f;while(mi){if(mi&1)ans=work(ans,x);x=work(x,x);mi>>=1;}return ans;
}
int main()
{cin>>n>>k;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a.data[i][j];for(int i=1;i<=n;i++)f.data[i][i]=1;AC x=fast_pow(a,k);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cout< FOURTH Pei Shu theorem （裴蜀定理）
#include
#include
using namespace std;
int n,x,y;
int gcd(int xx,int yx)
{xx=xx<0?(-xx):xx;yx=yx<0?(-yx):yx;if(yx==0)return xx;return gcd(yx,xx%yx);
}
int main()
{cin>>n;cin>>x>>y;y=gcd(x,y);for(int i=3;i<=n&&y!=1;i++)cin>>x,y=gcd(y,x);cout< FIFTH 匈牙利算法
//二分图最大匹配
#include
#include
#include
using namespace std;
int n,m,e,edge[2010][1010],u,v,vis[2010],p[2010],ans;
bool DFS(int x)
{for(int j=1;j<=edge[x][0];j++)if(!vis[edge[x][j]]){vis[edge[x][j]]=1;if(!p[edge[x][j]]||DFS(p[edge[x][j]])){p[edge[x][j]]=x;return 1;}}return 0;
}
int main()
{cin>>n>>m>>e;for(int i=1;i<=e;i++){cin>>u>>v;if(u>n||v>m)continue;edge[u][++edge[u][0]]=n+v;edge[n+v][++edge[n+v][0]]=u;}for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(DFS(i))ans++;}/*for(int i=1;i<=m;i++)if(p[i+n])ans++;*/cout< SIXTH 逆元
//线性求逆元
#include
#define ll long long
using namespace std;
int inv[3000010],n,p;
int main()
{cin>>n>>p;inv[1]=1;for(int i=2;i<=n;i++)inv[i]=(ll)(p-p/i)*inv[p%i]%p;//开long long for(int i=1;i<=n;i++)cout< //扩欧求逆元
#include
using namespace std;
int n,mod,x,y;
void exgcd(int a,int b,int &x,int &y)
{if(b==0){x=1,y=0;return;}exgcd(b,a%b,y,x); y-=a/b*x;return ;
}
int main()
{cin>>n>>mod;exgcd(n,mod,x,y);cout<<(x+mod)%mod;
} SEVENTH 线性基
#include
#include
#define ll long long
using namespace std;
int n;ll x,ans,mp[55];
void add(ll xx)
{for(int i=50;i>=0;i--)if(xx&(1ll<>n;for(int i=1;i<=n;i++)cin>>x,add(x);ll ret=0;for(int i=50;i>=0;i--)if ((ret^mp[i])>ret)ret^=mp[i];cout< EIGHTH 逆序对
//树状数组求逆序对
#include
#include
#include #include
using namespace std;
//下面就是 归并排序求逆序对 的过程==
const int maxn=1008611;
int a[maxn],r[maxn],ans=0,n;//ans作为全局变量，记录逆序对的数量；
void msort(int s,int t)
{if(s==t) return ;int mid=(s+t)/2;msort(s,mid);//→→→→→→→递归的体现msort(mid+1,t);//→→→→→↗↗ int i=s,j=mid+1,k=s;while(i<=mid&&j<=t){if(a[i]<=a[j])r[k]=a[i],k++,i++;else{r[k]=a[j],k++,j++;ans+=mid-i+1;//只可意会，不可言传==；}}while(i<=mid)r[k]=a[i],k++,i++;while(j<=t)r[k]=a[j],k++,j++;for(int i=s;i<=t;i++)a[i]=r[i];
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);msort(1,n);//从1到n将a数组排序；printf("%d\n",ans);return 0;
} NINETH splay
#include
#include
#include
using namespace std;
#define ll long long
const int N=1e5+5;
int fa[N],size[N],key[N],cnt[N],ch[N][2],sz,root;
inline int read()//读入优化
{int ans=0,f=1;char ch=getchar();while(!isdigit(ch)&&ch!='-')ch=getchar();if(ch=='-')f=-1,ch=getchar();while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();return ans*f;
}
inline void update(int x)//更新节点的值
{size[x]=cnt[x]+size[ch[x][0]]+size[ch[x][1]];
}
inline int get(int x)//查询x是左节点还是右节点
{ return x==ch[fa[x]][1];
}
inline void clear(int x)//清空x的值
{ch[x][0]=ch[x][1]=fa[x]=size[x]=cnt[x]=key[x]=0;
}
inline void rotate(int x,int &k)//只是将x旋到了其父亲的位置
{int old,oldfa,o;old=fa[x];oldfa=fa[old];o=get(x);//x要与其父亲节点交换位置 即将x旋到其父亲的位置 if(old==k)k=x;//k就是x的父亲节点 经过处理后x会来到k的位置完成操作 else ch[oldfa][get(old)]=x;//更新其经过操作的父亲的节点 //因为k是跟节点 所以当k是x的父亲 x经过操作就是根节点 不用更新其父亲的节点 fa[x]=oldfa;//更新x的父亲 ch[old][o]=ch[x][o^1];//更新原来父亲的节点 fa[ch[x][o^1]]=old;//更新原来节点的父亲 ch[x][o^1]=old;//更新自己的节点 fa[old]=x;//更新原来父亲的父亲 update(x),update(old);//更新两个被修改的节点的size值
}
inline void splay(int x,int &k)//将x旋到k的位置
{while(x!=k)//操作边界 {if(fa[x]!=k)rotate(get(x)^get(fa[x])?x:fa[x],k);//如果x当前的父亲不是k 若是x与其父亲节点都是左或右节点 可以将x的父亲向上旋 rotate(x,k);//将x向上旋 }
}
inline void insert(int x)//插入x
{if(!root){root=++sz;size[sz]=cnt[sz]=1;key[sz]=x;return;}//还没有建成树 int now=root,o;while(1){if(x==key[now])//x的值与当前节点的值相同 {++cnt[now];//计数器++ splay(now,root);//将当前节点旋到根位置 以便 update(now);//更新当前节点的size return;}o=x>key[now]?1:0;//判断x应是左还是右节点 if(!ch[now][o])//如果此位置没有节点 {ch[now][o]=++sz;//更新节点的size size[sz]=cnt[sz]=1;//更新size和计数器 key[sz]=x;fa[sz]=now;//初始化新节点 splay(sz,root);//将此节点旋到根节点 return;}else now=ch[now][o];//继续向下寻找 }
}
inline int find_pos(int x)//寻找x的位置
{int now=root;while(1)//根据二叉平衡树的性质 {if(x==key[now]){return now;}if(x1){--cnt[root];return;}//若是有多个值相同的 计数器-- if(!ch[root][0]&&!ch[root][1]){clear(root);root=0;return;}//若是只有一个值 一个节点 清空树即可 if(ch[root][0]&&ch[root][1])//左子树 右子树都存在 {int oldroot=root;//记录当前的根 splay(pre(),root);//将前驱旋成根 fa[ch[oldroot][1]]=root;//把原先根的右子树连到新根上 ch[root][1]=ch[oldroot][1];clear(oldroot);//清空原先的根 update(root);//更新现在的根 }else//存在一颗子树 {int o=ch[root][1]>0;root=ch[root][o];//更新根 clear(fa[root]);//清空原根 fa[root]=0;//更新 }
}
inline int find_order_of_key(int x)//寻找x的排名
{int res=0,now=root;while(1)//根据二叉平衡树的性质 { if(x TENTH 筛素数
//线性筛
#include
using namespace std;
int tot=0,p[10000001],c[10000001],n,m;
int sushu(int x)
{for(int i=2;i<=x;i++){if(p[i]!=1)c[tot++]=i;for(int j=0;jx)break;p[i*c[j]]=1;if(i%c[j]==0)break;}}
}
int main()
{cin>>n>>m;sushu(n);for(int i=1;i<=m;i++){cin>>n;if(n==1){cout<<"No"< ELEVENTH hash（哈希）
//双hash值 输出多少不同的字符串
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef unsigned long long ull;
ull hh=19260817;
int base=131;
ull hhh=19660813;
struct AC
{int x,y;
}a[10010];
char ch[10010];
int n;
ull len;
int ans=1;
bool cmp(AC x,AC y)
{return x.x TWELVETH 一笔画(欧拉回路)
图是联通的 .统计所有的点的出度。如果出度全部为偶数或者恰好只有两个点为奇数。则可以一笔画。
联通的话用并查集也可以。用dfs从任意一个点进行搜索然后看下能不能走到所有的点。也可以。但是推荐用dfs，因为可以一边统计出度信息。
THIRTEENTH LCA
#include
#include
using namespace std;
int n,m,root,p,next[1000010],last[500010],h[1000010];
int per[500010][20],log[500010],dep[500010],x,y;
inline int read()
{char ch=getchar();int xv=0;while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9')xv=xv*10+ch-'0',ch=getchar();return xv;
}
void add(int x,int y)
{p++;next[p]=last[x];last[x]=p;h[p]=y;swap(x,y);p++;next[p]=last[x];last[x]=p;h[p]=y;
}
void dfs(int x,int fa)
{for(int i=last[x];i;i=next[i])if(h[i]!=fa)dep[h[i]]=dep[x]+1,per[h[i]][0]=x,dfs(h[i],x);
}
int lca(int x,int y)
{if(dep[x]dep[y])x=per[x][log[dep[x]-dep[y]]-1];if(x==y)return x;for(int i=log[dep[x]]-1;i>=0;i--)if(per[x][i]!=per[y][i])x=per[x][i],y=per[y][i];return per[x][0];
}
int main()
{//cin>>n>>m>>root;n=read();m=read(),root=read();for(int i=1;i FOURTEENTH Tarjan+拓扑
#include
#include
#include
using namespace std;
const int maxn=100010;
int p,next[maxn],last[maxn],h[maxn],dfn[maxn],low[maxn],tot,flag;
int stack[maxn],data[maxn],data_level[maxn],fa[maxn],vis[maxn];
int n,m,x[maxn],y[maxn],l[maxn],hh[maxn],nxt[maxn],pp,per[maxn];
int ans[maxn],ansx,ru[maxn];
queueq;
inline int read()
{char ch=getchar();int xv=0;while(ch<'0'||ch>'9')ch=getchar();while(ch<='9'&&ch>='0')xv=xv*10+ch-'0',ch=getchar();return xv;
}
void add(int u,int v)
{p++;next[p]=last[u];last[u]=p;h[p]=v;
}
void tarjan(int x)
{int ansz=0;dfn[x]=low[x]=++tot;vis[x]=1;stack[++flag]=x;for(int i=last[x];i;i=next[i]){if(!dfn[h[i]])tarjan(h[i]),low[x]=min(low[x],low[h[i]]);else if(vis[h[i]])low[x]=min(low[x],low[h[i]]);}if(low[x]==dfn[x]){do{fa[stack[flag]]=x;ansz+=data[stack[flag]];vis[stack[flag]]=0;flag--;}while(x!=stack[flag+1]);ans[x]=data_level[x]=ansz;per[++per[0]]=x;}
}
void add_level(int u,int v)
{pp++;nxt[pp]=l[u];l[u]=pp;hh[pp]=v;ru[v]++;
}
void build()
{for(int i=1;i<=m;i++)if(fa[x[i]]!=fa[y[i]])add_level(fa[x[i]],fa[y[i]]);
}
void TP()
{while(!q.empty()){int x=q.front();q.pop();for(int i=l[x];i;i=nxt[i]){ru[hh[i]]--;if(ru[hh[i]]==0)q.push(hh[i]);ans[hh[i]]=max(ans[hh[i]],data_level[hh[i]]+ans[x]);ansx=max(ansx,ans[hh[i]]);}ansx=max(ansx,ans[x]);}
}
int main()
{n=read();m=read();for(int i=1;i<=n;i++)data[i]=read();for(int i=1;i<=m;i++)x[i]=read(),y[i]=read(),add(x[i],y[i]);for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);build();for(int i=1;i<=per[0];i++)if(ru[per[i]]==0)q.push(per[i]);TP();cout< FIFTEENTH 单源最短路
#include
#include
#include
#include
using namespace std;
int x,y,z,n,m,k,last[100010],nxt[200010],h[200010],wis[200010],dis[100010],p,vis[100010];
void add(int u,int v,int w)
{p++;nxt[p]=last[u];last[u]=p;h[p]=v;wis[p]=w;
}
priority_queue< pair >q;
int main()
{cin>>n>>m>>k;for(int i=1;i<=m;i++)cin>>x>>y>>z,add(x,y,z);memset(dis,127/2,sizeof(dis));dis[k]=0;q.push(make_pair(0,k));while(!q.empty()){x=q.top().second,q.pop();if(vis[x])continue;vis[x]=1;for(int i=last[x];i;i=nxt[i]){if(dis[h[i]]>dis[x]+wis[i]){dis[h[i]]=dis[x]+wis[i];q.push(make_pair(-dis[h[i]],h[i]));}}}for(int i=1;i<=n;i++)cout< //热浪 双向路
#include
#include
#include
#include
#include
#include
using namespace std;
queueq;
int p,n,m,s,t,vis[2501],last[2501],wis[12401],nxt[12401],h[12401],x,y,z,dis[2501];
void add(int u,int v,int w)
{p++;nxt[p]=last[u];h[p]=v;wis[p]=w;last[u]=p;swap(u,v);p++;nxt[p]=last[u];h[p]=v;wis[p]=w;last[u]=p;
}
int main()
{cin>>n>>m>>s>>t;for(int i=1;i<=m;i++)cin>>x>>y>>z,add(x,y,z);memset(dis,127/2,sizeof(dis));dis[s]=0;q.push(s);vis[s]=1;while(!q.empty()){x=q.front(),q.pop();vis[x]=0;for(int i=last[x];i;i=nxt[i])if(dis[h[i]]>dis[x]+wis[i]){dis[h[i]]=dis[x]+wis[i];if(!vis[h[i]])q.push(h[i]),vis[h[i]]=1;}}cout< SIXTEENTH nim游戏
#include
using namespace std;
int T,n,ans,x;
int main()
{cin>>T;while(T--){cin>>n;ans=0;for(int i=1;i<=n;i++)cin>>x,ans^=x;if(ans==0)cout<<"No\n";else cout<<"Yes\n";}
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！