集训前复习

King

Kruskal


#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define re register
int n,m,ans,fa[5001];
struct bian{
    int from,to,v;
}len[200010];
inline int fd(){
    int s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
bool cmp(bian a,bian b){
    return a.v < b.v;
}
int find(int x){
    if(x == fa[x])
        return x;
    else return fa[x] = find(fa[x]);
}
int main()
{
    freopen("kru.in","r",stdin);
    freopen("kru.out","w",stdout);
    n = fd(),m = fd();
    for(re int i=1;i<=n;++i)
        fa[i] = i;
    for(re int i=1;i<=m;++i)
        len[i].from = fd(),len[i].to = fd(),len[i].v = fd();
    sort(len+1,len+1+m,cmp);
    for(re int i=1;i<=m;++i){
        int fa1 = find(len[i].from),fa2 = find(len[i].to);
        if(fa1 != fa2){
            fa[fa1] = fa2;
            ans += len[i].v;
        } 
    }
    printf("%d",ans);
    return 0;
}

知识兔

Prim


#include<cstring>
#include<cstdio>
using namespace std;
#define re register
#define inf 19260817
const int maxn = 2*1e5+5;
int n,m,now,cnt,ans,head[maxn<<1],dis[maxn],vis[maxn];
struct bian{
    int to,next,v;
}len[maxn<<1];
inline int fd(){
    int s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
void add(int from,int to,int v){
    len[++cnt].v = v;
    len[cnt].to = to;
    len[cnt].next = head[from];
    head[from] = cnt;
}
int main()
{
    n = fd(),m = fd();
    for(re int i=1;i<=m;++i){
        int from = fd(),to = fd(),v = fd();
        add(from,to,v),add(to,from,v);
    }
    for(re int i=1;i<=n;++i)
        dis[i] = inf,vis[i] = 0;
    dis[1] = 0;
    for(re int k=head[1];k;k=len[k].next){
        int to = len[k].to,v = len[k].v;
        dis[to] = min(dis[to],dis[1]+v);
    }
    now = 1;
    for(re int i=1;i<=n-1;++i){
        int minn = inf;
        vis[now] = 1;
        for(re int j=1;j<=n;++j)
            if(!vis[j]&&minn>dis[j])
                minn = dis[j],now = j;
        //遍历n个点,保证每次选不同的点,一共选n-1次.
        ans += minn;
        for(re int j=head[now];j;j=len[j].next){
            int to = len[j].to,v = len[j].v;
            if(vis[to]) continue;
            dis[to] = min(dis[to],v);//dis可理解为加入生成树的最小代价.
        }
    }
    printf("%d",ans);
    //用kru理解,手动模拟贪心选小边再选大边的'hack',感性证明.
    return 0;
}

知识兔

DJ:


#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define e exit(0);
#define re register
#define inf 2147483647
const int maxn = 2*1e5+5;
int n,m,s,cnt,head[maxn],dis[maxn],vis[maxn];
struct bian{
    int to,next,v;
}len[maxn];
inline int fd(){
    int s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
void add(int from,int to,int v){
    len[++cnt].v = v;
    len[cnt].to = to;
    len[cnt].next = head[from];
    head[from] = cnt;
}
void dj(int s){
    for(re int i=1;i<=n;++i)
        dis[i] = inf,vis[i] = 0;
    dis[s] = 0;
    priority_queue<pair<int,int> > q;
    q.push(make_pair(0,s));
    while(q.size()){
        int now = q.top().second;
        q.pop();
        if(vis[now]) continue;
        vis[now] = 1;
        for(re int k=head[now];k;k=len[k].next){
            int to = len[k].to,v = len[k].v;
            if(dis[to] > dis[now]+v){
                dis[to] = dis[now]+v;
                q.push(make_pair(-dis[to],to));
            }
        }
    }
}
int main()
{
    freopen("dj.in","r",stdin);
    freopen("dj.out","w",stdout);
    n = fd(),m = fd(),s = fd();
    for(re int i=1;i<=m;++i){
        int from = fd(),to = fd(),v = fd();
        add(from,to,v);
    }
    dj(s);
    for(re int i=1;i<=n;++i){
        if(i == s) dis[i] = 0;
        printf("%d ",dis[i]);
    }
    return 0;
}

知识兔

Spfa


#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define e exit(0);
#define re register
#define inf 2147483647
const int maxn = 2*1e5+5;
int n,m,s,cnt,head[maxn],dis[maxn],vis[maxn];
struct bian{
    int to,next,v;
}len[maxn];
inline int fd(){
    int s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
void add(int from,int to,int v){
    len[++cnt].v = v;
    len[cnt].to = to;
    len[cnt].next = head[from];
    head[from] = cnt;
}
void dj(int s){
    for(re int i=1;i<=n;++i)
        dis[i] = inf,vis[i] = 0;
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    vis[s] = 1;
    while(q.size()){
        int now = q.front();
        q.pop();
        vis[now] = 0;
        for(re int k=head[now];k;k=len[k].next){
            int to = len[k].to,v = len[k].v;
            if(dis[to] > dis[now]+v){
                dis[to] = dis[now]+v;
                if(!vis[to]){
                    q.push(to);
                    vis[to] = 1;
                }
            }
        }
    }
}
int main()
{
    n = fd(),m = fd(),s = fd();
    for(re int i=1;i<=m;++i){
        int from = fd(),to = fd(),v = fd();
        add(from,to,v);
    }
    dj(s);
    for(re int i=1;i<=n;++i){
        if(i == s) dis[i] = 0;
        printf("%d ",dis[i]);
    }
    return 0;
}

知识兔

Trie:


#include<cstring>
#include<cstdio>
using namespace std;
#define re register
const int maxn = 10000*51*26+5;
char a[60];
int n,m,cnt,root,trie[maxn][27],vis[maxn],check[maxn];
inline int fd(){
    int s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
void insert(char a[]){
    int lenth = strlen(a);
    root = 0;
    for(re int i=0;i<lenth;++i){
        int x = a[i]-'a';
        if(!trie[root][x])
            trie[root][x] = ++cnt;
        root = trie[root][x];
    }
    vis[root] = 1;
}
int find(char a[]){
    int lenth = strlen(a);
    root = 0;
    for(re int i=0;i<lenth;++i){
        int x = a[i]-'a';
        if(!trie[root][x])
            return 1;
        root = trie[root][x];
    }
    if(!vis[root])
        return 1;
    if(check[root])
        return 2;
    check[root] = 1;
    return 3;
}
int main()
{
    freopen("trie.in","r",stdin);
    freopen("trie.out","w",stdout);
    n = fd();
    for(re int i=1;i<=n;++i){
        scanf("%s",a);
        insert(a);
    }
    m = fd();
    for(re int i=1;i<=m;++i){
        scanf("%s",a);
        int flag = find(a);
        if(flag == 1)
            printf("WRONG\n");
        if(flag == 2)
            printf("REPEAT\n");
        if(flag == 3)
            printf("OK\n");
    }
    return 0;
}

知识兔

LCA( bz )


#include<cstring>
#include<cstdio>
using namespace std;
#define re register
const int maxn = 5*1e5+5;
int n,m,s,cnt,head[maxn],h[maxn],fa[maxn],bz[maxn][24];
struct bian{
    int to,next,v;
}len[maxn<<1];
inline int fd(){
    int s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
void add(int from,int to){
    len[++cnt].to = to;
    len[cnt].next = head[from];
    head[from] = cnt;
}
void dfs(int x){
    for(re int k=head[x];k;k=len[k].next){
        int to = len[k].to;
        if(!h[to]){
            fa[to] = x;
            h[to] = h[x]+1;
            dfs(to);
        }
    }
}
void makebz(){
    for(re int i=1;i<=n;++i)
        bz[i][0] = fa[i];
    for(re int j=1;j<=19;++j)
        for(re int i=1;i<=n;++i)
            bz[i][j] = bz[bz[i][j-1]][j-1];
}
int LCA(int x,int y){
    if(h[x] < h[y])
        swap(x,y);
    for(re int j=19;j>=0;--j)
        if(h[bz[x][j]] >= h[y])
            x = bz[x][j];
    if(x == y)
        return x;
    for(re int j=19;j>=0;--j)
        if(bz[x][j] != bz[y][j])
            x = bz[x][j],y = bz[y][j];
    return fa[x];
}
int main()
{
    freopen("Lca.in","r",stdin);
    freopen("Lca.out","w",stdout);
    n = fd(),m = fd(),s = fd();
    for(re int i=1;i<=n-1;++i){
        int from = fd(),to = fd();
        add(from,to),add(to,from);
    }
    fa[s] = s,h[s] = 1;
    dfs(s);
    makebz();
    for(re int i=1;i<=m;++i){
        int from = fd(),to =fd();
        printf("%d\n",LCA(from,to));
    }
    return 0;
}

知识兔

Treearray:


#include<cstring>
#include<cstdio>
using namespace std;
#define re register
const int maxn = 5*1e5+5;
int n,m,tree[maxn];
inline int fd(){
    int s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
int lowbit(int x){
    return x&(-x);
}
void add(int id,int v){
    while(id<=n){
        tree[id] += v;
        id += lowbit(id);
    }
}
long long ask(int x){
    long long sum = 0;
    while(x){
        sum += tree[x];
        x -= lowbit(x);
    }
    return sum;
}
int main()
{
    freopen("Treearray.in","r",stdin);
    freopen("Treearray.out","w",stdout);
    n = fd(),m = fd();
    for(re int i=1;i<=n;++i){
        int num = fd();
        add(i,num);
    }
    for(re int i=1;i<=m;++i){
        int flag = fd(),x = fd(),y = fd();
        if(flag == 1)
            add(x,y);
        else if(flag == 2)
            printf("%lld\n",ask(y)-ask(x-1));
    }
    return 0;
}

知识兔

Treearraycf:


#include<cstring>
#include<cstdio>
using namespace std;
#define re register
const int maxn = 5*1e5+5;
int n,m,tree[maxn],val[maxn];
inline int fd(){
    int s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
int lowbit(int x){
    return x&(-x);
}
void add(int x,int v){
    while(x<=n){
        tree[x] += v;
        x += lowbit(x);
    }
}
long long ask(int x){
    long long sum = 0;
    while(x){
        sum += tree[x];
        x -= lowbit(x);
    }
    return sum;
}
int main()
{
    freopen("Treearraycf.in","r",stdin);
    freopen("Treearraycf.out","w",stdout);
    n = fd(),m = fd();
    for(re int i=1;i<=n;++i)
        val[i] = fd();
    for(re int i=1;i<=n;++i)
        add(i,val[i]-val[i-1]);
    for(re int i=1;i<=m;++i){
        int flag = fd();
        if(flag == 1){
            int x = fd(),y = fd(),v = fd();
            add(x,v),add(y+1,-v);//cf理解.
        }
        else if(flag == 2){
            int x = fd();
            printf("%lld\n",ask(x));
        }
    }
    return 0;
}

知识兔

RMQ:


#include<cstring>
#include<cstdio>
using namespace std;
#define re register
const int maxn = 1e6+10;
int n,m,f[maxn][24],logn[maxn];
inline int fd(){
    int s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
int main()
{
    freopen("RMQ.in","r",stdin);
    freopen("RMQ.out","w",stdout);
    n = fd(),m = fd();
    logn[0] = -1;
    for(re int i=1;i<=n;++i)
        f[i][0] = fd(),logn[i] = logn[i>>1]+1;
    for(re int j=1;j<=19;++j)
        for(re int i=1;i+(1<<j)-1<=n;++i)
            f[i][j] = max(f[i][j-1],f[i+(1<<j-1)][j-1]);
    //f[i+(i<<j-1)][j-1];
    for(re int i=1;i<=m;++i){
        int L = fd(),R = fd();
        int id = logn[R-L+1];
        printf("%d\n",max(f[L][id],f[R-(1<<id)+1][id]));
    }
    //f[R-(1<<id)+1];
    return 0;
}

知识兔

Invfm:


#include<cstring>
#include<cstdio>
using namespace std;
#define re register
int n,mod;
inline int fd(){
    int s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
int qsm(int x,int y){
    int base = 1;
    while(y){
        if(y&1) base = (base%mod*x%mod)%mod;
        x = (x%mod*x%mod)%mod;
        y>>=1;
    }
    return base;
}
int main()
{
    freopen("Ivfm.in","r",stdin);
    freopen("Ivfm.out","w",stdout);
    n = fd(),mod = fd();
    for(re int i=1;i<=n;++i){
        int ans = qsm(i,mod-2);
        ans = (ans%mod+mod)%mod;
        printf("%d\n",ans);
    }
    return 0;
}

知识兔

Invexgcd:


#include<cstring>
#include<cstdio>
using namespace std;
#define re register
int n,x1,y1,x2,y2,mod;
inline int fd(){
    int s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
void exgcd(int a,int b){
    if(!b){
        x1 = 1;
        y1 = 0;
        return;
    }
    exgcd(b,a%b);
    x2 = x1,y2 = y1;
    x1 = y2;
    y1 = x2 - (a/b)*y2;
}
int main()
{
    freopen("Invexgcd.in","r",stdin);
    freopen("Invexgcd.out","w",stdout);
    n = fd(),mod = fd();
    for(re int i=1;i<=n;++i){
        exgcd(i,mod);
        printf("%d\n",(x1%mod+mod)%mod);
    }
    return 0;
}

知识兔

Invdt:


#include<cstring>
#include<cstdio>
using namespace std;
#define re register
const int maxn = 3*1e6+10;
int n,mod,inv[maxn];
inline int fd(){
    int s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
int main()
{
    freopen("Invdt.in","r",stdin);
    freopen("Invdt.out","w",stdout);
    n = fd(),mod = fd();
    inv[1] = 1;
    for(re int i=2;i<=n;++i)
        inv[i] = ((1ll*(-inv[mod%i])*(mod/i))%mod+mod)%mod;
    for(re int i=1;i<=n;++i)
        printf("%d\n",inv[i]);
    return 0;
}

知识兔

Tyfc:


#include<cstring>
#include<cstdio>
using namespace std;
#define re register
int a,b,x1,x2,y1,y2;
inline int fd(){
    int s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
void exgcd(int a,int b){
    if(!b){
        x1 = 1;
        y1 = 0;
        return;
    }
    exgcd(b,a%b);
    x2 = x1,y2 = y1;
    x1 = y2;
    y1 = x2 - a/b*y2;
}
int main()
{
    freopen("Tyfc.in","r",stdin);
    freopen("Tyfc.out","w",stdout);
    a = fd(),b = fd();
    exgcd(a,b);
    x1 = (x1%b+b)%b;
    printf("%d",x1);
    return 0;
}

知识兔

bdfc:


#include<cstring>
#include<cstdio>
using namespace std;
#define e exit(0)
#define re register
int a,b,c,g,x1,y1,x2,y2,x,y;
inline int fd(){
    int s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
int gcd(int x,int y){
    if(!y)
        return x;
    else return gcd(y,x%y);
}
void exgcd(int a,int b){
    if(!b){
        x1 = 1;
        y1 = 0;
        return;
    }
    exgcd(b,a%b);
    x2 = x1,y2 = y1;
    x1 = y2;
    y1 = x2 - a/b*y2;
}
int main()
{
    freopen("bdfc.in","r",stdin);
    freopen("bdfc.out","w",stdout);
    a = fd(),b = fd(),c = fd();
    g = gcd(a,b);
    exgcd(a,b);
    x1 = x1*(c/g),y1 = y1*(c/g);
    for(re int k = 0;k<=100;++k){
        x = x1 + k*(b/g);
        y = y1 - k*(a/g);
        printf("%d %d\n",x,y);
    }
    return 0;
}

知识兔

CRT:


#include<cstring>
#include<cstdio>
using namespace std;
#define e exit(0)
#define re register
#define LL long long
const int maxn = 1010;
long long n,M=1,k,x1,y1,x2,y2,ans,a[maxn],b[maxn];
inline long long fd(){
    long long s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
void exgcd(LL a,LL b){
    if(!b){
        x1 = 1;
        y1 = 0;
        return;
    }
    exgcd(b,a%b);
    x2 = x1,y2 = y1;
    x1 = y2;
    y1 = x2-a/b*y2;
}
int main()
{
    freopen("CRT.in","r",stdin);
    freopen("CRT.out","w",stdout);
    n = fd();
    for(re LL i=1;i<=n;++i){
        a[i] = fd(),b[i] = fd();
        M*=a[i];
    }
    for(re LL i=1;i<=n;++i){
        LL mi = M/a[i];
        exgcd(mi,a[i]);
        k = x1;
        ans += k*mi*b[i];
    }
    ans = ((ans%M)+M)%M;
    printf("%lld",ans);
    //注意最后模数为M.
    return 0;
}

知识兔

jzqsm:


#include<cstring>
#include<cstdio>
using namespace std;
#define e exit(0)
#define re register
#define LL long long
const long long mod = 1e9+7;
long long n,k;
struct jz{
    long long a[101][101];
    jz(){memset(a,0,sizeof(a));}
    inline jz operator*(const jz & b)const{
        jz p;
        for(re LL k=1;k<=n;++k)
            for(re LL i=1;i<=n;++i)
                for(re LL j=1;j<=n;++j)
                    p.a[i][j] = (p.a[i][j]%mod+(1ll*a[i][k]%mod*b.a[k][j]%mod)%mod)%mod;
        return p;
    }
};
inline long long fd(){
    long long s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
jz qsm(jz x,LL y){
    jz base;
    for(re LL i=1;i<=n;++i)
        base.a[i][i] = 1;
    while(y){
        if(y&1) base = base*x;
        x = x*x;
        y>>=1;
    }
    return base;
}
int main()
{
    freopen("jzqsm.in","r",stdin);
    freopen("jzqsm.out","w",stdout);
    n = fd(),k = fd();
    jz ori;
    for(re LL i=1;i<=n;++i)
        for(re LL j=1;j<=n;++j)
            ori.a[i][j] = fd();
    jz p = qsm(ori,k);
    for(re LL i=1;i<=n;++i){
        for(re LL j=1;j<=n;++j)
            printf("%lld ",p.a[i][j]);
        printf("\n");
    }
    return 0;
}

知识兔

计算机

2022年1月19日

集训前复习

热门标签

最新文章