A.Minimal Square

题意：

给定两个 $a * b$ 的长方形，两个长方形的边必须和所求的正方形的边平行，而且两个长方形不能重合。求能包住这两个长方形的最小正方形边长

题解：

比较较短边的两倍和较长边的关系即可

#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

题意：

给定一个长度为 $n$ 的数组 $s_n$ ，将 $s_n$ 分成两份，要求其中一份的最大值和另一份的最小值的差最小，输出其最小值

题解：

排序，遍历找相邻两者之差的最小值即可

#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

题意：

给定一个长度为 $n$ 的数组 $a_n$ ，判断数组是否存在成对的划分，以使数组的每个元素恰好属于一对并且相似

两个数的奇偶性相同
两个数的差的绝对值为 $1$

满足以上两个条件之一，就可以说两个数是相似的
题目保证 $n$ 为偶数

题解：

因为题目保证 $n$ 为偶数，偶数+偶数=偶数，奇数+奇数=偶数，因此先判断为哪种情况，如果两者均为偶数，则直接输出 $YES$ ，否则继续判断是否存在一对相邻的数，如果有就将它们组成一对，剩下的就变成偶数+偶数，输出 $YES$ ，否则就为 $NO$

#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

题意：

一共要买 $n$ 个铲子，现有 $k$ 种包装，第 $i$ 种包装里有 $i$ 个铲子，现在只能选择一种包装。询问恰好买 $n$ 个铲子所需购买的最小包装数

题解：

因为只能选择一种包装，只需要从 $1 \sim k$ 中选择一个最大能被 $n$ 整除的值即可

#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

题意：

给定一个 $n*n$ 的格子，在格子的左侧和上侧都有一个炮台，每一时刻可以有一个炮台发出炮弹，炮弹碰到墙壁或者另一个炮弹会停下来并留在原地。询问给出的结果是否合法
图片说明

题解：

只需要对于每个炮弹判断是否以下三种情况：

在最下面的那一行
在最右边的那一列
它的下面一格或右边一格是否有炮弹

如果每个炮弹都满足就合法，否则就不合法

#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

题意：

给定 $n$ 个长度为 $m$ 的字符串，要求找出一个长度同样为 $m$ 的字符串使得它与每一个字符串最多只有一个位置不同 $(1 \leq n \leq 10 \&\& 1 \leq m \leq 10)$

题解：

因为数据范围够小只要拿第一个串作为基准，要么不改，要么只改一位，将每一位和 $n$ 个串的同一位置替换暴力查找是否存在答案即可

#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.

题意：

给定 $n,m,a,b$ ,要求构造一个 $n∗m$ 的矩阵,使得矩阵的每行恰有 $a$ 个 $1$ ，每列恰有 $b$ 个 $1$ ，其余为 $0$

题解：

先判断能否构造，如果能 $a*n=b*m$ ，因为需要 $1$ 的总数是一定的。
如果能构造，则可以在第一行的第 $1、2...a$ 位置上放 $1$ ，在第二行的第 $2、3...a+1$ 位置上放 $1...$

#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

题意：

给定一个 $m$ 可以构成 $2^{m}$ 个不同的 $01$ 串，现在要求删除其中给定的 $n$ 个字符串，求剩下的字符串中第 $\lfloor \frac{k-1}{2} \rfloor$ 个字符串 $(1 \leq n \leq \min(2^m-1, 100) \&\& 1 \leq m \leq 60)$

题解：

先将给定的 $n$ 个字符串进行排序，与 $k=\lfloor \frac{k-1}{2} \rfloor$ 进行比较，如果比 $k$ 小，说明所求的字符串在原字符串的位置需要往后移一位，即 $k++$ 。最后算出原字符串中第 $k$ 个字符串是什么即是所求字符串

#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();
}

Codeforces Round #644 (Div. 3)