|
题目名称 |
“与” |
小象涂色 |
行动！行动！ |
|
输入文件 |
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
据说暴力就能过...
/*
n*n暴力很好想
如果按照二进制位数给这些数分类的话
不是很极端的数据的话每一类的数不会很多
从高位开始处理 找出第一个一定是答案
然后乱搞一下把极端数据特判掉就好了
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 300010
using namespace std;
int n,a[maxn],c[][maxn],r[maxn],tot,ans;
int init(){
int x=;char s=getchar();
while(s<''||s>'')
s=getchar();
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x;
}
int cmp(int a,int b){
return a>b;
}
int main()
{
freopen("and.in","r",stdin);
freopen("and.out","w",stdout);
n=init();
for(int i=;i<=n;i++)
a[i]=init();
sort(a+,a++n,cmp);
if(a[]==a[]){
printf("%d\n",a[]);
return ;
}
for(int i=;i<=n;i++)
if(a[i]==a[i-])ans=max(ans,a[i]);
for(int i=;i<=n;i++){
int x=a[i],k=;
while(x)k++,x>>=;
c[k][++c[k][]]=a[i];
}
for(int i=;i>=;i--){
if(!c[i][])continue;
if(c[i][]<=ans)break;
int mxx=;
for(int j=;j<=c[i][];j++)
for(int k=;k<=c[i][];k++){
if(j!=k)mxx=max(mxx,c[i][j]&c[i][k]);
if(mxx>c[i][k]||ans>c[i][k])break;
} for(int j=;j<=c[i][];j++)
for(int k=;k<=tot;k++)
mxx=max(mxx,c[i][j]&r[k]);
ans=max(ans,mxx);
if(ans)break;
for(int j=;j<=c[i][];j++)
r[++tot]=c[i][j];
}
printf("%d\n",ans);
return ;
}
小象涂色
（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题 没想到....
f[i][j][k]第i次涂色之后 j位置是k颜色的概率
这会超时 其实考虑到所有物品具有相似性，即n个物品本质是相同的，
所以不用枚举物品
f[i][j]表示一个物品操作i次颜色变为j的概率
先搞出每个物品染色的次数 然后dp
最后统计答案
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 110
using namespace std;
int T,n,c,K,l,r,cnt[maxn],mxx;
double f[maxn][maxn],ans;
void Clear(){
memset(cnt,,sizeof(cnt));
memset(f,,sizeof(f));
f[][]=;ans=;mxx=;
}
int main()
{
freopen("elephant.in","r",stdin);
freopen("elephant.out","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&c,&K);
Clear();
for(int i=;i<=K;i++){
scanf("%d%d",&l,&r);
for(int j=l;j<=r;j++){
cnt[j]++;mxx=max(mxx,cnt[j]);
}
}
for(int i=;i<mxx;i++){
for(int j=;j<c;j++){
f[i+][j]+=f[i][j]/;
for(int k=;k<c;k++)
f[i+][(j*k)%c]+=f[i][j]/(*c);
}
}
for(int i=;i<=n;i++)
for(int j=;j<c;j++)
ans+=f[cnt[i]][j]*j;
printf("%.9f\n",ans);
}
return ;
}
行动！行动！
（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.
/*
分层图 没啥可说的
因为k<=10所以拓展点的时候直接x+10+y了
但其实k==10的话这样拓展会重复...
幸好只有一个点...
谨慎谨慎..
还有就是 这题这样做的话卡SPFA
要用dij
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define pa pair<int,int>
#define mk make_pair
#define maxn 200100
#define maxm 2000100
using namespace std;
int n,m,k,num,head[maxn],f[maxn],dis[maxn],S,T,l,r,ans=0x3f3f3f3f;
struct node{
int v,t,pre;
}e[maxm*];
priority_queue<pa,vector<pa>,greater<pa> >q;
int init(){
int x=;char s=getchar();
while(s<''||s>'')s=getchar();
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x;
}
int Cal(int x,int y){
return *x+y;
}
void Add(int from,int to,int dis){
for(int i=head[from];i;i=e[i].pre)
if(e[i].v==to){
e[i].t=min(e[i].t,dis);
return;
}
num++;e[num].v=to;
e[num].t=dis;
e[num].pre=head[from];
head[from]=num;
}
void Dij(int s){
memset(dis,/,sizeof(dis));
dis[s]=;q.push(mk(,s));
while(!q.empty()){
int u=q.top().second;
q.pop();
if(f[u])continue;f[u]=;
for(int i=head[u];i;i=e[i].pre){
int v=e[i].v;
if(dis[v]>dis[u]+e[i].t){
dis[v]=dis[u]+e[i].t;
q.push(mk(dis[v],v));
}
}
}
}
int main()
{
freopen("move.in","r",stdin);
freopen("move.out","w",stdout);
n=init();m=init();k=init();
S=init();T=init();S++;T++;
int u,v,t;
for(int i=;i<=m;i++){
u=init();v=init();t=init();
u++;v++;
for(int j=;j<=k;j++){
Add(Cal(u,j),Cal(v,j),t);
Add(Cal(v,j),Cal(u,j),t);
if(j){
Add(Cal(u,j),Cal(v,j-),);
Add(Cal(v,j),Cal(u,j-),);
}
}
}
Dij(Cal(S,k));
for(int i=;i<=k;i++)
ans=min(ans,dis[Cal(T,i)]);
printf("%d\n",ans);
return ;
}
Hzwer的陨石
（meteorite.pas/.c/.cpp）
时间限制：1s；空间限制：128MB
题目描述：
经过不懈的努力，Hzwer召唤了很多陨石。已知Hzwer的地图上共有n个区域，且一开始的时候第i个陨石掉在了第i个区域。有电力喷射背包的ndsf很自豪，他认为搬陨石很容易，所以他将一些区域的陨石全搬到了另外一些区域。
在ndsf愉快的搬运过程中，Hzwer想知道一些陨石的信息。对于Hzwer询问的每个陨石i，你必须告诉他，在当前这个时候，i号陨石在所在区域x、x区域共有的陨石数y、以及i号陨石被搬运的次数z。
输入描述：
输入的第一行是一个正整数T。表示有多少组输入数据。
接下来共有T组数据，对于每组数据，第一行包含两个整数：N和Q。
接下来Q行，每行表示一次搬运或一次询问，格式如下：
T A B：表示搬运，即将所有在A号球所在地区的陨石都搬到B号球所在地区去。
Q A：悟空想知道Ａ号陨石的x，y，z。
输出描述：
对于第ｉ组数据，第一行输出“Case i：”接下来输出每一个询问操作的x，y，z，每一个询问操作的答案占一行。每组数据之间没有空行。
样例输入：
2
3 3
T 1 2
T 3 2
Q 2
3 4
T 1 2
Q 1
T 1 3
Q 1
样例输出：
Case 1:
2 3 0
Case 2:
2 2 1
3 3 2
数据范围：
20%的数据保证：0≤T≤20，2＜N＜＝100，2＜Q＜＝100。
100%的数据保证：0≤T≤100，2＜N＜＝10000，2＜Q＜＝10000。
对于所有数据保证搬运操作中AB在Ｎ的范围内且所在区域不相同。：
/*
带权并查集
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 10010
using namespace std;
int T,n,m,fa[maxn],cnt[maxn],sum[maxn],cas;
char c[];
int init(){
int x=;char s=getchar();
while(s<''||s>'')s=getchar();
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x;
}
void Clear(){
for(int i=;i<=n;i++){
fa[i]=i;sum[i]=;
}
memset(cnt,,sizeof(cnt));
}
int find(int x){
if(x==fa[x])return x;
int f=fa[x];
fa[x]=find(fa[x]);
cnt[x]+=cnt[f];
return fa[x];
}
void Union(int a,int b){
int r1=find(a);
int r2=find(b);
if(r1==r2)return;
fa[r1]=r2;
sum[r2]+=sum[r1];
sum[r1]=;cnt[r1]++;
}
int main()
{
freopen("meteorite.in","r",stdin);
freopen("meteorite.out","w",stdout);
T=init();
while(T--){
n=init();m=init();
Clear();int x,y;
printf("Case %d:\n",++cas);
while(m--){
scanf("%s",c);
if(c[]=='T'){
x=init();y=init();
Union(x,y);
}
else{
x=init();int r=find(x);
printf("%d %d %d\n",r,sum[r],cnt[x]);
}
}
}
}
conclusion
/*
今天很蛋疼...
T1想了半天正解 还是考虑不全wa了一个
然而同桌写的暴力A了 ....这数据
T2概率dp直接暴力
T3分层图 考虑不全没分配好节点编号wa了一个
这算幸运了 只有一个这样的数据 要是出题人丧心病狂的话可以卡成零蛋... T2还是学到了东西
优化的思想很好 因为每个都一样 所以直接去掉一维
瞬间优化掉一个n
其他的嘛 记得对拍 T1可以把错误拍出来的 然而并没写
*/