比赛链接

Codeforces Round #706 (Div. 2)

总结范围

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$。

代码

Pastebin链接

代码

#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} $$

代码

Pastebin链接

代码

#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|$，
没要求输出方案，直接遍历计算结果即可。

代码

Pastebin链接

代码

#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

输出

解释：

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

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

故答案为$1$。

第二组

输入

7
1 2 4 6 5 3 7

输出

解释：

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$：

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

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

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

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

代码

Pastebin链接

代码

#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;
}