2017-9-2 NOIP模拟赛

时间:2022-12-17 09:26:38

“与”

(and.pas/.c/.cpp)

时间限制:1s;空间限制64MB

题目描述:

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

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

输入描述:

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

输出描述:

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

样例输入:

3

8

10

2

样例输出:

8

样例解释:

8 and 10 = 8

8 and 2 = 0

10 and 2 = 2

数据范围:

20%的数据保证n<=5000

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

2017-9-2 NOIP模拟赛2017-9-2 NOIP模拟赛
/*
    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=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=31;i>=1;i--){
        int flag=0;
        for(int j=1;j<=n;j++)
            if((a[j]&(1<<(i-1)))&&!vis[j])flag++;
        if(flag>=2){
            ans+=(1<<(i-1)); 
            for(int j=1;j<=n;j++)
                if(!(a[j]&(1<<(i-1))))vis[j]=1;
        }
    }
    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

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

2017-9-2 NOIP模拟赛2017-9-2 NOIP模拟赛
/*
    一道有关期望的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[51];
double dp[51][101],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,0,sizeof(dp));
        memset(cnt,0,sizeof(cnt));
        ans=0;mc=0;
        scanf("%d%d%d",&n,&c,&K);
        for(int i=1;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[0][1]=1;
        for(int i=0;i<mc;i++){
            for(int j=0;j<c;j++){
                dp[i+1][j]+=dp[i][j]/2;
                for(int k=0;k<c;k++){
                    dp[i+1][(j*k)%c]+=dp[i][j]/(2*c);
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=0;j<c;j++){
                ans+=dp[cnt[i]][j]*j;//概率乘以收益
            }
        }
        printf("%.9lf\n",ans);
    }
    return 0;
}
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

样例输出:

8

数据范围:

对于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.

2017-9-2 NOIP模拟赛2017-9-2 NOIP模拟赛
#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=9999999999999;
struct node{
    int to,pre;
    long long v;
}e[50010*2];
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,0,sizeof(a));
    for(int i=1;i<=cnt;i++)a[i]=path[i];
    sort(a+1,a+cnt+1);
    for(int i=cnt,j=1;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]=1;
        cnt++;
        path[cnt]=e[i].v;
        dfs(to,sum+e[i].v);
        vis[to]=0;
        cnt--;
    }
}
void spfa(){
    queue<int>q;
    memset(path,127,sizeof(path));
    q.push(s);vis[s]=0;path[s]=0;
    while(!q.empty()){
        int now=q.front();q.pop();vis[now]=0;
        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]=1;
                    q.push(to);
                }
            }
        }
    }
    cout<<path[t];
}
long long qread(){
    long long i=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();}
    while(ch<='9'&&ch>='0'){i=i*10+ch-'0';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=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        z=qread();
        Insert(x,y,z);
        Insert(y,x,z);
    }
    if(k==0){
        spfa();
        return 0;
    }
    vis[s]=1;
    dfs(s,0);
    cout<<ans;
    return 0;
}
40分 暴力
2017-9-2 NOIP模拟赛2017-9-2 NOIP模拟赛
/*
    因为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[10010*11],n,m,k,S,T;
struct node{
    int to,pre,v;
}e[50010*11*2];
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*11+y;
}
priority_queue<pa,vector<pa>,greater<pa> >q;
bool vis[50010*11];
int dis[50010*11];
void Dij(int s){
    q.push(mk(0,s));
    memset(dis,127/3,sizeof(dis));
    dis[s]=0;
    while(!q.empty()){
        int now=q.top().second;q.pop();
        if(vis[now])continue;
        vis[now]=1;
        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=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        x++,y++;
        for(int j=0;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-1),y2=Cal(y,j-1);
                Insert(x1,y2,0);
                Insert(y1,x2,0);
            }
        }
    }
    Dij(Cal(S,k));
    int ans=0x7fffffff;
    for(int i=0;i<=k;i++)
        ans=min(ans,dis[Cal(T,i)]);
    printf("%d",ans);
}
100分 分层图+堆优化Dij