NOIP 模拟 七十七
100+60+95+30; T4 一个变量打错挂了40。。
T1 最大或
考虑从高到低枚举𝑟的二进制位，然后和𝑙的对应二进制位进行比较。如果两
者相同，那么不论怎么选择𝑥,𝑦，答案在这个位置上的值一定和𝑟在这个位置上的
值相同；否则，一定有𝑟在这个位置上是1，而𝑙在这个位置上是0。那么，我们只
需要选择𝑦 = 𝑟，而𝑥 = (…011…1)2即可，其中𝑥前面省略号的部分表示𝑙,𝑟二进
制表示相同的部分。以此进行答案计算即可。
考试时没有严谨的证明，感觉固定 r 好像是对的，试了好几组数据全部调整了出来，然后就按照这个思路打的。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,l,r,lim[61],maxn,need[61],limm[69],zhi[66];
inline void dfs(int x,int lim1,int lim2,int val)
{ maxn=max(maxn,r|val);if(x==-1)return;
int be=0,en=1;if(lim1)en=lim[x];if(lim2)be=limm[x];
if(!lim1 and !lim2){val|=(zhi[x]);maxn=max(maxn,r|val);return;}
for(int i=be;i<=en;++i)dfs(x-1,(lim1 and i==lim[x]),(lim2 and i==limm[x]),i?val|(1ll<<x):val);
}
signed main()
{ freopen("maxor.in","r",stdin);
freopen("maxor.out","w",stdout);
scanf("%lld",&T);
for(int i=0;i<=59;++i)zhi[i]=zhi[i-1]+(1ll<<i);
while(T--)
{ scanf("%lld%lld",&l,&r);
maxn=r;memset(lim,0,sizeof(lim));memset(limm,0,sizeof(limm));
for(int i=59;i>=0;--i)lim[i]=((r&(1ll<<i))!=0),limm[i]=((l&(1ll<<i))!=0);
dfs(60,1,1,0);printf("%lld\n",maxn);
}
}
T2 答题
本道题的实质其实是求用所给的𝑛个数组成的2:个数中的第𝑘大值。其中𝑘 =
𝑐𝑒𝑖𝑙(2:×𝑃)。
直接枚举显然不能通过，所以我们需要进行折半枚举，即枚举求出前:
3个数可
以组成的所有值，以及后:
3个数可以组成的所有值。二分需要求的第𝑘大值是多少，
这样，题目相当于求从前:
3个数组成的所有值以及后:
3个数组成的所有值中各取出
一个数，并且两个数的和大于等于二分值的数对有多少组。对两部分从小到大进
行排序，并按顺序枚举第一部分选择的数，则第二部分中可以选择的数落在第二
部分的一个后缀中，并且随着第一部分的枚举值越来越大，这个后缀也越来越大。
使用指针进行线性扫描即可。
想到了转化为划分 k 大值，也想到了middle，然后就罢工了。。。。今天状态不好，脑子热。。
#include<bits/stdc++.h>
#define int long long
using namespace std;
double p,dd=1;
int a[41],n,siz,sum=0,maxn,w1[(1<<20)+10],w2[(1<<20)+10],U1,U2,tot1,tot2,lim;
inline bool check(int x)
{ int res=0;int zhi=U2;
for(int i=1;i<=U1;++i)
{ while(zhi and w1[i]+w2[zhi]>x)--zhi;
res+=zhi;
}
return res>=lim;
}
signed main()
{ freopen("answer.in","r",stdin);
freopen("answer.out","w",stdout);
scanf("%lld %lf",&n,&p);
for(int i=1;i<=n;++i)scanf("%lld",&a[i]),siz+=a[i];
U1=(1<<n/2);U2=(1<<(n+1)/2);
for(int i=1;i<=n/2;++i)w1[1<<i-1]=a[i];
for(int i=1;i<=(n+1)/2;++i)w2[1<<i-1]=a[i+n/2];
for(int i=1;i<U1;++i)if(!w1[i])w1[i]=w1[i&(-i)]+w1[i^(i&(-i))];
for(int i=1;i<U2;++i)if(!w2[i])w2[i]=w2[i&(-i)]+w2[i^(i&(-i))];
sort(w1+1,w1+1+U1);sort(w2+1,w2+1+U2);
lim=ceil(p*(1ll<<n));
cout<<lim<<endl;
int l=0,r=siz,ans=0;
while(l<=r)
{ int mid=(l+r)>>1;
if(check(mid))ans=mid,r=mid-1;
else l=mid+1;
}
printf("%lld\n",ans);
}
T3 联合权值?改
本题的正解复杂度为𝑂(𝑚-.M)。
先提出一个结论：在一个有𝑚条边的图中，三元环的个数为𝑂(𝑚-.M)的。显然
一个点数为𝑂(𝑚N.M)的完全图可以使得三元环个数取到这个上界，但是这是对边
的利用率最高的一种做法，你无法找到一个利用率更高的图。
第一问（求最大值）：枚举点𝑤，将和它相邻的点按权值从大到小排序。接着
二重循环枚举点对（即枚举点𝑢,𝑣），每次枚举𝑢时，𝑣如果可行（𝑢 −𝑤 −𝑣是(𝑢,𝑣)
之间的一条最短路）就停止枚举。否则一定是找到了一个三元环(𝑢,𝑣,𝑤)。所以
总的失败枚举数不会超过𝑂(𝑚-.M)。如果使用哈希来判定是否失败，就可以做到
单次判定失败𝑂(1)，总复杂度𝑂(𝑚-.M)。
第二问（求和）：枚举点𝑤，求出和𝑤相邻的点的权值的和的平方，再减去和
𝑤相邻的点的权值的平方的和。在没有三元环的情况下，上述操作就可以正确求
出答案。再把三元环纳入考虑，即扣掉因三元环产生的非法联合权值。
考虑按如下方式寻找三元环：对于每个点𝑎进行一次预处理，求出和𝑎相邻的，
并且点的度数大于𝑎，或者点的度数和𝑎相同，但点的编号大于𝑎的点。接着，枚
举点𝑢，再枚举与𝑢相邻的满足上述条件的点𝑣，再枚举与𝑣相邻的满足上述条件
的点𝑤，然后使用哈希算法判断(𝑢,𝑣,𝑤)是否构成三元环。如果构成三元环，则我
们可以把该三元环产生的三种联合权值从答案中扣去。我们可以分析一下这么做
的复杂度：枚举点𝑢和𝑣的总复杂度应该是𝑂(𝑚)的。如果𝑣的度数不超过𝑚N.M，则
枚举第三个点的时间不超过𝑂(𝑚N.M)；否则𝑤的个数应该不超过𝑂(𝑚N.M)（因为度
数总和是𝑂(𝑚)的，所以度数超过𝑚N.M的点数应该是𝑚N.M的）。实际上，上述做法
可以直接证明“在一个有𝑚条边的图中，三元环的个数为𝑂(𝑚-.M)的”这一个结论。
综上，本题做法的总复杂度是𝑂(𝑚-.M)的。
然而暴力可以撵过，由于评测机波动，掉了 5 分。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans2,ans1,t,val[40001];
vector<int>p[40001];
set<int>st[40001];
signed main()
{ freopen("link.in","r",stdin);
freopen("link.out","w",stdout);
scanf("%lld%lld%lld",&n,&m,&t);
for(int i=1;i<=m;++i)
{ int a,b;scanf("%lld%lld",&a,&b);
p[a].push_back(b);p[b].push_back(a);
st[a].insert(b);st[b].insert(a);
}
ans1=-1;
for(int i=1;i<=n;++i)scanf("%lld",&val[i]);
for(int i=1;i<=n;++i)
for(int j=0;j<p[i].size();++j)
for(int k=j+1;k<p[i].size();++k)
{ int u=p[i][j],v=p[i][k];
if(st[u].find(v)!=st[u].end())continue;
ans1=max(ans1,val[u]*val[v]);
ans2+=val[u]*val[v];
}
if(t!=2)cout<<ans1<<endl;
else puts("0");
if(t!=1)cout<<ans2*2<<endl;
else puts("0");
}
T4 主仆见证了 Hobo 的离别
考场暴力建边暴力搜，应该是平方复杂度，预估七十分，然而。。
for(int j=1;j<=k;++j)scanf("%d",&a[k]);直接干废了。。
真不知道我是怎么打的，状态极差。
正解同样建树，如果无祖先关系，肯定不行。否则就是一路交，另一种是一路并。并查集不会用，用了倍增。
#include<bits/stdc++.h>
using namespace std;
int n,m,tot,a[500001],id[500001],du[500001],zhi,siz[500001],dfn[500001],rt,cnt,f[500001][24],fa[500001][24],dep[500001];
vector<int>p[500001];
queue<int>Q;pair<int,int>t[500001];
bool vis[500001];
inline void dfs(int x,int ff)
{ f[x][0]=id[ff];fa[x][0]=ff;siz[x]=1;dfn[x]=++cnt;dep[x]=dep[ff]+1;
for(int i=1;i<=23;++i)fa[x][i]=fa[fa[x][i-1]][i-1],f[x][i]=f[fa[x][i-1]][i-1]|f[x][i-1];
for(auto i:p[x])if(i!=ff)dfs(i,x),siz[x]+=siz[i];
}
inline int work(int x,int y)
{ if(dfn[x]>=dfn[y] and dfn[x]+siz[x]<=dfn[y]+siz[y])
{ int ii=0;
for(int i=23;i>=0;--i)if(dep[fa[x][i]]>=dep[y])ii|=f[x][i],x=fa[x][i];
return (ii!=3 and ii!=1);
}
if(dfn[x]<=dfn[y] and dfn[x]+siz[x]>=dfn[y]+siz[y])
{ int ii=0;
for(int i=23;i>=0;--i)if(dep[fa[y][i]]>=dep[x])ii|=f[y][i],y=fa[y][i];
return (ii!=2 and ii!=3);
}
return 0;
}
signed main()
{ freopen("friendship.in","r",stdin);
freopen("friendship.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)id[i]=i;tot=n;
for(int i=1;i<=m;++i)
{ int opt,op,k,x,y;
scanf("%d",&opt);
if(opt==1)
{scanf("%d%d",&x,&y);t[++zhi]=make_pair(x,y);}
else
{ scanf("%d%d",&op,&k);
for(int j=1;j<=k;++j)scanf("%d",&a[j]);
int ii=id[a[1]];
if(k==1){id[++tot]=0;p[tot].push_back(a[1]);p[a[1]].push_back(tot);du[a[1]]++;continue;}
++tot;
if(op==0)
{ id[tot]=1;
for(int j=1;j<=k;++j)p[tot].push_back(a[j]),p[a[j]].push_back(tot),++du[a[j]];
}
else
{ id[tot]=2;
for(int j=1;j<=k;++j)p[tot].push_back(a[j]),p[a[j]].push_back(tot),++du[a[j]];
}
}
}
rt=tot+1;
for(int i=1;i<=tot;++i)if(!du[i]){p[rt].push_back(i);p[i].push_back(rt);}
dfs(rt,0);
for(int i=1;i<=zhi;++i)printf("%d\n",work(t[i].first,t[i].second));
}
