| 题目名称 | “与” | 小象涂色 | 行动！行动！ |
| 输入文件 | and.in | elephant.in | move.in |
| 输出文件 | and.out | elephant.in | move.in |
| 时间限制 | 1s | 1s | 1s |
| 空间限制 | 64MB | 128MB | 128MB |
测评环境：windows XP
比赛时间：3小时
得分情况
蒟蒻我才得了180分，其他大佬肯定都AK了；
T1，20min正解思路10min写完，A掉了；
T2，一眼概率DP，然而根本看不懂题目什么意思；
T3，思路纠结了近1h，然后30min写代码，然后数组开小了，这样80，其实开够的话也还会T一个点；
“与”
（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
思路
从高位开始筛选；
如果有至少两个数该位(f)存在，则ans+=f并且筛去&f==0的数；
因为某位后所有位的数的和不可能大于本位的数，所以可以这样做；
代码实现
1 #include2 #include 3 using namespace std; 4 const int maxn=3e5+10; 5 inline int max_(int x,int y){ return x>y?x:y;} 6 int n,f,big,now,ans; 7 int s[maxn]; 8 bool comp(int a,int b){ return (a&f)>(b&f);} 9 int main(){10 freopen("and.in","r",stdin);11 freopen("and.out","w",stdout);12 scanf("%d",&n);13 for(int i=1;i<=n;i++){14 scanf("%d",&s[i]);15 big=max_(big,s[i]);16 }17 for(f=1;f<=big;f<<=1);18 for(f>>=1;f;f>>=1){19 sort(s+1,s+n+1,comp);20 for(now=1;s[now]&f&&now<=n;now++);21 if(now>2){ans+=f,n=now-1;}22 }23 printf("%d\n",ans);24 return 0;25 }
小象涂色
（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
思路
f[i][j]表示一个物品操作i次颜色变为j的概率；
时间复杂度O(T*K*c2);
代码实现
1 #include2 #include 3 using namespace std; 4 inline int max_(int x,int y){ return x>y?x:y;} 5 const int maxn=55; 6 int T,n,c,maxc; 7 int cs[maxn]; 8 double f[maxn][maxn<<1]; 9 void init(){10 memset(cs,0,sizeof(cs));11 int k,x,y;maxc=0;12 scanf("%d%d%d",&n,&c,&k);13 for(int i=1;i<=k;i++){14 scanf("%d%d",&x,&y);15 for(int j=x;j<=y;j++){16 cs[j]++;17 maxc=max_(maxc,cs[j]);18 }19 }20 }21 void dp(){22 memset(f,0,sizeof(f));23 double ans=0;24 f[0][1]=1;25 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.
思路
d[i][j]表示使用j个医疗包的情况下，跑到i城市的流血量；
然后跑一边SPFA，求的最短路即可；
最重要的是，这个题需要优化，，，使用SLF方案优化SPFA；
代码实现
1 #include2 #include 3 const int maxn=1e4+10; 4 const int maxm=1e5+10; 5 inline int min_(int x,int y){ return x