[考试反思]0929csp-s模拟测试55：消逝

菜得过分。

面对T1的大板子不知所措，然后T2的贪心不小心把排序语句删了。。。

T1这种大模板啊。。。其实我是觉得我能打出来的，然后先用一个小时码了一个2k。

然后做T2想贪心就出来了。十分钟码完T3暴力之后回T1打对拍瞬间爆炸。

于是又重新打了一个2k，WA0。对拍发现。

然后考试就没几分钟了交暴力走了。

不要打完就跑，记得早点对拍改进思路。

T1：联

的确是挺裸的线段树。离散化或者权值线段树都可以。

但是考场上两个都打出来都死了。

最后用离散化A的。

 #include<cstdio>

 #include<unordered_map>

 #include<algorithm>

 using namespace std;

 #define inf 10000001

 unordered_map<long long,int>M;

 int m,cnt,k[];long long x[],l[],r[],re[];

 struct Segment_Tree{

     int cl[],cr[],lz[],lzxor[],w0[],w1[];

     void build(int p,int l,int r){

         cl[p]=l;cr[p]=r;lz[p]=-;w0[p]=l;w1[p]=inf;

         if(l==r)return;

         build(p<<,l,l+r>>);build(p<<|,(l+r>>)+,r);

     }

     void up(int p){w0[p]=min(w0[p<<],w0[p<<|]);w1[p]=min(w1[p<<],w1[p<<|]);}

     void down(int p){

         if(lz[p]!=-){

             lz[p<<]=lz[p],lz[p<<|]=lz[p];

             lzxor[p<<]=lzxor[p<<|]=;

             if(lz[p])w1[p<<]=cl[p<<],w1[p<<|]=cl[p<<|],w0[p<<]=w0[p<<|]=inf;

             else w1[p<<]=w1[p<<|]=inf,w0[p<<]=cl[p<<],w0[p<<|]=cl[p<<|];

             lz[p]=-;

         }else if(lzxor[p]){

             if(lz[p<<]!=-)lz[p<<]^=;else lzxor[p<<]^=;

             if(lz[p<<|]!=-)lz[p<<|]^=;else lzxor[p<<|]^=;

             swap(w1[p<<],w0[p<<]);

             swap(w1[p<<|],w0[p<<|]);

             lzxor[p]=;

         }

         up(p);

     }

     void set(int p,int l,int r,int w){

         if(l<=cl[p]&&cr[p]<=r){

             lz[p]=w;lzxor[p]=;

             if(w)w1[p]=cl[p],w0[p]=inf;

             else w1[p]=inf,w0[p]=cl[p];

             return;

         }

         down(p);

         if(l<=cr[p<<])set(p<<,l,r,w);

         if(r>=cl[p<<|])set(p<<|,l,r,w);

         up(p);

     }

     void Xor(int p,int l,int r){

         if(l<=cl[p]&&cr[p]<=r){

             if(lz[p]!=-)lz[p]^=;else lzxor[p]^=;

             swap(w0[p],w1[p]);

             return;

         }

         down(p);

         if(l<=cr[p<<])Xor(p<<,l,r);

         if(r>=cl[p<<|])Xor(p<<|,l,r);

         up(p);

     }

 }Tree;

 main(){

     scanf("%d",&m);

     for(int i=;i<=m;++i)scanf("%d%lld%lld",&k[i],&l[i],&r[i]),x[i]=l[i],x[m+i]=r[i],x[m+m+i]=r[i]+;

     sort(x+,x++m+m+m);

     for(int i=;i<=m*;++i)if(x[i]!=x[i-])M[x[i]]=++cnt,re[cnt]=x[i];

     for(int i=;i<=m;++i)l[i]=M[l[i]],r[i]=M[r[i]];

     if(M.find()==M.end()){for(int i=;i<=m;++i)puts("");return ;}

     Tree.build(,,cnt);Tree.lz[]=;

     for(int i=;i<=m;++i){

         if(k[i]==)Tree.set(,l[i],r[i],);

         if(k[i]==)Tree.set(,l[i],r[i],);

         if(k[i]==)Tree.Xor(,l[i],r[i]);

         printf("%lld\n",re[Tree.w0[]]);

     }

 }

思路积累：

线段树模板

T2：赛

三分其实不完全正确。虽然secret证明了单峰性质，但是ooo给出了函数值在谷底以外的地方不严格单调的例子。

直接贪心的话我们会发现决策有点复杂而且还可能会反悔。

但是其实只有四种物品，它们内部先排一下序（一定要排序啊啊啊）

根据数据范围的提示，两人都喜欢的物品是特殊的。

然后如果我们确定了两人都喜欢的物品的选择数量，剩下的贪心决策就好说了。

总费用关于它是个单峰函数（非严格）。

注意左右端点。

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 struct ps{

     int c1,c2;long long v;

     friend bool operator<(ps a,ps b){return a.v<b.v;}

 }p[];

 int n,m,k,a,b,n0,n1,n2,n3;long long v[],c1[],c2[];

 long long q0[],q1[],q2[],q3[],ans=100000000000000000ll;

 long long chk(int p){

     long long tot=,lft=m-k-(k-p);

     for(int i=;i<=p;++i)tot+=q3[i];

     for(int j=;j<=k-p;++j)tot+=q1[j]+q2[j];

     int p0=,p1=k-p+,p2=k-p+;

     while(lft--)

         if(q0[p0]<q1[p1]&&q0[p0]<q2[p2])tot+=q0[p0],p0++;

         else if(q1[p1]<q2[p2])tot+=q1[p1],p1++;

         else tot+=q2[p2],p2++;

     ans=min(ans,tot);//printf("%d %lld\n",p,tot);

     return tot;

 }

 main(){

     scanf("%d%d%d",&n,&m,&k);

     for(int i=;i<=n;++i)scanf("%lld",&v[i]);

     scanf("%d",&a);for(int i=,x;i<=a;++i)scanf("%d",&x),c1[x]=;

     scanf("%d",&b);for(int i=,x;i<=b;++i)scanf("%d",&x),c2[x]=;

     for(int i=;i<=n;++i)

         if(c1[i]&&c2[i])q3[++n3]=v[i];

         else if(c1[i])q1[++n1]=v[i];

         else if(c2[i])q2[++n2]=v[i];

         else q0[++n0]=v[i];

     sort(q0+,q0+n0+);

     sort(q1+,q1+n1+);

     sort(q2+,q2+n2+);

     sort(q3+,q3+n3+);

     q0[n0+]=q1[n1+]=q2[n2+]=1000000000000ll;

     int l=,r=n3;

     l=max(l,max(k-n1,k-n2));l=max(l,*k-m);//printf("%d %d\n",l,r);

     if(l>r){puts("-1");return ;}

     while(l<r-)if(chk(l+r>>)<chk((l+r>>)+))r=l+r>>;else l=l+r>>;

     for(int i=l;i<=r;++i)chk(i);

     printf("%lld\n",ans);

 }

贪心
单峰函数三分
这两个知识点总在一起出现？

T3：题

见下发题解。

挺神仙的。

 #include<cstdio>

 #include<bitset>

 using namespace std;

 bitset<>B[];

 int n,m,a[],b[],ans;

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;++i)scanf("%d%d",&a[i],&b[i]);

     for(int i=;i<=n;++i)B[i][i]=;

     for(int i=;i<=n;++i)for(int j=m;j;--j)

         if(B[i][a[j]]&&B[i][b[j]]){B[i].reset();break;}

         else if(B[i][a[j]]&&!B[i][b[j]])B[i][b[j]]=;

         else if(B[i][b[j]]&&!B[i][a[j]])B[i][a[j]]=;

     for(int i=;i<=n;++i)if(B[i].any())for(int j=i+;j<=n;++j)if(B[j].any()&&(B[i]&B[j]).none())ans++;

     printf("%d\n",ans);

 }

什么时候才能回到原来的状态啊。。。

为什么会这么菜啊。。。

可是我好像会做啊。。。

巴特西

[考试反思]0929csp-s模拟测试55：消逝

最新文章

热门文章