A - Minimal Square

题意

给两个完全一样的矩形(平行且不重叠) 求能覆盖两个矩形的最小正方形的面积

思路

只有两种摆放方式将两个矩形上下并列或者左右并列得到的新图形长或者宽是之前的二倍

判断一下并排之后的图形长和宽的最小值即可

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1010;


int main() {
   
	int t;cin >> t;
	while (t--) {
   
		int a, b;cin >> a >> b;
		int minn = min(a, b);
		int maxn = max(a, b);
		int ans = max(minn * 2, maxn);
		cout << ans * ans << endl;
	}
	return 0;
}

B - Honest Coach

题意

将一组数据分成两组使得其中一组的最大值和另一组的最小值相差最小

思路

sort后找到相邻两个数的差值的最小值即可

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 60;

int a[N];
int main() {
   
	int t;cin >> t;
	while (t--) {
   
		int n;cin >> n;
		for (int i = 1;i <= n;++i)cin >> a[i];
		sort(a + 1, a + n + 1, [](int x, int y) {
   return x < y;});
		int res = INF;
		for (int i = 2;i <= n;++i)res = min(res, a[i] - a[i - 1]);

		cout << res << endl;
	}
	return 0;
}

C - Similar Pairs

题意

问：给出一个数组，求是否能够使所有的数都可以“类似”匹配。
”类似“：两个数具有相同的奇偶性，或差的绝对值为1。

思路

设奇数的个数为 $x$ 偶数的个数为 $y$ 因为 $n$ 为偶数所以 $x + y$ 肯定为偶数

无非三种情况

① $x$ 和 $y$ 都为偶数显然满足条件

② $x$ 和 $y$ 都为奇数只要存在两个相邻的数则他俩“类似” 且 $x$ 和 $y$ 都变成了偶数也满足条件

③ $x$ 和 $y$ 都为奇数且没有相邻的数显然无解

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 60;

int a[N];

int main() {
   
	int t;cin >> t;
	while (t--) {
   
		int n;cin >> n;
		int odd = 0,  even = 0;
		for (int i = 1;i <= n;++i) {
   
			cin >> a[i];
			if (a[i] & 1)odd++;
			else even++;
		}
		bool flag = false;
		if (odd % 2 == 0 && even % 2 == 0)puts("YES");
		else {
   
			sort(a + 1, a + n + 1, [](int x, int y) {
   return x < y;});
			for (int i = 2;i <= n;++i)
				if (a[i] - a[i - 1] == 1) {
   
					flag = true;
				}
			if (flag)puts("YES");
			else puts("NO");
		}
		
	}
	return 0;
}

D - Buying Shovels

题意

需要买 $n$ 件物品有 $k$ 种包裹第 $k$ 种包裹有 $k$ 件物品用最小的包裹数买到需要的物品

思路

当 $k > = n$ 时毫无疑问答案为1

当 $k < n$ 时找到 $n$ 的小于等于 $k$ 的第一个因子

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 60;
set<int>s;
int a[N];
vector<int> divisors(int n) {
   
	vector<int >res;
	for (int i = 1;i <= n / i; ++i) {
   
		if (n % i == 0) {
   
			res.push_back(i);
			if (n / i != i)res.push_back(n / i);
		}
	}
	sort(res.begin(), res.end(), greater<int>());
	return res;
}
int main() {
   
	int t;cin >> t;
	while (t--) {
   
		int n, k;cin >> n >> k;
		if (k >= n) {
   
			cout << 1 << endl;
			continue;
		}
		else {
   
			int res = 0;
			vector<int>div = divisors(n);

			for (auto t : div) {
   
				if (t <= k) {
   
					res = n / t;
					break;
				}
			}
			cout << res << endl;
		}
	}
	return 0;
}

E - Polygon

题意

一个矩阵的左边和右边分别有一排大炮大炮射出的子弹会在遇到边界或者1停止并把当前位置变成1 给定一个矩阵问能否通过大炮射出子弹得到对应的矩阵

思路

参照样例不难发现当一个位置是1时当且仅当它的右方或下方为1

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 60;
char mp[N][N];
int main() {
   
	int t;cin >> t;
	while(t--){
   
		bool flag = true;
		int n;cin >> n;
		for (int i = 0;i < n;++i) 
			for (int j = 0;j < n;++j) 
				cin >> mp[i][j];
		for (int i = 0;i < n;++i) {
   
			for (int j = 0;j < n;++j) {
   
				if (mp[i][j] == '1') {
   
					if (i == n - 1)continue;
					else if (j == n - 1)continue;
					else if (mp[i + 1][j] != '1' && mp[i][j + 1] != '1') {
   
						flag = false;
						break;
					}
				}
			}
		}
		if (flag)puts("YES");
		else puts("NO");
	}
	return 0;
}

F - Spy-string

题意

给定 $n$ 个长度为 $m$ 的字符串找出长度为m的任何字符串s，使得给定的n个字符串中的每一个在至多一个位置上与s不同。

思路

数据范围很小暴力枚举即可

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 60;

string s[20];
int n, m;
bool check(string& ans) {
   
	int cnt = 0;
	for (int i = 0;i < n;++i) {
   
		cnt = 0;
		for (int j = 0;j < m;++j) {
   
			if (s[i][j] != ans[j])++cnt;
			if (cnt > 1)return 0;
		}
	}

	return 1;
}
int main() {
   
	int t;cin >> t;
	while(t--){
   
		cin >> n >> m;
		bool flag = false;
		for (int i = 0;i < n;++i)cin >> s[i];
		string ans;
		for (int i = 0;i < m;++i) {
   
			for (char j = 'a';j <= 'z';++j) {
   
				ans = s[0];
				ans[i] = j;
				if (check(ans))flag = true;
				if (flag)break;
			}
			if (flag)break;
		}
		if (flag)cout << ans << endl;
		else puts("-1");
	}
	return 0;
}

G - A/B Matrix

题意

给你四个正整数 $n 、 m 、 a 、 b$ 找出大小为 $n \times m$ 且满足以下所有条件的任何此类矩形矩阵：

矩阵的每一行恰好包含 $a$ 个 $1$ ；
矩阵的每一列恰好包含 $b$ 个 $1$ ；
所有其他元素都是零。

可能不存在

思路

由题可知每一行的1乘以行数等于每一列的1乘以列数当 $\,\, != m*b$ 时显然不符合题意

先考虑每行放 $a$ 个 $1$ 那么如何保证每列都有 $b$ 个 $1$ ？其实只需要得到之前放了多少个 $1$ ，在这个基础上对该行放 $1$ 时，只需用之前的总个数对 $m$ 取模，就可以形成如下的一个对称的效果：

111100
110011
001111

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 60;

int mp[N][N];

int main() {
   
	int t;cin >> t;
	while(t--){
   
		int n, m, a, b;cin >> n >> m >> a >> b;
		if (n * a != m * b) {
   
			puts("NO");
			continue;
		}
		else {
   
			puts("YES");
			int s = 0;
			memset(mp, 0, sizeof mp);
			for (int i = 0;i < n;++i) {
   
				for (int j = s;j < s + a;++j) {
   
					mp[i][j % m] = 1;
				}
				s += a;
			}
			for (int i = 0;i < n;++i) {
   
				for (int j = 0;j < m;++j) {
   
					cout << mp[i][j];
				}
				cout << endl;
			}
		}
	}
	return 0;
}

H - Binary Median

题意

给一个长度为 $m$ 的二进制串从中删去 $n$ 个不同的二进制串问最终中位数为多少

思路

将二进制串转换成整数分类讨论

将待删去的二进制串转换成十进制数 $x$ 设 $p$ 为当前中位数

当 $k$ 为奇数时

① $x\geq p$ 中位数左移

② $x > p$ 不变

当 $k$ 为偶数时

① $x\leq p$ 中位数右移

② $x > p$ 不变

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1010;


int main() {
   
	int t;cin >> t;
	while (t--) {
   
		LL n, m;cin >> n >> m;
		set<LL>S;
		bool flag = true;
		LL k = 1LL << m;
		LL p = (k - 1) / 2;
		for (int i = 1;i <= n;++i) {
   
			string str;cin >> str;
			LL x = 0;
			for (int i = 0;i < str.size();++i) {
   
				if ((str[i] - '0') & 1)
					x += 1LL << (m - i - 1);
			}
			if (k & 1) {
   
				if (x >= p)
					while (S.count(--p));
			}
			else {
   
				if (x <= p)
					while (S.count(++p));
			}
			S.insert(x);
			--k;
		}
		string res = "";
		for (int i = 0;i < m;++i) {
   
			if (p & 1)res += "1";
			else res += "0";
			p >>= 1;
		}
		for (int i = res.size() - 1;i >= 0;--i)cout << res[i];
		cout << endl;
	}

	return 0;
}

Codeforces Round #644(Div. 3) A-H

题意

思路

题意

思路

题意

思路

题意

思路

题意

思路

题意

思路

题意

思路

题意

思路