【Codeforces Round #693 (Div. 3) F】New Year's Puzzle
39 Codeforces div New round year
2023-09-14 09:03:41 时间
题目链接
翻译
给你一个 \(2*n\) 的方格,让你用 \(1*2\) 的骨牌,横着或者竖着放,铺满整个方格。
其中有一些被黑色方块阻挡,不能放骨牌。问你可不可行。
题解
首先考虑 整个方格 第一列,如果两行都是空的。
那么考虑第二列的几种情况:
- 第二列也是空的,那么第一列放竖的没问题。
- 第二列有一个方格被堵住了,那么第一列只能竖着放了,不然铺不满(注意这是第一列,它之前没有列了)
- 第二列有两个方格都被堵住了,那么第一列也同样是竖着放。
综上所述,第一列如果两行都是空的,那么就竖着放一个就行。
这样就可以不断地 \(Reduce\) 问题。然后如果新的第一列还是空的,就不断缩减。
当然,如果第一列两行都被堵住了,那么同样的也可以缩减问题,因为这一列不用放骨牌...
这样,我们的问题的第一列就总是只有一个方格被堵住的情况了。
这个时候我们只能放一个横的骨牌,会突出来一部分。而且,如果它的右边仍然是两行都是空着的情况,那么又得继续横着放一个。
直到遇到某个位置也恰好只有一行被堵住,则需要判断一下能不能刚好填满两行。所以中间的大概 \(n-m\) 个空格可以直接跳过。
这里能否填满两行的情况需要根据前后两个 只有一行被堵住 的列的坐标差的奇偶性来判断,为奇数,则被堵住的行号应该相同。否则,应该不同。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5;
const LL MOD = 1e9 + 7;
const int K = 5000;
int n, m;
map<int, int> dic;
int main() {
#ifdef LOCAL_DEFINE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0), cin.tie(0);
int T;
cin >> T;
while (T--) {
dic.clear();
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int r, c;
cin >> r >> c;
dic[c] |= (1 << (r - 1));
}
//reduce
map<int,int>::iterator it = dic.begin();
while (it != dic.end()) {
pair<int, int> temp = *it;
if (temp.second == 0 || temp.second == 3) {
m--;
it++;
continue;
}
else {
break;
}
}
if (it == dic.end()) {
cout << "YES" << endl;
continue;
}
//it.second == 2 || it.second == 1
pair<int,int> pre = (*it);
it++;
bool ok = true;
while (it != dic.end()) {
if (pre.second == 0 || pre.second == 3) {
pre = (*it);
it++;
continue;
}
int temp = (*it).second;
int delta = (*it).first - pre.first;
if (temp == 0) {
if (delta%2 == 0) {
pre.second = 3 - pre.second;
}
pre.first = (*it).first;
}
else if (temp == 1 || temp == 2){
if (delta % 2 == 0) {
if (temp != pre.second) {
}
else {
ok = false;
break;
}
}
else {
if (temp == pre.second) {
}
else {
ok = false;
break;
}
}
pre = *it;
pre.second = 3;
it++;
}
else {
//temp==3
if (pre.second != 0 && pre.second != 3) {
ok = false;
break;
}
it++;
}
}
if (!ok || pre.second == 1 || pre.second == 2) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
}
}
return 0;
}
相关文章
- ECharts整合HT for Web的网络拓扑图应用
- 自定义PHP页面跳转函数redirect($url, $time = 0, $msg = '')
- 【异常】 'ascii' codec can't decode byte 0xe8 in position 2: ordinal not in range(128)
- pycharm 'AttributeError: module 'thread' has no attribute 'start_new_thread''
- MS SQL Could not obtain information about Windows NT group/user 'domainlogin', error code 0x5. [SQLSTATE 42000] (Error 15404)
- Cannot assign to read only property 'exports' of object '#<Object>'
- [Typescript 4.9] 'in' operator
- 2. Using 'dp' instead of 'px' to set text size
- Mysql模糊查询 select count(*) from sys_invitation where from_id like '%1006%';
- Universal-image-loader Mason 修复版(ImageLoader Image can't be decoded)
- Attempt to write to field 'android.support.v4.app.FragmentManagerImpl android.support.v4.app.Fragment.mFragmentManager' on a null object reference
- Caused by: org.gradle.api.internal.artifacts.ivyservice.DefaultLenientConfiguration$ArtifactResolveException: Could not resolve all files for configuration ':classpath'.
- atitit.React 优缺点 相比angular react是最靠谱的web ui组件化方案了
- atitit.线程死锁 卡住无反应 的原因in cmd调用的解决方案 v3 q39
- Atitit.一些公司的开源项目 重大知名开源项目attilax总结
- Atitit.收银机小票打印功能的设计 java php c#.net版本
- Atitit.java swing打印功能 api attilax总结
- atitit。流程图的设计与制作 attilax 总结
- 【Good Bye 2020 F】Euclid's nightmare
- 【Codeforces 118B】Caesar's Legions
- Unable to update the EntitySet 'T_JsAPI' because it has a DefiningQuery and no <InsertFunction> element exists in the <ModificationFunctionMapping> element to support the current operation.
- Android - 报错 More than one file was found with OS independent path 'META-INF/license.txt' 解决
- java.lang.Exception: 资源处理失败,失败原因:com.mysql.jdbc.exceptions.jdbc4.MySQLSyntaxErrorException: Unknown column '?????‰' in 'where clause'
- Why I don't want use JPA anymore
- 0x01 MySQL What's DataBase
- UVA 816 - Abbott's Revenge(BFS)
- 'org.hibernate.SQLQuery' is deprecated
- python 绘图 异常点绘制使用 ax.plot(abnormal_points['ds'], abnormal_points['y'], "rX", label='abnormal points')
- leetcode 119. Pascal's Triangle II
- ERROR 2002 (HY000): Can't connect to local MySQL server through socket '/var/run/mysqld/mysqld.sock'