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 xx 偶数的个数为y yy 因为n nn为偶数 所以x + y x + yx+y肯定为偶数
无非三种情况
① x xx 和 y yy都为偶数 显然满足条件
② x xx和y yy 都为奇数 只要存在两个相邻的数 则他俩“类似” 且x xx和y yy都变成了偶数 也满足条件
③x xx 和 y yy都为奇数 且没有相邻的数 显然无解
#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 nn件物品 有k kk种包裹 第k kk种包裹有k kk件物品 用最小的包裹数买到需要的物品
思路
当k > = n k >= nk>=n时毫无疑问答案为1
当k < n k < nk<n 时 找到n nn的小于等于k kk的第一个因子
#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 nn个长度为m mm的字符串 找出长度为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、m、a、bn、m、a、b 找出大小为n × m n×mn×m且满足以下所有条件的任何此类矩形矩阵：
矩阵的每一行恰好包含a aa个1 11；
矩阵的每一列恰好包含b bb个1 11；
所有其他元素都是零。
可能不存在
思路
由题可知每一行的1乘以行数 等于 每一列的1乘以列数 当n ∗ a ! = m ∗ b n*a \,\, != m*bn∗a!=m∗b时显然不符合题意
先考虑每行放a aa个1 11 那么如何保证每列都有b bb个1 11？其实只需要得到之前放了多少个1 11，在这个基础上对该行放1 11时，只需用之前的总个数对m mm取模，就可以形成如下的一个对称的效果：
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 mm的二进制串 从中删去n nn个不同的二进制串 问最终中位数为多少
思路
将二进制串转换成整数 分类讨论
将待删去的二进制串转换成十进制数 x xx 设p pp为当前中位数
当k kk为奇数时
①x ≥ p x\geq px≥p 中位数左移
②x > p x > px>p 不变
当k kk为偶数时
①x ≤ p x\leq px≤p 中位数右移
②x > p x > px>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; }
