2017-9-2 NOIP模拟赛

“与”

（and.pas/.c/.cpp）

时间限制：1s；空间限制64MB

题目描述：

给你一个长度为n的序列A，请你求出一对Ai，Aj（1<=i<j<=n）使Ai“与”Aj最大。

Ps：“与”表示位运算and，在c++中表示为&。

输入描述：

第一行为n。接下来n行，一行一个数字表示Ai。

输出描述：

输出最大的Ai“与”Aj的结果。

样例输入：

样例输出：

样例解释：

8 and 10 = 8

8 and 2 = 0

10 and 2 = 2

数据范围：

20%的数据保证n<=5000

100%的数据保证 n<=3*10^5，0<=Ai<=10^9

/*

    10^9内的二进制最多只有30位，所以我们可以从高到低枚举每一位

    如果发现有两个或两个以上的数这位上有1，就说明答案的这一位一定有1，方法比较贪心，正确性很明显

*/

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define maxn 300010

int a[maxn],n,ans,len;

bool vis[maxn];

int main(){

    freopen("and.in","r",stdin);

    freopen("and.out","w",stdout);

    scanf("%d",&n);

    int x;

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

    for(int i=;i>=;i--){

        int flag=;

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

            if((a[j]&(<<(i-)))&&!vis[j])flag++;

        if(flag>=){

            ans+=(<<(i-));

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

                if(!(a[j]&(<<(i-))))vis[j]=;

        }

    }

    printf("%d",ans);

}

100分

小象涂色

（elephant.pas/.c/.cpp）

时间限制：1s，空间限制128MB

题目描述：

小象喜欢为箱子涂色。小象现在有c种颜色，编号为0~c-1；还有n个箱子，编号为1~n，最开始每个箱子的颜色为1。小象涂色时喜欢遵循灵感：它将箱子按编号排成一排，每次涂色时，它随机选择[L，R]这个区间里的一些箱子（不选看做选0个），为之涂上随机一种颜色。若一个颜色为a的箱子被涂上b色，那么这个箱子的颜色会变成（a*b）mod c。请问在k次涂色后，所有箱子颜色的编号和期望为多少？

输入描述：

第一行为T，表示有T组测试数据。

对于每组数据，第一行为三个整数n,c,k。

接下来k行，每行两个整数Li，Ri，表示第i个操作的L和R。

输出描述：

对于每组测试数据，输出所有箱子颜色编号和的期望值，结果保留9位小数。

样例输入：

3 2 2

2 2

1 3

1 3 1

1 1

5 2 2

3 4

2 4

样例输出：

2.062500000

1.000000000

3.875000000

数据范围：

40%的数据1 <= T <= 5，1 <= n, k <= 15，2 <= c <= 20

100%的数据满足1 <= T <= 10，1 <= n, k <= 50，2 <= c <= 100，1 <= Li <= Ri <= n

/*

    一道有关期望的dp。首先可知每个操作中，一个物品会被染色的概率为1/2，用某种颜色染色的概率为1/c。

    40分的方程是用f[i][j][k]表示第i个物品在j次操作次数后颜色变为k的概率，时间复杂度大概是O(T*N*K*c^2)

    60分要考虑到所有物品具有相似性，即n个物品本质是相同的，所以不用枚举物品f[i][j]表示一个物品操作i次颜色变为j的概率。满足：

    f[i+1][j]+=f[i][j]*(1/2)        f[i+1][(j*b)%c]+=f[i][j]*[(1/2)*(1/c)]

    初始值f[0][1]=1，答案就是∑f[i][j]*j  (i表示该箱子的操作次数,0 <= j<c)。复杂度O（T*K*c^2）

*/

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int T,n,c,K,mc,cnt[];

double dp[][],ans;

int main(){

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

    freopen("elephant.in","r",stdin);

    freopen("elephant.out","w",stdout);

    scanf("%d",&T);

    while(T--){

        memset(dp,,sizeof(dp));

        memset(cnt,,sizeof(cnt));

        ans=;mc=;

        scanf("%d%d%d",&n,&c,&K);

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

            int l,r;

            scanf("%d%d",&l,&r);

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

                cnt[j]++;

                mc=max(cnt[j],mc);

            }

        }

        dp[][]=;

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

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

                dp[i+][j]+=dp[i][j]/;

                for(int k=;k<c;k++){

                    dp[i+][(j*k)%c]+=dp[i][j]/(*c);

                }

            }

        }

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

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

                ans+=dp[cnt[i]][j]*j;//概率乘以收益

            }

        }

        printf("%.9lf\n",ans);

    }

    return ;

}

100分概率dp

行动！行动！

（move.pas/.c/.cpp）

时间限制：1s；空间限制：128MB

题目描述：

大CX国的大兵Jack接到一项任务：敌方占领了n座城市（编号0~n-1），有些城市之间有双向道路相连。Jack需要空降在一个城市S，并徒步沿那些道路移动到T城市。虽然Jack每从一个城市到另一个城市都会受伤流血，但大CX国毕竟有着“过硬”的军事实力，它不仅已经算出Jack在每条道路上会损失的血量，还给Jack提供了k个“简易急救包”，一个包可以让Jack在一条路上的流血量为0。Jack想知道自己最少会流多少血，不过他毕竟是无脑的大兵，需要你的帮助。

输入描述：

第一行有三个整数n,m,k，分别表示城市数，道路数和急救包个数。

第二行有两个整数，S,T。分别表示Jack空降到的城市编号和最终要到的城市。

接下来有m行，每行三个整数a,b,c，表示城市a与城市b之间有一条双向道路。

输出描述：

Jack最少要流的血量。

样例输入：

5 6 1

0 3

3 4 5

0 1 5

0 2 100

1 2 5

2 4 5

2 4 3

样例输出：

数据范围：

对于30%的数据,2<=n<=50,1<=m<=300,k=0;

对于50%的数据,2<=n<=600,1<=m<=6000,0<=k<=1;

对于100%的数据,2<=n<=10000,1<=m<=50000,0<=k<=10.

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxn 10010

int n,m,k,s,t,head[maxn],num,cnt,a[maxn];

long long path[maxn];

bool vis[maxn];

long long ans=;

struct node{

    int to,pre;

    long long v;

}e[*];

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

    e[++num].to=to;

    e[num].v=v;

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

    head[from]=num;

}

void check(long long sum){

    memset(a,,sizeof(a));

    for(int i=;i<=cnt;i++)a[i]=path[i];

    sort(a+,a+cnt+);

    for(int i=cnt,j=;j<=k;i--,j++)sum-=a[i];

    ans=min(ans,sum);

}

void dfs(int now,long long sum){

    if(now==t){

        check(sum);

        return;

    }

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

        int to=e[i].to;

        if(vis[to])continue;

        vis[to]=;

        cnt++;

        path[cnt]=e[i].v;

        dfs(to,sum+e[i].v);

        vis[to]=;

        cnt--;

    }

}

void spfa(){

    queue<int>q;

    memset(path,,sizeof(path));

    q.push(s);vis[s]=;path[s]=;

    while(!q.empty()){

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

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

            int to=e[i].to;

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

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

                if(!vis[to]){

                    vis[to]=;

                    q.push(to);

                }

            }

        }

    }

    cout<<path[t];

}

long long qread(){

    long long i=;

    char ch=getchar();

    while(ch<''||ch>''){ch=getchar();}

    while(ch<=''&&ch>=''){i=i*+ch-'';ch=getchar();}

    return i;

}

int main(){

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

    freopen("move.in","r",stdin);

    freopen("move.out","w",stdout);

    scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);

    int x,y,z;

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

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

        z=qread();

        Insert(x,y,z);

        Insert(y,x,z);

    }

    if(k==){

        spfa();

        return ;

    }

    vis[s]=;

    dfs(s,);

    cout<<ans;

    return ;

}

40分暴力

/*

    因为k<=10所以拓展点的时候直接x+10+y了

    但其实k==10的话这样拓展会重复...

    幸好只有一个点...

    谨慎谨慎..

    还有就是 这题这样做的话卡SPFA

    要用dij

*/

#include<iostream>

#include<cstdio>

#include<vector>

#include<cstring>

#include<queue>

#define pa pair<int,int>

#define mk make_pair

using namespace std;

int num,head[*],n,m,k,S,T;

struct node{

    int to,pre,v;

}e[**];

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

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

        if(e[i].to==to){

            e[i].v=min(e[i].v,v);

            return;

        }

    e[++num].to=to;

    e[num].v=v;

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

    head[from]=num;

}

int Cal(int x,int y){

    return x*+y;

}

priority_queue<pa,vector<pa>,greater<pa> >q;

bool vis[*];

int dis[*];

void Dij(int s){

    q.push(mk(,s));

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

    dis[s]=;

    while(!q.empty()){

        int now=q.top().second;q.pop();

        if(vis[now])continue;

        vis[now]=;

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

            int to=e[i].to;

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

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

                q.push(mk(dis[to],to));

            }

        }

    }

}

int main(){

    freopen("move.in","r",stdin);

    freopen("move.out","w",stdout);

    scanf("%d%d%d%d%d",&n,&m,&k,&S,&T);

    S++;T++;

    int x,y,z;

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

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

        x++,y++;

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

            int x1=Cal(x,j),y1=Cal(y,j);

            Insert(x1,y1,z);

            Insert(y1,x1,z);

            if(j){

                int x2=Cal(x,j-),y2=Cal(y,j-);

                Insert(x1,y2,);

                Insert(y1,x2,);

            }

        }

    }

    Dij(Cal(S,k));

    int ans=0x7fffffff;

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

        ans=min(ans,dis[Cal(T,i)]);

    printf("%d",ans);

}

100分分层图+堆优化Dij

巴特西

2017-9-2 NOIP模拟赛

“与”

小象涂色

行动！行动！

最新文章

热门文章