Codeforces Round #639 (Div. 2)

A. Puzzle Pieces

能否将题目所给拼图拼成n*m大小。

能拼的规格只有1*x，x*1，2*2。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (register int i = a; i <= b; i++)
 
int t;
int n, m;
 
void solve()
{
    cin >> n >> m;
    if (n == 1 || m == 1 || (n == 2 && m == 2))
        puts("YES");
    else
        puts("NO");
}
int main()
{
    cin >> t;
    while (t--)
    {
        solve();
    }
}

View Code

B. Card Constructions

用已有的卡片搭尽可能高的金字塔，最多能搭几座。

预处理金字塔需要的卡片，二分搜索当前能搭的最大层，对卡片数进行缩减。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (register int i = a; i <= b; i++)
 
int t;
ll n;
 
ll h[100000], id;
 
void solve()
{
    int ans = 0, tmp = 0;
    cin >> n;
 
    while (n >= 2)
    {
        tmp = upper_bound(h, h + id, n) - h - 1;
        n -= h[tmp];
        ans++;
    }
    cout << ans << endl;
}
int main()
{
    id = 1;
    h[0] = 2;
    while (h[id - 1] + 3 * id + 2 < 1000000000ll)
    {
        h[id] = h[id - 1] + 3 * id + 2;
        id++;
    }
    cin >> t;
    while (t--)
    {
        solve();
    }
}

View Code

C. Hilbert's Hotel

对于每个非负整数k，将k变化为k+a[k%n]，问变化后有没有重复。

如果有重复，则i+a_i%n≡j+a_j%n（mod n），因为i>n时，i+a_i%n=i%n+a_i%n，

那么就直接考虑i，j小于n的情况，只需要满足（i+ai）%n不重复即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (register int i = a; i <= b; i++)
 
int t;
ll n, a[200010];
int cnt[200010];
void solve()
{
    cin >> n;
    ll mod = n * (1000000000ll / n + 1);
    rep(i, 0, n - 1)
    {
        cin >> a[i];
        cnt[i] = 0;
    }
    rep(i, 0, n - 1)
    {
        if (cnt[(i + a[i] + mod) % n])
        {
            puts("NO");
            return;
        }
        cnt[(i + a[i] + mod) % n] = 1;
    }
    puts("YES");
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--)
    {
        solve();
    }
}

View Code

D. Monopole Magnets

在矩阵中放置南北磁石，北磁石可能会靠近任意一个南磁石一格，满足：

每行每列至少有一个南磁石；

如果单元格为黑色，变换后北磁石可能会到达此单元格；

如果单元格为白色，变换后北磁石不可能会到达此单元格，

问最小的北磁石的数量。

首先白色单元格两侧不能同时存在黑色单元格，因为当前行或列必须有一个南磁石，必然会经过白色单元格，

第二个条件是如果当前行为全白行，那么一定要存在一个全白列，在交点放南磁石，

在满足条件的情况下计算黑色格子连通块个数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (register int i = a; i <= b; i++)

int t;
int n, m, a[1010][1010];
int row[1010][1010], col[1010][1010], vx[1010], vy[1010];

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
queue<pair<int, int> > q;
int ans;

void solve()
{
    char f;
    cin >> n >> m;
    rep(i, 1, n) rep(j, 1, m)
    {
        cin >> f;
        a[i][j] = f == '#';
        row[i][j] = a[i][j] + row[i - 1][j];
        col[i][j] = a[i][j] + col[i][j - 1];
    }
    int flag = 1;
    rep(i, 1, n) rep(j, 1, m) if (!a[i][j])
    {
        if (row[i][j] != 0 && row[i][j] != row[n][j])
            flag = 0;
        if (col[i][j] != 0 && col[i][j] != col[i][m])
            flag = 0;
        if (row[n][j] != 0 && col[i][m] == 0 && !vx[i])
            vx[i] = 1;
        if (row[n][j] == 0 && col[i][m] != 0 && !vy[j])
            vy[j] = 1;
        if (row[n][j] == 0 && col[i][m] == 0)
            vx[i] = vy[j] = 2;
        if (!flag)
        {
            puts("-1");
            return;
        }
    }
    rep(i, 1, n) if (vx[i] == 1) flag = 0;
    rep(j, 1, m) if (vy[j] == 1) flag = 0;
    if (!flag)
    {
        puts("-1");
        return;
    }
    rep(i, 1, n) rep(j, 1, m)
    {
        if (!a[i][j])
            continue;
        ans++;
        a[i][j] = 0;
        q.push(make_pair(i, j));
        while (!q.empty())
        {
            int x = q.front().first, y = q.front().second;
            q.pop();
            rep(z, 0, 3) if (x + dx[z] > 0 && x + dx[z] <= n && y + dy[z] > 0 && y + dy[z] <= m && a[x + dx[z]][y + dy[z]])
            {
                a[x + dx[z]][y + dy[z]] = 0;
                q.push(make_pair(x + dx[z], y + dy[z]));
            }
        }
    }
    cout << ans << endl;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    t = 1;
    while (t--)
    {
        solve();
    }
}

View Code