C++

「置顶文章」代码仓库 Codes Repo

code’s Repo

Luogu 2661 code:

#include <iostream>
using namespace std;
int a[200005],ru[200005],tmp,n,ans=99999999;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        ru[a[i]]++;
    }
    for(int i=1;i<=n;i++){
        if(!ru[i]){
            ru[i]=-1;
            //for(int j=a[i];ru[j]==1 && ru[j]!=0;j=a[j]){
            for(int j=a[i];--ru[j]==0;j=a[j]){
                ru[j]=-1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(ru[i]!=-1){
            tmp=0;
            for(int j=i;j!=i||!tmp;j=a[j]){
                tmp++;
                ru[j]=-1;
            }
            ans=min(ans,tmp);
        }
    }
    printf("%d\n",ans); 
    return 0;
}

Luogu 1351 code:

/*
NOIp - 2014 联合权值
2017/10/29
*/
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
#define N 2005
#define mod 10007

int n,w[N],tot,head[N],nextt[N*2],to[N*2],sum;
int max1,max2,ans1,ans2;

void addedge(int a,int b){
    to[++tot]=b;  
    nextt[tot]=head[a];
    head[a]=tot;
}

int main(){
    scanf("%d",&n);

    for(int i=1;i<=n-1;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }

    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }

    for(int i=1;i<=n;i++){
        max1=max2=-1; //max1 max2 最大 次大
        sum=0;
        for(int j=head[i];j;j=nextt[j]){
            int temp=w[to[j]];
            sum+=temp;//sum所有儿子的联合权值之和
            sum%=mod;
            if(temp>max1){
                max2=max1;
                max1=temp;
            }
            else if(temp>max2)
                max2=temp;
        }
        ans2=max(ans2,max1*max2);
        for(int j=head[i];j;j=nextt[j]){
            ans1+=(w[to[j]]*(sum-w[to[j]]))%mod;
            ans1%=mod;
        }
    }

    ans1=(ans1+mod)%mod;
    cout<<ans2<<" "<<ans1<<endl;
    return 0;
}
/*

Sample Input
5
1 2
2 3
3 4
4 5
1 5 2 3 10

Sample Output
20 74

*/

快速幂:

#include <iostream>
#define mod 10000007
using namespace std;
int pow(int a,int n){
    if(n==0) return 1;
    long long result=1;
    int t=a;
    while(n){
        if(n & 1) result = (result * t) % mod;
        t = (t * t) % mod;
        n >>= 1;
    }
    return result;
}
int main(){
    int x,y;
    while(1){
        cin>>x>>y;
        cout<<pow(x,y)<<endl;
    }
    return 0;
}

Luogu 1078 Code:

/*
这道题写的可真是666了,刚开始读错题以为是暴搜,后来才发现是文化之间排斥而不是国家对于文化的排斥,可能出后者的话就不是普及题了,然后想到最短路,其实就是最短路,可是我在写的时候竟然机(nao)智(can)的发现走过的国家不能再走了这个条件,然后我就改了一下最短路,结果40分,考虑再三,最短路要是重复走某个国家不就不是最短路了么,那我为什么要改最短路呢,然后AC了。我想说的是,要用好算法,一定要理解明白了,败想我那样瞎改。
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#define N 105
#define INF 9999999
using namespace std;
int n,k,m,s,t;
int c[N],map[N][N],a[N][N],dis[N],vis[N];
queue<int>q;
int main(){
    cin>>n>>k>>m>>s>>t;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=k;i++){
        for(int j=1;j<=k;j++){
            cin>>a[i][j];//a i j 代表第i个文化排斥第j个文化
        }
    }
    for(int i=1;i<=m;i++){
        int x,y,v;
        cin>>x>>y>>v;
        map[x][y]=map[y][x]=v;
        if(a[c[x]][c[y]]==1) map[y][x]=INF;
        if(a[c[y]][c[x]]==1) map[x][y]=INF;
    }
    for(int i=1;i<=n;i++) dis[i]=9999999;
    vis[s]=1;
    dis[s]=0;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=1;i<=n;i++){
            if(map[x][i]!=0 && dis[x]+map[x][i]<dis[i]){
                dis[i]=dis[x]+map[x][i];
                if(!vis[i]){
                    vis[i]=1;
                    q.push(i);
                }
            }
        }
        vis[x]=0;
    }
    if(dis[t]!=INF)    cout<<dis[t]<<endl;
    else cout<<-1<<endl;
    return 0;
}

Luogu 1072 hankson 100%数据版 未完成 code:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define N 1000005
using namespace std;
int n,a0,a1,b0,b1,numa0,numa1,numb0,numb1;
int aa0[N][2],aa1[N][2],bb0[N][2],bb1[N][2];//fac表
void factorb1(){
    numb1=0;
    for(int i=2;i*i<=b1;i++){
        if(b1%i==0){
            bb1[++numb1][0]=i;
            bb1[numb1][1]=0;
            do{
                bb1[numb1][1]++;
                b1/=i;
            }while(b1%i==0);
        }
    }
    if(b1>1){
        bb1[++numb1][0]=b1;
        bb1[numb1][1]=1;
    }
}
void factorb0(){
    numb0=0;
    for(int i=2;i*i<=b0;i++){
        if(b0%i==0){
            bb0[++numb0][0]=i;
            bb0[numb0][1]=0;
            do{
                bb0[numb0][1]++;
                b0/=i;
            }while(b0%i==0);
        }
    }
    if(b0>1){
        bb0[++numb0][0]=b0;
        bb0[numb0][1]=1;
    }
}
void factora1(){
    numa1=0;
    for(int i=2;i*i<=a1;i++){
        if(a1%i==0){
            aa1[++numa1][0]=i;
            aa1[numa1][1]=0;
            do{
                aa1[numa1][1]++;
                a1/=i;
            }while(a1%i==0);
        }
    }
    if(a1>1){
        aa1[++numa1][0]=a1;
        aa1[numa1][1]=1;
    }
}
void factora0(){
    numa0=0;
    for(int i=2;i*i<=a0;i++){
        if(a0%i==0){
            aa0[++numa0][0]=i;
            aa0[numa0][1]=0;
            do{
                aa0[numa0][1]++;
                a0/=i;
            }while(a0%i==0);
        }
    }
    if(a0>1){
        aa0[++numa0][0]=a0;
        aa0[numa0][1]=1;
    }
}
//反正没有码长限制 可劲霍霍...
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a0>>a1>>b0>>b1;
        factora1();
        factora0();
        factorb1();
        factorb0();
        for(int i=1;i<=numa0;i++){
            cout<<aa0[i][0]<<" ";
        }
    }
    return 0;
}

SPFA

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define N 1005
using namespace std;
struct edge{
    int to,v;
}ee[N];
queue<int>q;
vector<edge>G[N];
int e,n,f,s,vis[N],dis[N];
edge t;
void addedge(){G[f].push_back(t);}
void SPFA(){
    q.push(s);
    vis[s]=1;
    dis[s]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<G[x].size();i++){
            int next=G[x][i].to;
            if(dis[x]+G[x][i].v<dis[next]){
                dis[next]=dis[x]+G[x][i].v;
                if(!vis[next]){
                    q.push(next);
                    vis[next]=1;
                }
            }
        }
        vis[x]=0;
    }
}
int main(){
    cin>>n>>e;
    for(int i=1;i<=e;i++){
        cin>>f>>t.to>>t.v;
        addedge();
        int aa;
        aa=t.to;
        t.to=f;
        f=aa;
        addedge();
    }
    memset(dis,127,sizeof(dis));
    cin>>s;
    SPFA();
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
    }
    return 0;
}
分享到