[考试反思]1004csp-s模拟测试59：惊醒

一句话：我看错考试时间了，我以为11：30结束，T2T3暴力没来得及交。

为什么考试的时间忽然变了啊。。。没转过来

一定要看清考试的起止时间！

虽说T2T3连爆搜都没打，只打特殊性质只有32分。爆搜分还挺高的。

当特殊性质不好扩展时，记得把爆搜打上。

本来是想T1先送上暴力，然后尝试肝T2，然后是T3暴力，有时间再回来优化T1。

但是整场考试时间是崩的，也没回T1。。。然而T2T3

注意分数与时间的权衡。

T1：Reverse

BFS。

二营长打法极其简单。因为是BFS所以一个点不会被多次更新。

那么一次更新了一个区间内的全部奇数或偶数，下次遇到的时候直接跳过就行了。

用链表实现，代码特别特别特别简单。常数也特别小，复杂度O(n)，相较于线段树优化建边还少个log。

 #include<iostream>

 using namespace std;

 int dt[],q[],R[],n,m,k,S,x;

 int main(){

     cin>>n>>k>>m>>S;

     for(int i=;i<=n;++i)dt[i]=n+,R[i]=i+;

     while(m--)cin>>x,dt[x]=-;

     dt[S]=;q[]=S;

     for(int h=,t=;h<=t;++h){

         int st=max(,q[h]-k+),l=st+st+k--q[h];st=min(n-k+,q[h]);int r=st+st+k--q[h];

         for(int i=l;i<=r;i=R[i])if(dt[i]>dt[q[h]]+)dt[i]=dt[q[h]]+,q[++t]=i;

         for(int i=l;i<=r;){int rr=R[i];R[i]=max(R[i],r);i=rr;}

     }

     for(int i=;i<=n;++i)cout<<(dt[i]>n?-:dt[i])<<" ";cout<<endl;

 }

T2：Silhouette

神仙数学题，考场上死在容斥上了。

无解的判定就是横纵最大值不同。

不然的话我们把读入序列排序，对答案没有影响。

从大到小扩展，扫每一种权值。

然后这种权值占据的是一个矩形或一个L形，并且要求这个区域内每行每列都恰好出现了这个值。

容斥，f[i]表示一共a行中至少i行不满足条件。

ABab表示的是一个A×B的矩形挖掉一个(A-a)×(B-b)的小矩形之后得到的L形，当前处理的数字是S。

$f[i]=\sum\limits_{i=0}^{a}C_a^i \times (S^i \times ( (S+1)^{A-i} - S^{A-i} ) )^b \times ( S^i \times (S+1)^{a-i} )^{B-b}$

这一类“至少”的容斥也没少做，容斥系数是$(-1)^i$

式子的含义是先选出是哪i行不合条件，$C_a^i$

接下来在A×b的矩阵里选合法的方案,

考虑每一列，其中这不合法的i行不出现数字S，所以是[0,S-1]里面选，$S^i$

然后剩下的行里面需要出现数字S，那就是瞎选的方案减去没出现S的方案，即$( (S+1)^{A-i} - S^{A-i} )$

每一列都是这样，所以要b次方

接下来需要计算那一个a×(B-b)的矩形，被限制不合法的i行还是不能放$S^i$，剩下的随便$(S+1)^{a-i}$

然后每一列都这样，要B-b次方

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define mod 1000000007

 #define int long long

 int pw(int b,int t,int a=){for(;t;t>>=,b=b*b%mod)if(t&)a=a*b%mod;return a;}

 bool com(int a,int b){return a>b;}

 int fac[],x[],n,y[],ans=,invv[],inv[];

 int C(int b,int t){return fac[b]*inv[t]%mod*inv[b-t]%mod;}

 int cal(int A,int B,int a,int b,int s){

     int tot=;

     for(int i=;i<=a;++i)tot=(tot+pw(mod-,i)*C(a,i)%mod*pw(s,B*i)%mod*pw(pw(s+,A-i)-pw(s,A-i)+mod,b)%mod*pw(pw(s+,a-i),B-b))%mod;

     return tot%mod+mod;

 }

 main(){

     fac[]=inv[]=inv[]=fac[]=invv[]=;

     for(int i=;i<=;++i)fac[i]=fac[i-]*i%mod,invv[i]=mod-mod/i*invv[mod%i]%mod,inv[i]=inv[i-]*invv[i]%mod;

     scanf("%lld",&n);

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

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

     sort(x+,x++n,com);sort(y+,y++n,com);

     int p1=,p2=;

     while(p1<=n||p2<=n){

         int num=max(x[p1],y[p2]),cnt1=,cnt2=;

         while(p1<=n&&x[p1]==num)p1++,cnt1++;

         while(p2<=n&&y[p2]==num)p2++,cnt2++;

         ans=ans*cal(p1-,p2-,cnt1,cnt2,num)%mod;

     }

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

 }

Tips：感谢王hecao更正。

T3：Seat

skyh倾情压行注释。

巴特西

[考试反思]1004csp-s模拟测试59：惊醒

最新文章

热门文章