[Codeforces]Round 662 div2题解(A-D)
本文最后更新于 162 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/cf1393/

前言

补题。Virtual Participate。
感觉这场好难啊,要是打了恐怕只能2/3题滚粗。

C

给出 $a_i$,要求重排使得 $\min i – j(a_i = a_j)$ 最大。
想了下二分,没写出来,偷瞄一眼题解发现是构造,想想构造解法。
设 $ans$ 为最小距离,其中 $cnt(i)$ 代表数字 $i$ 出现次数。此时最优排放为:$x,.,.,…,x,.,.,\ldots$,每个 $x$ 占用 $ans + 1$ 格,而最后一个 $x$ 占用 $1$ 格,最后 $1 + (ans + 1) \times (cnt(x) – 1) \le n$,解出 $ans \le \dfrac{n – 1}{cnt(x) – 1} – 1$,然而这时单个 $x$ 的情况,如果有多个呢?
设有 $num$ 个 $x$ 使得 $cnt(x)$ 是最大值,分别记为 $x_1,x_2,\ldots,x_{num}$,那么最优排放为:$x_1,x_2,\ldots,x_{num},.,.,\ldots$,一串 $x$ 占用为 $ans + 1$ 格,最后一串 $x$ 占用 $num$ 格,有 $num + (ans + 1) \times (cnt(x) – 1) \le n$,解得 $ans \le \dfrac{n – num}{cnt(x) – 1} – 1$。
求出了答案的上界,如何证明上界一定能取到呢?将相同的数放在相同的相对位置,即可使距离不小于 $ans$。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 1e5 + 100;
int T,n,a[maxn];
int cnt[maxn];
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        for (int i = 1; i <= n; ++i) cnt[i] = 0;
        for (int i = 1; i <= n; ++i) read(a[i]), cnt[a[i]]++;
        int maxx = 1, num = 0;
        for (int i = 2; i <= n; ++i) if (cnt[i] > cnt[maxx]) maxx = i;
        for (int i = 1; i <= n; ++i) if (cnt[i] == cnt[maxx]) ++num;
        printf("%d\n", (n - num) / (cnt[maxx] - 1) - 1);
    }
    return 0;
}

A

手玩一下,发现答案是 $n / 2 + 1$。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
int T,n;
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        printf("%d\n",n/2+1);
    }
    return 0;
}

B

围正方形需要4个长度相同的,围矩形需要2个2条长度相同的组,记录 $num(i)$ 为 $i$ 条线段长度相同的个数,然后更新一下维护一下就可以了。有点像是莫队常用的维护方法。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
#define DEBUG
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; c != '+' && c != '-'; c = nc());
    for (; c == '+' || c == '-'; c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 1e5 + 100;
int n,m;
int cnt[maxn],num[5];
inline void add(int x)
{
    if(cnt[x] < 4) num[cnt[x]]--,num[++cnt[x]]++;
    else
    {
        num[4] -= cnt[x] / 4;
        num[cnt[x] % 4]--;
        ++cnt[x];
        num[4] += cnt[x] / 4;
        num[cnt[x] % 4]++;
    }
}
inline void dele(int x)
{
    if(cnt[x] <= 4) num[cnt[x]]--,num[--cnt[x]]++;
    else
    {
        num[4] -= cnt[x] / 4;
        num[cnt[x] % 4]--;
        --cnt[x];
        num[4] += cnt[x] / 4;
        num[cnt[x] % 4]++;
    }
}
char s[10];
int main()
{
    read(n);
    for (int i = 1; i <= n; ++i) 
    {
        int x;
        read(x), add(x);
    }
    read(m);
    while(m--)
    {
        read(s + 1);
        int x; read(x);
        if(s[1] == '+') add(x);
        else if(s[1] = '-') dele(x);
        if(num[4] > 1 || (num[4] == 1 && (num[3] + num[2]) >= 2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

D

题意让人很容易联想到悬线法,看看能不能用悬线法来解。

定义 $up(i,j),down(i,j)$ 为向上相同、向下相同的最长长度,定义 $h(i,j) = \min(up(i,j),down(i,j))$,那么 $h(i,j)$ 就是只考虑竖直方向时,以该点为中心的十字单边长最大值。

再考虑左右的限定,定义 $L(i,j)$ 为以该点为中心,向左满足条件拓展的最大长度。

若该点与上一点字母相同,$L(i,j) = \min(L(i,j-1) + 1,h(i,j))$ 即可。向右同理。

统计答案时,取 $\min(L(i,j),R(i,j))$。

#include <algorithm>
#include <cstdio>
#include <ctype.h>

const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char* s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 2100;
int n, m;
char a[maxn][maxn];
int up[maxn][maxn], down[maxn][maxn], h[maxn][maxn];
int L[maxn][maxn], R[maxn][maxn];
int main()
{
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(a[i] + 1);
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j)
    {
        up[i][j] = 1;
        if (a[i][j] == a[i - 1][j]) up[i][j] = up[i - 1][j] + 1;
    }
    for (int i = n; i; --i) for (int j = 1; j <= m; ++j)
    {
        down[i][j] = 1;
        if (a[i][j] == a[i + 1][j]) down[i][j] = down[i + 1][j] + 1;
    }
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) h[i][j] = std::min(up[i][j], down[i][j]);
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j)
    {
        L[i][j] = 1;
        if (a[i][j] == a[i][j - 1]) L[i][j] = std::min(L[i][j - 1] + 1, h[i][j]);
    }
    for (int i = 1; i <= n; ++i) for (int j = m; j; --j)
    {
        R[i][j] = 1;
        if (a[i][j] == a[i][j + 1]) R[i][j] = std::min(R[i][j + 1] + 1, h[i][j]);
    }
    long long ans = 0;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) ans += std::min(L[i][j], R[i][j]);
    printf("%lld\n", ans);
    return 0;
}
本文标题:[Codeforces]Round 662 div2题解(A-D)
本文作者:Clouder
本文链接: https://www.codein.icu/cf1393/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇