首页 > 其他分享 >题解:CF1551D1 Domino (easy version)

题解:CF1551D1 Domino (easy version)

时间:2024-08-14 16:27:13浏览次数:12  
标签:frac int 题解 Domino cin times 偶数 version

题解:CF1551D1 Domino (easy version)

分析

题目中保证 \(n\times m\) 为偶数,下面进行分类讨论。

情况一

如果 \(n\) 和 \(m\) 都是偶数,那么可以分割成 \(\frac{n}{2}\times\frac{m}{2}\) 个 \(2\times2\) 的方块。

根据上图我们发现,只要 \(k\) 满足 \(0\le k\le \frac{n}{2}\times\frac{m}{2}\times 2\) 且 \(2 \mid k\),就一定可以凑出来。

情况二

如果 \(n\) 是奇数,\(m\) 是偶数,我们考虑把 \(n\) 变为偶数转化为第一种情况。

如上图,可以先在第一行排 \(\frac{m}{2}\) 个多米诺骨牌,这时如果 \(k<\frac{m}{2}\) 就无解,否则就直接转化为了第一种情况,此时 \(k\) 变为 \(k-\frac{m}{2}\)。

情况三

如果 \(n\) 是偶数,\(m\) 是奇数,我们考虑把 \(m\) 变为偶数转化为第一种情况。

如上图,可以先在第一列排 \(\frac{n}{2}\) 个多米诺骨牌。由于 \(k\) 的限制是横向的多米诺骨牌,所以 \(k\) 不变,转换为情况一。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
bool check(int a,int b,int c)
{
    if(c&1)return 0;
    if(c>(a/2)*(b/2)*2)return 0;
    return 1;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>k;
        if(!(n&1)&&!(m&1))
        {
            if(check(n,m,k))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
        else if((n&1)&&!(m&1))
        {
            if(k<m/2)
            {
                cout<<"NO"<<endl;
                continue;
            }
            k-=m/2;
            n--;
            if(check(n,m,k))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
        else if(!(n&1)&&(m&1))
        {
            m--;
            if(check(n,m,k))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
    }
    return 0;
}

标签:frac,int,题解,Domino,cin,times,偶数,version
From: https://www.cnblogs.com/RyanAdam/p/18359277

相关文章

  • 题解:CF685A Robbers' watch
    题解:CF685ARobbers'watch感觉这题难点主要在理解题意。题意一天\(n\)个小时,一小时\(m\)分钟,手表用\(7\)进制表示时间(位数未填满补前导零),求问这个手表显示的每一位数字都不一样的时刻数量。分析因为是\(7\)进制,所以每一个数字位只可能出现\(0\sim6\)这\(7\)种......
  • P8776 最长不下降子序列 题解
    Statement最长不下降子序列(LIS),但是有一次机会,让序列中连续\(k\)个数改成同一个数。\(n\le10^5,a_i\le10^6\).Solution记\(f(i)\)为以\(i\)结尾的LIS长度,\(g(i)\)为以\(i\)开始的LIS长度,可预处理.答案一定是\(f(i)+k+g(j)\)这样拼接起来的,其中\(i+k+1\le......
  • (CF 10D)最长公共上升子序列(LCIS)(要求输出序列) - 题解
    最长公共上升子序列(LCIS)原题链接:CodeForces、洛谷时间限制:C/C++1000MS,其他语言2000MS内存限制:C/C++256MB,其他语言512MB描述给定两个整数序列,写一个程序求它们的最长上升公共子序列。当以下条件满足的时候,我们将长度\(N\)的序列\(S_1,S_2,...,S_N\)称为长度为\(M......
  • 【题解】CF1942C1 Bessie's Birthday Cake (Easy Version)
    \(\mathfrak{1st.\Preamble\|}\)前言题目传送门:CF1942C1Bessie'sBirthdayCake(EasyVersion)。蒟蒻在洛谷上第一篇通过的题解。\(\mathfrak{2nd.\Reasoning\|}\)思路其实只需要把选中的点组成一个新的多边形,然后我们就可以发现有\(x\)个点的多边形可以连出\(x-2......
  • 【知识】并查集的单点删除 &【题解】SP5150
    \(\mathfrak{1st.}\)前言-->题目传送门<--原先这道题的难度是紫,我觉得题目翻译看不懂,就去讨论版发了个贴,然后题管更新了题目翻译,并且把难度降到了蓝……\(\mathfrak{2nd.}\)思路赶时间或嫌啰嗦的可以直接跳到『思路归纳』。我们先从普通并查集开始思考对于删除单点\(x\),......
  • 【问题解决】git status中文文件名乱码
    问题复现解决办法在gitbash中直接执行如下命令gitconfig--globalcore.quotepathfalse原因通过gitconfig--help可以查看到以下内容:core.quotePathCommandsthatoutputpaths(e.g.ls-files,diff),willquote"unusual"charactersinthepathnamebyencl......
  • 启动应用程序出现PCLXL.DLL找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个PCLXL.DLL文件(挑选合适的版本文件)把它放入......
  • 项目推荐——音频标注wavesurfer.js用法及相关问题解决
    一、前言上期推荐了文本标注poplar-annotation用法,这期针对音视频标注推荐wavesurfer.js库;Wavesurfer.js是一个基于WebAudioAPI和HTML5Canvas的开源音频可视化库,用于创建可交互、可定制的波形。同时拥有众多插件库。二、demo效果可以实现音视频播放暂停、指定区域......
  • 【实践问题】UART通信问题解决过程
    近期开发了一项通过UART进行读写操作的功能。说起来并不难,但是实际操作起来还是遇到了不少问题,解决问题也费了一番周折。因此记录下来作为积累,也供遇到类似问题的同学参考。问题背景当前的项目需要开发一项功能:BMC通过UART串口与另一设备通信,进行读写操作。听起来并不难,......
  • [CS61A] 学习记录六 Lab2 题解思路分享
    前言观前提示,笔者写的代码答案放在GitHub仓库中,此处仅记录过程与心得。此外,请最好在尝试独立完成该任务后再看本文,否则就很可能失去了体验本项目精华的机会正文Q1:WWPD:LambdatheFree有两个问题有点意思。lambda与参数>>>b=lambdax:lambda:x#Lambdascanr......