发表于 | 更新于:

Codeforces Round #499 (Div. 2)

总结： 二分专场，巨多二分题

# Name
A Stagesstandard input/output1 s, 256 MB Submit Add to favourites img x4069
B Planning The Expeditionstandard input/output1 s, 256 MB Submit Add to favourites img x3354
C Flystandard input/output1 s, 256 MB Submit Add to favourites img x2073
D Rocketstandard input/output1 s, 256 MB Submit Add to favourites img x912
E Borderstandard input/output1 s, 256 MB Submit Add to favourites img x644
F Mars roverstandard input/output5 s, 256 MB Submit Add to favourites img x156

A题 Stages

题意：给一个长为n的串，从其中取出k个字符排成一列，要求每个字符比前一个字符至少多2（ascii码），比如c后面的字符起码为e。不能生成这样的串就输出-1，否则按a=1，b=2 …求生成串的和

题解：emmmm排序从前往后扫一遍应该可以了

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 1000;
int n, k;
char a[maxn];
int main(int argc,char *argv[])
{
    scanf("%d%d", &n, &k);
    scanf("%s", a);
    sort(a, a + n);
    int res = a[0] - 'a' + 1;
    int flag = 1;
    int temp = a[0];
    for (int i = 1; i < n; ++i) {
        if (flag == k) break;
        if (temp + 1 < a[i]) res += a[i] - 'a' + 1, temp = a[i], flag++;
    }
    if (flag < k) printf("-1\n");
    else printf("%d\n", res);
    return 0;
}

一定要有良好的代码习惯，考虑边界值之类的，这种前后有关联的扫描操作就应该处理完第一个数之后再写循环，挂fst的人还挺多

B题 Planning The Expedition

题意：给m个物品，有n个人，每人每天要消耗一个物品，每个人只能消耗一种物品，求最多可以支撑多少天，输入为n，m，m件物品的种类编号

题解：扫描一遍记录所有种类的个数，数据范围奇小直接暴力也能写，但是注意能支撑x天说明也能支撑1~x天，所以是可以二分解的，把种类个数排序，每次从最大的开始扫，扫到0直接break，如果最后结果大于等于人数就往右二分，否则往左。
$$
\sum{p_i/ans} \ge n
$$
代码：（没写二分真是不好意思，有点懒，不过n写成i wa了一发，pos忘记改又wa一发不然上1700了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 1000;
int a[maxn];
int n, m;
vector <int> p;
int main(int argc,char *argv[])
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) scanf("%d", &a[i]);
    sort(a, a + m);
    int temp = a[0];
    p.push_back(1);
    for (int i = 1; i < m; ++i) {
        if (a[i] == temp) {
            p[p.size() - 1]++;
        } else {
            temp = a[i];
            p.push_back(1);
        }
    } //是不是很完美的扫描操作
    sort(p.begin(), p.end());
    int res = 0;
    for (int i = m / n; i > 0; --i) {
        int temp = 0;
        for (int j = p.size() - 1; j >= 0; --j) {
            if (p[j] < i) break;
            temp += p[j] / i;
        }
        if (temp >= n) {
            res = i;
            break;
        }
    }
    printf("%d\n", res);
    return 0;
}

C题 Fly

题意：从地球到火星，经过n个星球，路线从1-2-3-…-n-1，每次起飞降落都消耗燃料，求最初需要多少燃料，消耗燃料的质量为:
$$
\delta m = { m_{货物} + m_{燃料} \over a_i }
$$
题解：二分一下求解即可，听说dfs可以写但是感觉不好想而且说实话这个路线不太好处理所以直接写二分答案了，题目给出提示最初燃料质量不会超过1e9，注意点细节即可，详见代码注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 1005;

int n;
int a[maxn], b[maxn];
double m;

int main(int argc,char *argv[])
{
    scanf("%d%lf", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    scanf("%d", &b[n]); //细节先读b[n]，原因是它最后一步是降落在地球，这样循环里面就不用特判
    for (int i = 1; i < n; ++i) scanf("%d", &b[i]);
    double l = 0, r = 1e9+5;
    double mid, temp;
    int res = 0;
    int flag = 1;
    while (r - l > 1e-8) { //1e-10居然tle了有点不敢相信，最后1e-8只跑了30ms
        flag = 1;
        mid = (l + r) / 2;
        for (int i = 1; i <= n; ++i) {
            temp = (m + mid) / a[i];
            if (mid - temp > 1e-10) mid -= temp; //其实temp变量是个细节去常数，自己理解一下
            else {
                flag = 0;
                break;
            }
            temp = (m + mid) / b[i];
            if (mid - temp > 1e-10) mid -= temp;
            else {
                flag = 0;
                break;
            }
        }
        if (flag == 0) l = (l + r) / 2;
        else r = (l + r) / 2, res = 1; //res也可以直接记录r的值，这样记得把res初始化为-1
    }
    if (res == 0) printf("-1\n");
    else printf("%.10f\n", l);
    return 0;
}

D题 Rocket

题意：交互题，emmmmm，题巨长比赛中没有看懂，简单的猜数问题，你知道一个数一定小于等于m，然后机器会回答你的猜测，你猜x<res机器输出（需要你读入）-1，x==res输出0，x>res输出1，但是机器说实话是周期性的，就是说以n为周期，第x询问中机器会像x % n那次一样回答你，如果x % n那次是正确回答，那么x也是，反之亦然，错误回答的定义是输出正确回答的相反数，en cslnb

题解：emmmm真的是没有写交互题的经验根本无法动手，反正又是二分，为了知道机器一个周期内回答你的是正确还是错误，可以先询问n次1，因为x一定是大于等于1的（等于直接结束程序就好），回答1就说明为真否则为假，然后后面再二分的去询问，直到回答为0，二分logn复杂度60次之内绝对在1-1e6出结果了

注意事项：交互题是指，你手动输出询问，然后评测机端会返回值，你用读入接受那个返回的值，然后处理，直到得出一个结果，本题得出结果就是机器端返回0的时候

代码：（cslnb）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int m, n;
    cin >> m >> n;
    vector<int> a;
    for (int i = 0, x; i < n; i++)
    {
        cout << 1 << endl;
        cin >> x;
        if (x == 0) return 0;
        a.push_back(x);
    }
    int l = 1, r = m;
    for (int i = 0, x;; (++i) %= n)
    {
        int mid = l + r >> 1;
        cout << mid << endl;
        cin >> x;
        if (x == 0) return 0;
        if (a[i] == -1)
        {
            if (x == -1)
                l = mid + 1;
            else
                r = mid - 1;
        }
        else
        {
            if (x == 1)
                l = mid + 1;
            else
                r = mid - 1;
        }
    }
    return 0;
}

但是有一种nb的操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

int a[33];
int main()
{
    int m, n, l = 1;
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; ++i) {
        printf("%d\n", l);
        fflush(stdout);
        scanf("%d", &a[i]);
        if (a[i] == 0) exit(0);
        l++;
    }
    int r = m, mid, x, flag = 0;
    for (int i = 1; ; ++i) {
        flag++;
        if (flag > n) flag = 1;
        mid = l + r >> 1;
        printf("%d\n", mid);
        fflush(stdout);
        scanf("%d", &x);
        if (x == 0) exit(0);
        x *= a[flag];
        if (x == 1) l = mid + 1;
        else r = mid - 1;
    }
}

这段代码很nb看了一会才知道为什么是对的

首先它不像蔡队那样前n次询问1来判断，实际上你把l区间不断暴力向右枚举，得到答案0当然直接输出，但是在此之前如果没有0，说明1-l都比答案小，然后你在前n次询问不仅把机器正确的周期性得到了还缩短了区间，其他的就是x*a[flag]比蔡队的代码优美一点。

E题 Border

题意：给n个10进制数，求他们任意求和在k进制下的末位可以为多少，任意求和可以和自己求和，可以多次求和

题解：
$$
res = gcd(k, a_1, a_2, a_3, … ,a_n) * x (x \in R)
$$
​ 证明我当然是不会的，但是写出来就是对的，注意一点就是res==n时把它变成0加到首位，代码写丑了加了末位排了个序

​ 当然还是证明一下吧2333
$$
gcd(a, b) = ax_1 + by_1——————–1
$$
​ 拓展欧几里得定理一定有解

​ 这题就相当于
$$
gcd(a, b) = (ax_2 + by_2) \% k——————–2
$$
​ 由于只能做加法，x，y必须为正数

​ 将1式带入2式得
$$
ax_1+by_1=(ax_2+by_2)\%k
$$

$$
ax_1+by_1=ax_2+by_2 - k * temp
$$

$$
ktemp=a(x_2-x_1)+b*(y_2-y_1)
$$

​ 一定也是有解的，所以也就是说2式一定有解，然后还有个结论是a在k进制下乘上任意大于0的倍数（模k），能产生最小的数一定是gcd(a,k)，所以把a1~an全部求gcd得到a，然后按结论可知得解（ai都是a的倍数所以也不能产生新的解，全都是a的倍数）。然后注意一点就是k是a的倍数的话0也是解。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 1e5+5;

ll n, k;
ll a[maxn];
vector<ll>res;
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main(int argc,char *argv[])
{
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]), a[i] %= k;
    ll temp = k;
    for (int i = 1; i <= n; ++i) {
        temp = gcd(a[i], temp);
    }
    if (temp == 1) {
        printf("%lld\n", k);
        for (int i = 0; i < k; ++i) {
            printf("%d%c", i, i == k - 1 ? '\n' : ' ');
        }
    } else {
        printf("%lld\n", k / temp);
        ll gg = temp;
        while (gg <= k) res.push_back(gg % k), gg += temp;
        sort(res.begin(), res.end());
        for (int i = 0; i < res.size(); ++i) {
            printf("%lld%c", res[i], i == res.size() - 1? '\n' : ' ');
        }
    }
    return 0;
}

F题 Mars rover

题意：

题解：有机会再补一下吧树形dp