多校A层冲刺NOIP2024模拟赛02 csp-s模拟9

多校A层冲刺NOIP2024模拟赛02

四道题因为暑假被拉去当模拟赛 暑假集训CSP提高模拟22 了，遂直接把赛后代码交了上去，然后就被通知换题了。

原 \(100+100+100+20\) 被在 accoders NOI 上被卡成了 \(100+100+90+10\) ，更改 long long 和 int 后达到了 \(100+100+100+30\) 。

\(T1\) P318. 法阵

• 详见 暑假集训CSP提高模拟22 T1 P264. 法阵 。

\(T2\) P265. 连通块

• 详见 暑假集训CSP提高模拟22 T2 P265. 连通块 。

\(T3\) P266. 军队

• 详见 暑假集训CSP提高模拟22 T3 P266. 军队 。

\(T4\) P267. 棋盘

• 详见 暑假集训CSP提高模拟22 T4 P267. 棋盘 。

csp-s模拟9

\(T1\) T1075. 邻面合并 \(0pts\)

• 部分分
  • \(30 \%\) ：打表加手摸。
    • 该代码 仅手摸了 \(n,m \le 3\) 的数据，且不保证正确性。
• 正解

  • 观察到 \(\min \{ n,m \} \le 8\) ，考虑状压 \(DP\) 。

  • 具体地，以每一块的开头作为分割点，并记录作状态，总状态数为 \(2^{m}\) 。

    • 判断是否合法的一个重要标准是原矩阵中的 \(0\) 不可以是分割点，原矩阵的 \(1\) 若本身不是分割点则到前面最近的分割点直接不能有 \(0\) 。

  • 转移的时候枚举上一行的状态，计算达成这两行的分割方式需要新创建多少个块。较为简便的做法是拿本行块的总数减去与上一行分割方式相同的块数（可以直接合并的块），建议画图理解。

    • 图来自官方题解。

      

  • 时间复杂度为 \(O(nm2^{m})\) 。

    点击查看代码

    int a[120][10],f[110][1<<10],opt[110][10][1<<10];
    bool check(int hang,int s,int m)
    {int last=0;for(int i=0;i<=m-1;i++){if(((s>>i)&1)&&a[hang][i+1]==0){return false;}}for(int i=0;i<=m-1;i++){if((s>>i)&1){last=1;}if(a[hang][i+1]==0){last=0;}if(last==0&&a[hang][i+1]==1){return false;}}return true;
    }
    int work(int hang,int lie,int s)
    {while(a[hang][lie+1]==1&&((s>>(lie-1+1))&1)==0){lie++;}return lie;
    }
    int main()
    {freopen("merging.in","r",stdin);freopen("merging.out","w",stdout);int n,m,ans=0x7f7f7f7f,sum,i,j,k,h;cin>>n>>m;for(i=1;i<=n;i++){for(j=1;j<=m;j++){cin>>a[i][j];}}memset(f,0x3f,sizeof(f));f[0][0]=0;for(i=0;i<=(1<<m)-1;i++){f[0][i]=0;}for(k=1;k<=n;k++){for(i=0;i<=(1<<m)-1;i++){if(check(k,i,m)==true){for(j=1;j<=m;j++){opt[k][j][i]=work(k,j,i);}}}}for(k=1;k<=n;k++){for(i=0;i<=(1<<m)-1;i++){if(check(k,i,m)==true){for(j=0;j<=(1<<m)-1;j++){if(check(k-1,j,m)==true) {sum=__builtin_popcount(i);for(h=0;h<=m-1;h++){if(((i>>h)&1)&&((j>>h)&1)){sum-=(opt[k][h+1][i]==opt[k-1][h+1][j]);}}f[k][i]=min(f[k][i],f[k-1][j]+sum);}}}}}for(i=0;i<=(1<<m)-1;i++){ans=min(ans,f[n][i]);}cout<<ans<<endl;fclose(stdin);fclose(stdout);return 0;
    }
    

\(T2\) T1076. 光线追踪 \(0pts\)

• 正解

\(T3\) T2186. 百鸽笼 \(0pts\)

• 原题： UOJ 390. 【UNR #3】百鸽笼
• 部分分

  • \(0pts\) ：爆搜。

    点击查看代码

    const ll p=998244353;
    ll a[50],aa[50],pos[50],inv[50],f[50];
    ll qpow(ll a,ll b,ll p)
    {ll ans=1;while(b){if(b&1){ans=ans*a%p;}b>>=1;a=a*a%p;}return ans;
    }
    void dfs(ll len,ll n,ll sum,ll mul,ll cnt)
    {if(len==sum){for(ll i=1;i<=n;i++){if(a[i]==1){f[i]=(f[i]+mul)%p;return;}}}else{for(ll i=1;i<=n;i++){if(a[i]>=1){a[i]--;dfs(len+1,n,sum,mul*inv[cnt]%p,cnt-(a[i]==0));a[i]++;}}}
    }
    int main()
    {freopen("c.in","r",stdin);freopen("c.out","w",stdout);ll n,sum=-1,i;cin>>n;for(i=1;i<=n;i++){cin>>a[i];sum+=a[i];inv[i]=qpow(i,p-2,p);}dfs(0,n,sum,1,n);for(i=1;i<=n;i++){cout<<f[i]<<" ";}fclose(stdin);fclose(stdout);return 0;
    }
    

\(T4\) T2188. 滑稽树下你和我 \(0pts\)

• 原题： UOJ 371. 【UR #17】滑稽树下你和我
• 部分分

  • \(5 \%\) ：输出 \(stx,sty\) 在图上的距离。

    点击查看代码

    struct node
    {int nxt,to;
    }e[2010];
    int head[2010],du[2010],cnt=0;
    double x[2010],y[2010];
    void add(int u,int v)
    {cnt++;e[cnt].nxt=head[u];e[cnt].to=v;head[u]=cnt;
    }
    double work(double x1,double y1,double x2,double y2)
    { return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
    }
    int main()
    {freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);int n,u,v,stx,sty,i;double ans=0x7f7f7f7f;cin>>n>>stx>>sty;for(i=1;i<=n;i++){cin>>x[i]>>y[i];}for(i=1;i<=n-1;i++){cin>>u>>v;add(u,v);add(v,u);du[u]++;du[v]++;}printf("%.8lf\n",work(x[stx],y[stx],x[sty],y[sty]));fclose(stdin);fclose(stdout);return 0;
    }
    

总结

• \(T1\) 不会写爆搜，打表程序出的结果都是手动判断的。
• \(T2\) 做法假了，把矩形覆盖当成了点的覆盖，询问直接死掉，从一开始的暴力到 map 套动态开点线段树、珂朵莉树都 \(RE,MLE,TLE,WA\) 了。
• \(T4\) 两点间距离公式炸 int 了，挂了 \(20pts\) 。

后记