@Dmaxiya 2018-08-17T10:23:55.000000Z 字数 5286 阅读 1072

Codeforces Round #441 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #441 (Div. 2)
过题数：4
排名：840/9270

A. Trip For Meal

题意

小熊维尼一天要吃 $n$ 次蜂蜜，而兔子、猫头鹰和屹耳的家里都有蜂蜜，最初他在兔子的家里，先吃一次蜂蜜，接着去另一个朋友的家里吃蜂蜜，假设当他离开某个朋友的家之后，这个朋友家里的蜂蜜就会恢复，给定三个朋友的家之间的距离，问小熊维尼想要吃 $n$ 次蜂蜜，最少要走多少米。

输入

输入包括四行整数，分别为 $n,a,b,c~(1\leq n,a,b,c\leq100)$ ，表示小熊要吃蜂蜜的次数、兔子和猫头鹰家之间的距离、兔子和屹耳家之间的距离以及猫头鹰和屹耳家之间的距离。

输出

输出要吃 $n$ 次蜂蜜，维尼至少要走的距离。

样例

输入	输出	提示
3 2 3 1	3	对于维尼来说最优的策略是：兔子 $\rightarrow$ 猫头鹰 $\rightarrow$ 屹耳。
1 2 3 5	0	维尼只要在兔子家吃一次蜂蜜，之后不需要移动任何距离。

题解

分别对 $n=1$ 和 $n\neq1$ 分情况按贪心策略讨论即可。

过题代码

#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
int n, a, b, c;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d%d", &n, &a, &b, &c) != EOF) {
        if(n == 1) {
            printf("0\n");
        } else {
            printf("%d\n", min(a, b) + (n - 2) * min(min(a, b), c));
        }
    }
    return 0;
}

B. Divisiblity of Differences

题意

给出 $n$ 个整数的序列 $a_1,a_2,\cdots,a_n$ ，从中找出 $k$ 个数字，使这 $k$ 个数字两两之间的差能整除 $m$ 。

输入

第一行包含三个整数 $n,k$ 和 $m~(2\leq k\leq n\leq10^5,1\leq m\leq10^5)$ ，第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n~(0\leq a_i\leq10^9)$ 。

输出

如果无法找出 $k$ 个满足要求的数字，就输出 $No$ ，否则在第一行输出 $Yes$ ，第二行输出 $k$ 个满足条件的整数，如果有多解，则输出任意一组。

样例

输入	输出
3 2 3 1 8 4	Yes 1 4
3 3 3 1 8 4	No
4 3 5 2 7 7 7	Yes 2 7 7

题解

如果每个数字对 $m$ 的模数相等，那么这几个数字任意两个数字之间的差一定是 $m$ 的倍数。

过题代码

#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 = 100000 + 100;
int n, k, m, num, Index;
vector<int> ans[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d", &n, &k, &m) != EOF) {
        Index = -1;
        for(int i = 0; i < n; ++i) {
            ans[i].clear();
        }
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num);
            ans[num % m].push_back(num);
            if((int)ans[num % m].size() >= k) {
                Index = num % m;
            }
        }
        if(Index == -1) {
            printf("No\n");
            continue;
        }
        printf("Yes\n");
        for(int i = 0; i < k; ++i) {
            if(i != 0) {
                printf(" ");
            }
            printf("%d", ans[Index][i]);
        }
        printf("\n");
    }
    return 0;
}

C. Classroom Watch

题意

给定一个数字 $n$ ，求有多少个数字 $x$ ，满足 $x+\sum_{i=0}^{dig_x}\lfloor\frac{x}{10^i}\rfloor\%10=n$ ，其中 $dig_x$ 表示数字 $x$ 的位数。

输入

输入只有一个整数 $n~(1\leq n\leq10^9)$ 。

输出

第一行输出一个整数 $k$ ，表示有 $k$ 个满足条件的数字，接下去 $k$ 行每行一个整数，表示每个满足条件的整数，按照从小到大的顺序输出。

样例

输入	输出	提示
21	1 15	$x=15$ 是唯一一个满足条件的数字： $15+1+5=21$ .
20	0	没有任何数字满足条件

题解

从数据范围可以知道，满足条件的数字一定在范围 $[\max(0,n-90),n]$ 内，因为 $10^9$ 内的数字所有数位的和最大为 $90$ ，所以暴力枚举 $90$ 个数字就能找到所有满足条件的答案。

过题代码

#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 = 300;
int n, cnt;
int ans[maxn];
int get_sum(int num) {
    int ret = num;
    while(num != 0) {
        ret += num % 10;
        num /= 10;
    }
    return ret;
}
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) {
        cnt = 0;
        for(int i = 0; i <= 90; ++i) {
            if(n - i >= 0) {
                if(get_sum(n - i) == n) {
                    ans[cnt++] = n - i;
                }
            }
        }
        printf("%d\n", cnt);
        for(int i = cnt - 1; i >= 0; --i) {
            if(i != cnt - 1) {
                printf(" ");
            }
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}

D. Sorting the Coins

题意

对一个长度为 $n$ 的序列，进行下面的操作：

从左到右扫一遍整个序列；

如果第 $i$ 个数字是被标记的，而第 $i+1$ 个数字是没有被标记的，就将第 $i$ 个数字和第 $i+1$ 个数字交换。

重复以上步骤，直到无法再对这个序列的任意两个数字进行交换。
定义一个序列的“难度”，为一个序列能进行以上操作的次数，如果这个序列已经不能再交换数字，它的“难度”为 $1$ 。
最初这个序列没有数字是被标记的，它的“难度”为 $1$ ，接着将这个序列每一位上的数字逐一标记，总共标记 $n$ 次，对这个序列的每次标记，输出这个序列的“难度”。

输入

第一行为一个整数 $n~(1\leq n\leq3\times10^5)$ ，第二行为 $1-n$ 的排列 $p_1,p_2,\cdots,p_n~(1\leq p_i\leq n)$ ，表示每次标记的数字为序列的第 $p_i$ 项。

输出

输出 $n+1$ 个数字 $a_0,a_1,a_2,\cdots,a_n$ ， $a_0$ 表示初始序列的“难度”， $a_i$ 表示第 $p_i$ 个数字被标记后序列的难度。

样例

输入	输出	提示
4 1 3 4 2	1 2 3 2 1	设 $O$ 表示没有被标记的数字， $X$ 表示被标记的数字，最初没有任何数字可以被交换，序列的“难度”为 $a_0=1$ ，第 $p_1=1$ 个数字被标记后，对序列的操作为： $XOOO\rightarrow OOOX$ 序列的“难度”为 $a_1=2$ ，第 $p_2=3$ 个数字被标记后，对序列的操作为： $XOXO\rightarrow OXOX\rightarrow OOXX$ 序列的“难度”为 $a_2=3$ ，第 $p_3=4$ 个数字被标记后，序列的操作为： $XOXX\rightarrow OXXX$ 序列的“难度”为 $a_3=2$ ，第 $P_4=2$ 个数字被标记后，序列的操作为： $XXXX$ 序列的“难度”为 $a_4=1$ 。
8 6 8 3 4 7 2 1 5	1 2 2 3 4 3 4 5 1

题解

每次操作的时候，最右边的所有被标记的数字都无法移动，且不在最右边的所有数字中，只能移动一个最右边的数字到最右边，如：
$XXXXOOXXXXOXXX$
一次操作之后变为
$XXXOOXXXXOXXXX$
最右边的 $3$ 个数字都无法移动，而前面的数字里，只有倒数第 $5$ 个数字能够移动到最右边，所以每次操作只能移动一个数字到最右边，因此总的操作次数就是已经被标记的数字个数 $-$ 最右边的数字个数，可以用并查集维护。

过题代码

#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 = 300000 + 100;
int n, x;
int fa[maxn], num[maxn];
bool vis[maxn];
void Init() {
    for(int i = 1; i <= n; ++i) {
        fa[i] = i;
        vis[i] = false;
        num[i] = 1;
    }
}
int Find(int x) {
    return (fa[x] == x? x: fa[x] = Find(fa[x]));
}
void unit(int x, int y) {
    int xx = Find(x);
    int yy = Find(y);
    if(xx != yy) {
        fa[xx] = yy;
        num[yy] += num[xx];
    }
}
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) {
        Init();
        printf("1");
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &x);
            vis[x] = true;
            if(vis[x - 1]) {
                unit(x - 1, x);
            }
            if(vis[x + 1]) {
                unit(x, x + 1);
            }
            int ans;
            if(vis[n]) {
                int f = Find(n);
                ans = i - num[f] + 1;
            } else {
                ans = i + 1;
            }
            printf(" %d", ans);
        }
        printf("\n");
    }
    return 0;
}

Codeforces Round #441 (Div. 2)

A. Trip For Meal

题意

输入

输出

样例

题解

过题代码

B. Divisiblity of Differences

题意

输入

输出

样例

题解

过题代码

C. Classroom Watch

题意

输入

输出

样例

题解

过题代码

D. Sorting the Coins

题意

输入

输出

样例

题解

过题代码

内容目录