首页 > > 程序设计 > C/C++ >

11.6

2018-06-17 21:37:00来源：未知阅读 ()

1642. 与计算
☆ 输入文件：and.in 输出文件：and.out 简单对比
时间限制：1 s 内存限制：64 MB
【题目描述】
给你一个长度为n的序列A，请你求出一对Ai，Aj（1<=i<j<=n）使Ai“与”Aj最大。
说明：“与”表示二进制位运算and，在c++中表示为 & 。
例如：(1000)2 & (1010)2=(1000)2
【输入格式】
第一行为n。接下来n行，一行一个数字表示Ai。
【输出格式】
输出最大的Ai“与”Aj的结果。
【样例输入】
3
8
10
2
【样例输出】
8
【提示】
样例解释：
(8 & 10 )= 8
(8 & 2) = 0
(10 & 2 )= 2
数据范围：
20%的数据保证n<=5000
100%的数据保证 n<=3*10^5，0<=Ai<=10^9
【来源】
在此键入。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define maxn 300005
 6 using namespace std;
 7 void Emine(){
 8     freopen("and.in","r",stdin);
 9     freopen("and.out","w",stdout);
10 }
11 int read(){
12     int x=0,f=1;char ch=getchar();
13     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
14     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
15     return x*f;
16 }
17 int n,ans,b[maxn],vis[maxn];
18 int main(){
19     Emine();
20     n=read();ans=0;
21     for(int i=1;i<=n;i++)b[i]=read(),vis[i]=1;
22     for(int j=30;j>=0;j--){
23         int cnt=0;
24         for(int i=1;i<=n;i++){
25             if((b[i]&(1<<j))&&vis[i])cnt++;
26             if(cnt==2){ans+=(1<<j);break;}
27         }
28         if(cnt==2){
29             for(int i=1;i<=n;i++)if((b[i]&(1<<j))==0)vis[i]=0;
30         }
31     }
32     printf("%d\n",ans);
33     return 0;
34 }

View Code

1643. 宠物之战
★ 输入文件：senso.in 输出文件：senso.out 简单对比
时间限制：1 s 内存限制：256 MB
【题目描述】
众所周知，moreD的宠物已经被moreD奴役得体无完肤。这只宠物实在忍无可忍，把自己每天走魔法树的经历告诉了自己的宠物。同时他还说明了自己爬树是多么地慢，以至于moreD每天都残酷地训练他爬树。
幸运的是moreD的宠物的宠物不是moreD的宠物，moreD的宠物深知”宠物是用来宠的而不是用来奴役的”这一点，所以moreD的宠物对待自己的宠物很有爱。所以moreD的宠物与其宠物商量着要推翻moreD的暴政，方法是把moreD告上法庭，就以自己每天被迫爬树来做证据。
由于魔法树是树，训练树当然也是树啦。
moreD的训练有着GX的文化，每天moreD会把自己的宠物通灵到树的一个端点上，这个通灵点可能与之前的通灵点相同。然后moreD命令他的宠物从这个点开始走，让这只宠物随便访问自己该天之前没有访问过的节点，一直走到该天无路可走，训练才会结束，宠物才可以休息。
moreD的宠物每天都会在这棵树上训练，幸运的是他每天走过的训练路径都不同，直到若干天后，所有可能的训练路径都被走遍了。
你，作为moreD宠物的宠物，一只被moreD的宠物宠着的宠物，当然想帮moreD的宠物算出他总共走过的路径长度啦。
【输入格式】
第一行包含两个正整数N,M，表示树的点数与边数。
接下来M行，每行三个正整数表示Li,bi,ci分别表示树上有一条长度为Li的连接bi,ci两个结点的边。
【输出格式】
仅一行表示答案
【样例输入】
5 4
1 2 1
1 3 1
2 4 2
2 5 2
【样例输出】
37
【提示】
可能的训练路径有(1-2-4),(1-2-5),(1-3),(2-4),(2-5),(2-1-3),(3-1-2-4),(3-1-2-5)(4-2-5),(4-2-1-3),(5-2-4),(5-2-1-3)
长度依次为3，3，1，2，2，2，4，4，4，4，4，4。和为37
数据范围
对于30%的数据N≤300
对于70%的数据N≤3,000
对于100%的数据对于所有输入的整数均不大于100,000。
输入的树保证连通，无重边，无自环。
【来源】
在此键入。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define maxn 100005
 6 #define ll long long
 7 using namespace std;
 8 void Emine(){
 9     freopen("senso.in","r",stdin);
10     freopen("senso.out","w",stdout);
11 }
12 int read(){
13     int x=0,f=1;char ch=getchar();
14     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
15     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
16     return x*f;
17 }
18 int n,m,cnt,last[maxn],yd,siz1[maxn],siz2[maxn],out[maxn];
19 ll ans=0;
20 struct edge{int to,next,cost,flag;}e[maxn<<1];
21 void add(int u,int v,int w){e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].cost=w;}
22 void dfs(int x){
23     siz1[x]=1;
24     for(int i=last[x];i;i=e[i].next){
25         if(siz1[e[i].to])continue;
26         e[i].flag=1;
27         dfs(e[i].to);
28         siz1[x]+=siz1[e[i].to];
29         siz2[x]+=siz2[e[i].to];
30     }
31 }
32 int main(){
33     Emine();
34     n=read(),m=read();
35     for(int i=1;i<=m;i++){
36         int w=read(),u=read(),v=read();
37         add(u,v,w);add(v,u,w);
38         out[u]++,out[v]++;
39     }
40     for(int i=1;i<=n;i++)if(out[i]==1)siz2[i]=1,yd++;
41     dfs(1);
42     for(int i=1;i<=(m<<1);i++){
43         if(!e[i].flag)continue;
44         ans+=1ll*(n-siz1[e[i].to])*siz2[e[i].to]*e[i].cost;
45         ans+=1ll*siz1[e[i].to]*(yd-siz2[e[i].to])*e[i].cost;
46     }
47     printf("%lld",ans);
48     return 0;
49 }

View Code

1644. 行动！行动！
★ 输入文件：moved.in 输出文件：moved.out 简单对比
时间限制：1 s 内存限制：256 MB
【题目描述】
大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之间有一条双向道路，c表示Jack在这条路上损失的血量。
【输出格式】
Jack从S到T最少要流的血量。
【样例输入】
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.
【来源】
在此键入。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<queue>
 6 #define maxn 10005
 7 #define maxm 50005
 8 #define ll long long
 9 using namespace std;
10 void Emine(){
11     freopen("moved.in","r",stdin);
12     freopen("moved.out","w",stdout);
13 }
14 int read(){
15     int x=0,f=1;char ch=getchar();
16     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
17     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 int n,m,k,s,t,last[maxn],cnt;
21 ll dis[maxn][12],minn=0x7fffffff;
22 struct edge{int to,next,cost,flag;}e[maxm<<1];
23 void add(int u,int v,int w){e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].cost=w;}
24 struct node{
25     int id,num;ll d;
26     node(){}
27     node(int a,int b,ll c){id=a;num=b;d=c;}
28     bool operator < (const node &b) const {
29         return d>b.d;
30     }
31 };
32 void dijkstra(){
33     priority_queue<node> Q;
34     memset(dis,0x3f3f3f3f,sizeof(dis));
35     Q.push(node(s,0,0));
36     while(!Q.empty()){
37         node u=Q.top();Q.pop();
38         for(int i=last[u.id];i;i=e[i].next){
39             if(dis[e[i].to][u.num]>u.d+e[i].cost){
40                 dis[e[i].to][u.num]=u.d+e[i].cost;
41                 Q.push(node(e[i].to,u.num,u.d+e[i].cost));
42             }
43             if(u.num<k){
44                 if(dis[e[i].to][u.num+1]>u.d){
45                     dis[e[i].to][u.num+1]=u.d;
46                     Q.push(node(e[i].to,u.num+1,u.d));
47                 }
48             }
49         }
50     }
51 }
52 int main(){
53     Emine();
54     n=read(),m=read(),k=read(),s=read(),t=read();
55     for(int i=1;i<=m;i++){
56         int u=read(),v=read(),w=read();
57         add(u,v,w);add(v,u,w);
58     }
59     dijkstra();
60     for(int i=0;i<=k;i++)minn=min(minn,dis[t][i]);
61     printf("%lld\n",minn);
62     return 0;
63 }