LimitFlat水题集

一粒夸克 · 2021-04-20 12:16:31 · 个人记录

【模板】快读

这scanf不是能过吗

#include<bits/stdc++.h>
using namespace std;
int n,ans,a;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a);
        ans=max(ans,a);
    }
    printf("%d",ans);

    return 0;
}

fread 只能读文件

#include<bits/stdc++.h>
using namespace std;
int n,ans,a;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
inline char gc(){
    if(p1==p2){
        p1=buf;
        p2=buf+fread(buf,1,1000000,stdin);
    }
    if(p1==p2)return EOF;
    return *p1++;
}
inline int read(){
    register int res=0;register char c=gc();
    register bool is=0;
    while(c<'0'||c>'9'){
        if(c=='-')is=1;
        c=gc();
    }
    while(c>='0'&&c<='9'){
        res=(res<<1)+(res<<3)+(c^48);
        c=gc();
    }
    return is?-res:res;
}
int main(){
    n=read();
    for(int i=0;i<n;i++){
        ans=max(ans,read());
    }
    printf("%d",ans);

    return 0;
}

【模板】权值线段树合并

std是错的：

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=1e6;
struct Node{
    int ls,rs;
    int val,pos;
}tr[MAXN*20*4];
int nodeCnt=0;
void insert(int &p,int l,int r,int x,int val){
    if(!p)p=++nodeCnt;
    if(l==r){
        tr[p].val+=val;
        tr[p].pos=l;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)insert(tr[p].ls,l,mid,x,val);
    else if(x>mid)insert(tr[p].rs,mid+1,r,x,val);
    tr[p].val=max(tr[tr[p].ls].val,tr[tr[p].rs].val);
    tr[p].pos=tr[tr[p].ls].val>=tr[tr[p].rs].val?tr[tr[p].ls].pos:tr[tr[p].rs].pos;
}
int merge(int p,int q,int l,int r){
    if(!p)return q;
    if(!q)return p;
    if(l==r){
        tr[p].val+=tr[q].val;
        tr[p].pos=tr[p].val?l:0;
        return p;
    }
    int mid=(l+r)>>1;
    tr[p].ls=merge(tr[p].ls,tr[q].ls,l,mid);
    tr[p].rs=merge(tr[p].rs,tr[q].rs,mid+1,r);
    tr[p].val=max(tr[tr[p].ls].val,tr[tr[p].rs].val);
    tr[p].pos=tr[tr[p].ls].val>=tr[tr[p].rs].val?tr[tr[p].ls].pos:tr[tr[p].rs].pos;
    return p;
}
int roots[MAXN],rootCnt=0;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int opt;
        cin>>opt;
        if(opt==1){//新建线段树
            roots[++rootCnt]=++nodeCnt;
        }else if(opt==2){//向某棵线段树中加入值
            int nowRoot,x,num;
            scanf("%d%d%d",&nowRoot,&x,&num);
            insert(roots[nowRoot],1,MAXN,x,num);
        }else if(opt==3){//查询某棵线段树中出现最多的是哪个值
            int nowRoot;
            scanf("%d",&nowRoot);
            cout<<tr[roots[nowRoot]].pos<<endl;
        }else if(opt==4){//合并两棵线段树
            int root1,root2;
            scanf("%d%d",&root1,&root2);
            roots[++rootCnt]=merge(root1,root2,1,MAXN);//这里！！！！
        }
    }
    return 0;
}

【模板】乘法逆元（快速幂）

#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
int n,p;
int poww(int a,int b){
    ll ans=1,tmp=a;
    while(b){
        if(b&1){
            ans*=tmp;
            ans%=p;
        }
        tmp=tmp*tmp;
        tmp%=p;
        b>>=1;
    }
    return ans;
}
int main(){
    //freopen("pow10.in","r",stdin);
    //freopen("pow10.out","w",stdout);
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++){
        ll ans=poww(i,p-2);
        cout<<ans<<endl;
    }
    return 0;
} 

【模板】O(1)快速乘

#include<bits/stdc++.h>
using namespace std;
long long a,b,p;
long long ksc(long long a,long long b,long long p){
    long long fir=a*b;
    long long sec=((long long)((long double)a*b/p))*p;
    return fir-sec;
}
int main(){
    scanf("%lld%lld%lld",&a,&b,&p);
    printf("%lld",ksc(a,b,p));

    return 0;
}

【模板】A*

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a,b;
int dis[1005];
bool vis[1005];
namespace Val{
    int to[200005],ne[200005],w[200005],f[1005],cnt;
    void link(int x,int y,int v){
        to[++cnt]=y;
        ne[cnt]=f[x];
        f[x]=cnt;
        w[cnt]=v;
    }
    void dij(){
        memset(dis,127,sizeof(dis));
        memset(vis,0,sizeof(vis));
        dis[b]=0;
        priority_queue<pair<int,int> > q;
        q.push(make_pair(0,b));
        while(!q.empty()){
            int u=q.top().second;q.pop();
            if(vis[u])continue;
            for(int i=f[u];i;i=ne[i]){
                if(dis[to[i]]>dis[u]+w[i]){
                    dis[to[i]]=dis[u]+w[i];
                    q.push(make_pair(-dis[to[i]],to[i]));
                }
            }
        }
    }
}
/*struct data{
    int x,len;
    long long is;
    data(int a,int b){
        x=a;len=b;is=0;
    }
    bool operator <(const data &b)const{
        if((len+dis[x])^(b.len+dis[b.x]))return len+dis[x]<b.len+dis[b.x];
        return x<b.x;
    }
};*/
namespace Astar{
    int to[200005],ne[200005],w[200005],f[1005],cnt;
    void link(int x,int y,int v){
        to[++cnt]=y;
        ne[cnt]=f[x];
        f[x]=cnt;
        w[cnt]=v;
    }
    void work(){
        priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
        q.push(make_pair(dis[a],a));
        while(!q.empty()){
            int len=q.top().first,u=q.top().second;
            q.pop();len-=dis[u];
//          printf("%d %d\n",u,len); 
            if(u==b&&!--k){
                printf("%d",len);
                return ;
            }
            for(int i=f[u];i;i=ne[i]){
                int v=to[i];
                q.push(make_pair(dis[v]+w[i]+len,v));
            }
        }
        puts("-1");
    }

}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int x,y,val;
        scanf("%d%d%d",&x,&y,&val);
        Val::link(y,x,val);
        Astar::link(x,y,val);
    }
    scanf("%d%d%d",&a,&b,&k);
    if(a==b)k++;

    Val::dij();
    Astar::work(); 

    return 0;
}

【模板】欧拉回路

#include<bits/stdc++.h>
using namespace std;
int n,m;
int to[200005],ne[200005],f[10005],cnt=1;
bool vis[200005];
void link(int x,int y){
    to[++cnt]=y;
    ne[cnt]=f[x];
    f[x]=cnt;
}
int stk[200005],top,ans[200005],ed;
void eulrd(int x){
    for(int &i=f[x];i;i=ne[i]){
        if(vis[i])continue;
        vis[i]=vis[i^1]=1;
        eulrd(to[i]);
    }
    ans[ed++]=x;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        link(x,y);
        link(y,x);
    }
    eulrd(1);
    for(int i=0;i<ed;i++)printf("%d\n",ans[i]);

    return 0;
}

【模板】矩阵乘法

#include<bits/stdc++.h>
using namespace std;
struct mat{
    int x,y;
    int a[105][105];
    void gets(){
        scanf("%d%d",&x,&y);
    }
    void clear(){
        memset(a,0,sizeof(a));
    }
    void read(){
        for(int j=1;j<=y;j++){
            for(int i=1;i<=x;i++){
                scanf("%d",&a[j][i]);
            }
        }
    }
    void write(){
        for(int j=1;j<=y;j++){
            for(int i=1;i<=x;i++){
                printf("%d ",a[j][i]);
            }
            putchar('\n');
        }
    }
    mat operator *(const mat &b)const{
        mat c;c.clear();
        c.x=b.x;c.y=y;
        for(int i=1;i<=c.x;i++){
            for(int j=1;j<=c.y;j++){
                for(int k=1;k<=x;k++){
                    c.a[j][i]+=a[j][k]*b.a[k][i];
                }
            }
        }
        return c;
    }
}a,b;

int main(){
    a.gets();b.gets();
    a.read();b.read();
//  a.write();b.write(); 
    (a*b).write();
    return 0;
}

【模板】缩点

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=1e5,MAXM=1e6;
struct Edge{
    int from,to,nxt;
}e[MAXM];
int head[MAXN],edgeCnt=1;
void addEdge(int u,int v){
    e[++edgeCnt].from=u;
    e[edgeCnt].to=v;
    e[edgeCnt].nxt=head[u];
    head[u]=edgeCnt;
}
int dfn[MAXN],low[MAXN],dfnCnt=0;
int stck[MAXN],top=0;
bool inStck[MAXN];
int inScc[MAXN],sccCnt=0;
int pointVal[MAXN];
int sumVal[MAXN];
void tarjan(int x){
    dfn[x]=low[x]=++dfnCnt;
    stck[++top]=x;
    inStck[x]=1;
    for(int i=head[x];i;i=e[i].nxt){
        int nowV=e[i].to;
        if(!dfn[nowV]){
            tarjan(nowV);
            low[x]=min(low[x],low[nowV]);
        }else if(inStck[nowV]){
            low[x]=min(low[x],dfn[nowV]);
        }
    }
    if(low[x]==dfn[x]){
        int y;
        sccCnt++;
        do{
            y=stck[top--];
            inScc[y]=sccCnt;
            inStck[y]=0;//
            sumVal[sccCnt]+=pointVal[y];//
        }while(x!=y);
    }
}
bool vis[MAXN];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&pointVal[i]);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addEdge(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;i++){
        if(!vis[inScc[i]]){
            vis[inScc[i]]=1;
            printf("%d\n",sumVal[inScc[i]]);
        }
    }
    return 0;
}

【模板】割边

#include<bits/stdc++.h>
using namespace std;
int to[600005],ne[600005],f[50005],cnt=1;
void link(int x,int y){
    to[++cnt]=y;
    ne[cnt]=f[x];
    f[x]=cnt;
}
int n,m;
int dfn[50005],low[50005];
bool cut[600005];
void tar(int x,int fr){
    if(!dfn[x])dfn[x]=low[x]=++cnt;
    for(int i=f[x];i;i=ne[i]){
        if(i==(fr^1))continue;
        int u=to[i];
        if(!dfn[u]){
            tar(u,i);
            low[x]=min(low[u],low[x]);
            if(low[u]>dfn[x])cut[i]=cut[i^1]=1;
        }
        else low[x]=min(low[x],dfn[u]);
    }

}
int ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        link(x,y);link(y,x);
    }cnt=0;
    for(int i=1;i<=n;i++)if(!dfn[i])tar(i,0);
    for(int i=1;i<=m;i++)if(cut[i<<1])ans++;
    printf("%d",ans);

    return 0;
}

【模板】边双连通分量

#include<bits/stdc++.h>
using namespace std;
int to[600005],ne[600005],f[50005],cnt=1;
void link(int x,int y){
    to[++cnt]=y;
    ne[cnt]=f[x];
    f[x]=cnt;
}
int n,m;
int dfn[50005],low[50005];
bool cut[600005];
void tar(int x,int fr){
    if(!dfn[x])dfn[x]=low[x]=++cnt;
    for(int i=f[x];i;i=ne[i]){
        if(i==(fr^1))continue;
        int u=to[i];
        if(!dfn[u]){
            tar(u,i);
            low[x]=min(low[u],low[x]);
            if(low[u]>dfn[x])cut[i]=cut[i^1]=1;
        }
        else low[x]=min(low[x],dfn[u]);
    }

}
int ans;
int dcc[50005];
void dfs(int x){
    dcc[x]=ans;
    for(int i=f[x];i;i=ne[i]){
        if(cut[i])continue;
        int u=to[i];
        if(!dcc[u]){
            dfs(u);
        }
    }

}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        link(x,y);link(y,x);
    }cnt=0;
    for(int i=1;i<=n;i++)if(!dfn[i])tar(i,0);
    for(int i=1;i<=n;i++)if(!dcc[i])ans++,dfs(i);
    printf("%d",ans);

    return 0;
}

学到的第三种强连通分量求法：

void dfs(int u){
    for(int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if(!vis[v]){//如果没搜索
            vis[v] = vis[u] + 1;//记录“深度”
            dfs(v);//继续搜
        }
        int fu = anc(u), fv = anc(v);//anc 是并查集函数
        if(vis[fv] > 0){//一定要是搜索中的
            if(vis[fu] < vis[fv]) f[fv] = fu;
            else f[fu] = fv;//注意这里，深度小的为祖先节点
        }
    }
    vis[u] = -1;//标记搜索完
    return;
}

【模板】点双连通分量

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 1e5;
int head[SIZE],ver[SIZE*2],Next[SIZE * 2];
int dfn[SIZE],low[SIZE],stk[SIZE],new_id[SIZE],c[SIZE];
int n,m,tot,num,root,top,cnt;
vector<int> dcc[SIZE];
void add(int x,int y){
    ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
void tarjan(int x) {
    dfn[x] = low[x] = ++num;
    stk[++top] = x;
    if(x==root&&head[x]==0){
        dcc[++cnt].push_back(x);
        return;
    }
    for (int i=head[x];i;i =Next[i]) {
        int y=ver[i];
        if (!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if (low[y]>=dfn[x]) {
                cnt++;
                for(int z=-1;z!=y;dcc[cnt].push_back(z)){
                    z=stk[top--];
                }
                dcc[cnt].push_back(x);
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}

int main() {
    cin >> n >> m;
    tot = 1;
    for (int i = 1; i <= m; i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        if (x==y)continue;
        add(x, y),add(y, x);
    }
    for (int i=1;i<=n;i++)
        if (!dfn[i])root=i,tarjan(i);
    for (int i=1;i<=cnt;i++) {
        for (int j=0;j<dcc[i].size();j++)
            printf("%d ",dcc[i][j]);
        puts("");
    }
    return 0;
}

【模板】Trie树

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=1000010;
int trie[SIZE][26],ed[SIZE],tot=1;
void insert(char* str){
    int len=strlen(str),p=1;
    for(int i=0;i<len;i++){
        int ch=str[i]-'a';
        if(!trie[p][ch])trie[p][ch]=++tot;
        p=trie[p][ch];
    }
    ed[p]+=1;
}
int search(char* str){
    int ans=0;
    int len=strlen(str),p=1;
    for(int i=0;i<len;i++){
        int ch=str[i]-'a';
        if(!trie[p][ch])return ans;
        p=trie[p][ch],ans+=ed[p];
    }
    return ans;
}
char str[SIZE];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",&str);
        insert(str);
    }
    for(int i=1;i<=m;i++){
        scanf("%s",&str);
        printf("%d\n",search(str));
    }
    return 0;
}