A.Minimal Square
题意:
给定两个的长方形,两个长方形的边必须和所求的正方形的边平行,而且两个长方形不能重合。求能包住这两个长方形的最小正方形边长
题解:
比较较短边的两倍和较长边的关系即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { int a, b; scanf("%d%d", &a, &b); printf("%d\n", (int)pow(max(min(a, b) * 2, max(a, b)), 2)); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
B.Honest Coach
题意:
给定一个长度为的数组,将分成两份,要求其中一份的最大值和另一份的最小值的差最小,输出其最小值
题解:
排序,遍历找相邻两者之差的最小值即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int a[55]; void solve() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n); int ans = INF; for (int i = 1; i < n; i++) ans = min(ans, a[i] - a[i - 1]); printf("%d\n", ans); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
C.Similar Pairs
题意:
给定一个长度为的数组,判断数组是否存在成对的划分,以使数组的每个元素恰好属于一对并且相似
- 两个数的奇偶性相同
- 两个数的差的绝对值为
满足以上两个条件之一,就可以说两个数是相似的
题目保证为偶数
题解:
因为题目保证为偶数,偶数+偶数=偶数,奇数+奇数=偶数,因此先判断为哪种情况,如果两者均为偶数,则直接输出,否则继续判断是否存在一对相邻的数,如果有就将它们组成一对,剩下的就变成偶数+偶数,输出,否则就为
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int a[55]; void solve() { int n, sum = 0; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", a + i), sum += a[i] & 1; if (sum % 2 == 0) { puts("YES"); return; } sort(a, a + n); for (int i = 1; i < n; i++) if (a[i] == a[i - 1] + 1) { puts("YES"); return; } puts("NO"); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
D.Buying Shovels
题意:
一共要买个铲子,现有种包装,第种包装里有个铲子,现在只能选择一种包装。询问恰好买个铲子所需购买的最小包装数
题解:
因为只能选择一种包装,只需要从中选择一个最大能被整除的值即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { ll n, k; scanf("%lld%lld", &n, &k); ll ans = INF; for (ll i = 1; i * i <= n && i <= k; i++) { if (n % i == 0) { if (n / i > k) ans = n / i; else { ans = i; break; } } } printf("%lld\n", ans); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
E.Polygon
题意:
给定一个的格子,在格子的左侧和上侧都有一个炮台,每一时刻可以有一个炮台发出炮弹,炮弹碰到墙壁或者另一个炮弹会停下来并留在原地。询问给出的结果是否合法
题解:
只需要对于每个炮弹判断是否以下三种情况:
- 在最下面的那一行
- 在最右边的那一列
- 它的下面一格或右边一格是否有炮弹
如果每个炮弹都满足就合法,否则就不合法
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; char c[55][55]; void solve() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%s", c[i]); for (int i = 0; i < n - 1; i++) for (int j = 0; j < n - 1; j++) if (c[i][j] == '1' && c[i + 1][j] == '0' && c[i][j + 1] == '0') { puts("NO"); return; } puts("YES"); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
F.Spy-string
题意:
给定个长度为的字符串,要求找出一个长度同样为的字符串使得它与每一个字符串最多只有一个位置不同
题解:
因为数据范围够小只要拿第一个串作为基准,要么不改,要么只改一位,将每一位和个串的同一位置替换暴力查找是否存在答案即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int n, m; string s[15]; string ans; bool check() { for (int i = 0; i < n; i++) { int cnt = 0; for (int j = 0; j < m; j++) cnt += (ans[j] != s[i][j]); if (cnt > 1) return false; } return true; } void solve() { cin >> n >> m; for (int i = 0; i < n; i++) cin >> s[i]; ans = s[0]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { int t = ans[j]; ans[j] = s[i][j]; if (check()) { cout << ans << "\n"; return; } ans[j] = t; } cout << "-1" << "\n"; } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
G.
题意:
给定,要求构造一个的矩阵,使得矩阵的每行恰有个,每列恰有个,其余为
题解:
先判断能否构造,如果能,因为需要的总数是一定的。
如果能构造,则可以在第一行的第位置上放,在第二行的第位置上放
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int ans[55][55]; int n, m, a, b, c; void solve() { memset(ans, 0, sizeof(ans)); scanf("%d%d%d%d", &n, &m, &a, &b); if (a * n != b * m) { puts("NO"); return; } puts("YES"); for (int i = 0; i < n; i++) for (int j = 0; j < a; j++) ans[i][c++] = 1, c %= m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) printf("%d", ans[i][j]); puts(""); } } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
H.Binary Median
题意:
给定一个可以构成个不同的串,现在要求删除其中给定的个字符串,求剩下的字符串中第个字符串
题解:
先将给定的个字符串进行排序,与进行比较,如果比小,说明所求的字符串在原字符串的位置需要往后移一位,即。最后算出原字符串中第个字符串是什么即是所求字符串
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; ll a[105], ans[105]; void solve() { memset(a,0,sizeof(a)); memset(ans,0,sizeof(ans)); ll n, m, k; scanf("%lld%lld", &n, &m); k = (1LL << m) - n - 1, k /= 2; char s[65]; for (int i = 0; i < n; i++) { scanf("%s", s); for (int j = 0; j < m; j++) a[i] = a[i] * 2 + s[j] - '0'; } sort(a, a + n); for (int i = 0; i < n; i++) if (a[i] <= k) k++; for (int i = 0; i < m; i++) ans[i] = k % 2, k /= 2; for (int i = m - 1; i >= 0; i--) printf("%d", ans[i]); puts(""); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }