B. Berland Crossword (构造)

男娘i 2021-07-16 15:28 300阅读 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 条评论，300人围观）

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

相关阅读

相关【贪心+构造】CF1806B

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

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

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

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

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

相关 Sicily 11157. Crossword

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

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

相关 codeforces 25C. Roads in Berland

有n个城市，每个城市都能到达别的城市，n\n的矩阵表明i到j城市的最短距离，现在要建造一些新的道路，在两个城市之间。问每次建造这些道路之后每两个城市之间的距离之和为多少。如

旧城等待，/ 2022年08月03日 08:23/ 0 赞/ 26 阅读

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

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

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

相关 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 赞/ 169 阅读

相关 Crossword Answers UVA - 232

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

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

相关 UVA - 232 Crossword Answers

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

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

相关 1475C Ball in Berland (思维)

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

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

相关 B. Berland Crossword (构造)

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

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