Codeforces Round #662 (Div. 2)

2024-01-04 16:15:46

A. Rainbow Dash, Fluttershy and Chess Coloring

题意：
给出 \(n \times n\) 的棋盘，每次可以选择一种颜色涂任意次，并且只能在之前涂过的相邻位置涂色，
问把棋盘涂成黑白相邻的最少步数。

题解：
可以大概画个图，从外层填到内层，每次换一种颜色，答案为 \(\lfloor \frac{n}{2} \rfloor + 1\)

Code


#include&ltbits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define SZ(a) (int)((a).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef double db;
typedef pair &ltint, int> Pii;
typedef pair &ltll, int> Pli;
typedef unsigned long long ull;
const double eps = 1e-8;
const int mod = (int)(1e9) + 7;
const int inf = 0x7fffffff;
const int N = (int)(2e5) + 7;
 
int _, n;
 
int main() {
 
    // freopen("in.in", "r", stdin);
    for (scanf("%d", &_); _; _--) {
        scanf("%d", &n);
        printf("%d\n", n / 2 + 1);
    }    
 
    return 0;
}

B. Applejack and Storages

题意：
有 \(n\) 个木板，每个木板的长度为 \(a_i\)，有 \(q\) 次操作，每次操作为增加或减少一个长度的木板数量，
对于每次操作后，判断当前是否能用现有的木板凑出两个矩形，其中至少一个为正方形，能就输出 "YES", 否则输出 "NO"。

题解：
这题得分类讨论，若能够满足题目要求，那一定属于如下情况之一：

三种不同长度木板，其中一种长度拼成正方形，另外两种拼出长方形。
两种不同长度木板：
- 其中一种拼成正方形并给长方形提供两条边，另外一种提供长方形剩下两条边。
- 两种不同边长的正方形。
一种长度的木板，拼出两个相同边长的正方形。
注意到讨论的这几种情况只会涉及到 \(2\), \(4\), \(6\), \(8\), 这四种数量的木板，
所以可以通过 \(g[i]\), \({i \in \{2, 4, 6, 8\}}\) 表示木板数量大于等于 \(i\) 有几种长度，最后分类作答即可。

Code


#include&ltbits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define SZ(a) (int)((a).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef double db;
typedef pair &ltint, int> Pii;
typedef pair &ltll, int> Pli;
typedef unsigned long long ull;
const double eps = 1e-8;
const int mod = (int)(1e9) + 7;
const int inf = 0x7fffffff;
const int N = (int)(2e5) + 7;
 
int n, q, t[N], g[10];
char ch[5];
bool check() {
    if (g[8] >= 1) return true;
    if (g[6] && (g[2] - 1) >= 1) return true;
    if (g[4] && (g[2] - 1) >= 2) return true;   
    if (g[4] >= 2) return true;
    return false;
}
 
int main() {
 
    // freopen("in.in", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        t[x]++;
    }
    for (int i = 1; i <= (int)(1e5); i++) {
        if (t[i] >= 2) g[2]++;
        if (t[i] >= 4) g[4]++;
        if (t[i] >= 6) g[6]++;
        if (t[i] >= 8) g[8]++;
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        int x;
        scanf("%s%d", ch, &x);
        // printf("(%d)\n", x);
        // for (int j = 1; j <= 10; j++) printf("%d%c", t[j], " \n"[j == 10]);
        // printf("(%d, %d, %d, %d)\n", g[2], g[4], g[6], g[8]);
        if (ch[0] == '+') {
            t[x]++;
            if (t[x] == 2) g[2]++;
            if (t[x] == 4) g[4]++;
            if (t[x] == 6) g[6]++;
            if (t[x] == 8) g[8]++;
        } else {
            if (t[x] == 2) g[2]--;
            if (t[x] == 4) g[4]--;
            if (t[x] == 6) g[6]--;
            if (t[x] == 8) g[8]--;
            t[x]--;
        }
        puts(check() ? "YES" : "NO");   
    }
 
    return 0;
}

C. Pinkie Pie Eats Patty-cakes

题意：
给出 \(n\) 个 cakes，每个 cake 的种类为 \(a_i\)，要求一种顺序，使得相同种类的 cake 之间的最小距离（不包括两端）最大化。

题解：
这题看到最小值最大化第一反应是二分，但没想清怎么模拟。

法1（贪心）：
题目要求最小距离最大化，可以感觉到出现次数最多的元素最难隔开，贪心地考虑我们可以先处理这些元素。
大概就是这种排列（1，2，3 出现次数都为最多）：

记出现最多的次数为 \(ma\)，出现次数为 \(ma\) 的不同元素个数为 \(cnt\)，
显然剩下的相同元素出现次数一定小于等于 \(ma - 1\)，可以塞到开始留下的空里，且至少被一组 \(cnt\) 个元素分隔开来。
所以最小距离的最大值为 \(cnt - 1 + \lfloor \frac{n - ma \times cnt}{ma - 1} \rfloor\)（如图两 \(1\) 之间元素的个数）

Code


#include&ltbits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define SZ(a) (int)((a).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef double db;
typedef pair &ltint, int> Pii;
typedef pair &ltll, int> Pli;
typedef unsigned long long ull;
const double eps = 1e-8;
const int mod = (int)(1e9) + 7;
const int inf = 0x7fffffff;
const int N = (int)(2e5) + 7;
 
int _, n, t[N];
 
int main() {
 
    // freopen("in.in", "r", stdin);
    for (scanf("%d", &_); _; _--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) t[i] = 0;
        for (int i = 1; i <= n; i++) {
            int x;
            scanf("%d", &x);
            t[x]++;
        }
        int ma = *max_element(t + 1, t + 1 + n), cnt = 0;
        for (int i = 1; i <= n; i++) if (t[i] == ma) cnt++;
        printf("%d\n", cnt - 1 + (n - ma * cnt) / (ma - 1));
    }
 
    return 0;
}

法2（二分+堆+贪心）：
由题可知，最小距离越小越容易凑出，所以可得单调性如图：

可以二分答案，之后用堆硬搞，优先处理目前出现次数最多的元素，
\(b[i]\) 为元素个数的桶，\(t[i]\) 表示第 \(i\) 预留的需要处理的元素。

Code


#include&ltbits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define SZ(a) (int)((a).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef double db;
typedef pair &ltint, int> Pii;
typedef pair &ltll, int> Pli;
typedef unsigned long long ull;
const double eps = 1e-8;
const int mod = (int)(1e9) + 7;
const int inf = 0x7fffffff;
const int N = (int)(2e5) + 7;
 
int _, n, a[N], b[N], t[N];
bool check(int x) {
    for (int i = 1; i <= n; i++) t[i] = b[i] = 0;
    for (int i = 1; i <= n; i++) b[a[i]]++;
    priority_queue &ltPii> q;
    for (int i = 1; i <= n; i++) {// 优先填出现次数最多的
        if (b[i]) q.push(mp(b[i], i));
    }
    for (int i = 1; i <= n; i++) {
        if (t[i]) q.push(mp(b[t[i]], t[i]));// 继续填
        if (q.empty()) return false;// 没东西填了说明不符题意
        int cur = q.top().sec; q.pop();
        if (--b[cur]) t[i + x + 1] = cur;// 没填完, 留到 x 个数后再填
    }
    return true;
}
 
int main() {
 
    // freopen("in.in", "r", stdin);
    for (scanf("%d", &_); _; _--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        int L = 0, R = n - 2;
        while (L < R) {
            int mid = (L + R + 1) >> 1;
            if (check(mid)) L = mid;
            else R = mid - 1;
        }
        printf("%d\n", R);
    }
 
    return 0;
}

菜哭了Q^Q

码农公寓

A. Rainbow Dash, Fluttershy and Chess Coloring

B. Applejack and Storages

C. Pinkie Pie Eats Patty-cakes

相关文章