还记得这场考试机房所有人都忘开足数组了QAQ

T1 运算

题目描述：

小花上了一节计算机课，听到老师讲到了“与运算”的概念，于是便自己展开了尝试。她在纸上写下了 3 个数，并将他们两两进行二进制“与”运算，之后找到了最大的结果。正当她开心之时，作为 JDFZ 高一鸡精扛把子的 Superbia 走了过来：这太菜了，数据这么弱，再加大 100000 倍我也能做！
小花不服气，便真的出了好多好多个数，问 Superbia 究竟哪两个数进行二进制下的与运算结果最大。
Superbia 前一天晚上补作业补到了他出发上学前 1e-15s 所以他现在已经算不出来了，他请求你帮他算一下。

输入格式

第一行为元素个数 n。
第二行开始 n 行每行一个数 a[i]表示第 i 个元素。

输出格式

最大的与运算结果。

样例输入

3 8 10 2

样例输出

数据范围

20%的数据保证 n<=5000
100%的数据保证 n<=3*10^5，0<=a[i]<=10^9

题目分析：

二进制或运算的拓展性质这里直接用出题人的题解

我们知道”&”运算是两个数二进制位上全为1则为1，有一个数或以上为0则为0.

我们同时也知道，(1<<20) > (1<<20)-1

即：

100000000000000000000

大于

011111111111111111111

所以，我们可以从二进制位上的最高位（对于int可以用1<<30）开始向下枚举，必定有如果两个数在当前的最高位上相与为1则结果在此位上为1，使得相与的结果最大。

所以我们就进行枚举，如果有两个及以上的数字上我们制定的位上为1则说明答案一定从这些元素中选出，那么删去不合法的继续进行下一位的枚举，当只剩两个的时候恭喜你找到了OvO

嗯就是这样然而考场把原数列sort一下竟然骗A了原来数据这么水QAQ

附上std代码

#include <cstdio>
int a[300010],ans,n;
bool use[300010];
int main()
{
    freopen("calc.in" ,"r",stdin);
    freopen("calc.out" ,"w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=30;i>=0;--i)
    {
        int tmp=1<<i,cnt=0;
        for(int j=1;j<=n;++j)
            if(!use[j]&&(a[j]&tmp)) ++cnt;
        if(cnt<2) continue;
        ans^=(1<<i);
        for(int j=1;j<=n;++j)
            if(!(a[j]&(1<<i))) use[j]=true;
    }
    printf("%d",ans);
    return 0;
}

T2 道路

题目描述：

小花所在的学校十分先进。学校中一共有 n 个房间，这些房间之间有 m 条通道连接，因为这些房间之间的距离可能会非常的长，所以这些通道使用了从隔壁学园都市进口的快速传输技术，但是这项技术并不是十分完善，所以只能安全地单向进行传输。
值得注意的是，尽管每条通道传输都需要一定时间，但是也有例外：学校中有多个“教师办公中心”，只要进入这些中心，便可以享受到最快速最便捷的传输，即在办公中心里进行传输不需要消耗通道本应消耗的时间。当然小花是不担心时间的，但是学园都市又研发出了新功能——在办公中心内进行传输所能提交的作业数是办公中心内房间的个数乘以办公中心内能交作业最多的房间能交的作业个数，即办公中心内每个房间能交作业的数量以最多的为准。
可惜，记录办公中心地址的单子丢了，但是她从老师那里听说，所有的办公中心里的所有房间都是可以互相（直接或间接）抵达的。注意因为资源开发完全，所以不会出现一个区域房间之间可以相互抵达，但却不是办公中心的情况。办公中心必然由多个房间组成。
小花想知道，对于给定的起点 S，小花应该如何走才能交最多的作业？请输出最多能交的作业个数并输出交最多作业时经过的最少办公中心。

输入格式

第一行 m,n,s 表示一共有 m 个房间，n 条通道，以 s 号房间作为起点。
第二行 m 个数表示每个房间可以上交的作业 a[i]
第三行开始的 n 行每行 2 个整数 x[i],y[i]表示从 x[i]到 y[i]号房间有一条通道。

输出格式

一行两个整数，之间用空格分开，分别表示最多能交作业的个数以及经过的最少的办公中心。

样例输入

样例输出

20 1

数据范围

对于 30%的数据，保证 n<=500,m<=5000.
对于 100%的数据，保证 n<=15000,m<=200000.
同时有 30%的数据，保证学校中没有办公中心。

题目分析：

首先注意这里：有多个办公中心并且办公中心里的所有房间都能互相到达
这显然是强连通分量嘛QAQ 所以我们先用tarjan 缩点
因为题目描述所以tarjan 后的点的点权是强连通分量里{点权最大*点数}
然后我们跑spfa最长路这里的更新需要注意一下
我们不仅需要从S到每个点的交作业数最多还要经过最少的办公中心
并且要明确一点办公中心由多个房间组成
所以spfa更新时要注意一下
最后我们在跑完spfa后枚举非s点取最优解就可以了

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,tota,timee,color;
struct your
{
    int next,to;
}a[210000],b[210000];
int heada[16000];
int headb[16000];
int totb;
void add_a(int x,int y)
{
    a[++tota].next=heada[x];
    a[tota].to=y;
    heada[x]=tota;
}
void add_b(int x,int y)
{
    b[++totb].next=headb[x];
    b[totb].to=y;
    headb[x]=totb;
}
int v[16000],vv[16000],cnt[16000];
int deep[16000],low[16000],belong[16000],st[16000],visit[16000];
void tarjan(int x)
{
    low[x]=deep[x]=timee++;
    visit[x]=true;
    st[++st[0]]=x;
    for(int i=heada[x];i;i=a[i].next)
    {
        if(!deep[a[i].to])
        {
            tarjan(a[i].to);
            low[x]=min(low[x],low[a[i].to]);
        }
        else if(visit[a[i].to])
            low[x]=min(low[x],deep[a[i].to]);
    }
    if(deep[x]==low[x])
    {
        int tmp;
        color++;
        do
        {   
            tmp=st[st[0]--];
            cnt[color]++;
            visit[tmp]=false;
            belong[tmp]=color;
            vv[color]=max(vv[color],v[tmp]);
        }while(tmp!=x);
    }
}
int S;
int num[16000];
bool book[16000];
int dis[16000],in[16000];
int ans,number;
int calc(int x)
{
    return x>1?1:0; 
}
int temp1,temp2;
void spfa()
{
    queue<int>q;
    memset(num,0x7f,sizeof num);
    q.push(belong[S]);
    book[belong[S]]=true;
    if(cnt[belong[S]]>1) num[belong[S]]=1;
    else num[belong[S]]=0;
    dis[belong[S]]=vv[belong[S]];
    while(q.size())
    {
        int nmp=q.front();
        q.pop();
        book[nmp]=false;
        for(int i=headb[nmp];i;i=b[i].next)
        {
            if(dis[b[i].to]<dis[nmp]+vv[b[i].to])
            {
                dis[b[i].to]=dis[nmp]+vv[b[i].to];
                num[b[i].to]=num[nmp]+calc(cnt[b[i].to]);
                if(!book[b[i].to])
                    q.push(b[i].to),book[b[i].to]=true;
            }
            if(dis[b[i].to]==dis[nmp]+vv[b[i].to]&&num[b[i].to]>num[nmp]+calc(cnt[b[i].to]))
            {
                num[b[i].to]=num[nmp]+calc(cnt[b[i].to]);
                if(!book[b[i].to]) book[b[i].to]=true,q.push(b[i].to);
            }
        }
    }
}
void work()
{
    spfa();
    for(int i=1;i<=color;i++)
    {
        if(ans<dis[i]) ans=dis[i],number=num[i];
        if(ans==dis[i]&&num[i]<number) number=num[i];
    }
    printf("%d %d",ans,number);
}
int main()
{
    scanf("%d%d%d",&n,&m,&S);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add_a(x,y);
    }
    for(int i=1;i<=n;i++)
        if(!deep[i]) tarjan(i);
    for(int i=1;i<=color;i++)
        vv[i]=vv[i]*cnt[i];
    for(int i=1;i<=n;i++)
        for(int j=heada[i];j;j=a[j].next)
            if(belong[i]!=belong[a[j].to])
                add_b(belong[i],belong[a[j].to]),in[belong[a[j].to]]++;
    work();
    return 0;
}

T3 小花

题目描述：

小花的名字叫小花，当然家里也要养一些花啦~
小花养了好多好多盆小花，但是他们距离很远，所以会变的孤单，于是小花决定建立一个通讯系统供他们通讯。
小花的花园里有 N 盆小花。因为小花家使用了从隔壁学园都市进口的运行在太空名为“织女星一号”的卫星，可将 S 盆花联系在一起，他们之间可以互相通讯。除此之外还可以加装无线电通讯设备，但是只通过无线电收发器通话的花之间的距离不能超过 D，这是受收发器的功率限制。收发器的功率越高，通讯距离 D 会更远，但同时价格也会更贵。
收发器需要统一购买和安装，所以所有的花只能选择安装一种型号的收发器。换句话说，每一对花之间的通讯距离都是同一个 D。你的任务是确定收发器必须的最小通讯距离 D，使得每一对花之间至少有一条通讯路径（直接的或者间接的）。

输入格式

第 1 行：2 个整数 S 和 P，S 表示可使用卫星通讯的小花数，P 表示小花的数量。
接下来 P 行，每行描述一盆花的平面坐标（x,y），以 m 为单位，整数。

输出格式

实数 D，含义如上。精确到小数点后两位。

样例输入

212.13

数据范围

对于 20%的数据，P=2，S=1
对于 100%的数据，1<=S<=100，S<P<=500，0<=x，y<=10000

题目分析：

这题一开始看没什么思路但是我们贪心的来想我们现在能免费连接S盆花那么一定是用连接着S盆花的机会来连接距离比较大的花
我们先假设用卫星将S盆花连接成了一个整体
然后剩下n-S盆花那么这n-S盆花需要我们来花钱连了那么我们要求的D就是剩下的n-S盆花中能够使得所有花都连接的最小的最大距离这里我们可以使用Kruskal求
但是这么做对吗很显然不对虽然我们花钱把n-S的花连到了一起但是所有的n盆花并不是一个整体所以我们还要把他们连上
那么 D就是把两个集合连接在一起的边权
所以我们先处理出所有的边然后用Kruskal求出第n-S条的边权就可以了

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
struct your
{
    int x,y;
    double c;
}a[300000];
int tot;
int x[600],y[600],f[600];
int find(int x)
{
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
int n,m;
int cmp(your j,your k)
{
    return j.c<k.c;
}
void Kruskal()
{
    int cnt=0;
    for(int i=1;i<=tot;i++)
    {
        int dx=find(a[i].x),dy=find(a[i].y);
        if(dx!=dy)
            f[dx]=dy,cnt++;
        if(cnt==n-m)
        {
            printf("%.2lf",a[i].c);
            return ;
        }
    }
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&x[i],&y[i]),f[i]=i;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            tot++;
            a[++tot].x=i;
            a[tot].y=j;
            a[tot].c=sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
        }
    sort(a+1,a+tot+1,cmp);
    Kruskal();
        return 0;
}

Superbia-zyb

Away From OI

Tonyzhao test Ⅰ

T1 运算

题目描述：

输入格式

输出格式

样例输入

样例输出

数据范围

题目分析：

T2 道路

题目描述：

输入格式

输出格式

样例输入

样例输出

数据范围

题目分析：

T3 小花

题目描述：

输入格式

输出格式

样例输入

数据范围

题目分析：

发表评论取消回复

T1 运算

题目描述：

输入格式

输出格式

样例输入

样例输出

数据范围

题目分析：

T2 道路

题目描述：

输入格式

输出格式

样例输入

样例输出

数据范围

题目分析：

T3 小花

题目描述：

输入格式

输出格式

样例输入

数据范围

题目分析：

发表评论 取消回复

发表评论取消回复