[考试反思]1110csp-s模拟测试109：细节

细节。。。决定成败

T2数组开小，T3long long没开够。

而且其实不止这样，考试结束前15分钟发现了好多低错：

T3双向边没开2倍。dfs没递归调用。T2为了调试bitset开20没改（后来改成了6000，虽说还是错的但是还是好了不少）

一定要手模几个样例测一下。严格注意数组大小

最后几天了，一定要注意这种细节了。

T1：Adore

状压，dp。

复杂度$O(mk \times 2^k)$不够优但是足以通过。

 #include<cstdio>

 int add(int &a,int b){a+=b;if(a>=)a-=;}

 int cntbit[],m,k,dp[][],E[],NE[],ans;

 int re(){register char ch=getchar();

     while(ch<''||ch>'')ch=getchar();

     return ch-'';

 }

 int main(){

     freopen("adore.in","r",stdin);freopen("adore.out","w",stdout);

     for(int i=;i<;++i)cntbit[i]=cntbit[i^i&-i]+;

     scanf("%d%d",&m,&k);m-=;

     int st=,ths=,nxt=;

     for(int i=;i<k;++i)st|=re()<<i;

     dp[nxt][st]=;

     while(m--){

         ths^=;nxt^=;

         for(int i=;i<<<k;++i)dp[nxt][i]=;

         for(int i=;i<k;++i)E[i]=NE[i]=;

         for(int i=;i<k;++i)for(int j=,x;j<k;++j)x=re(),E[i]|=x<<j,NE[j]|=x<<i;

         for(int s=;s<<<k;++s)if(dp[ths][s]){

             int tst=,ntst=;

             for(int i=;i<k;++i)if(s&<<i)tst^=E[i],ntst^=NE[i];

             add(dp[nxt][tst],dp[ths][s]);add(dp[nxt][ntst],dp[ths][s]);

         }

     }st=;

     for(int i=;i<k;++i)st|=re()<<i;

     for(int i=;i<<<k;++i)if(!(cntbit[st&i]&))add(ans,dp[nxt][i]);

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

 }

T2：Confess

手动构造，发现交集大于n的很多。所以采用随机化。注意数组大小。

 #include<bits/stdc++.h>

 using namespace std;

 bitset<>B[];

 int n,k;char s[];

 int main(){

     freopen("confess.in","r",stdin);freopen("confess.out","w",stdout);

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

     while(s[k])k++;

     int cnt=;

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

         int x=s[i]-;

         for(int j=;j<&&cnt<=n<<;++j)B[][cnt]=(x&<<j?:),cnt++;

     }

     for(int I=;I<=n+;++I){

         scanf("%s",s);

         int cnt=;

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

             int x=s[i]-;

             for(int j=;j<&&cnt<=n<<;++j)B[I][cnt]=(x&<<j?:),cnt++;

         }

     }

     srand(time());

     while(){

         int a=rand()%(n+)+,b=rand()%(n+)+;

         while(a==b)b=rand()%(n+)+;

         if((B[a]&B[b]).count()>=n>>)return printf("%d %d\n",a,b),;

     }

 }

T3：Repulsed

设dp[i][j]表示距离i这个点j条边的需要灭火器的子节点有多少个。Idp[i][j]表示距离i点有j条边的还没用完的灭火器还能用几次。

在一棵子树内，互相消除，然后上传。

如果有的点dp[i][k]>0而Idp[i][0]=0那么就需要申请新的灭火器。

从远到近依次解决需求，不断上传。最后在1号节点特殊处理：不管剩下多少需求都要直接申请灭火器解决。

注意Idp数组需要开longlong。

 #include<bits/stdc++.h>

 using namespace std;

 int n,k,s,fir[],l[],to[],ec,ans,dp[][];long long Idp[][];

 void link(int a,int b){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;}

 void dfs(int p,int fa){

     dp[p][]++;

     for(int i=fir[p];i;i=l[i])if(to[i]!=fa){

         dfs(to[i],p);

         for(int j=;j<k;++j)dp[p][j+]+=dp[to[i]][j],Idp[p][j+]+=Idp[to[i]][j];

     }

     while(dp[p][k]>Idp[p][])Idp[p][]+=s,ans++;

     for(int i=k;~i;--i)for(int j=k-i;~j;--j){

         int x=min(1ll*dp[p][i],Idp[p][j]);

         dp[p][i]-=x;Idp[p][j]-=x;

     }

     if(p==){

         int totcnt=;

         for(int i=;i<=k;++i)totcnt+=dp[p][i];

         while(totcnt>)totcnt-=s,ans++;

     }

 }

 int main(){

     freopen("repulsed.in","r",stdin);freopen("repulsed.out","w",stdout);

     scanf("%d%d%d",&n,&s,&k);if(s>n)s=n;

     for(int i=,a,b;i<n;++i)scanf("%d%d",&a,&b),link(a,b),link(b,a);

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

 }

这是错的！！！

上述算法稍伪。当且仅当需求距离和灭火器距离加和为k或k-1时才会配对，否则就可以上传，以后再匹配。

上传答案一定不会变差，反而可能找到更优的匹配。

要注意根节点就可以随意匹配了。

代码基本没有变。同时时间复杂度也下降到了$O(nk)$

 #include<bits/stdc++.h>

 using namespace std;

 int n,k,s,fir[],l[],to[],ec,ans,dp[][];long long Idp[][];

 void link(int a,int b){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;}

 void dfs(int p,int fa){

     dp[p][]++;

     for(int i=fir[p];i;i=l[i])if(to[i]!=fa){

         dfs(to[i],p);

         for(int j=;j<k;++j)dp[p][j+]+=dp[to[i]][j],Idp[p][j+]+=Idp[to[i]][j];

     }

     while(dp[p][k]>Idp[p][])Idp[p][]+=s,ans++;

     for(int i=k;i>=((p==)?:k-);--i)for(int j=i;~j;--j){

         int x=min(1ll*dp[p][j],Idp[p][i-j]);

         dp[p][j]-=x;Idp[p][i-j]-=x;

     }

     if(p==){

         int totcnt=;

         for(int i=;i<=k;++i)totcnt+=dp[p][i];

         while(totcnt>)totcnt-=s,ans++;

     }

 }

 int main(){

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

     for(int i=,a,b;i<n;++i)scanf("%d%d",&a,&b),link(a,b),link(b,a);

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

 }

真正的AC代码

自家OJ数据水了，去BZOJ1117自测吧。（送个链接）

巴特西

[考试反思]1110csp-s模拟测试109：细节

最新文章

热门文章