首页 > 其他分享 >题解 CF980B

题解 CF980B

时间:2023-02-16 16:56:25浏览次数:33  
标签:障碍物 上且 题解 矩阵 CF980B 条数 对称 define

前言:

关于原题目中的 “旅馆” 这一用词,个人感觉用起来十分不畅,于是下文中将会用 “障碍物” 一词来代指旅馆。

题目大意:

有一座 \(4 \times n\) 的矩阵,然后让你放置障碍物(其中,障碍物不能放置到矩阵的边缘,换句话说,障碍物只能放到位于中央的 \(2 \times (n-1)\) 这一子矩阵中),使其保证从左上到右下的最短路径条数和从左下到右上的最短路径条数一致.

问能否构造出相应的矩阵,如果能,输出“YES”并输出构造出来的矩阵,否则输出“NO”。

题目保证 \(\boldsymbol{n}\) 为奇数

题目分析:

这道题显然有很多种做法,我这里来讲一讲我的做法,我的做法是:我们只需要保证障碍物在矩阵中保持对称,就能保证其最短路径条数一致。

理由是显然的(但我不会证),因为此时能保持对称的矩阵一共就如下几种:

  1. 障碍物都在一行且左右对称分布。
  2. 障碍物在两行上且上下对称分布。
  3. 障碍物在两行上且左右对称分布(保证第一行填满了)。
  4. 障碍物在两行上且左右对称分布(不保证第一行填满)

其中,第 \(2,3,4\) 种是显然的,因为都相当于堵住了在同样的位置被障碍物堵死了。

至于第一种,不会证,但是浅浅的跑了一下从 \(3 \sim 99\) 的程序来验证了一下,发现确实没啥问题,所以可以放心大胆的用这一条性质。

综上,我们的做题思路是:

  1. 若 \(k\) 为偶数,则可以构造第 \(2\) 类矩阵。
  2. 若 \(k\) 为奇数,则先尝试构造第 \(1\) 类矩阵,若第一行被填满后还有剩余,则在尝试构造第 \(3\) 类矩阵。

代码实现:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define TIME_LIMIT (time_t)1e3
#define dbg(x) cerr<<#x<<": "<<x<<endl;
bool block[100][100];
signed main() {
    ios::sync_with_stdio(false);
#ifdef LOCAL
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
    time_t cs = clock();
#endif
//========================================
    int n,k;
    cin>>n>>k;
    cout<<"YES"<<endl;
    if(!(k&1)){
        for(int i=2;i<=1+k/2;i++){
            block[2][i] = 1;
            block[3][i] = 1;
        }
    }
    else{
        int row = 2;
        while(k>(n-2)){
            for(int i=2;i<=n-1;i++)
                block[row][i] = 1;
            k-=n-2;
            row++;
        }
        int space = n-2-k;
        for(int i=2;i<=1+k/2;i++)
            block[row][i] = 1;
        if(k&1){
            int center = n/2+1;
            block[row][center] = 1;
        }
        for(int i=2+k/2+space+(k&1);i<=n-1;i++)
            block[row][i] = 1;
    }
    for(int i=1;i<=4;i++){
        for(int j=1;j<=n;j++){
            if(block[i][j])
                cout<<'#';
            else
                cout<<'.';
        }
        cout<<'\n';
    }
    cout<<endl;
//========================================
#ifdef LOCAL
    fclose(stdin);
    fclose(stdout);
    time_t ce = clock();
    cerr<< "Used Time: " << ce-cs << " ms."<<endl;
    if(TIME_LIMIT<ce-cs)
        cerr<< "Warning!! Time exceeded limit!!"<<endl;
#endif
    return 0;
}

标签:障碍物,上且,题解,矩阵,CF980B,条数,对称,define
From: https://www.cnblogs.com/larry76/p/17127358.html

相关文章

  • MASA Stack 1.0 发布会 —— 社区问题解答
    MASAStack1.0圆桌讨论Q1: 全职开源的团队,你们的收入是什么?1.首先感谢我们的金主朗诗德公司,朗诗德是一家大型的净水器研发、生产、销售的公司,我们的产品也在朗诗德公......
  • ABC222H 题解
    很久之前我问joke3579有没有什么水黑,然后他给我了这个题。小推一波。题解看到这种东西首先找找有没有什么性质。简单分析可以得出一棵美丽的\(n\)阶二叉树一定满足如......
  • zfs 之 `label is missing` 问题解决方法.
    具体报错信息status:Oneormoredevicescouldnotbeusedbecausethelabelismissingorinvalid.Sufficientreplicasexistforthepooltocontinue......
  • abc289F 题解
    某人vp时10min口胡了这道题,然后调了两天,第一天卡在WA4,第二天WA7WA10交相辉映,心态快崩了,因此写了这篇题解。\(a=b\)处理有借鉴这篇题解。firstobservation......
  • P7468 愤怒的小N 题解
    P7468愤怒的小N题解首先发现答案等于\[\sum_{i=0}^{n-1}[cnt(i)\&1]\cdotf(i)\\\]其中\(cnt(x)\)为\(x\)在二进制表示下\(1\)的个数。考虑从高到低枚举第一个......
  • AtCoder Beginner Contest 272 题解
    AtCoderBeginnerContest272Solution目录AtCoderBeginnerContest272Solution更好的阅读体验戳此进入题面链接题面Luogu链接abcd跳了[ABC272E]AddandMex题面S......
  • [ABC272F] Two Strings 题解
    [ABC272F]TwoStringsSolution目录[ABC272F]TwoStringsSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面给定两字符串$S,T$,求......
  • CF819D Mister B and Astronomers 题解
    CF819DMisterBandAstronomersSolution目录CF819DMisterBandAstronomersSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面存在......
  • P9064 [yLOI2023] 苦竹林 题解
    洛谷P9064[yLOI2023]苦竹林题意给定一个数列$a$,找一个最小的整数$ε$,使得$a$存在一个长度为$m$的子数列(可以不连续)$b\(,\)b$中任意两数之差的......
  • [ABC267D] Index × A(Not Continuous ver.) 题解
    [ABC267D]Index×A(NotContinuousver.)Solution目录[ABC267D]Index×A(NotContinuousver.)Solution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体......