考试总结：这次考试，题目较为简单，本来我觉得能A掉一个，但是不知道为啥A了两个。成绩还是可以的。
首先是阅读题面，然后按顺序开题，T1一看就有思路，首先明确一个性质，或运算是一种不进位加法，那么根据这个性质我们很容易得出取到最优值的策略，就是从高到低位贪心地填补空位。
T2，数据范围较小，当时我想到了折半搜索，但是就是没有想到利用二分求排名为\(k\)的数。
T3，刚开始我打了个暴力，跑最短路，但是后来我又想了想打了一个更简洁的算法，结果竟然A了，我把暴力交上去得了0分，原来是暴力假了。。
T4 没什么时间想了，就打了个暴力，想着用\(bitset\)水过70，但是\(bitset\)时间复杂度是\(O(n)\)的，不是\(O(1)\)的。而且这样做不太有正确性。
总结：1.不论题目难易，首先拿到暴力分，可以保住心态
2.可以在暴力的基础上进行优化和改进，也许就能想出正解
3.合理安排时间，最后要检查文件格式，输入输出
T1 最大或
思路：因为或运算是一种不进位加法，那么根据这个性质我们很容易得出取到最优值的策略，就是从高到低位贪心地填补空位。
一些细节不再赘述，代码如下:
AC_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define head heeead
#define next neet
using namespace std;
const int N=510;
int t,l,r,ans,w1,w2,cnt;
int cun[80],jw[80];
ii read()
{
int x=0;char ch=getchar();bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
ii lowbit(int x) {return x&(-x);}
signed main()
{
freopen("maxor.in","r",stdin);
freopen("maxor.out","w",stdout);
cun[1]=1;
for(re i=2;i<=59;i++) cun[i]=cun[i-1]+(1ll<<1ll*(i-1));
t=read();
while(t--)
{
l=read(),r=read();
if(l==r) {printf("%lld\n",l);continue;}
ans=0;
w1=w2=0,cnt=0;
int x=l,y=r,now=0,my=0;
for(re i=1;i<=60;i++) jw[i]=0;
while(x) w1++,x>>=1;
while(y) w2++,y>>=1;
y=r;
while(y)
{
x=lowbit(y);
jw[++cnt]=(int)log2(x);
y-=x;
}
if(cun[w2-1]>=l)
printf("%lld\n",cun[w2-1]|r);
else
{
while(cnt>1)
{
my+=(1ll<<jw[cnt]);
now=max(jw[cnt-1],1ll);
cnt--;
now=(1ll<<now)-1+my;
if(now>=l) break;
}
printf("%lld\n",max(r|now,r|l));
}
}
return 0;
}
T2 答题
思路：因为\(2^20\)是可接受的，所以考虑折半搜索。
代码如下：
AC_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define head heeead
#define next neet
using namespace std;
const int N=50;
const int M=2e6+10;
int n,s1,s2,cnt_1,cnt_2;
double p;
int a[N];
int c1[M],c2[M];
bool vis[N];
ii read()
{
int x=0;char ch=getchar();bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
iv dfs_1(int st)
{
if(st>(n/2))
{
int ans=0;
for(re i=1;i<=(n/2);i++) if(vis[i]) ans+=a[i];
c1[++cnt_1]=ans;
return;
}
vis[st]=1,dfs_1(st+1);
vis[st]=0,dfs_1(st+1);
}
iv dfs_2(int st)
{
if(st>n)
{
int ans=0;
for(re i=s2;i<=n;i++) if(vis[i]) ans+=a[i];
c2[++cnt_2]=ans;
return;
}
vis[st]=1,dfs_2(st+1);
vis[st]=0,dfs_2(st+1);
}
signed main()
{
freopen("answer.in","r",stdin),freopen("answer.out","w",stdout);
n=read();
cin>>p;
for(re i=1;i<=n;i++) a[i]=read();
s1=1,s2=(n/2)+1;
dfs_1(s1);
for(re i=1;i<=n;i++) vis[i]=0;
dfs_2(s2);
sort(c1+1,c1+cnt_1+1),sort(c2+1,c2+cnt_2+1);
double pos=p*(double) (1ll<<n);
int now=(1ll<<n)-ceil(pos)+1;
int L=0,R=c1[cnt_1]+c2[cnt_2],d=0,out;
while(L<=R)
{
int mid=(L+R)>>1;
int t2=cnt_2;
d=0;
for(re i=1;i<=cnt_1;i++)
{
while(c1[i]+c2[t2]>=mid and t2) --t2;
d+=cnt_2-t2;
}
if(d>=now) L=mid+1,out=mid;
else R=mid-1;
}
printf("%lld\n",out);
return 0;
}
T3 联合权值？改
思路：计算以每个点为中转点的答案，进行累加，更新最大值即可。可以用\(vector\)存储，用\(bitset\)判断连边
代码如下：
AC_code
#include<bits/stdc++.h>
#define ll long long
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define head heeead
#define next neet
using namespace std;
const int N=3e4+10;
const int M=6e4+10;
const int INF=1e8;
int n,m,t,tot;
bitset<30010> BS[30010];
vector<int> v[30010];
ll maxx,sum;
ll w[N];
ii read()
{
int x=0;char ch=getchar();bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
signed main()
{
freopen("link.in","r",stdin),freopen("link.out","w",stdout);
n=read(),m=read(),t=read();
int x,y;
for(re i=1;i<=m;i++)
{
x=read(),y=read();
BS[x][y]=1,BS[y][x]=1;
v[x].push_back(y),v[y].push_back(x);
}
for(re i=1;i<=n;i++) w[i]=read();
for(re i=1;i<=n;i++)
{
for(re j=0;j<v[i].size();j++)
{
for(re k=j+1;k<v[i].size();k++)
{
if(!BS[v[i][j]][v[i][k]])
{
maxx=max(maxx,w[v[i][j]]*w[v[i][k]]);
sum+=w[v[i][j]]*w[v[i][k]];
}
}
}
}
sum=sum*2ll;
if(t==1)
{
if(maxx) printf("%lld\n0",maxx);
else printf("-1\n0");
}
else if(t==2) printf("0\n%lld\n",sum);
else
{
if(maxx) printf("%lld\n%lld\n",maxx,sum);
else printf("-1\n0");
}
return 0;
}
T4 主仆见证了 Hobo 的离别
代码如下：
AC_code
#include<bits/stdc++.h>
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define head heeead
#define next neet
using namespace std;
const int N=5e5+10;
int n,m,cnt,timi,tot;
struct node
{
int x,y;
}cun[N];
int to[N<<1],next[N<<1],head[N];
int fa[N],size[N],son[N],top[N],deep[N];
int B[N],J[N],st[N],be[N];
bool vis[N],in[N];
ii read()
{
int x=0;char ch=getchar();bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
iv add(int x,int y)
{
to[++tot]=y;
next[tot]=head[x];
head[x]=tot;
}
ii get_B(int x) {return B[x]==x?x:B[x]=get_B(B[x]);}
ii get_J(int x) {return J[x]==x?x:J[x]=get_J(J[x]);}
iv dfs(int st,int f,int g)
{
vis[st]=1;
be[st]=g;
fa[st]=f;
size[st]=1;
deep[st]=deep[f]+1;
for(re i=head[st];i;i=next[i])
{
int p=to[i];
if(vis[p]) continue;
dfs(p,st,g);
size[st]+=size[p];
son[st]=(size[son[st]]>size[p])?son[st]:p;
}
}
iv dfs2(int st,int t)
{
top[st]=t;
if(!son[st]) return;
dfs2(son[st],t);
for(re i=head[st];i;i=next[i])
{
int p=to[i];
if(p==fa[st] or p==son[st]) continue;
dfs2(p,p);
}
}
ii get_lca(int x,int y)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(deep[x]<deep[y]) swap(x,y),swap(fx,fy);
x=fa[fx],fx=top[x];
}
return deep[x]<deep[y]?x:y;
}
signed main()
{
freopen("friendship.in","r",stdin),freopen("friendship.out","w",stdout);
n=read(),m=read();
for(re i=1;i<=500000;i++) B[i]=J[i]=i;
int opt,k,x;
timi=n;
for(re i=1;i<=m;i++)
{
opt=read();
if(opt==0)
{
opt=read(),k=read();
++timi;
if(opt==1)
{
for(re j=1;j<=k;j++)
{
x=read();
add(timi,x);
in[x]=1;
int fx=get_B(x);
B[fx]=timi;
if(k==1) J[get_J(x)]=timi;
}
}
else
{
for(re j=1;j<=k;j++)
{
x=read();
add(timi,x);
in[x]=1;
int fx=get_J(x);
J[fx]=timi;
if(k==1) B[get_B(x)]=timi;
}
}
}
else
cun[++cnt]=(node){read(),read()};
}
for(re i=1;i<=timi;i++)
if(!vis[i] and !in[i]) dfs(i,0,i),dfs2(i,i);
for(re i=1;i<=cnt;i++)
{
int x=cun[i].x,y=cun[i].y;
if(be[x]!=be[y] or be[x]==0 or be[y]==0) printf("0\n");
else
{
int lca=get_lca(x,y);
if(lca==x)
{
int fx=get_J(x),fy=get_J(y);
(fx==fy)?printf("1\n"):printf("0\n");
}
else if(lca==y)
{
int fx=get_B(x),fy=get_B(y);
(fx==fy)?printf("1\n"):printf("0\n");
}
else printf("0\n");
}
}
return 0;
}