主页
Featured image of post ACM比赛总结——Codeforces #706 (Div. 2)……

ACM比赛总结——Codeforces #706 (Div. 2)……

2021.3.10 —— Codeforces #706 (Div. 2)……

文章字数:6010
预计阅读时长: 分钟

比赛链接

总结范围

  • A
  • B
  • C
  • D
  • E
  • F

A. Split it!

比赛状态:AC

题目大意

问题描述

给定一个字符串$s$和一个数$k$,
判断字符串是否存在$k+1$个非空子串,满足: $$s=a_1+a_2+\cdots+a_k+a_{k+1}+R(a_k)+R(a_{k-1})+\cdots+R(a_1)$$

其中$R(a_i)$代表倒置字符串$a_i$,
如$R(nico)=ocin$。

读入格式

$T$组数据。

每组第一行为字符串长度$n$和$k$,
第二行为长度为$n$的字符串$s$。

输出格式

如满足,输出一行YES
如不满足,输出一行NO

数据范围

$1\le t\le 100$

$1 \le n \le 100$
$0 \le k \le \lfloor \frac{n}{2} \rfloor$

分析

先假设所有子串$a_i$的长度均为$1$,
则$R(a_i)=a_i$。

条件就变成了$s=a_1+a_2+\cdots+a_k+a_{k+1}+a_k+\cdots+a_2+a_1$,
也就是$s$要为回文字符串

对于$a_{k+1}$,由于条件中只有一个,
这个子串可以为任意字符串
所以只需要字符串$s$两边有回文字符即可。

如:abc iowfen cba(为了区分$a_{k+1}$和其两边,用空格隔开)
其中abc便为回文字符,有三个。

对于$a_1\sim a_k$中的一子串$a_i$,如长度为$n$,
则其可以拆成$n$个长度为$1$的子串,也使得条件满足。

如上例中abciowfencba

可以为$a_1=abc$、$a_2=iowfen$,
满足$s=a_1+a_2+R(a_1)$,

也可以拆成$a_1=a$、$a_2=b$、$a_3=c$、$a_4=iowfen$,
满足$s=a_1+a_2+a_3+a_4+R(a_3)+R(a_2)+R(a_1)$

即如果两边有$cnt$个回文字符,
则可以通过组合,变为$1\sim l$个满足条件的$a_i$。

综上:
即从字符串$s$两边开始找有多少个回文字符,记为$cnt$个,
如果$k\le cnt$,则满足条件输出YES,否则输出NO


需要注意的是:

$a_{k+1}$必须存在(非空),
所以判断范围为(n - 1) / 2 - 1

也就是对于奇数长度字符串abcba,判断范围为$0\sim1$(字符串下标从$0$开始),
对于偶数长度字符串abccba,判断范围也为$0\sim1$。

代码

代码
#include <bits/stdc++.h>
#define ALL(NAME_i, BEGIN, TO) \
    int NAME_i = BEGIN;        \
    NAME_i <= TO;              \
    NAME_i++
#define ALL_invert(NAME_i, BEGIN, TO) \
    int NAME_i = BEGIN;               \
    NAME_i >= TO;                     \
    NAME_i--
using namespace std;

#define MAX_N 100

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int len, k;
        char str[MAX_N + 5];
        scanf("%d%d%s", &len, &k, str);
        int cnt = 0;
        for (ALL(i, 0, (len - 1) / 2 - 1)) //注意判断范围
            if (str[i] == str[len - i - 1]) //如果头尾字符相等,则为回文字符,cnt++
                cnt++;
            else //如果判断到某处两侧不等,则该处到中间部分均为a_{k+1},提前退出循环
                break;
        if (k <= cnt)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

B. Max and Mex

比赛状态:AC

题目大意

问题描述

对于一个集合$S$,其包含$n$个不同元素$a_i$。

定义一次操作,为向该集合$S$中添加元素$\lceil\frac{a+b}{2}\rceil$,
其中$a=mex(S)$、$b=max(S)$。

对于函数$mex(S)$,其意义为:$S$集合中最小的不存在的非负数
对于函数$max(S)$,其意义为:$S$集合中最大的元素

e.g.

$mex(\{1,4,0,2\})=3$
$mex(\{3,5,6,7\})=0$

$max(\{2,5,1\})=5$

如果该操作添加的元素$\lceil\frac{a+b}{2}\rceil$已存在于集合$S$中,
则会重复添加。

e.g.

$S=\{1,3,4,6\}$

如该操作要添加的元素为$4$,
则新集合$S'=\{1,3,4,4,6\}$。


现在要求对某集合$S$进行$k$次操作,
问:$k$次操作后,集合有多少个不同元素

读入格式

$T$组数据。

每组第一行为集合初始元素个数$n$和操作次数$k$,
第二行为集合$S$的$n$个元素$a_i$。

输出格式

输出$k$次操作后集合$S$的不同元素个数。

数据范围

$1\le t\le 100$

$1 \le n \le 10^5$
$0 \le k \le 10^9$
$0 \le a_i \le 10^9$

保证$n$总和不超过$10^5$。

分析

易知道:
$a=mex(S)$结果为集合中不存在的元素,
$b=max(S)$结果为集合中存在的元素。
所以一定满足$a \ne b$。

记:添加的元素$\lceil\frac{a+b}{2}\rceil$为$x$,
当$a < b$时,则$a < x \le b$(且仅当$a=b-1$时,$x=b$)

因此向$S$添加$x$过后,是不会更改$mex(S)$和$max(S)$的值的,
所以经过一次操作后,下一次操作添加的元素仍为$x$。

也就是说:
$a < b$时
若$x \not∈ S$,则$k$此操作后只会添加$1$个元素,答案为$n+1$。(并且注意$k\ne0$)
若$x ∈ S$或者$k=0$,$k$此操作均不会向$S$添加新的不同元素,答案为$n$


但仍存在$a>b$的情况。

e.g.

$S=\{0,1,2,3\}$

则$a=mex(S)=4$,
$b=max(S)=3$。

且仅能是这种元素从$0$到$n-1$均存在的集合。
如中间任意存在一处空缺,则会导致$mex(S)<max(S)$。

那么这个时候$x=a$,则会向$S$中添加新元素$a$,
一次操作过后,新的$a,b$则会变化:
$a'=a$、$b'=a$,
则又会添加新的元素。

e.g.

上例中:添加了$x=4$后,
$S'=\{0,1,2,3,4\}$。

则新的$a'=5$、$b'=4$,
$x'=5$。

$S''=\{0,1,2,3,4,5\}$

所以对于这种情况($a>b$),最终$S$中不同元素为$n+k$个。


综上: $$ ans= \begin{cases} n+1 & (a<b & and & (k\ne0 & and & x\not∈S)) \\ n & (a<b & and & (k=0 & or & x∈S)) \\ n+k & (a>b) \end{cases} $$

代码

代码
#include <bits/stdc++.h>
#define ALL(NAME_i, BEGIN, TO) \
    int NAME_i = BEGIN;        \
    NAME_i <= TO;              \
    NAME_i++
#define ALL_invert(NAME_i, BEGIN, TO) \
    int NAME_i = BEGIN;               \
    NAME_i >= TO;                     \
    NAME_i--
using namespace std;

#define MAX_N 100000

int num[MAX_N + 5];
set<int> s;

int mex(int n)
{
    if (num[1] != 0)
        return 0;
    for (ALL(i, 2, n))
        if (num[i] - num[i - 1] != 1)
            return num[i - 1] + 1;
    return num[n] + 1;
}

int calc(int a, int b) { return (a + b) / 2 + (a + b) % 2; } //计算x

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        s.clear();
        int n, k;
        scanf("%d%d", &n, &k);
        for (ALL(i, 1, n))
            scanf("%d", &num[i]), s.insert(num[i]); //用set集合来方便查找
        sort(num + 1, num + n + 1);                 //先对数据排序,方便求mex(S)和max(S)
        int a = mex(n), b = num[n];

        if (a < b)
            if (k == 0 || s.find(calc(a, b)) != s.end())
                printf("%d\n", n);
            else
                printf("%d\n", n + 1);
        else
            printf("%d\n", n + k);
    }
    return 0;
}

C. Diamond Miner

比赛状态:未完成(看过题目未在时间内做出)

题目大意

问题描述

平面直角坐标系$xOy$中,
有$n$个矿工,均在$y$轴上,
有$n$处矿物,均在$x$轴上。

其中一位矿工只能挖一处矿物,一处矿物只能被一个矿工挖,
即$x$和$y$轴上的点要一一配对

若每个矿工采矿代价是两点间距离$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$,
问:如何安排,使得总代价最小,并输出最小代价。

读入格式

$T$组数据。

每组第一行为矿工和矿物个数$n$,
接下来$2n$行为矿工或矿物的坐标$x,y$(注意是无序的,不一定先全为矿工)。

输出格式

输出每组数据的最小总代价,精确到$15$位小数。

数据范围

$1\le t\le 10$

$1 \le n \le 10^5$
$-10^8 \le x_i \le 10^8$
$-10^8 \le y_u \le 10^8$

保证$n$总和不超过$10^5$。

分析

采用贪心思想中的排序型贪心

对于任意两个矿工,其纵坐标分别为$y_a,y_b$,
假设现在他们分别匹配到横坐标为$x_a,x_b$的两处矿。

那么现在的代价为$\sqrt{x_a^2+y_a^2}+\sqrt{x_b^2+y_b^2}$。

如果两个矿工匹配的矿对换,
则代价变为$\sqrt{x_b^2+y_a^2}+\sqrt{x_a^2+y_b^2}$。

那么对换的条件就是: $$\sqrt{x_a^2+y_a^2}+\sqrt{x_b^2+y_b^2} > \sqrt{x_b^2+y_a^2}+\sqrt{x_a^2+y_b^2}$$

开始化简:

$$2\sqrt{x_a^2+y_a^2}\sqrt{x_b^2+y_b^2} > 2\sqrt{x_a^2+y_b^2}\sqrt{x_b^2+y_a^2}$$ $$(x_a^2+y_a^2)(x_b^2+y_b^2) > (x_a^2+y_b^2)(x_b^2+y_a^2)$$ $$x_a^2y_b^2+x_b^2y_a^2 > x_a^2y_a^2+x_b^2y_b^2$$

移项消去,可得两条件: $$ \begin{cases} |x_a|>|x_b| \\ |y_a|<|y_b| \end{cases} $$

于是这样排序后最终效果,
就是$|y_i|$越大的,匹配的$|x_i|$也就越大。


也就是说,
我们可以直接对$x$和$y$数组进行排序
条件分别为$|x_i|$大小和$|y_i|$大小。

这样排序后,也就是越大$|y_i|$对应越大的$|x_i|$
没要求输出方案,直接遍历计算结果即可。

代码

代码
#include <bits/stdc++.h>
#define ALL(NAME_i, BEGIN, TO) \
    int NAME_i = BEGIN;        \
    NAME_i <= TO;              \
    NAME_i++
#define ALL_invert(NAME_i, BEGIN, TO) \
    int NAME_i = BEGIN;               \
    NAME_i >= TO;                     \
    NAME_i--
using namespace std;

#define MAX_N 100000

struct posType
{
    int X, Y;

    posType() : X(0), Y(0) {}
    posType(int _X, int _Y) : X(_X), Y(_Y) {}

    bool operator==(const posType &a) const { return a.X == X && a.Y == Y; }
    bool operator<(const posType &a) const { return X == a.X ? Y < a.Y : X < a.X; }
    posType operator+(const posType &a) const { return posType(X + a.X, Y + a.Y); }

    bool inMap(const int &mapX, const int &mapY) const { return X >= 1 && X <= mapX && Y >= 1 && Y <= mapY; }
} miner[MAX_N + 5], mine[MAX_N + 5];

inline double dist(const posType &a, const posType &b) { return sqrt((double)(a.X - b.X) * (double)(a.X - b.X) + (double)(a.Y - b.Y) * (double)(a.Y - b.Y)); }

bool cmp(const posType &a, const posType &b) { return abs(a.X) == abs(b.X) ? abs(a.Y) < abs(b.Y) : abs(a.X) < abs(b.X); } //这里我将两个cmp合并为一个来写的,觉得不放行可以分开写。

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, _X, _Y, miner_cnt = 0, mine_cnt = 0;
        scanf("%d", &n);
        for (ALL(i, 1, 2 * n))
        {
            scanf("%d%d", &_X, &_Y);
            if (_Y)
                miner[++miner_cnt] = posType(_X, _Y);
            else
                mine[++mine_cnt] = posType(_X, _Y);
        }

        sort(miner + 1, miner + miner_cnt + 1, cmp);
        sort(mine + 1, mine + mine_cnt + 1, cmp);

        double ans = 0;
        for (ALL(i, 1, n))
            ans += dist(miner[i], mine[i]);
        printf("%.15lf\n", ans); //注意小数位数为15位。
    }
    return 0;
}

D. Let’s Go Hiking

比赛状态:未完成(时间不足)

题目大意

问题描述

Qingshan和Daniel玩游戏。

存在任意$n$个数字$p_i$。
Qingshan为先手,其先选择这串数字的一个下标$x(1\le x \le n)$,
Daniel为后手,其再选择一个下标$y(1\le y\le n)$,并且$y \ne x$。

游戏操作为回合制,两人具体操作为:

  • Qingshan的回合中,其需要选择一个新的$x'(1\le x' \le n)$,其要满足三个条件:

    • 在$x$附近。($|x'-x|=1$)
    • 不与$y$相同。($x' \ne y$)
    • 要比原来的数小(下山)。($p_{x'}<p_x$)

    当成功选择出$x'$,会把$x'$赋给当前的$x$($x=x'$)。

  • Daniel的回合中,其需要选择一个新的$y'(1\le y' \le n)$,其要满足三个条件:

    • 在$y$附近。($|y'-y|=1$)
    • 不与$x$相同。($y' \ne x$)
    • 要比原来的数大(上山)。($p_{y'}>p_y$)

    当成功选择出$y'$,会把$y'$赋给当前的$y$($y=y'$)。

当某人没法找到新的$x$或$y$(无路可走)时,判这名玩家输。


你的任务是:
判断这组数字$p$中,有多少个$p_i$,使得其作为Qingshan初始选择的$x$时,Qingshan必赢。

读入格式

第一行为数字个数$n$,
第二行为$n$个数字$p_i$。

输出格式

输出有多少种初始的$x$,使得Qingshan必赢。

数据范围

$2 \le n \le 10^5$
$1 \le p_i \le n$

保证$n$总和不超过$10^5$。

样例数据

第一组

输入

5
1 2 5 4 3

输出

1

解释:

Qingshan只能选择$x=3$。
选择此处后,无论Danie选择哪里,之后的行动都总会使Danie被堵死。

而Qingshan选择其他地方时,Danie总有办法将Qingshan堵死。

故答案为$1$。

第二组

输入

7
1 2 4 6 5 3 7

输出

0

解释:

Qingshan无论怎么选择$x$,都总被Danie或边界堵死。

如$x=4$时,则$y=1$便能使Qingshan一定输掉游戏:

  • 当Qingshan选择$x'=3$,Danie选择$y'=2$,这之后Qingshan被Danie堵死,输掉游戏。
  • 当Qingshan选择$x'=5$,Danie选择$y'=2$,
    行动到最后$x=7$,$y=4$,这个时候时Qingshan的回合,但Qingshan被边界堵死,输掉游戏。

如$x=3$时,则$y=4$便能使Qingshan一定输掉游戏:

  • Qingshan只能选择$x'=2$,这个时候Danie选择$y'=5$从右侧下山。
    那么到最后,Qingshan会被边界堵死,输掉游戏。

故答案为$0$。

分析

这串数字可以分成一段段坡路(上坡路和下坡路可以相互转换)和平路。

首先两人都只能走上坡或者下坡,故只分析坡路。

对于Qingshan,如果其$x$选择一段不是最长的坡路,从顶往下走,
那么Danie只用选择最长的那条坡路,从底往上走,
这样就能把Qingshan耗死,使得最终Qingshan被边界堵死。

所以Qingshan只能选择最长的坡路开始走


对于最长的坡路,记其数量为$c$条,

  • 当$c=1$时:

    则无论Qingshan怎么选择起点(当然不能是最低点),
    Danie都能选择在他旁边低处,使得刚开始就被堵死,Qingshan输掉游戏

  • 当$c\ge3$时:

    则无论Qingshan选择哪条路,从顶往下走,
    Danie都能选择另外一条与他不会碰见的路,最终把Qingshan耗死,Qingshan输掉游戏

  • 当$c=2$时:

    由$c\ge3$的情况可知,如果两条路毫不相关(中间被隔开),
    Danie也总能选择一条与他不会碰见的路把Qingshan耗死,Qingshan输掉游戏

    那么对于不被隔开的两条路,只有形如"V"和"Λ"的两种情况

    • 对于"V"型:

      Qingshan无论是选择左边还是右边的顶点向下走,
      Danie只用选择中间的最低点,朝着Qingshan下来的反方向走,就能把Qingshan耗死,Qingshan输掉游戏

    • 对于"Λ"型:
      也就是样例1中的情况。

      • 如果路的长度$len$为奇数:

        那么Qingshan能且仅能选择顶点
        再根据Danie选择的$y$的方向,朝着他走,就能使Danie被堵死,Qingshan赢得游戏,并且只有一种方案

      • 如果路的长度$len$为偶数:

        那么Qingshan选择顶点后: 如果不选Danie上山的方向,就会被耗死;
        如果选Danie上山的方向,就会被堵死。
        最终都是Qingshan输掉游戏


综上:

只有满足以下四个条件,Qingshan才能赢得游戏,且答案仅能为$1$

  1. $c=2$。
  2. 两条路无间隔。
  3. 两条路为"Λ"型。
  4. $len$为偶数。

可以将每条坡路的信息存下来:

  • 记录每条坡路从左到右看,是上坡还是下坡,记为$state$。
  • 记录每条坡路的长度$len$。
  • 记录每条坡路的编号(是第几条路)$index$。

对于$2$号条件,可以判断$index$之差的绝对值是否为$1¥$。如果为$1$证明无间隔。
对于$3$号条件,可以判断$road[1]$的$state$是否为上坡,$road[2]$的$state$是否为下坡。

代码

代码
#include <bits/stdc++.h>
#define ALL(NAME_i, BEGIN, TO) \
    int NAME_i = BEGIN;        \
    NAME_i <= TO;              \
    NAME_i++
#define ALL_invert(NAME_i, BEGIN, TO) \
    int NAME_i = BEGIN;               \
    NAME_i >= TO;                     \
    NAME_i--
using namespace std;

#define MAX_N 100000

#define NOW_ROAD road[road_cnt]
#define NEW_ROAD get_state(_num, num), 2, road_cnt

struct roadType
{
    int state, len, index;
    roadType() : state(0), len(0), index(0) {}
    roadType(int _state, int _len, int _index) : state(_state), len(_len), index(_index) {}

    const bool operator<(const roadType &a) { return len == a.len ? index < a.index : len > a.len; } //重载<为按len降序排序。注意:len相等时,要以index小的在前,防止破坏上坡下坡的顺序。
} road[MAX_N + 5];

int get_state(int _num, int num) { return num - _num > 0 ? 1 : (num - _num == 0 ? 0 : -1); } //state==1为上坡; state==0为平路; state==-1为下坡

int main()
{
    int n, num, _num, road_cnt = 1;
    scanf("%d%d%d", &n, &_num, &num);
    road[1] = roadType(NEW_ROAD);
    for (ALL(i, 3, n))
    {
        _num = num, scanf("%d", &num);
        if (get_state(_num, num) != NOW_ROAD.state)                                       //与当前路状态不同,增加新路
            road_cnt += NOW_ROAD.state == 0 ? 0 : 1, road[road_cnt] = roadType(NEW_ROAD); //当NOW_ROAD的state为0时,证明当前路为平路。所以road_cnt不++,覆盖掉这段平路。
        else                                                                              //与当前路状态相同,当前路长度++
            NOW_ROAD.len++;
    }
    if (NOW_ROAD.state == 0) //如果最后一条路是平路,road_cnt--
        road_cnt--;
    sort(road + 1, road + road_cnt + 1); //用排序,方便找最大的len。但注意不能破坏相同len的路的顺序。

    int c = road[1].len == road[2].len ? road[2].len == road[3].len ? 3 : 2 : 1, len = road[1].len;                      //这里如果c>3,统一看成c=3的情况。
    if ((c == 2) && (abs(road[2].index - road[1].index) == 1) && (road[1].state == 1 && road[2].state == -1) && len % 2) //四个括号分别对应四个条件
        printf("1");
    else
        printf("0");

    return 0;
}
采用 CC BY-NC-SA 4.0 许可协议
文章封面配图来源于非常见图站,需要出处可以使用以图搜图工具