Codeforces Round #662 (Div. 2)

链接

A. Rainbow Dash, Fluttershy and Chess Coloring

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

题解:
可以大概画个图,从外层填到内层,每次换一种颜色,答案为 \(\lfloor \frac{n}{2} \rfloor + 1\)
Codeforces Round #662 (Div. 2)Codeforces Round #662 (Div. 2)

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 出现次数都为最多):
Codeforces Round #662 (Div. 2)
记出现最多的次数为 \(ma\),出现次数为 \(ma\) 的不同元素个数为 \(cnt\),
显然剩下的相同元素出现次数一定小于等于 \(ma - 1\),可以塞到开始留下的空里,且至少被一组 \(cnt\) 个元素分隔开来。
所以最小距离的最大值为 \(cnt - 1 + \lfloor \frac{n - ma \times cnt}{ma - 1} \rfloor\)(如图两 \(1\) 之间元素的个数)
Codeforces Round #662 (Div. 2)

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(二分+堆+贪心):
由题可知,最小距离越小越容易凑出,所以可得单调性如图:
Codeforces Round #662 (Div. 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

上一篇:662. 点的坐标


下一篇:day15