[考试反思]1111csp-s模拟测试110：三思
分类:
IT文章
•
2022-08-26 12:42:55
![[考试反思]1111csp-s模拟测试110：三思](/default/index/img?u=aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2NvbW1vbi8xNzA4MDA0LzIwMTkxMS8xNzA4MDA0LTIwMTkxMTExMTkxMTA2NzU2LTI5NzAyNTk0My5wbmc= "[考试反思]1111csp-s模拟测试110：三思")
题目名是为了照应3天的倒计时（我才不会说是因为我考场又摸鱼了）
在OJ上得到了295的好成绩，但是本地评测没有O2掉了10分。
总体来说还可以。T1全场切，T2半场切，T3纯暴力不卡常都有95。。。
又是AK场，做的不够好。
如上所述，有点摸鱼了。但是T3说是原题。。。正解的思想的确也想不到。。。
啊，总之，还有3天，加油吧！
这一场是Day1，和明天一起记分，和前面比起来还是落后了一些，Day2加油吧
T1：最大或
半结论题，很好想。
首先对于lr相同的部分最后的答案也一定与之相同。
最高的不同位，两个数分别取1/0，然后后面的位数都取0/1，这就是最优决策。
![]()
1 #include<cstdio>
2 int main(){
3 freopen("maxor.in","r",stdin);freopen("maxor.out","w",stdout);
4 int t;long long l,r,ans;
5 scanf("%d",&t);
6 while(t--){ans=0;
7 scanf("%lld%lld",&l,&r);
8 for(int i=59;~i;--i)
9 if((l&1ll<<i)==(r&1ll<<i))ans|=l&1ll<<i;
10 else {ans+=(1ll<<i+1)-1;break;}
11 printf("%lld
",ans);
12 }
13 }
这题有代码？
T2：答题
看到数据范围：40？肯定折半搜索meet in middle
meet in middle+two pointers板子题。
暴力思路就是分别处理前后20位，然后枚举前面的$2^{20}$个数lower_bound。
复杂度为$O(2^{20} imes 20 imes log 40000000)$
考场上在这里卡了一会，想卡常，计算发现处理前18位/后22位的总复杂度更低。
预处理：$O(22 imes 2^{22})$(状压枚举+sort)
二分答案：$O(26 imes 22 imes 2^{18})$(二分答案+lower_bound)
据说starsing用这种方式AC了。
正解：可以发现lower_bound挺蠢的，如果你把前几位也排序的话，那么后几遍的指针移动就是单调的了。
一个two pointers解决问题。
![]()
1 #include<cstdio>
2 #include<iostream>
3 #include<algorithm>
4 #include<cmath>
5 using namespace std;
6 int n,w[42],pre,suf,W[1048577],V[1048577],tot;long double p;
7 bool chk(int s){
8 int ptr=1<<suf;long long totp=0;
9 for(int i=0;i<1<<pre;++i){
10 while(ptr&&V[ptr-1]+W[i]>s)ptr--;
11 totp+=ptr;
12 }
13 return totp*pow(0.5,n)>=p;
14 }
15 int main(){
16 freopen("answer.in","r",stdin);freopen("answer.out","w",stdout);
17 cin>>n>>p;
18 for(int i=1;i<=n;++i)cin>>w[i],tot+=w[i];
19 pre=n>>1;suf=n-pre;
20 for(int i=0;i<1<<pre;++i)for(int j=0;j<pre;++j)if(i&1<<j)W[i]+=w[j+1];
21 for(int i=0;i<1<<suf;++i)for(int j=0;j<suf;++j)if(i&1<<j)V[i]+=w[j+pre+1];
22 sort(W,W+(1<<pre));sort(V,V+(1<<suf));
23 int l=0,r=tot,ans;
24 while(l<=r)if(chk(l+r>>1))r=ans=l+r>>1,r--;else l=(l+r>>1)+1;
25 cout<<ans<<endl;
26 }
View Code
T3：联合权值·改
![]()
1 #include<cstdio>
2 #include<bitset>
3 #include<ctime>
4 using namespace std;
5 int max(int a,int b){return a>b?a:b;}
6 bitset<30001>B[30001];
7 int w[30001],fir[30001],l[60002],to[60002],ec,n,m,t,mx;long long tot;
8 void link(int a,int b){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;}
9 int main(){
10 freopen("link.in","r",stdin);freopen("link.out","w",stdout);
11 scanf("%d%d%d",&n,&m,&t);
12 for(int i=1,a,b;i<=m;++i)scanf("%d%d",&a,&b),B[a][b]=B[b][a]=1,link(a,b),link(b,a);
13 for(int i=1;i<=n;++i)scanf("%d",&w[i]),B[i][i]=1;
14 for(int i=1;i<=n;++i){
15 if(t==1&&clock()>950000)return printf("%d
0
",mx),0;
16 for(int j=fir[i];j;j=l[j])for(int k=fir[to[j]];k;k=l[k])
17 if(!B[i][to[k]])tot+=w[i]*w[to[k]],mx=max(mx,w[i]*w[to[k]]);
18 }
19 printf("%d
%lld
",t==2?0:mx,t==1?0:tot);
20 }
95分暴力
好题。难题。（呃，乱搞不算）
如果写正解的话数据范围开到100000，权值出到10000，内存卡到8MB都是可做的。
但是出题人比较仁慈数据又小又水，让很多人多拿了不少分数～（就像我的95分暴力）
但是暴力归暴力，得分归得分。还是要承认：正解的确很牛逼%%%skyh
正解可以做到在任何题目里以$O(m^{1.5})$的复杂度求出图里的所有三元环。（无自环/重边），思路值得积累。
以前都是bitset$O(frac{mn}{32})$暴干的，没什么水平。
首先一个结论是三元环个数不会超过$O(m^{1.5})$。因为在完全图里会达到上届。
对于所有点，我们将其按照度数排序，度数相同的要内部严格有序。得到每个点的排名。
然后重新建边，边只从排名小的连向大的。
这样的话我们枚举每一个点i，找出所有出边j，再找出所有到达点的出边k，检查i，k两点之间是否有边即可。
这样的话，对于每个度数大于根号的点j，它们的总出边小于等于m，而每个点的入边小于根号，所以总数小于$m sqrt{m}$
如果一个点的度数小于根号，那么它们的总入边小于等于m，而每个点的出边小于根号，所以总数小于$m sqrt{m}$
这样，计算总值的时候，枚举每一个点计算其邻点的和的平方减去平方的和，再取出三元环贡献即可。
计算最大值时，从大到小枚举邻点（二重循环），遇到非三元环就跳出。因为三元环不超过$msqrt{m}$所以总复杂度也是$m sqrt{m}$
代码也好写。是道好题。
![]()
1 #include<bits/stdc++.h>
2 using namespace std;
3 bitset<30001>B[30001];
4 struct Q{int p,w;friend bool operator<(Q x,Q y){return x.w>y.w;}}q[30001];
5 vector<Q>v[30001];
6 struct P{int deg,ord;friend bool operator<(P x,P y){return x.deg>y.deg;}}p[30005];
7 int w[30001],fir[30001],l[60002],to[60002],ec,n,m,t,mx,FIR[30001],L[60002];
8 int deg[30005],TO[60002],rk[30002],EC;long long tot;
9 void link(int a,int b){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;deg[b]++;}
10 void LINK(int a,int b){L[++EC]=FIR[a];FIR[a]=EC;TO[EC]=b;}
11 int main(){
12 freopen("link.in","r",stdin);freopen("link.out","w",stdout);
13 scanf("%d%d%d",&n,&m,&t);
14 for(int i=1,a,b;i<=m;++i)scanf("%d%d",&a,&b),B[a][b]=B[b][a]=1,link(a,b),link(b,a);
15 for(int i=1;i<=n;++i)scanf("%d",&w[i]),B[i][i]=1,p[i]=(P){deg[i],i},q[i]=(Q){i,w[i]};
16 sort(p+1,p+1+n);
17 for(int i=1;i<=n;++i)rk[p[i].ord]=i;
18 for(int i=1;i<=n;++i)for(int j=fir[i];j;j=l[j])if(rk[to[j]]<rk[i])LINK(i,to[j]);
19 for(int i=1;i<=n;++i){
20 long long sum=0;
21 for(int j=fir[i];j;j=l[j])tot-=w[to[j]]*w[to[j]],sum+=w[to[j]];
22 tot+=sum*sum;
23 }
24 for(int i=1;i<=n;++i)for(int j=FIR[i];j;j=L[j])for(int k=FIR[TO[j]];k;k=L[k])
25 if(B[i][TO[k]])tot-=w[i]*w[TO[j]]+w[TO[j]]*w[TO[k]]+w[i]*w[TO[k]]<<1;
26 for(int i=1;i<=n;++i)for(int j=fir[i];j;j=l[j])v[i].push_back(q[to[j]]);
27 for(int i=1;i<=n;++i)sort(v[i].begin(),v[i].end());
28 for(int i=1;i<=n;++i)for(int j=0;j<v[i].size();++j)for(int k=j+1;k<v[i].size();++k)
29 if(!B[v[i][j].p][v[i][k].p]){mx=max(mx,v[i][j].w*v[i][k].w);break;}
30 else if(v[i][j].w*v[i][k].w<=mx)break;
31 printf("%d
%lld
",t==2?0:mx,t==1?0:tot);
32 }
View Code
