- 大米饼的左偏树
#include<iostream>
#include<cstdio>
#define N 1000005
using namespace std;
int n,m,fa[N],l[N],r[N],d[N],v[N];
bool die[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int merge(int x,int y)
{
if(!x)return y;if(!y)return x;//树结构合并的递归边界
if(v[x]>v[y])swap(x,y);//找到两个树根中键值最小的节点
r[x]=merge(r[x],y);//右儿子插入操作(左偏树特性),将键值较大的树作为另一个树的右儿子
if(d[r[x]]>d[l[x]])swap(l[x],r[x]);//维护左偏性质
d[x]=d[r[x]]+1;//记录dis(左偏树的基础信息)
return x;//返回根
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
for(int i=1;i<=n;i++)fa[i]=i;d[0]=-1;char ch[10];scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",ch);int x,y;
if(ch[0]=='M')//要求：合并团
{
scanf("%d%d",&x,&y);
if(die[x]||die[y])continue;//若最小值已死，则命令无效
int p=find(x),q=find(y);//并查集找出左偏树根
if(p!=q)//不是同一棵左偏树
{
int t=merge(p,q);//左偏树合并，返回新根
fa[p]=fa[q]=t;//维护并查集
}
}
else//要求：询问团
{
scanf("%d",&x);
if(die[x])printf("0
");//人已死，命令无效输出0
else
{
int p=find(x);die[p]=1;//找到这个人所在团(左偏树)，将其弄死
printf("%d
",v[p]);//按照题目要求输出那个人的分数
fa[p]=merge(l[p],r[p]);//分最低人死了，将其移出左偏树，左右儿子合并重建
fa[fa[p]]=fa[p];//并查集变成初始化状态（相当于删除）
}
}
}
return 0;
}
- P1177 【模板】快速排序
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[100005],n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<n;i++) printf("%d ",a[i]);
printf("%d",a[n]);
return 0;
}
- P1439 【模板】最长公共子序列
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int A[100005],B[100005],tmp[100005];
int n;
int LIS(int *a){
static int t[100005],p; p=0;
for(int i=1;i<=n;i++){
if(B[i]>t[p]||t==0) t[++p]=B[i];
else{
int l=lower_bound(t+1,t+p+1,B[i])-t;
t[l]=B[i];
}
}
return p;
}
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)scanf("%d",&A[i]),tmp[A[i]]=i;
for(int i=1; i<=n; i++)scanf("%d",&B[i]),B[i]=tmp[B[i]];
int ans=LIS(B);
printf("%d",ans);
return 0;
}
- P3366 【模板】最小生成树 kruskal
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct edge{
int u,v,w;
bool operator <(const edge &rtm) const{
return w<rtm.w;
}
}e[200005];
int fa[5005];
int n,m,ans;
int find(int u){
return u==fa[u]?u:fa[u]=find(fa[u]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
sort(e+1,e+m+1);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1,need=n-1;i<=m&&need;i++){
int u=e[i].u,v=e[i].v,w=e[i].w;
int fu=find(u),fv=find(v);
if(fu==fv) continue;
fa[fv]=fu; need--;
ans+=w;
}
printf("%d",ans);
return 0;
}
- P3366 【模板】最小生成树 prim
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
struct node{
int id,val;
bool operator <(const node &rtm) const{
return val>rtm.val;
}
};
struct edge{
int to,val,next;
}e[200005*2];
int head[5005];
int n,m,ent=2;
void add(int u,int v,int w){
e[ent]=(edge){v,w,head[u]};
head[u]=ent++;
}
void cmin(int &a,int b){
if(a>b) a=b;
}
int prim(){
static int d[5005],ans;
memset(d,0x3f,sizeof(d));
priority_queue<node>q; q.push((node){1,0});
while(!q.empty()){
int u=(q.top()).id,w=(q.top()).val; q.pop();
if(!(~d[u])) continue;
ans+=w; d[u]=-1;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(!(~d[v])) continue;
cmin(d[v],e[i].val);
q.push((node){v,d[v]});
}
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,u,v,w;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,w);
}
int ans=prim();
printf("%d",ans);
return 0;
}
- P3368 【模板】树状数组 2
/*
(正反都可以)
*/
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct BIT{
int a[500005],n;
void init(int N){
n=N; memset(a,0,sizeof(a));
}
int lowbit(int x){
return x&-x;
}
void add(int l,int r,int w){
for(int i=l-1;i;i-=lowbit(i)) a[i]-=w;
for(int i=r;i;i-=lowbit(i)) a[i]+=w;
}
int query(int p){
int now=0;
for(int i=p;i<=n;i+=lowbit(i)) now+=a[i];
return now;
}
}T;
int a[500005];
int n,m;
int main()
{
scanf("%d%d",&n,&m); T.init(n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int com,x,y,k;
for(int i=1;i<=m;i++){
scanf("%d",&com);
if(com==1){
scanf("%d%d%d",&x,&y,&k);
T.add(x,y,k);
}
else{
scanf("%d",&x);
printf("%d
",a[x]+T.query(x));
}
}
return 0;
}
- P3370 【模板】字符串哈希
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int a,b;
bool operator ==(const node &rtm) const{
return a==rtm.a&&b==rtm.b;
}
bool operator <(const node &rtm) const {
return a==rtm.a?b<rtm.b:a<rtm.a;
}
}a[10005];
int hash1(char *s){
static int mod=19260817,bit=233;
int now=0;
for(int i=0;s[i];i++)
now=(1ll*now*bit+s[i]-0)%mod;
return now;
}
int hash2(char *s){
static int mod=12356789,bit=79;
int now=0;
for(int i=0;s[i];i++)
now=(1ll*now*bit+s[i]-0)%mod;
return now;
}
int n;
int main()
{
char s[1505];
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s);
a[i]=(node){hash1(s),hash2(s)};
}
sort(a+1,a+n+1);
n=unique(a+1,a+n+1)-a-1;
printf("%d",n);
return 0;
}
- P3371 【模板】单源最短路径
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define node(a,b) (node){a,b}
using namespace std;
struct node{
int id,val;
bool operator <(const node &rtm) const{
return val>rtm.val;
}
};
struct edge{
int to,val,next;
}e[500005];
int head[10005];
int n,m,ent=2,S;
void add(int u,int v,int w){
e[ent]=(edge){v,w,head[u]};
head[u]=ent++;
}
void Dijkstra(){
static int dis[10005];
static bool vis[10005];
priority_queue<node> q;
for(int i=1;i<=n;i++) dis[i]=2147483647;
q.push(node(S,0)); dis[S]=0;
while(!q.empty()){
int u=(q.top()).id; q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(dis[v]<=dis[u]+e[i].val) continue;
dis[v]=dis[u]+e[i].val;
q.push(node(v,dis[v]));
}
}
for(int i=1;i<=n;i++) printf("%d ",dis[i]);
}
void SPFA(){
static int dis[10005];
static bool inq[10005];
deque<int>q;
for(int i=1;i<=n;i++) dis[i]=2147483647;
q.push_back(S); dis[S]=0; inq[S]=1;
while(!q.empty()){
int u=q.front(); q.pop_front(); inq[u]=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(dis[v]<=dis[u]+e[i].val) continue;
dis[v]=dis[u]+e[i].val;
if(inq[v]) continue; inq[v]=1;
if(!q.empty()&&dis[q.front()]>dis[v]) q.push_front(v);
else q.push_back(v);
}
}
for(int i=1;i<=n;i++) printf("%d ",dis[i]);
}
int main()
{
scanf("%d%d%d",&n,&m,&S);
for(int i=1,u,v,w;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
//Dijkstra();
SPFA();
return 0;
}
- P3375 【模板】KMP字符串匹配
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char A[1000005],B[1000005];
int nxt[1000005];
void get_nxt(char *s){
nxt[0]=-1; int k=-1,j=0;
while(s[j]){
if(k==-1||s[j]==s[k]){
k++; j++; nxt[j]=k;
}
else k=nxt[k];
}
}
void matching(char *T,char *S){
int i=0,j=0;
while(T[i]){
if(j==-1||T[i]==S[j]) i++,j++;
else j=nxt[j];
if(~j&&!S[j]) printf("%d
",i-j+1);
}
for(int i=1;S[i-1];i++) printf("%d ",nxt[i]);
}
int main()
{
scanf("%s",A); scanf("%s",B);
get_nxt(B);
matching(A,B);
return 0;
}
- P3383 【模板】线性筛素数
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
bool iscom[10000005];
int prim[10000005],cnt;
void Get(int N){
iscom[1]=1;
for(int i=2;i<=N;i++){
if(!iscom[i]) prim[++cnt]=i;
for(int j=1;j<=cnt&&i<=N/prim[j];j++){
iscom[i*prim[j]]=1;
if(i%prim[j]==0) break;
}
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
Get(n);
while(m--){
scanf("%d",&n);
if(iscom[n]) puts("No");
else puts("Yes");
}
return 0;
}
- P3386 【模板】二分图匹配
/*
匈牙利算法匹配时，那个vis标记是遇到一个v就标记，而不是进入一个dfs才标记。
*/
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct edge{
int to,next;
}e[1005*1005*2];
int head[2005],match[2005],vis[2005];
int n,m,ent=2,tim,ans,ee;
void add(int u,int v){
e[ent]=(edge){v,head[u]};
head[u]=ent++;
}
bool dfs(int u){
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(vis[v]==tim) continue;
vis[v]=tim;
if(!match[v]||dfs(match[v])){
match[v]=u;
return 1;
}
}
return 0;
}
int main()
{
scanf("%d%d%d",&n,&m,&ee);
for(int i=1,u,v;i<=ee;i++){
scanf("%d%d",&u,&v);
if(u>n||v>m) continue;
v+=n;
add(u,v); add(v,u);
}
for(int i=1;i<=n+m;i++){
tim++;
if(dfs(i)) ans++;
}
printf("%d",ans/2);
return 0;
}
- P3808 【模板】AC自动机（简单版）
#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
struct Trie{
int next,last,val;
int ch[30];
}T[1000006];
char s[1000006];
int n,sz=0,ans;
int idx(char ch){
return ch-'a';
}
void add(char *S){
int u=0,l=strlen(S);
for(int i=0;i<l;i++){
int c=idx(S[i]);
if(!T[u].ch[c]) T[u].ch[c]=++sz;
u=T[u].ch[c];
}
T[u].val++;
}
void build(){
queue<int>q;
for(int i=0;i<26;i++) if(T[0].ch[i]) q.push(T[0].ch[i]);
while(!q.empty()){
int u=q.front(); q.pop();
for(int i=0;i<26;i++){
if(!T[u].ch[i]) T[u].ch[i]=T[T[u].next].ch[i];
else{
int v=T[u].ch[i];
T[v].next=T[T[u].next].ch[i];
T[v].last=T[T[v].next].val?T[v].next:T[T[v].next].last;
q.push(v);
}
}
}
}
void get(int j){
if(!j||!T[j].val) return;
ans+=T[j].val; T[j].val=0;
get(T[j].last);
}
void match(char *S){
int l=strlen(S); int j=0;
for(int i=0;i<l;i++)
{
int c=idx(S[i]);
j=T[j].ch[c];
if(T[j].val) get(j);
else if(T[j].last) get(T[j].last);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s);
add(s);
}
build(); scanf("%s",s);
match(s);
printf("%d",ans);
return 0;
}
- P3811 【模板】乘法逆元
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
long long inv[3000006],mod,n;
int main()
{
scanf("%lld%lld",&n,&mod);
inv[1]=1;printf("%lld
",inv[1]);
for(int i=2;i<=n;i++){
inv[i]=( (-(mod/i)*inv[mod%i]) %mod+mod)%mod;
printf("%lld
",inv[i]);
}
return 0;
}