noip模拟77 solutions
关于我因为牙的原因一直分心导致我考不好这件事
都怪我，太担心这个牙了
但是这一场的教训还是挺多的
比如说，算内存这件事，我第二题内存直接炸了
T1 最大或
这个肯定是要选最大的那一个，
因为如果你要高位，最大的一定可以最大限度的满足你
低位完全可以选那些小一点的
这样的话我们直接枚举每一位，看左右边界的当前位是否相同
如果遇到不同的了，那么一定是左边界当前位是0，右边界是1
那么我们直接吧后面所有位(不包括当前位)全变成1，直接或起来就好了
AC_code
#include<bits/stdc++.h>
using namespace std;
#define oj
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int T,l,r;
signed main(){
#ifdef oj
freopen("maxor.in","r",stdin);
freopen("maxor.out","w",stdout);
#endif
//cout<<(1ll<<60)<<endl<<1000000000000000000ll<<endl;
scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&l,&r);
int now=0;
fu(j,60,0){
if(((l>>j)&1ll)==((r>>j)&1ll))now|=((l>>j)&1ll)<<j;
else now|=(1ll<<j)-1;
}
printf("%lld\n",now|r);
}
}
T2 答题
一开始以为最大的体积是1e6，然后我算着空间能开下啊
觉得这个题有点过于水了，打了个背包就走了
后来回来看的时候发现还要乘个40，直接乘上就走了，\(MLE\)
这个正解就是\(meet\ in\ the\ middle\)
分别对前20和后20处理，然后直接二分+单调指针
AC_code
#include<bits/stdc++.h>
using namespace std;
#define oj
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=45;
const int M=(1<<20)+10;
int n,s[N],ans;
int sum,num,u1,u2;
int dp1[M],wh1[M],dp2[M],wh2[M];
long double p;
bool check(int x){
int it=(1<<u2)-1,sum=0;
fo(i,0,(1<<u1)-1){
while(it>=0&&dp1[i]+dp2[it]>x)it--;
sum+=it+1;
}
return 1.0*sum<1.0*(1ll<<n)*p;
}
signed main(){
#ifdef oj
freopen("answer.in","r",stdin);
freopen("answer.out","w",stdout);
#endif
scanf("%lld%Lf",&n,&p);
fo(i,1,n)scanf("%lld",&s[i]);
u1=n>>1,u2=n+1>>1;
fo(i,1,n>>1)wh1[1<<(i-1)]=s[i];
fo(i,1,n+1>>1)wh2[1<<(i-1)]=s[i+(n>>1)];
fo(i,0,(1<<u1)-1)dp1[i]=dp1[i-(i&-i)]+wh1[(i&-i)];
fo(i,0,(1<<u2)-1)dp2[i]=dp2[i-(i&-i)]+wh2[(i&-i)];
sort(dp1+0,dp1+(1<<u1));
sort(dp2+0,dp2+(1<<u2));
// pr1[0]=dp1[0];fo(i,1,(1<<u1)-1)pr1[i]=pr1[i-1]+dp1[i];
// pr2[0]=dp2[0];fo(i,1,(1<<u2)-1)pr2[i]=pr2[i-1]+dp2[i];
int l=0,r=N*M,mid;
while(l<r){
mid=l+r>>1;
if(check(mid))l=mid+1;
else r=mid;
}
printf("%lld",r);
return 0;
}
T3 联合权值
这个？？\(bitset\)暴力水过
好像复杂度是对的？？
AC_code
#include<bits/stdc++.h>
using namespace std;
#define oj
#define ll long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=30002;
bitset<N> bit[N],tmp;
int n,m,t;
int fr[N],tr[N],val[N];
vector<int> edg[N];
int maxn;
ll sum[N],sumn;
bool comp(int x,int y){
return val[x]>val[y];
}
signed main(){
#ifdef oj
freopen("link.in","r",stdin);
freopen("link.out","w",stdout);
#endif
//cout<<((sizeof(bit)+sizeof(edg)+sizeof(fr)*4)>>20)<<endl;
scanf("%d%d%d",&n,&m,&t);
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
fr[i]=x;tr[i]=y;
edg[x].push_back(y);
edg[y].push_back(x);
bit[x].set(y);
bit[y].set(x);
}
fo(i,1,n)scanf("%d",&val[i]);
fo(i,1,m){
sum[fr[i]]+=val[tr[i]];
sum[tr[i]]+=val[fr[i]];
}
fo(i,1,n){
sumn+=1ll*sum[i]*sum[i];
sumn-=1ll*val[i]*val[i]*(bit[i].count());
}
for(int i=1,x,y,s;i<=m;i++){
x=fr[i];y=tr[i];
tmp=bit[x]&bit[y];
s=tmp.count();
sumn-=2ll*s*val[x]*val[y];
}
if(t==2){printf("0\n%lld",sumn);return 0;}
fo(x,1,n){
sort(edg[x].begin(),edg[x].end(),comp);
int u,v;
fo(i,0,(int)edg[x].size()-1){
fo(j,i+1,(int)edg[x].size()-1){
u=edg[x][i];
v=edg[x][j];
if(val[u]*val[v]<maxn)break;
if(bit[u][v]==1)continue;
maxn=val[u]*val[v];
}
}
}
if(t==1)sumn=0;
printf("%d\n%lld",maxn,sumn);
}
T4 主仆见证了 Hobo 的离别
考试的时候就没有好好读题，导致脑子里一点思路都没有
每个点最多融合一次
AC_code
#include<bits/stdc++.h>
using namespace std;
#define oj
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=500005;
int n,m;
int tp,op,k;
vector<int> cho[N];
int to[N],nxt[N],val[N],head[N],rp;
void add_edg(int x,int y,int z){
to[++rp]=y;
val[rp]=z;
nxt[rp]=head[x];
head[x]=rp;
}
struct dsu{
int fa[N];
dsu(){fo(i,1,N-5)fa[i]=i;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy)fa[fx]=fy;
}
}t0,t1;
bool vis[N];
int dfn[N],cnt,dfm[N];
void dfs(int x){
vis[x]=true;dfn[x]=++cnt;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(val[i]&1)t0.merge(y,x);
if(val[i]&2) t1.merge(y,x);
dfs(y);
}
dfm[x]=cnt;
}
signed main(){
#ifdef oj
freopen("friendship.in","r",stdin);
freopen("friendship.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
fo(i,1,m){
scanf("%d",&tp);
cho[i].push_back(tp);
if(tp==0){
scanf("%d%d",&op,&k);n++;
if(op==0)op=1;
else op=2;
if(k==1)op=3;
fo(j,1,k){
int x;
scanf("%d",&x);
add_edg(n,x,op);
}
}
if(tp==1){
scanf("%d%d",&op,&k);
cho[i].push_back(op);
cho[i].push_back(k);
}
}
fu(i,n,1)if(!vis[i])dfs(i);
fo(i,1,m){
if(cho[i][0]){
int x=cho[i][1],y=cho[i][2];
bool flag=false;
if(dfn[x]<=dfn[y]&&dfn[y]<=dfm[x]){
int top=t0.find(y);
//cout<<top<<endl;
if(dfn[top]<=dfn[x]&&dfn[x]<=dfm[top])flag=true;
}
if(dfn[y]<=dfn[x]&&dfn[x]<=dfm[y]){
int top=t1.find(x);
//cout<<top<<endl;
if(dfn[top]<=dfn[y]&&dfn[y]<=dfm[top])flag=true;
}
if(flag)printf("1\n");
else printf("0\n");
}
}
}