@Dmaxiya 2018-08-17T10:23:18.000000Z 字数 3965 阅读 897

Codeforces Round #443 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #443 (Div. 2)
过题数：3
排名：162/10198

A. Borya's Diagnosis

题意

$Borya$ 病得很重，所以他需要按顺序依次到多个医生那里看病，第 $i$ 个医生的第一次上班时间为 $s_i$ ，之后每隔 $d_i$ 天上一次班，且每个医生看病都需要前一个医生的诊断结果，由于看病需要的时间非常久，所以 $Borya$ 每天只能去一个医生那里看病，他必须看到最后一个医生才能确诊。问如果给定 $n$ 个医生的第一天上班时间 $s_i$ 和上班周期 $d_i$ ， $Borya$ 最少需要多少天才能确诊。

输入

第一行包括一个整数 $n~(1\leq n\leq1000)$ ，接下去 $n$ 行每行两个整数 $s_i$ 和 $d_i~(1\leq s_i,d_i\leq1000)$ 。

输出

输出 $Borya$ 确诊的最短时间。

样例

输入	输出	提示
3 2 2 1 2 2 2	4	$Borya$ 可以在第 $2、3、4$ 天去看病。
2 10 1 6 5	11	$Borya$ 可以在第 $10、11$ 天看病。

题解

按照题意模拟。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
LL n, s, d;
LL day;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    while(scanf("%I64d", &n) != EOF) {
        day = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%I64d%I64d", &s, &d);
            if(day < s) {
                day = s;
            } else {
                day = ((day - s) / d + 1) * d + s;
            }
        }
        printf("%I64d\n", day);
    }
    return 0;
}

B. Table Tennis

题意

有 $n$ 个人排成一队进行乒乓球比赛，最开始队首的两个人出队进行比赛，失败的人到队尾等待下次比赛，胜利的人与当前队首的人继续进行比赛，连续 $k$ 场比赛胜利的人获得最终的胜利。每个人都有不同的 $power$ 值，两个 $power$ 值不同的人比赛， $power$ 值高的人将获胜，求获得最终胜利者的 $power$ 值。

输入

第一行包含两个整数 $n$ 和 $k~(2\leq n\leq500,2\leq k\leq10^{12})$ ，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq n)$ ，表示每个人的 $power$ 值，每个 $a_i$ 值都是不同的。

输出

输出最终获胜者的 $power$ 值。

样例

输入	输出	提示
2 2 1 2	2
4 2 3 1 2 4	3	$3$ 和 $1$ 比赛， $3$ 获胜且 $1$ 到队尾， $3$ 再和 $2$ 比赛， $3$ 第 $2$ 次获得胜利，连续两场比赛获得胜利，因此 $3$ 最终获胜。
6 2 6 5 3 1 2 4	6
2 10000000000 2 1	2

题解

如果 $k\leq n$ ，就直接按照题意模拟，否则直接输出 $n$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 600;
LL n, k;
int num;
queue<int> que;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    while(scanf("%I64d%I64d", &n, &k) != EOF) {
        while(!que.empty()) {
            que.pop();
        }
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num);
            que.push(num);
        }
        if(k > n) {
            printf("%I64d\n", n);
        } else {
            int win = 0;
            num = que.front();
            que.pop();
            while(true) {
                if(num > que.front()) {
                    int tmp = que.front();
                    que.pop();
                    que.push(tmp);
                    ++win;
                } else {
                    que.push(num);
                    num = que.front();
                    que.pop();
                    win = 1;
                }
                if(win >= k) {
                    break;
                }
            }
            printf("%d\n", num);
        }
    }
    return 0;
}

C. Short Program

题意

一个程序由 $n$ 个位运算符以及 $n$ 个 $[0,1023]$ 之间的数字组成，程序的输入为一个 $[0,1023]$ 范围内的整数，输出是将这个整数按顺序进行位运算后的结果，但是这个程序太长了，现在要将这个程序减少到五行以内，但是能实现的功能和原来的程序是一样的，输出最终的程序。

输入

第一行包含一个整数 $n~(1\leq n\leq5\times10^5)$ ，接下去 $n$ 行每行一个字符与一个整数 $x_i~(0\leq x_i\leq1023)$ ，字符 '&' '|' '^' 对应位运算中的与、或、异或运算。

输出

输出第一行为一个整数 $k(1\leq k\leq5)$ ，表示即将输出的程序的行数，接下去 $k$ 行输出格式与输入格式相同，执行的效果对于任意数字都能得到和原程序得到的结果相同。

样例

输入	输出	提示
3 $\|$ 3 ^ 2 $\|$ 1	2 $\|$ 3 ^ 2
3 & 1 & 3 & 5	1 & 1	假设 $x$ 为对程序输入的数字，则 $((x\&1)\&3)\&5=x\&(1\&3\&5)=x\&1$ 。
3 ^ 1 ^ 2 ^ 3	0

题解

一个数组来记每一位的状态：一定为 $1$ 、一定为 $0$ 、一定取反、一定等于原来的值，例如某个数字的某一位和 $3$ 相与，则低 $2$ 位一定等于原来的值，高位一定等于 $0$ ，其他运算根据运算规则确定状态，最后可以将一定为 $0$ 的位用 (& 0) 表示，将一定为 $1$ 的位用 (| 1) 表示，一定取反的位用 ('^' 1) 表示，一定和原来相等的位用 ('|' 0) 或者 ('&' 1) 或者 ('^' 0) 表示，最后只需要 $3$ 个运算符就可以表示所有运算。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 20;
int n, c;
char ch[2];
int num[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        memset(num, 0, sizeof(num));
        for(int i = 0; i < n; ++i) {
            scanf("%s%d", ch, &c);
            for(int j = 0; j < 10; ++j) {
                int tmp = ((c >> j) & 1);
                if(ch[0] == '&') {
                    if(tmp == 0) {
                        num[j] = 3;
                    }
                } else if(ch[0] == '|') {
                    if(tmp == 1) {
                        num[j] = 2;
                    }
                } else if(ch[0] == '^') {
                    if(tmp == 1) {
                        num[j] ^= 1;
                    }
                }
            }
        }
        int Xor = 0, Or = 0, And = 1023;
        for(int i = 0; i < 10; ++i) {
            if(num[i] == 1) {
                Xor |= (1 << i);
            } else if(num[i] == 2) {
                Or |= (1 << i);
            } else if(num[i] == 3) {
                And ^= (1 << i);
            }
        }
        printf("3\n");
        printf("| %d\n", Or);
        printf("^ %d\n", Xor);
        printf("& %d\n", And);
    }
    return 0;
}

Codeforces Round #443 (Div. 2)

A. Borya's Diagnosis

题意

输入

输出

样例

题解

过题代码

B. Table Tennis

题意

输入

输出

样例

题解

过题代码

C. Short Program

题意

输入

输出

样例

题解

过题代码

内容目录