首页 > 其他分享 >CF1898 C Colorful Grid 题解

CF1898 C Colorful Grid 题解

时间:2023-11-20 17:13:05浏览次数:37  
标签:ch int 题解 ret read Grid CF1898 getchar

Link

CF1898 C Colorful Grid

Question

image.png

给出一个 \(N\times M\) 的网格图

给每一条边染色(R/B),需要存在一条长度为 \(K\) 的路径从 \((1,1)\) 到 \((N,M)\),路径允许重复通过一个节点。

Solution

非常有意思的一道题

先考虑 \(K\) 满足的最小值,显然是 \((N-1)+(M-1)\) ,假设走 上->左 这样的路径

image.png

接着思考其他可行的 \(K\) 值,当到终点后,顺着一个格子转几圈显然也成立,所以对于一个可行的 \(K\), \(K+4c\) 也可行,\(c\) 为任意整数

image.png

当走在一条直线上,往下走一步,又往上走一步,显然也是成立的,所以对于一个可行的 \(K\) ,\(K+2\) 也成立

image.png

综上,\(K\%((N-1)+(M-1))\) 为 \(0\) 和 \(2\) 时 是 YES

Code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
const int maxn=20;

void solve(){
    int N=read(),M=read(),K=read();
    int lst=K-(N-1)-(M-1);
    if(lst<0||(lst%4!=0&&lst%4!=2)) {printf("NO\n");return;}
    int L[maxn][maxn]={0},C[maxn][maxn]={0};
    int tim=0;
    for(int i=1;i<M;i++) 
        {L[1][i]=tim,tim^=1;}    
    for(int j=1;j<N;j++) 
        {C[j][M]=tim,tim^=1;}
    L[N][M-1]=tim,tim^=1;
    C[N-1][M-1]=tim,tim^=1;
    L[N-1][M-1]=tim,tim^=1;

    tim=0;
    C[1][1]=tim,tim^=1;
    L[2][1]=tim,tim^=1;
    C[1][2]=tim,tim^=1;
    printf("YES\n");
    for(int i=1;i<=N;i++){
        for(int j=1;j<M;j++) printf("%c ",L[i][j]?'B':'R');
        printf("\n");
    }
    for(int i=1;i<N;i++){
        for(int j=1;j<=M;j++) printf("%c ",C[i][j]?'B':'R');
        printf("\n");
    }
}
int main(){
    // freopen("C.in","r",stdin);
    // freopen("C.out","w",stdout);
    int T=read();
    while(T--) solve();
    return 0;
}

标签:ch,int,题解,ret,read,Grid,CF1898,getchar
From: https://www.cnblogs.com/martian148/p/17844365.html

相关文章

  • CF1898 B Milena and Admirer 题解
    LinkCF1898BMilenaandAdmirerQuestion给出一个长度为\(n\)的序列\(a\),我们可以做一种操作使得\(a\)非降,操作是:对于一个\(a_i\)选择一个整数\(0\lex\lea_i\),用两个数\(x,(a_i-x)\)来替换\(a_i\)。求最小操作次数。Solution考虑哪些数是需要操作的,如......
  • CF1899 G Unusual Entertainment 题解
    LinkCF1899GUnusualEntertainmentQuestion给出一个排列\(p_i\)和一棵树,给出\(Q\)组询问,每组询问\([L,R,x]\)表示求\(p_L\simp_R\)上是否存在\(p_i\)在\(x\)的字数上。Solution这道题确实是一个好题。我们先考虑一个问题,怎么样才能判断子树,我们给书上的每个......
  • Windows端口占用问题解决
    查询被占用的端口进程8080为端口号netstat-ano|findstr8080杀掉线程14816为进程号taskkill/f/t/im14816......
  • easyui datagrid实现通用编辑
    functionBillEdit(Jquerygrd){varself=this;this.grd=Jquerygrdthis.editIndex=undefinedthis.GetCurrentIndex=function(){letindex=nullletrow=this.grd.datagrid("getSelected")if(row!=null)......
  • noip2023 题解(民间数据)
    P9868[NOIP2023]词典(民间)直接把每个串\(w_i\)都从大到小/从小到大排一下,记作\(a_i,b_i\)。如果\(b_i\)小于除了\(i\)之外的所有\(a_i\),说明可以,否则不行。求一个前后缀最大值即可。复杂度\(\mathcal{O}(26n+nm)\)。点击查看代码#include<bits/stdc++.h>usingname......
  • CF1898D - Absolute Beauty(绝对值)
    题目地址Solution考虑把\(|a_i-b_i|\)转化为数轴上的线段的一条线段,那么\(swap\)操作可以形象转化为下图(借用官方\(Editoral\))考虑最大的增加(第一张图的情况)即可。Summary学到了绝对值转线段,把指定操作形象化,数形结合(雾......
  • uniapp使用uni-grid时出现BUG第二次进入少一列
    在使用uniapp的uni-grid组件时,出现了一个bug,第一次进入页面是是显示正常的,第二次进入就会发送少一列的情况第一次进入时显示第二次进入时显示在网上找了半天没啥解决办法,最后是在dcloud社区中找到解决方法:1.把最外层的view固定宽度2.去掉边框因为我这边是需要进行对不同设......
  • 【洛谷 P1125】[NOIP2008 提高组] 笨小猴 题解(字符串+映射+集合)
    [NOIP2008提高组]笨小猴题目描述笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!这种方法的具体描述如下:假设是单词中出现次数最多的字母的出现次数,是单词中出现次数最少的字母的出现次数,......
  • [ABC326C] Peak 题解
    题目链接题目思路这个问题要求找到一个半开区间,使得在这个区间内包含尽可能多的礼物。首先,我们需要将输入的礼物坐标按照从小到大的顺序进行排序。然后,我们可以使用双指针的方法来寻找最佳的区间。代码以下是代码解释:#include<bits/stdc++.h>usingnamespacestd;constint......
  • [ABC328C] Consecutive 题解
    HelloWorld链接这道题是一个很明显的前缀和,我们把$sum_i$表示为前$i$个字符有多少个有重复,查询的时候就用$sum_{r-1}-sum_{l-1}$就行了。代码#include<bits/stdc++.h>usingnamespacestd;strings;intsum[300010];intmain(){ intn,q; cin>>n>>q>>s; for(in......