B. Berland Crossword (构造)

男娘i 2021-07-16 15:28 288阅读 0赞

[题目][Link 1]

对于下面这个图可以知道当U涂中间三个时是不会对其它的三种产生限制的，而如果涂了4个则必然会占到L R其中一个相邻的格子，涂了5个必然会占掉相邻的L R两个格子，这样就产生了限制，我们只需把不满足限制的情况为NO，其余为YES即可。我们来看满足条件的情况，假如Un,Dn，得出L>=2 R>=2，因为必然会占掉L R两个相邻的格子，如果L或R为n，则L>=1 R>=1.假如U或D有一个=n-1，那么L R必然有一个格子会被占掉，得出L+R>=2\*(U D等于n的个数)+1\*（U D等于n-1的个数)，对于U Ｄ 的判断也类似。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]Code:

#include<iostream>
    using namespace std;
    typedef long long ll;
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n, s, y, x, z;cin >> n >> s >> y >> x >> z;
    		int q = 0, f = 0, ans = 1;
    		if (y == n)q++;
    		if (z == n)q++;
    		if (y == n - 1)f++;
    		if (z == n - 1)f++;
    		if (s < q || x < q)ans = 0;
    		if (s + x < f+2*q)ans = 0;
    		q = 0, f = 0;
    		if (s == n)q++;
    		if (x == n)q++;
    		if (s == n - 1)f++;
    		if (x == n - 1)f++;
    		if (y < q || z < q)ans = 0;
    		if (y + z < f+2*q)ans = 0;
    		if (ans)cout << "YES" << endl;
    		else cout << "NO" << endl;
    	}
    }

[Link 1]: https://codeforc.es/contest/1494/problem/B
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]: /images/20210716/97a56f92fecc4fca83e0539bd388d8ac.png

发表评论取消回复

表情：

评论列表（有 0 条评论，288人围观）

还没有评论，来说两句吧...

相关阅读

相关【贪心+构造】CF1806B

[? - Virtual Judge (vjudge.net)][- Virtual Judge _vjudge.net] 题意：给定一个长度为n的数列a，你可以重排这个

素颜马尾好姑娘i/ 2024年03月22日 17:17/ 0 赞/ 42 阅读

相关纵横字谜的答案（Crossword Answers)

输入一个r行c列(1<=r,c<=10)的网格，黑格用"\"表示，每个白格都填有一个字母，如果一个白格的左边相邻的位置或者边上相邻的位置没有白格（可能是黑格，也可能除了网格边界

今天药忘吃喽~/ 2023年03月06日 05:21/ 0 赞/ 7 阅读

相关 Sicily 11157. Crossword

<table style="font-size:9pt; margin-left:auto; margin-right:auto; margin-top:10px; table

红太狼/ 2022年08月08日 06:36/ 0 赞/ 153 阅读

相关 CodeForces - 723D - D. Lakes in Berland

-------------------- 题目连接：[http://codeforces.com/problemset/problem/723/D][http_codefor

蔚落/ 2022年06月12日 12:59/ 0 赞/ 146 阅读

相关 CodeForces 370 B.Berland Bingo（模拟）

Lately, a national version of a bingo game has become very popular in Berland. There are

刺骨的言语ヽ痛彻心扉/ 2022年06月10日 22:40/ 0 赞/ 156 阅读

相关 Crossword Answers UVA - 232

Crossword Answers UVA - 232 题目传送： [https://uva.onlinejudge.org/index.php?option=com

蔚落/ 2022年06月10日 10:53/ 0 赞/ 145 阅读

相关 UVA - 232 Crossword Answers

[题目描述][Link 1] include<iostream> include<stdio.h> include<string.h> usi

秒速五厘米/ 2022年05月09日 05:03/ 0 赞/ 136 阅读

相关 CF1194F Crossword Expert（数论，组合数学）

不难的一题。不知道为什么能 $2500$…… 不过场上推错了一直不会优化…… 首先考虑 $f\_i$ 表示恰好做完前 $i$ 道题的概率。这样很难算。修改一下，$f\_

系统管理员/ 2021年11月22日 15:08/ 0 赞/ 252 阅读

相关 1475C Ball in Berland (思维)

[题目][Link 1] 思路：看N为2e5可知复杂度为O(n)或O(nlogn)，在这我用两个map分别记录每个男和女各自可以和多少匹配，首先选好一组匹配，那么还可以找

系统管理员/ 2021年07月16日 15:33/ 0 赞/ 272 阅读

相关 B. Berland Crossword (构造)

[题目][Link 1] 对于下面这个图可以知道当U涂中间三个时是不会对其它的三种产生限制的，而如果涂了4个则必然会占到L R其中一个相邻的格子，涂了5个必然会占掉相邻的

男娘i/ 2021年07月16日 15:28/ 0 赞/ 289 阅读