T1 最大或
$T1$因为没有开$1ll$右移给炸掉了，调了一年不知道为啥，最后实在不懂了
换成$pow$就过掉了，但是考场上这题耽误了太多时间，后面的题也就没办法好好打了。。。。
以后一定要注意右移左移要加$1ll$
思路的话我的做法比较麻烦，就是开一个指针$pos$每次跳到下一个数是$0$的$1$的下一个（也就是指向那个$0$）
然后判断左边界或上从$pos$那一位开始后面都是$1$的那个数，如果不超过右边界，就给左边界或上那个数
最后再和右边界或便可得到答案，复杂度没分析，$log$级别的怎么跑都可以
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 int T,l,r,pos,cnt,n,ans;
5 int vis[100],bit[100];
6 inline void task(){
7 int ans=0;
8 for(int i=l;i<=r;i++) for(int j=i;j<=r;j++) ans=max(ans,i|j);
9 printf("%lld\n",ans);
10 }
11 namespace WSN{
12 inline short main(){
13 freopen("maxor.in","r",stdin);
14 freopen("maxor.out","w",stdout);
15 scanf("%lld",&T);
16 while(T--){
17 scanf("%lld%lld",&l,&r);
18 if(r<=500){task();continue;}
19 memset(vis,0,sizeof(vis));
20 memset(bit,0,sizeof(bit));
21 n=r,pos=1,ans=l,cnt=0;
22 while(n){
23 if(n&1) vis[pos]=1;
24 else bit[++cnt]=pos;
25 n>>=1; ++pos;
26 } --pos;
27 for(int i=cnt;i;i--){
28 int pw=pow(2,bit[i]-1),tmp=ans|pw;
29 if(tmp>r) continue;
30 ans=tmp;
31 } printf("%lld\n",(ans|r));
32 }
33 return 0;
34 }
35 }
36 signed main(){return WSN::main();}
View Code
T2 答题
题目转化都不会，一看貌似是概率题就跳了
但是不是概率题。。。
题目可以转化为求任意多个数的和组成的集合中排名第$k$大的数是几，其中$k=\lceil P\times 2^n \rceil$
那么可以$\textit{meet in the middle}$，处理出两个数组后排序，然后二分$k$的取值
判断的时候使用经典指针扫一遍就可以了，不用调，样例对了一遍过
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 #include<cmath>
6 #define int long long
7 using namespace std;
8 namespace AE86{
9 inline int read(){
10 int x=0,f=1;char ch=getchar();
11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
13 }inline void write(int x,char opt='\n'){
14 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
15 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
16 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
17 }using namespace AE86;
18 int n,k,a[41],U,s1[1100000],s2[1100000],mid,mx,mn=1e18;
19 int l1,l2;
20 double P;
21 inline void work(int l,int r,int *s){
22 for(int i=l;i<=r;i++){
23 for(int j=1;j<=n;j++)
24 if(i&(1ll<<j-1)) s[i]+=a[j];
25 mx=max(mx,s[i]); mn=min(mn,s[i]);
26 }
27 }
28 inline bool check(int x){
29 int pos=l2,tmp=0;
30 for(int i=1;i<=l1;i++){
31 while(s1[i]+s2[pos]>=x)--pos;
32 tmp+=l2-pos; if(tmp>(1ll<<n)-k) return 1;
33 } return 0;
34 }
35 namespace WSN{
36 inline short main(){
37 freopen("answer.in","r",stdin);
38 freopen("answer.out","w",stdout);
39 n=read(); scanf("%lf",&P); k=ceil(P*pow(2,n));
40 mid=n/2;l1=(1ll<<mid); l2=(1ll<<n-mid);
41 for(int i=1;i<=n;i++) a[i]=read();
42 sort(a+1,a+n+1);
43 for(int i=0;i<l1;i++){
44 for(int j=1;j<=mid;j++)
45 if(i&(1ll<<j-1)) s1[i+1]+=a[j];
46 mx=max(mx,s1[i+1]); mn=min(mn,s1[i+1]);
47 }
48 for(int i=0;i<l2;i++){
49 for(int j=mid+1;j<=n;j++)
50 if(i&(1ll<<(j-mid)-1)) s2[i+1]+=a[j];
51 mx=max(mx,s2[i+1]); mn=min(mn,s2[i+1]);
52 }
53 sort(s1+1,s1+l1+1); sort(s2+1,s2+l2+1);
54 int l=mn,r=mx,ans=l;
55 while(l<=r){
56 int mid=(l+r)>>1;
57 if(check(mid)) l=mid+1,ans=mid;
58 else r=mid-1;
59 }
60 write(ans);
61 return 0;
62 }
63 }
64 signed main(){return WSN::main();}
View Code
T3 联合权值？改
不懂$1s$如何跑$9e8$，但他就是快（我敢说放在$Waitingcoders$上连$50$都没有）
硬开$bitset$当邻接矩阵用，然后$n^3$枚举点判断是否有连边，然后就过了？？？？（大雾）
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<bitset>
5 #include<vector>
6 typedef long long LL;
7 using namespace std;
8 const int NN=30001;
9 inline int read(){
10 int x=0,f=1;char ch=getchar();
11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
13 return x*f;
14 }
15 inline int max_(int a,int b){return a>b?a:b;}
16 int n,m,t,w[NN],sz[NN];
17 vector<int> e[NN];
18 bitset<NN> g[NN];
19 LL ans1,ans2;
20 namespace WSN{
21 inline short main(){
22 freopen("link.in","r",stdin);
23 freopen("link.out","w",stdout);
24 n=read(); m=read(); t=read();
25 for(int i=1,u,v;i<=m;++i){
26 u=read(),v=read(); g[u][v]=g[v][u]=1;
27 e[u].push_back(v); e[v].push_back(u);
28 }
29 for(int i=1;i<=n;++i) w[i]=read(),sz[i]=e[i].size()-1;
30 for(int i=1;i<=n;++i)
31 for(int j=0,y,v;j<sz[i];++j)
32 for(int k=j+1;k<e[i].size();++k) if(!g[e[i][j]][e[i][k]]){
33 y=e[i][k],v=e[i][j];
34 ans1=max_(ans1,w[y]*w[v]);
35 ans2+=2ll*w[y]*w[v];
36 }
37 if(t!=2) printf("%lld\n",ans1); else puts("0");
38 if(t!=1) printf("%lld\n",ans2); else puts("0");
39 return 0;
40 }
41 }
42 signed main(){return WSN::main();}
View Code
T4 主仆见证了Hobo的离别
挺妙的一道题
关于交($j$)并($b$)的操作可以建两棵树分别表示，
新加入的点就是原来几个点的父亲，关于$k=1$的操作两个树上都要连边
那么询问就转化为判断两点之间的链上关系是否一致
详情可以看学长博客，这一篇是单独出题解的，更加详细
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 #include<bitset>
6 using namespace std;
7 namespace AE86{
8 inline int read(){
9 int x=0,f=1;char ch=getchar();
10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
11 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
12 }inline void write(int x,char opt='\n'){
13 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
14 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
15 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
16 }using namespace AE86;
17 const int NN=500005;
18 int n,m,a[NN],tot,x,y,k,opt,op,cnt;
19 int jiao,bing; bool vis[NN];
20 struct SNOW{
21 int dfn[NN],siz[NN],num;
22 struct edge{int to,next;}e[NN<<1];int head[NN],rp;
23 inline void add(int x,int y){
24 e[++rp]=(edge){y,head[x]};head[x]=rp;
25 e[++rp]=(edge){x,head[y]};head[y]=rp;
26 }
27 inline void dfs(int f,int x){
28 siz[x]=1; dfn[x]=++num; vis[x]=1;
29 for(int i=head[x];i;i=e[i].next){
30 int y=e[i].to; if(f==y) continue;
31 dfs(x,y); siz[x]+=siz[y];
32 }
33 }
34 }ji,bi;
35 struct node{int x,y;}p[NN];
36 inline int get_ans(int x,int y){
37 if(ji.dfn[x]<=ji.dfn[y]&&ji.dfn[x]+ji.siz[x]>=ji.dfn[y]+ji.siz[y]) return 1;
38 if(bi.dfn[y]<=bi.dfn[x]&&bi.dfn[y]+bi.siz[y]>=bi.dfn[x]+bi.siz[x]) return 1;
39 return 0;
40 }
41 namespace WSN{
42 inline short main(){
43 freopen("friendship.in","r",stdin);
44 freopen("friendship.out","w",stdout);
45 cnt=n=read(); m=read();
46 for(int i=1;i<=m;i++){
47 opt=read();
48 if(opt) x=read(),y=read(),p[++tot]=node{x,y};
49 else{
50 op=read(),k=read(); ++cnt;
51 if(!op){
52 ++jiao;
53 for(int j=1,a;j<=k;j++){
54 a=read();
55 if(k>1) ji.add(a,cnt);
56 else ji.add(a,cnt),bi.add(a,cnt);
57 }
58 }else{
59 ++bing;
60 for(int j=1,a;j<=k;j++){
61 a=read();
62 if(k>1) bi.add(a,cnt);
63 else ji.add(a,cnt),bi.add(a,cnt);
64 }
65 }
66 }
67 }
68 for(int i=cnt;i;i--) if(!vis[i]) ji.dfs(0,i);
69 memset(vis,0,sizeof(vis));
70 for(int i=cnt;i;i--) if(!vis[i]) bi.dfs(0,i);
71 for(int i=1;i<=tot;i++) write(get_ans(p[i].x,p[i].y));
72 return 0;
73 }
74 }
75 signed main(){return WSN::main();}
View Code
于是今天的题很快就改完了，于是就又来了几个小可爱
行吧，接着搞。。。。。