Codeforces Round #706 (Div. 2)

A Split it!

Tag：签到、思维

题意：

给定一个字符串s，参数k，字符串长度为n，问是否存在k+1个子串ai使得 s = a1 + a2 + a3 + ··· + ak + ak + 1 + r(ak) + r(ak - 1) + ··· + r(a2) + r(a1)。

思路：

首先证明：r(a3) + r(a2) + r(a1) = r(a3 + a2 + a1)，然后我们就可以得到 a1 + a2 + a3 + a4 + ··· + ak = r(ak) + ··· + r(a4) + r(a3) + r(a2) + r(a1)。然后使用双指针算法遍历，判断首尾对应的字符是否相同，若相同则计数，不相同则停止遍历。最后，如果计数大于k，则存在，否则就不存在。

题解：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int t, k, n;
string s;
int main()
{
    cin >> t;
    while (t --)
    {
        cin >> n >> k >> s;
        int i = 0, j = n - 1, cnt = 0;
        for (i, j;; i ++, j --)
        {
            if (s[i] != s[j]) break;
            cnt ++;
            if (i + 1 >= j - 1) break;
        }
        if (cnt == k && j - i == 1) puts("NO");
        else if (cnt >= k) puts("YES");
        else puts("NO");
    }
    
    return 0;
}

B Max and Mex

Tag：思维、二分

题意：

给定一个集合S，和一个操作数k，每次将 mex 和 max 的和的一半向上取整后加入集合，其中mex表示集合中不存在的最小非负整数，max表示集合中的最大数，最后输出集合中数字的个数。

思路：

读入输入之后，先特判一下k的值：

如果k为0，则直接输出n；

如果k不为0，则再从mex和max的大小来看，推导如图：

题解：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const double eps = 1e-4;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
int t, n;
ll k;
int main()
{
    cin >> t;
    while (t --)
    {
        int s[N];
        cin >> n >> k;
        for (int i = 0; i < n; i ++) cin >> s[i];
        sort(s, s + n);
        int b = 0, a = s[n - 1];
        for (int i = 0; i <= n; i ++)
        {
            if (i < s[i] || i == n)
            {
                b = i;
                break;
            }
        }
        if (k == 0) cout << n << endl;
        else if (b == n) cout << n + k << endl;
        else if (b < a)
        {
            int c = (1.0 * (a + b) / 2 + 0.5);
            int index = lower_bound(s, s + n, c) - s;
            if (s[index] == c) cout << n << endl;
            else cout << n + 1 << endl;
        }
    }
    return 0;
}

C Diamond Miner

Tag：贪心

题意：

给定n个矿工和n个矿脉的位置，矿工在y轴，矿脉在x轴，(0, 0)位置没有矿工也没有矿脉；矿工和矿脉一一匹配，求矿工到矿脉的距离总和的最小值。

思路：

用两个数组分别存矿工和矿脉，读取数据的时候在负半轴的数据映射到正半轴，然后从小到大排序，相同序号的矿工和矿脉配对计算距离然后求和。证明：三角形两边之和大于第三边

题解：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>
#include <math.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const double eps = 1e-4;
typedef long long ll;
typedef pair<int, int> pii;
int t, n;
int main()
{
    scanf("%d", &t);
    while (t --)
    {
        scanf("%d", &n);
        vector<ll> a, b;
        for (int i = 0; i < 2 * n; i ++)
        {
            ll x, y;
            scanf("%lld%lld", &x, &y);
            if (!x) a.push_back(abs(y));
            if (!y) b.push_back(abs(x));
        }
        sort(a.begin(), a.end()), sort(b.begin(), b.end());
        double ans = 0;
        for (int i = 0; i < n; i ++) 
            ans += sqrt(double(a[i] * a[i] + b[i] * b[i]));
        printf("%.15f\n", ans);
    }
    return 0;
}

D Let’s Go Hiking

Tag：博弈、思维

题意：

给定一个整数序列，Qingshan选择该序列中的一个位置，然后告诉Daniel，Daniel再选择一个位置。游戏开始，每次Qingshan的要选择一个相邻且低于当前位置的位置行动，Daniel选择一个相邻且高于当前位置的位置行动，重复进行，无法行动的人败。问：当给定一个序列p的时候，Qingshan获胜的方案数是多少个。

思路：

直接上分析图

题解：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 10;
int n, a[N], l[N], r[N], flag, cnt, top;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        cin >> a[i];
        l[i] = 1, r[i] = 1;
    }
    for (int i = 1; i < n; i ++)
    {
        if (a[i] > a[i - 1]) l[i] += l[i - 1];
        top = max(top, l[i]);
    }
    for (int i = n - 2; i >= 0; i --)
    {
        if (a[i] > a[i + 1]) r[i] += r[i + 1];
        top = max(top, r[i]);
    }
    for (int i = 0; i < n; i ++)
    {
        if (l[i] == r[i] && r[i] == top) flag ++;
        if (l[i] == top) cnt ++;
        if (r[i] == top) cnt ++;
    }
    if (flag == 1 && cnt == 2)
    {
        if (top % 2 == 1) cout << 1 << endl;
        else cout << 0 << endl;
    }
    else cout << 0 << endl;
    return 0;
}