11.6

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
【来源】
在此键入。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 300005
using namespace std;
void Emine(){
    freopen("and.in","r",stdin);
    freopen("and.out","w",stdout);
}
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,ans,b[maxn],vis[maxn];
int main(){
    Emine();
    n=read();ans=0;
    for(int i=1;i<=n;i++)b[i]=read(),vis[i]=1;
    for(int j=30;j>=0;j--){
        int cnt=0;
        for(int i=1;i<=n;i++){
            if((b[i]&(1<<j))&&vis[i])cnt++;
            if(cnt==2){ans+=(1<<j);break;}
        }
        if(cnt==2){
            for(int i=1;i<=n;i++)if((b[i]&(1<<j))==0)vis[i]=0;
        }
    }
    printf("%d
",ans);
    return 0;
}

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。
输入的树保证连通，无重边，无自环。
【来源】
在此键入。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 100005
#define ll long long
using namespace std;
void Emine(){
    freopen("senso.in","r",stdin);
    freopen("senso.out","w",stdout);
}
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,cnt,last[maxn],yd,siz1[maxn],siz2[maxn],out[maxn];
ll ans=0;
struct edge{int to,next,cost,flag;}e[maxn<<1];
void add(int u,int v,int w){e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].cost=w;}
void dfs(int x){
    siz1[x]=1;
    for(int i=last[x];i;i=e[i].next){
        if(siz1[e[i].to])continue;
        e[i].flag=1;
        dfs(e[i].to);
        siz1[x]+=siz1[e[i].to];
        siz2[x]+=siz2[e[i].to];
    }
}
int main(){
    Emine();
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int w=read(),u=read(),v=read();
        add(u,v,w);add(v,u,w);
        out[u]++,out[v]++;
    }
    for(int i=1;i<=n;i++)if(out[i]==1)siz2[i]=1,yd++;
    dfs(1);
    for(int i=1;i<=(m<<1);i++){
        if(!e[i].flag)continue;
        ans+=1ll*(n-siz1[e[i].to])*siz2[e[i].to]*e[i].cost;
        ans+=1ll*siz1[e[i].to]*(yd-siz2[e[i].to])*e[i].cost;
    }
    printf("%lld",ans);
    return 0;
}

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.
【来源】
在此键入。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define maxn 10005
#define maxm 50005
#define ll long long
using namespace std;
void Emine(){
    freopen("moved.in","r",stdin);
    freopen("moved.out","w",stdout);
}
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,k,s,t,last[maxn],cnt;
ll dis[maxn][12],minn=0x7fffffff;
struct edge{int to,next,cost,flag;}e[maxm<<1];
void add(int u,int v,int w){e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].cost=w;}
struct node{
    int id,num;ll d;
    node(){}
    node(int a,int b,ll c){id=a;num=b;d=c;}
    bool operator < (const node &b) const {
        return d>b.d;
    }
};
void dijkstra(){
    priority_queue<node> Q;
    memset(dis,0x3f3f3f3f,sizeof(dis));
    Q.push(node(s,0,0));
    while(!Q.empty()){
        node u=Q.top();Q.pop();
        for(int i=last[u.id];i;i=e[i].next){
            if(dis[e[i].to][u.num]>u.d+e[i].cost){
                dis[e[i].to][u.num]=u.d+e[i].cost;
                Q.push(node(e[i].to,u.num,u.d+e[i].cost));
            }
            if(u.num<k){
                if(dis[e[i].to][u.num+1]>u.d){
                    dis[e[i].to][u.num+1]=u.d;
                    Q.push(node(e[i].to,u.num+1,u.d));
                }
            }
        }
    }
}
int main(){
    Emine();
    n=read(),m=read(),k=read(),s=read(),t=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        add(u,v,w);add(v,u,w);
    }
    dijkstra();
    for(int i=0;i<=k;i++)minn=min(minn,dis[t][i]);
    printf("%lld
",minn);
    return 0;
}