A.Puzzle Pieces

题意：

给出三面凸一面凹的无限块拼图问是否能拼出行列的图形

题解：

只能一行或者一列或者两行两列

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n, m;
    scanf("%d%d", &n, &m);
    if (n == 1 || m == 1 || (n == 2 && m == 2))
        puts("YES");
    else
        puts("NO");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Card Constructions

题意：

用张卡片搭塔，优先搭最高的，剩下的可以接着搭，问最后层数总和。
图片说明

题解：

可以算出层数和卡片数的关系是。然后从大到小扫一遍即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll calc(ll n)
{
    return (n * (n + 1)) / 2 * 3 - n;
}
void solve()
{
    ll n, ans = 0;
    scanf("%lld", &n);
    for (int i = 26000; i >= 1; i--)
    {
        while (n >= calc(i))
        {
            n -= calc(i);
            ans++;
        }
    }
    printf("%lld\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Hilbert's Hotel

题意：

有一个大小为的序列，将整数集中的每个整数移至的位置，问同一位置是否只有一个数。

题解：

仅考虑在的范围即可。因为安排到新房间就相当于是平移了一定的位置，如果在这一个区间内不会重复那么后一个区间内也会因为互相交换导致满足条件。

#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[maxn];
map<int, int> mp;
void solve()
{
    mp.clear();
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d",&a[i]);
        a[i] = (a[i] % n + n) % n;
    }
    bool check = true;
    for (int i = 0; i < n; i++)
    {
        int nr = (i + a[i]) % n;
        if (mp[nr] != 0)
        {
            check = false;
            break;
        }
        mp[nr]++;
    }
    puts(check ? "YES" : "NO");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Monopole Magnets

题意：

给定一个的矩阵，' # ' 代表黑色方格，' . ' 代表白色方格，现在可以在任意方格上摆放任意个单向磁铁，磁铁具有的一个性质是：每秒钟 N 极磁铁会向同行或同列的 S 极磁铁靠拢，但 S 极磁铁不会移动，需要构造一种方案，使得：

  1. 无论如何移动，N 极磁铁都无法到达白色方格
  2. 存在一种移动方案，使得 N 极磁铁可以遍历所有黑色方格
  3. 每一行、每一列至少存在一个 S 极磁铁
  4. N 极磁铁的个数尽可能少

要求输出最少的N极磁铁数

题解：

首先判断不可能完成要求的情况。

  • 两个黑格之间存在若干个白格。
  • 存在全白行但不存在全白列
  • 存在全白列但不存在全白行

第一种情况会导致一旦经过某一个黑格，一定会因为该行存在一个南磁极而经过北磁极
后两种会因为无法在该行或者该列的某一个位置安放南磁极而不满足条件。
其余情况判断一下全黑的连通块就可以了。黑色部分全部填上南磁极然后每个连通块随便放一个北磁极即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e3 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
char mp[maxn][maxn];
int n, m, f1, f2, ans;
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void dfs(int x, int y)
{
    mp[x][y] = '.';
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '#')
            dfs(nx, ny);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", mp[i] + 1);
    for (int i = 1; i <= n; i++)
    {
        int c = 0;
        for (int j = 1; j <= m; j++)
            if (mp[i][j] == '#')
                if (!c || mp[i][j - 1] == '.')
                    c++;
        if (c > 1)
        {
            puts("-1");
            return 0;
        }
        if (!c)
            f1 = 1;
    }
    for (int j = 1; j <= m; j++)
    {
        int c = 0;
        for (int i = 1; i <= n; i++)
            if (mp[i][j] == '#')
                if (!c || mp[i - 1][j] == '.')
                    c++;
        if (c > 1)
        {
            puts("-1");
            return 0;
        }
        if (!c)
            f2 = 1;
    }
    if (f1 + f2 == 1)
    {
        puts("-1");
        return 0;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (mp[i][j] == '#')
            {
                dfs(i, j);
                ans++;
            } 
    printf("%d\n", ans);
    return 0;
}