9.2 NOIP模拟 

题目名称	“与”	小象涂色	行动！行动！
输入文件	and.in	elephant.in	move.in
输出文件	and.out	elephant.in	move.in
时间限制	1s	1s	1s
空间限制	64MB	128MB	128MB

 

“与”

（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

 

/*"与"是要求同一位均是1，结果才为1。而对于2进制，越高位有1，数字越大。所以我们可以考虑将所给数列的数字看成二进制，从二进制最高位向下枚举若有大于等于两个数"这一位上为1"，那么最终结果的这一位肯定是1，于是我们就可以将所有"这一位上为1"的数保留下来，剩下的数舍弃；而若有少于两个数"这一位上为1"，则这一位上一定为0。*/ #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,a[300002],d[35],ans;void init(){ scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]);}void find(){ int i,j,ct,now=n,t; for(i=30; i>=0; i--) { ct=0; for(j=1; j<=now; j++) if(a[j]&(1<
           
            =0; i--) if(d[i]) ans=ans^(1<
           
          
         
        
       
      
     

 

 

  

小象涂色

（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

/*dp[i][j][k]表示第i个箱子第j次染色，染为k颜色的概率。时间复杂度过高，只能拿部分分对于每个箱子，它们的本质是相同的，也就是第几个箱子这一维状态是不需要存在的。dp[i][j]表示染色i次颜色为j的概率　　dp[i+1][j]+=dp[i][j]/2; 上次不染色 　　dp[i+1][j*x%c]+=dp[i][j] /2 /c; (x枚举颜色) 上次染色，染成x 最后期望Σdp[cnt[i]][j]*j; */#include
     
      #include
      
       #include
       
        #define N 107using namespace std;int n,m,tot,c,k,t,l,r,cnt[N];double dp[N][N],ans;void init(){    memset(dp,0,sizeof dp);    memset(cnt,0,sizeof cnt);    tot=0;ans=0;    scanf("%d%d%d",&n,&c,&k);    for(int i=1;i<=k;i++)    {        scanf("%d%d",&l,&r);        for(int j=l;j<=r;j++)        {            cnt[j]++;tot=max(tot,cnt[j]);        }    }}void DP(){    dp[0][1]=1;    for(int i=0;i
       
      
     

 

 

 

 

 

 

 

行动！行动！

（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.

/*分层图spfa 应该只有70，卡spfa...要加优化，懒得加了。*/#include
     
      #include
      
       #include
       
        #define N 10001#define M 100001using namespace std;int head[N],d[N][11],q[M][2];bool inq[N][11];int n,m,k,st,ed,cnt;struct edge{    int u,to,dis,next;}e[M];inline int read(){    int x=0,f=1;char c=getchar();    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}inline void add(int u,int to,int dis){    e[++cnt].to=to;e[cnt].dis=dis;e[cnt].next=head[u];head[u]=cnt;}void spfa(){    memset(d,127/3,sizeof d);    int he=0,ta=1;    q[0][0]=st;q[0][1]=0;    inq[st][0]=1;d[st][0]=0;    while(he!=ta)    {        int now=q[he][0],tmp=q[he++][1];inq[now][tmp]=0;        if(he==100001) he=0;        for(int i=head[now];i;i=e[i].next)        {            int v=e[i].to;            if(d[v][tmp]>d[now][tmp]+e[i].dis)            {                d[v][tmp]=d[now][tmp]+e[i].dis;                if(!inq[v][tmp])                {                    q[ta][0]=v;q[ta++][1]=tmp;                    inq[v][tmp]=1;                    if(ta==100001) ta=0;                }            }            if(d[v][tmp+1]>d[now][tmp] && tmp