@Dmaxiya 2018-08-17T10:17:46.000000Z 字数 9164 阅读 1026

Codeforces Round #499 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #499 (Div. 2)
过题数：5
排名：145/7830

A. Stages

题意

给出 $n$ 个小写字母，从中选出 $k$ 个小写字母构成一个字符串，要求构成的字符串中 $t_i-t_{i-1}\geq2~(i>1)$ ，要使字符串所有字符的权值和最小，输出最小权值和，每个字符对应的权值大小为 $ASCII(ch)-ASCII('a')+1$ 。

输入

第一行为两个整数 $n,k~(1\leq k\leq n\leq50)$ ，第二行为一个长度为 $50$ 的字符串，字符串只包含小写字母。

输出

输出构成的字符串的最小权值，如果无法构成满足条件的字符串，输出 $-1$ 。

样例

输入	输出	提示
5 3 xyabd	29	以下为所有合法的字符串以及对应的权值： "adx"(权值为 $1+4+24=29$ )； "ady"(权值为 $1+4+25=30$ )； "bdx"(权值为 $2+4+24=30$ )； "bdy"(权值为 $2+4+25=31$ )。 "adx" 是权值最小的字符串，权值为 $29$ 。
7 4 problem	34	最优的字符串 "belo" 的权值为 $2+5+12+15=34$ 。
2 2 ab	-1	$n$ 和 $k$ 的值都为 $2$ ，所以只能将 $a$ 和 $b$ 都选上，但是 "ab" 并不是满足条件的字符串，因此应该输出 $-1$ 。
12 1 abaabbaaabbb	1

题解

贪心按从小到大找出满足条件的字符串。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 100;
int n, k, cnt;
char str[maxn], ans[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d%s", &n, &k, str) != EOF) {
        cnt = 0;
        int len = strlen(str);
        sort(str, str + len);
        ans[++cnt] = str[0];
        for(int i = 1; str[i]; ++i) {
            if(str[i] - ans[cnt] > 1) {
                ans[++cnt] = str[i];
            }
        }
        if(cnt < k) {
            printf("-1\n");
            continue;
        }
        int sum = 0;
        for(int i = 1; i <= k; ++i) {
            sum += ans[i] - 'a' + 1;
        }
        printf("%d\n", sum);
    }
    return 0;
}

B. Planning The Expedition

题意

有 $n$ 个人和 $m$ 袋食物，第 $i$ 个袋子里装的食物种类是 $a_i$ ，每个人每天要吃一袋食物，且他们必须从头到尾都只吃同一种食物。问这些食物最多能够所有人吃多少天。

输入

第一行包含两个整数 $n,m~(1\leq n,m\leq100)$ ，第二行包含 $m$ 个整数 $a_1,a_2,\cdots,a_m~(1\leq a_i\leq m)$ 。

输出

输出最多的天数。

样例

输入	输出	提示
4 10 1 5 2 1 1 1 2 5 7 2	2	可以将第 $1$ 种食物分配给第 $1,2$ 个人，第 $2$ 种食物分配给第 $3$ 个人，第 $5$ 种食物分配给第 $4$ 个人。
100 1 1	0	总共有 $100$ 个人而只有 $1$ 袋食物，他们连一天都撑不过。
2 5 5 4 3 2 1	1
3 9 42 42 42 42 42 42 42 42 42	3

题解

暴力从 $m$ 到 $0$ 枚举所有人能够撑过的天数，对于每一个 $i$ ，贪心检查他们是否能够撑过这些天，如果他们能够撑过 $i$ 天，那么每个人都给他们分 $i$ 袋一个种类的食物，看最后食物是否够分。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 100 + 100;
int n, m, ans, x;
int num[maxn], tmp[maxn];
bool judge(int x) {
    int Index = 1;
    memcpy(tmp, num, sizeof(num));
    for(int i = 1; i <= n; ++i) {
        while(Index <= 100 && tmp[Index] < x) {
            ++Index;
        }
        if(Index > 100) {
            return false;
        }
        tmp[Index] -= x;
    }
    return true;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        memset(num, 0, sizeof(num));
        for(int i = 1; i <= m; ++i) {
            scanf("%d", &x);
            ++num[x];
        }
        for(int i = m; i >= 0; --i) {
            if(judge(i)) {
                ans = i;
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Fly

题意

一个火箭要从第 $1$ 个星球经过 $n-1$ 个星球后回到第 $1$ 个星球，每到达一个星球都要经历降落与升空的过程，由于每个星球的引力不同，在每个星球降落与升空的过程中需要消耗的动力也不同。
火箭自身有一个质量 $m$ ，如果到达第 $i$ 个星球时的油的质量为 $x$ 吨，且在降落/升空过程中每吨重量需要消耗的油量为 $y$ 吨，则在这个过程中需要消耗的总油量为 $\frac{x+m}{y}$ 。在第 $i$ 个星球升空时每吨重量需要消耗的油量为 $a_i$ 吨，降落时每吨重量消耗的油量为 $b_i$ 吨，问要完成整个任务所需要的最少油量为多少。

输入

前两行为两个整数 $n,m~(2\leq n\leq1000,1\leq m\leq1000)$ ，第三行为 $n$ 个整数 $a_1,a_2,\cdots,a_n$ ，第四行为 $n$ 个整数 $b_1,b_2,\cdots,b_n$ ，其中 $1\leq a_i,b_i\leq1000$ 。

输出

输出完成任务需要的最少油量，如果无法完成任务，则输出 $-1$ ，误差在 $10^{-6}$ 以内都认为答案正确。

样例

输入	输出	提示
2 12 11 8 7 5	10.0000000000	火箭的初始质量为 $22$ ：离开第 $1$ 个星球需要的油的质量为 $2$ 吨，剩下 $20$ 吨总质量；在第 $2$ 个星球降落时的总质量为 $20$ ，需要的油的质量为 $4$ 吨，剩下 $16$ 吨总质量；离开第 $2$ 个星球需要的油的质量为 $2$ 吨，剩下 $14$ 吨总质量；在第 $1$ 个星球降落需要的油的质量为 $2$ 吨，剩下 $12$ 吨总质量，油刚好用完。
3 1 1 4 1 2 5 3	-1	火箭永远都无法离开第 $1$ 个星球。
6 2 4 6 3 3 5 6 2 6 3 6 5 3	85.4800000000

题解

$a_i,b_i$ 中只要存在 $1$ 个 $1$ ，就永远无法完成任务，否则可以二分初始油量，每次 $O(n)$ 判断油量是否会在中途消耗完，为减少精度误差，二分 $500$ 次。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
bool flag;
int n, m;
int a[maxn], b[maxn];
bool judge(double mid) {
    for(int i = 1; i <= n; ++i) {
        int ii = (i + 1) % n;
        if(ii == 0) {
            ii = n;
        }
        mid -= (m + mid) / a[i];
        if(mid < 0) {
            return false;
        }
        mid -= (m + mid) / b[ii];
        if(mid < 0) {
            return false;
        }
    }
    return true;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        flag = true;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            if(a[i] == 1) {
                flag = false;
            }
        }
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &b[i]);
            if(b[i] == 1) {
                flag = false;
            }
        }
        if(!flag) {
            printf("-1\n");
            continue;
        }
        double low = 0;
        double high = 1e9;
        double mid;
        for(int i = 0; i < 500; ++i) {
            mid = (low + high) / 2;
            if(judge(mid)) {
                high = mid;
            } else {
                low = mid;
            }
        }
        printf("%.10f\n", high);
    }
    return 0;
}

D. Rocket

题意

$Natasha$ 和机器人玩一个猜数字的游戏，要被猜中的数字为 $x$ ，最开始机器人会告诉 $Natasha$ 两个整数 $n,m$ ，表示 $x\in[1,m]$ ， $Natasha$ 每次询问一个整数 $y$ ，如果 $x<y$ ，正确的回复应该是 $-1$ ，如果 $x=y$ ，正确的回复应该是 $0$ ，如果 $x>y$ ，正确的回复应该是 $1$ ，机器人自己有一个长度为 $n$ 的 $01$ 序列， $Natasha$ 不知道这个序列是什么样的，机器人在 $Natasha$ 的第 $i$ 次询问中（ $i$ 从 $0$ 开始计数），如果序列中的第 $i\%n$ 个数字为 $1$ ，则机器人会回复正确的值 $t$ ，否则会回复 $-t$ 。要求 $Natasha$ 在 $60$ 次询问内猜中 $x$ 。

输入

第一次输入为两个整数 $n,m~(1\leq n\leq30,1\leq m\leq10^9)$ ，之后的输入根据题给规则给出。

输出

每次输出一个整数 $y~(1\leq y\leq m)$ ，要求在 $60$ 次输出内得到 $x$ 的值，且程序必须在得到 $0$ 的回复时立即退出。

样例

输入	输出	提示
5 2 1 -1 -1 1 0	1 2 4 5 3	机器人自身的序列为 $1~0$ ，最终的答案为 $3$ 在第 $0$ 次询问中 $y=1$ ，此时 $y<x$ ，正确回复为 $1$ ，序列中的第 $0$ 个数字为 $1$ ，因此机器人最终的回复为 $1$ ；在第 $1$ 次询问中 $y=2<x$ ，正确的回复为 $1$ ，序列中第 $1$ 个数字为 $0$ ，因此机器人最终的回复为 $-1$ ；在第 $2$ 次询问中 $y=4>x$ ，正确的回复为 $-1$ ，序列中的第 $0$ 个数字为 $1$ ，因此机器人最终的回复为 $-1$ ；在第 $3$ 次询问中 $y=3=x$ ，正确的回复为 $0$ ，序列中第 $1$ 个数字为 $0$ ，因此机器人最终的回复为 $0$ 。

题解

先输出 $n$ 次 $1$ ，如果 $x=1$ 则可以立即得到结果，否则由于所有可能的 $x$ 一定都大于 $1$ ，就可以根据得到的 $1$ 和 $-1$ 的序列得到机器人的 $01$ 序列，再进行 $\log m$ 次的二分询问，就可以得到答案。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 100 + 100;
int n, m, x;
int num[maxn];
int main() {
    #ifdef Dmaxiya
//    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    scanf("%d%d", &m, &n);
    printf("1\n");
    fflush(stdout);
    scanf("%d", &x);
    if(x == 0) {
        return 0;
    }
    num[0] = x;
    for(int i = 1; i < n; ++i) {
        printf("1\n");
        fflush(stdout);
        scanf("%d", &num[i]);
    }
    int low = 1;
    int high = m + 1;
    int mid;
    int Index = 0;
    while(high - low > 1) {
        mid = (low + high) / 2;
        printf("%d\n", mid);
        fflush(stdout);
        scanf("%d", &x);
        if(x == 0) {
            return 0;
        }
        if(num[Index] == -1) {
            x = -x;
        }
        if(x == 1) {
            low = mid;
        } else {
            high = mid;
        }
        Index = (Index + 1) % n;
    }
    return 0;
}

E. Border

题意

给定 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 以及 $k$ 的值，求 $(\sum_{i=1}^nc_ia_i)\%k$ 的所有取值，其中 $c_i$ 为任意非负整数且 $\sum_{i=1}^nc_i>0$ 。

输入

第一行为两个整数 $n,k~(1\leq n\leq10^5,2\leq k\leq10^5)$ ，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq10^9)$ 。

输出

第一行输出一个整数 $d$ 表示所有取值的数量，第二行按从小到大的顺序输出所有 $(\sum_{i=1}^nc_ia_i)\%k$ 的值。

样例

输入	输出	提示
2 8 12 20	2 0 4	$12\%8=4$ ； $(12+20)\%8=0$ ； $(20+20)\%8=0$ ；即使有其他的系数 $c_i$ 使 $c_1a_1+c_2a_2$ 得到其他的值，但是所有其他值对 $8$ 取模后的值都为 $0$ 或者 $4$ 。
3 10 10 20 30	1 0	三个数字都是 $10$ 的倍数，因此无论如何组合它们的和都是 $10$ 的倍数。

题解

对于任意一个数字 $a$ ，其 $ca\%k$ 的值一定是 $\gcd(a,k)$ 的倍数，两个数字 $a_1,a_2$ 任意组合再对 $k$ 取模的值一定是 $\gcd(k,a_1,a_2)$ ，以此类推，只要得到所有数字与 $k$ 的最大公约数即可。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n, k;
int num[maxn];
int gcd(int a, int b) {
    return (b == 0? a: gcd(b, a % b));
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &k) != EOF) {
        int g = k;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
            g = gcd(g, num[i]);
        }
        printf("%d\n", k / g);
        for(int i = 0; i < k; i += g) {
            if(i != 0) {
                printf(" ");
            }
            printf("%d", i);
        }
        printf("\n");
    }
    return 0;
}

F. Mars rover

题意

给出一个由 $n$ 个元器件组成的电路，每个元器件的功能只可能是“输入”、“与运算”、“或运算”、“非运算”、“异或运算”中的一个，整个电路是一个树形结构，只有一个输出，如果对某个输入取反，则可能会改变最终的输出，问对于每一个输入，如果仅将这个输入取反，得到的最终输出的结果。

输入

第一行包含一个整数 $n~(2\leq 10^6)$ ，接下去 $n$ 行，第 $i$ 行的第一个字符串表示元器件类型："IN"、"AND"、"OR"、"XOR"、"NOT"，其中 "AND"、"OR"、"XOR" 后面跟两个数字，表示这个元器件的两个输入元器件编号，"NOT" 后面跟一个数字，表示这个元器件的一个输入元器件的编号，"IN" 后面跟着 $0$ 或者 $1$ ，表示这个输入元器件的初始输入值。数据保证最终输出元器件编号为 $1$ 。

输出

按元器件编号从小到大的顺序输出每一个输入元器件取反后输出的值，每一个输入元器件取反是相互独立的，即每个输出都是在仅改变一个输入元器件的值的情况下的输出。

样例

输入	输出	提示
10 AND 9 4 IN 1 IN 1 XOR 6 5 AND 3 7 IN 0 NOT 10 IN 1 IN 1 AND 2 8	10110	对应的元器件结构如下图：其中绿色元器件表示这个元器件的计算结果为 $1$ ，黄色表示值为 $0$ ：如果改变输入 $2$ 的值为 $0$ ，则输出为 $1$ ；如果改变输入 $3$ 的值为 $0$ ，则输出的值为 $0$ ；如果改变输入 $6$ 的值为 $1$ ，则输出的值为 $1$ ；如果改变输入 $8$ 的值为 $0$ ，则输出的值为 $1$ ；如果改变输入 $9$ 的值为 $0$ ，则输出的值为 $0$ 。

题解

由于每修改一个输入元器件的值，都只会修改树上一条路径上的值，与其他路径无关，所以可以预处理第 $i$ 个元器件的计算结果修改为 $x$ 且其他元器件的计算结果不变时，最终输出的值，两次 $dfs$ 就可以得到结果。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <sstream>
using namespace std;
#define LL unsigned long long
const int maxn = 1000000 + 100;
int n, l, r;
char str[maxn][10];
int num[maxn], Y[maxn][2];
vector<int> G[maxn];
void dfs1(int x) {
    int len = G[x].size();
    for(int i = 0; i < len; ++i) {
        dfs1(G[x][i]);
    }
    switch(str[x][0]) {
    case 'A': num[x] = num[G[x][0]] & num[G[x][1]]; break;
    case 'O': num[x] = num[G[x][0]] | num[G[x][1]]; break;
    case 'X': num[x] = num[G[x][0]] ^ num[G[x][1]]; break;
    case 'N': num[x] = 1 - num[G[x][0]]; break;
    default: break;
    }
}
void dfs2(int x) {
    int len = G[x].size();
    for(int i = 0; i < len; ++i) {
        int xx = 1 - num[G[x][i]];
        switch(str[x][0]) {
        case 'A': Y[G[x][i]][xx] = Y[x][xx & num[G[x][1 - i]]]; break;
        case 'O': Y[G[x][i]][xx] = Y[x][xx | num[G[x][1 - i]]]; break;
        case 'X': Y[G[x][i]][xx] = Y[x][xx ^ num[G[x][1 - i]]]; break;
        case 'N': Y[G[x][i]][xx] = Y[x][1 - xx]; break;
        default: break;
        }
        dfs2(G[x][i]);
    }
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        for(int i = 1; i <= n; ++i) {
            num[i] = -1;
            G[i].clear();
            scanf("%s", str[i]);
            if(str[i][0] == 'I') {
                scanf("%d", &num[i]);
            } else if(str[i][0] == 'A' || str[i][0] == 'O' || str[i][0] == 'X') {
                scanf("%d%d", &l, &r);
                G[i].push_back(l);
                G[i].push_back(r);
            } else if(str[i][0] == 'N') {
                scanf("%d", &l);
                G[i].push_back(l);
            }
        }
        dfs1(1);
        for(int i = 1; i <= n; ++i) {
            Y[i][num[i]] = num[1];
        }
        Y[1][1 - num[1]] = 1 - num[1];
        dfs2(1);
        for(int i = 1; i <= n; ++i) {
            if(str[i][0] == 'I') {
                printf("%d", Y[i][1 - num[i]]);
            }
        }
        printf("\n");
    }
    return 0;
}

Codeforces Round #499 (Div. 2)

A. Stages

题意

输入

输出

样例

题解

过题代码

B. Planning The Expedition

题意

输入

输出

样例

题解

过题代码

C. Fly

题意

输入

输出

样例

题解

过题代码

D. Rocket

题意

输入

输出

样例

题解

过题代码

E. Border

题意

输入

输出

样例

题解

过题代码

F. Mars rover

题意

输入

输出

样例

题解

过题代码

内容目录