2021牛客国庆集训派对day2 - I.car (找规律)

简介: 笔记

I - car


题意

白云有一个 n ∗ n的矩形,可以在矩形边上放置一辆车,每辆车同时开始以每秒一格的速度从一行或一列的一侧移动到另一侧,如果两辆车同一秒位于矩形上的同一格相遇,会损坏。


白云在开始之前会将矩形中的 m个方格毁坏,当车辆行驶到这个方格时,车辆也会损坏。求在这种情况下,最多有多少辆车可以安全通过。


思路

先求出没有毁坏的方格的情况下,最多能放置多少车辆,如下:


容易发现,当 n 为偶数时,答案为 2 * n , 当 n 为奇数时,答案为 2 * n - 1


现在考虑有道路损坏的情况 以 n = 6 为例 以 x 代表毁坏的道路 如图:



当加入一个 x 时,可以发现 x 所在的行和列 也即(3,3) (6,3)上的车辆都无法通行,所以答案减少2


再加入一个 x 会有两种情况


1、两个 x 在同一行或者同一列


(3,3),(6,3),(1,4)上的车无法通行



2、两个 x 不在同一行或者同一列

(3,3),(6,3),(5,4),(5,6)上的车无法通行


可以得到这样一个规律,x 所在的那一行和那一列,车辆都无法通行,而一行或一列有且只有一辆车通过,所以我们只需要统计出 x 占用了多少个不同的行和多少个不同的列,即为无法通行的车的数量,再根据 n 的奇偶性算出本来最多有多少量车能够通过,两者相减即为答案。


但是,n 为奇数时,会有以下这种情况出现:

如果 x 在矩形的正中央,那么只会使答案减少 1,当 n 为奇数 特判这种情况即可 。


代码

#include<bits/stdc++.h>
#include<unordered_map>
#pragma GCC optimize(2)
#define int long long
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
#define debug(x,y) cerr << (x) << " == " << (y) << endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
//template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; }
const int N = 1e5 + 10;
bool vis_x[N], vis_y[N];
void solve() {
    int n, m; cin >> n >> m;
    memset(vis_x, 0, sizeof vis_x);
    memset(vis_y, 0, sizeof vis_y);
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        vis_x[x] = 1;
        vis_y[y] = 1;
    }
    int sum = n * 2;
    if (n & 1)sum--;
    for (int i = 1; i <= n; ++i) {
        if (vis_x[i])sum--;
        if (vis_y[i])sum--;
    }
    if ((n & 1) && (vis_x[n / 2 + 1] && vis_y[n / 2 + 1]))sum++;
    cout << sum << endl;
}
signed main() {
    // int _; cin >> _;
    // while (_--)
        solve();
    return 0;
}


目录
打赏
0
0
0
0
1
分享
相关文章
2021牛客国庆集训派对day1 J.Different Integers(莫队)
2021牛客国庆集训派对day1 J.Different Integers(莫队)
103 0
L2-029 特立独行的幸福 (25 分)
L2-029 特立独行的幸福 (25 分)
235 0
这个儿童节,我们和小时候有什么区别?
六一儿童节就快到了,在这样一个特殊的日子里,让我们看看如今的程序员宝宝们和过去有些什么不一样的地方吧。
1775 0
把所有的谎言献给你β(找规律数学题)
梓川咲太的面前坐着野兔先辈,作为约定,只好乖乖的打开笔记本开始学习了。 “加法符号写歪了,变成了乘法符号,在算式的第三行那个地方。”樱岛麻衣突然开口。
185 0
把所有的谎言献给你β(找规律数学题)
这个颜值逆天的姑娘,居然是一枚程序员!(多图慎入,内有彩蛋)
在2016年阿里云年会上,一位清纯美丽、身材高挑、健康阳光的“维秘天使”闪亮登场,令现场的阿里云汉子们按耐不住心中的激荡,惊呼“女神”驾到! 如今随着网络的传播,这位阿里云女神已经在IT圈掀起了小小的波澜,不仅是阿里人,很多技术小伙伴都加入了她的粉丝圈,纷纷询问,这位女神到底是谁?  今天,我们就
20766 0
八月十九风雨大作
梦觉苏土命方始, 沉月倾守墨清池。 枝花无意涉尘缘, 何故东风侵扰之。 --------张风捷特烈-2017.8.19 八月十九风雨大作
933 0
《C游记》 番外篇(壹)二分查找显神威 猜数游戏趣味生
《C游记》 番外篇(壹)二分查找显神威 猜数游戏趣味生
149 0
AlphaGo下战帖五月来华,柯洁称抱必死信念拼了!
阿尔法狗来势汹汹,柯洁积极应战 4月10日北京时间15:00,谷歌中国与中国棋院在北京联合举办发布会,公布了“中国乌镇·围棋峰会”的开展事宜,并宣布届时AlphaGo将与柯洁开展九段对弈。
1502 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等