病菌感染（思维）

2024-03-09 05:10

文章标签 思维感染病菌

本文主要是介绍病菌感染（思维），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面
题意：
解决思路：证明存在方格不会被感染。
证
用数学归纳法可以得出，如何所选的点都在对角线上且点是连续的，是最优的情况。不妨取最大值，只要证明 $\small n-1$ 个点无法感染全部方格，即证明 $\small m$ 无法感染全部方格 $\small (0 <m<n)$
证明
如图：

只有浅色会被感染，存在一个方格不能被感染
即：存在方格不会被感染。
证毕
AC代码

//优化
#pragma GCC optimize(2)
//C
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
//C++
//#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<istream>
#include<iomanip>
#include<climits>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
//宏定义
#define N 1010
#define DoIdo main
//#define scanf scanf_s
#define it set<ll>::iterator
//定义+命名空间
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 19260817;
const ll INF = 1e18;
const int maxn = 1e6 + 10;
using namespace std;
//全局变量
int cnt1[N], cnt2[N];
//函数区
ll max(ll a, ll b) { return a > b ? a : b; }
ll min(ll a, ll b) { return a < b ? a : b; }
//主函数
int DoIdo() {ios::sync_with_stdio(false);cin.tie(NULL), cout.tie(NULL);int n, m;cin >> n >> m;while (m--) {int x, y;cin >> x >> y;}cout << "NO" << endl;return 0;
}
//分割线---------------------------------QWQ
/**/