2017-10-6 清北刷题冲刺班p.m

1.数组异或

2017-10-6 清北刷题冲刺班p.m-LMLPHP

#include<iostream>

#include<cstdio>

#define maxn 100010

#define mod 1000000007

using namespace std;

int n,a[maxn],b[maxn],c[maxn];

int main(){

    freopen("xorarray.in","r",stdin);freopen("xorarray.out","w",stdout);

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    for(int i=;i<=n;i++)scanf("%d",&b[i]);

    c[]=a[]^b[];

    for(int i=;i<=n;i++){

        c[i]=c[i-];

        for(int j=;j<i;j++){

            c[i]+=a[i]^b[j];

            if(c[i]>=mod)c[i]-=mod;

        }

        for(int j=;j<i;j++){

            c[i]+=a[j]^b[i];

            if(c[i]>=mod)c[i]-=mod;

        }

        c[i]+=a[i]^b[i];

        if(c[i]>=mod)c[i]-=mod;

    }

    for(int i=;i<=n;i++)printf("%d ",c[i]);

    fclose(stdin);fclose(stdout);

    return ;

}

60分暴力

/*

    累计所有数二进制下的每一位0或1的个数

    又因为是xor，所以a[j][0]*b[j][1]+a[j][1]*b[j][0]

*/

#include<iostream>

#include<cstdio>

#define maxn 100010

#define mod 1000000007

using namespace std;

int n,A[maxn],B[maxn];

int a[][],b[][],C[maxn];

int main(){

    //freopen("Cola.txt","r",stdin);

    freopen("xorarray.in","r",stdin);freopen("xorarray.out","w",stdout);

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&A[i]);

    for(int i=;i<=n;i++)scanf("%d",&B[i]);

    for(int i=;i<=n;i++){

        for(int j=;j<=;j++){

            a[j][(A[i]>>j)&]++;

            b[j][(B[i]>>j)&]++;

            long long c=(1LL*a[j][]*b[j][]%mod+1LL*a[j][]*b[j][]%mod)%mod;

            c=c*(<<j)%mod;

            C[i]=(C[i]+c)%mod;

        }

    }

    for(int i=;i<=n;i++)printf("%d ",C[i]);

    return ;

}

100分

2.侦探游戏（最小生成树，期望）

2017-10-6 清北刷题冲刺班p.m-LMLPHP

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#define maxn 20010

using namespace std;

int n,m,num,head[maxn],dis[maxn],D[maxn];

double ans,w;

bool v[maxn];

struct node{

    int to,pre,v;

}e[*];

void Insert(int from,int to,int v){

    e[++num].to=to;

    e[num].v=v;

    e[num].pre=head[from];

    head[from]=num;

}

void spfa(int s1,int s2){

    queue<int>q;

    memset(v,,sizeof(v));memset(dis,/,sizeof(dis));

    v[s1]=;v[s2]=;dis[s1]=;dis[s2]=;

    if(!v[])v[]=,dis[]=,q.push();

    q.push(s1);q.push(s2);

    while(!q.empty()){

        int now=q.front();q.pop();v[now]=;

        for(int i=head[now];i;i=e[i].pre){

            int to=e[i].to;

            if(dis[to]>dis[now]+e[i].v){

                dis[to]=dis[now]+e[i].v;

                if(!v[to]){

                    v[to]=;

                    q.push(to);

                }

            }

        }

    }

    for(int i=;i<=n;i++){

        ans+=(double)dis[i]*w;

    }

    int k=min(D[s1],D[s2]);

    ans+=(double)k*w;

}

void SPFA(int s){

    queue<int>q;

    memset(v,,sizeof(v));

    memset(D,/,sizeof(D));

    v[s]=;D[s]=;

    q.push(s);

    while(!q.empty()){

        int now=q.front();q.pop();v[now]=;

        for(int i=head[now];i;i=e[i].pre){

            int to=e[i].to;

            if(D[to]>D[now]+e[i].v){

                D[to]=D[now]+e[i].v;

                if(!v[to]){

                    v[to]=;

                    q.push(to);

                }

            }

        }

    }

}

int main(){

    //freopen("Cola.txt","r",stdin);

    freopen("detective.in","r",stdin);freopen("detective.out","w",stdout);

    scanf("%d%d",&n,&m);

    w=(double)(n*(n-))/2.0;

    w=1.0/w;

    int x,y,z;

    for(int i=;i<=m;i++){

        scanf("%d%d%d",&x,&y,&z);

        Insert(x,y,z);Insert(y,x,z);

    }

    SPFA();

    for(int i=;i<=n;i++){

        for(int j=;j<i;j++){

            spfa(i,j);

        }

    }

    printf("%.2lf",ans);

    /*int sz=sizeof(head)+sizeof(e);

    cout<<sz/1048576;*/

}

0分暴力

/*

    暴力算法：

    求一遍最小生成树，枚举两个点，想象将两个点连上权值为0的边，然后进行倍增，求两点之间最长的一条边，删除这条边，当前树上所有边权和即为此时的花费，最后除以n*(n-1)

*/

O(n^2)暴力算法

/*

    枚举哪一条边可以删掉，由于克鲁斯卡尔最小生成树边是按从大到小顺序选入的，所以当前讨论的这条边一定是图上最大的边，而且既然他是最小生成树的一条边，他所连接的两个集合一定是两个树，将两棵树大小进行乘法原理，累计答案 （我在胡言乱语什么）

*/

#include<iostream>

#include<cstdio>

#include<algorithm>

#define maxn 20010

#define maxm 100010

using namespace std;

struct node{

    int from,to,v;

    bool operator < (const node a)const{

        return v<a.v;

    }

}e[maxm];

int n,m,fa[maxn],s[maxn];

unsigned long long sum,cnt;

int find(int a){

    if(a==fa[a])return a;

    return fa[a]=find(fa[a]);

}

int main(){

    //freopen("Cola.txt","r",stdin);

    freopen("detective.in","r",stdin);freopen("detective.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)fa[i]=i,s[i]=;

    for(int i=;i<=m;i++)scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].v);

    sort(e+,e+m+);

    for(int i=;i<=m;i++){

        int x=find(e[i].from),y=find(e[i].to);

        if(x==y)continue;

        cnt+=1ULL*s[x]*s[y]*e[i].v;

        sum+=e[i].v;

        fa[y]=x;s[x]+=s[y];

    }

    double ans=sum-cnt/((n*(n-))/2.0);

    //double ans = sum - 2.0 * cnt / n / (n - 1);

    printf("%.2lf",ans);

    return ;

}

100分最小生成树

3.棋盘迷宫（分治，搜索）

2017-10-6 清北刷题冲刺班p.m-LMLPHP

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int n,m,x1,x2,y1,y2,e[][]={{,},{,}};

char map[][];

bool vis[];

int f(int x,int y){

    return (x-)*m+y;

}

bool BFS(){

    queue<int>q;

    memset(vis,,sizeof(vis));

    vis[f(x1,y1)]=;

    q.push(f(x1,y1));

    while(!q.empty()){

        int now=q.front();q.pop();

        int x=(now-)/m+,y=now-(x-)*m;

        for(int i=;i<;i++){

            int xx=x+e[i][],yy=y+e[i][];

            int w=f(xx,yy);

            if(xx==x2&&yy==y2)return ;

            if(xx>=&&xx<=n&&yy>=&&yy<=n&&xx<=x2&&yy<=y2&&!vis[w]&&map[xx][yy]=='.'){

                vis[w]=;

                q.push(w);

            }

        }

    }

    return ;

}

int main(){

    //freopen("Cola.txt","r",stdin);

    freopen("boardgame.in","r",stdin);freopen("boardgame.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%s",map[i]+);

    int q;

    scanf("%d",&q);

    while(q--){

        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

        if(x2<x1||y2<y1){

            printf("No\n");

            continue;

        }

        if(x1==x2){

            bool flag=;

            for(int i=y1;i<=y2;i++){

                if(map[x1][i]=='#'){

                    flag=;

                    printf("No\n");break;

                }

            }

            if(!flag)printf("Yes\n");

            continue;

        }

        if(y1==y2){

            bool flag=;

            for(int i=x1;i<=x2;i++){

                if(map[i][y1]=='#'){

                    flag=;

                    printf("No\n");break;

                }

            }

            if(!flag)printf("Yes\n");

            continue;

        }

        int fl=BFS();

        if(fl)printf("Yes\n");

        else printf("No\n");

    }

    fclose(stdin);fclose(stdout);

    return ;

}

20分暴力

/*

    考试的时候忘记判断起点和终点是否合法了

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int n,m,x1,x2,y1,y2,e[][]={{,},{,}};

char map[][];

bool vis[];

int f(int x,int y){

    return (x-)*m+y;

}

bool BFS(){

    queue<int>q;

    memset(vis,,sizeof(vis));

    vis[f(x1,y1)]=;

    q.push(f(x1,y1));

    while(!q.empty()){

        int now=q.front();q.pop();

        int x=(now-)/m+,y=now-(x-)*m;

        for(int i=;i<;i++){

            int xx=x+e[i][],yy=y+e[i][];

            int w=f(xx,yy);

            if(xx>=&&xx<=n&&yy>=&&yy<=n&&xx<=x2&&yy<=y2&&!vis[w]&&map[xx][yy]=='.'){

                if(xx==x2&&yy==y2)return ;

                vis[w]=;

                q.push(w);

            }

        }

    }

    return ;

}

int main(){

    //freopen("Cola.txt","r",stdin);

    freopen("boardgame.in","r",stdin);freopen("boardgame.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%s",map[i]+);

    int q;

    scanf("%d",&q);

    while(q--){

        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

        if(x2<x1||y2<y1){

            printf("No\n");

            continue;

        }

        if(x1==x2){

            bool flag=;

            for(int i=y1;i<=y2;i++){

                if(map[x1][i]=='#'){

                    flag=;

                    printf("No\n");break;

                }

            }

            if(!flag)printf("Yes\n");

            continue;

        }

        if(y1==y2){

            bool flag=;

            for(int i=x1;i<=x2;i++){

                if(map[i][y1]=='#'){

                    flag=;

                    printf("No\n");break;

                }

            }

            if(!flag)printf("Yes\n");

            continue;

        }

        if(map[x1][y1]=='#'){

            printf("No\n");

            continue;

        }

        int fl=BFS();

        if(fl)printf("Yes\n");

        else printf("No\n");

    }

    fclose(stdin);fclose(stdout);

    return ;

}

40分暴力