@Dmaxiya 2018-08-17T10:23:04.000000Z 字数 6483 阅读 930

Codeforces Round #494 (Div. 3)

列表项

Codeforces

Contests 链接：Codeforces Round #494 (Div. 3)
过题数：1
排名：5005/8406

A. Polycarp's Pockets

题意

给定 $n$ 个数字 $a_1，a_2,\cdots,a_n$ ，将这 $n$ 个数字放到任意多个口袋里，使得相同的数字不在同一个口袋里，问最少可以放到多少个口袋。

输入

第一行为一个整数 $n~(1\leq n\leq100)$ ，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq100)$ 。

输出

输出最少的口袋数量。

样例

输入	输出
6 1 2 4 3 3 2	2
1 100	1

题解

计算出现次数最多的数字个数。

过题代码

#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 = 100 + 100;
int n, x, Max;
int cnt[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif //Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        Max = 0;
        memset(cnt, 0, sizeof(cnt));
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &x);
            ++cnt[x];
            Max = max(Max, cnt[x]);
        }
        printf("%d\n", Max);
    }
    return 0;
}

B. Binary String Constructing

题意

给定 $a,b,x$ 三个整数，要求构造一个仅含有 $0$ 和 $1$ 的字符串，字符串满足 $0$ 的数量等于 $a$ ， $1$ 的数量等于 $b$ ，并且对于 $1\leq i<a+b$ ，有 $x$ 个 $i$ 满足条件 $a_i\neq a_{i+1}$ 。

输入

输入包含三个整数 $a,b,x~(1\leq a,b\leq100,1\leq x<a+b)$ ，数据保证有解。

输出

输出一个满足题意的 $01$ 字符串，如果有多解输出任意一个。

样例

输入	输出	提示
2 2 1	1100	$0011$ 和 $1100$ 都是合法的答案。
3 3 3	101100	以下答案都是合法的答案： $110100$ $101100$ $110010$ $100110$ $011001$ $001101$ $010011$ $001011$
5 3 6	01010100

题解

第一个字符一定是 $a$ 和 $b$ 中数量比较多的那个字符，然后从 $x$ 中预留一个数字作为后面将剩下所有的 $0$ 和 $1$ 输出的不同位，其他的 $x-1$ 个不同位直接按 $0101\cdots$ 或者 $1010\cdots$ 穿插填空即可（数位多的在前面）。

过题代码

#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 num[2], x;
char ch[3] = "01";
void Print(int Index) {
    while(num[Index] != 0) {
        printf("%c", ch[Index]);
        --num[Index];
    }
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif //Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d", &num[0], &num[1], &x) != EOF) {
        --x;
        if(num[0] < num[1]) {
            swap(num[0], num[1]);
            swap(ch[0], ch[1]);
        }
        printf("%c", ch[0]);
        --num[0];
        int Index = 0;
        while(x != 0) {
            Index = 1 - Index;
            printf("%c", ch[Index]);
            --num[Index];
            --x;
        }
        Print(Index);
        Print(1 - Index);
        printf("\n");
    }
    return 0;
}

C. Intense Heat

题意

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$ ，求这个序列中，所有子段长度不小于 $k$ 的平均值的最大值。

输入

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

输出

输出答案，如果答案与真实值误差在 $10^{-6}$ 以内，则认为输出是正确的。

样例

输入	输出
4 3 3 4 1 2	2.666666666666667

题解

直接按照题意计算即可，用一个前缀和可以更方便计算。

过题代码

#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 = 5000 + 100;
int n, k;
double ans;
double num[maxn], sum[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif //Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &k) != EOF) {
        ans = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%lf", &num[i]);
            sum[i] = sum[i - 1] + num[i];
        }
        for(int kk = k; kk <= n; ++kk) {
            for(int i = 0; i + kk <= n; ++i) {
                ans = max(ans, (sum[i + kk] - sum[i]) / kk);
            }
        }
        printf("%.10f\n", ans);
    }
    return 0;
}

D. Coins and Queries

题意

给定 $n$ 个整数 $a_1,a_2,\cdots,a_n$ ，每个整数都等于 $2$ 的非负整数次幂，对这些数字进行 $q$ 次询问，每次询问一个整数 $b_i$ ，问 $b_i$ 能否由 $n$ 个整数中的某些数字凑成，如果可以，输出最少的需要的 $a_i$ 的数量，否则输出 $-1$ 。任意两次询问之间是独立的。

输入

第一行为两个整数 $n,q~(1\leq n,q\leq2\times10^5)$ ，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq2\times10^9)$ ，数据保证对于每一个 $a_i$ ，一定是 $2$ 的非负整数次幂，接下来有 $q$ 个数字 $b_i$ ，表示第 $i$ 次询问需要得到的数字。

输出

对于每一个询问，如果可以凑成需要的数字，则输出需要的最少的 $a_i$ 的数量，否则输出 $-1$ 。

样例

输入	输出
5 4 2 4 8 2 4 8 5 14 10	1 -1 3 2

题解

用 $map$ 来存每一个数字对应出现的次数（最多只有 $30$ 个关键字），对于每次询问从大到小贪心即可。

过题代码

#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, q, x, ans, tmp;
map<LL, LL> mp;
map<LL, LL>::iterator it;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif //Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%I64d%I64d", &n, &q) != EOF) {
        mp.clear();
        for(int i = 0; i < n; ++i) {
            scanf("%I64d", &x);
            ++mp[x];
        }
        while(q--) {
            scanf("%I64d", &x);
            ans = 0;
            it = mp.end();
            do {
                --it;
                tmp = min(it->second, x / it->first);
                ans += tmp;
                x -= tmp * it->first;
            } while(x != 0 && it != mp.begin());
            if(x == 0) {
                printf("%I64d\n", ans);
            } else {
                printf("-1\n");
            }
        }
    }
    return 0;
}

E. Tree Constructing

题意

给定三个整数 $n,d,k$ ，要求构造出一个 $n$ 个节点的树，这棵树的直径为 $d$ ，且树上每个节点的度最大为 $k$ 。输出构造的树的方案。

输入

输入包含三个整数 $n,d,k~(1\leq n,d,k\leq4\times10^5)$ 。

输出

如果可以构造出这样一棵树，第一行输出 $YES$ ，接下去 $n-1$ 行，每行输出树上一条边的两个端点，表示构造出来的树上的一条边，输出必须是一棵合法的树且满足题意。

样例

输入	输出
6 3 3	YES 3 1 4 1 1 2 5 2 2 6
6 2 3	NO
10 4 3	YES 2 9 2 10 10 3 3 1 6 10 8 2 4 3 5 6 6 7
8 5 3	YES 2 5 7 2 3 7 3 1 1 6 8 7 4 3

题解

先将 $d\geq n$ 和 $n=2$ 的情况特判，然后构造一条长度为 $d$ 的链，将链的中点选为树根，其中一半是一条长度为 $\lfloor\frac{d}{2}\rfloor$ 的链，另一半是长度为 $\lceil\frac{d}{2}\rceil$ 的链，对链上的每一个节点都标记上以该节点为根子的树的最大深度，其中树根的深度标记为 $\lfloor\frac{d}{2}\rfloor$ ，接着一边 $dfs$ 一边加边，每个节点所代表的子树的最大深度等于其父节点的子树的最大深度减一，且在加边的过程中要保证每个节点的度不大于 $k$ 。

过题代码

#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 = 400000 + 100;
struct Node {
    int u, v;
    Node() {}
    Node(int uu, int vv) {
        u = uu;
        v = vv;
    }
};
int n, d, k, cnt, Index, root;
int depth[maxn];
Node ans[maxn];
vector<int> G[maxn];
void Add(int u, int v) {
    ans[cnt++] = Node(u, v);
    depth[v] = depth[u] - 1;
    G[u].push_back(v);
    G[v].push_back(u);
}
void dfs(int f, int x) {
    if(Index > n || depth[x] == 0) {
        return ;
    }
    int len = G[x].size();
    for(int i = 0; i < len; ++i) {
        int pos = G[x][i];
        if(pos != f) {
            dfs(x, pos);
        }
    }
    while((int)G[x].size() < k) {
        if(Index > n) {
            return ;
        }
        Add(x, Index);
        int tmp = Index;
        ++Index;
        dfs(x, tmp);
    }
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif //Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d", &n, &d, &k) != EOF) {
        if(d >= n) {
            printf("NO\n");
            continue;
        }
        if(n == 2) {
            printf("YES\n1 2\n");
            continue;
        }
        for(int i = 1; i <= n; ++i) {
            G[i].clear();
        }
        cnt = 0;
        for(int i = 2; i <= d + 1; ++i) {
            Add(i - 1, i);
        }
        root = d / 2 + 1;
        Index = d + 2;
        for(int i = 1; i <= d + 1; ++i) {
            if(i <= root) {
                depth[i] = d / 2 - (root - i);
            } else {
                depth[i] = (d - d / 2) - (i - root);
            }
        }
        dfs(root, root);
        bool flag = true;
        for(int i = 1; i <= n; ++i) {
            if((int)G[i].size() > k) {
                flag = false;
                break;
            }
        }
        if(!flag) {
            printf("NO\n");
            continue;
        }
        if(cnt == n - 1) {
            printf("YES\n");
            for(int i = 0; i < cnt; ++i) {
                printf("%d %d\n", ans[i].u, ans[i].v);
            }
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

Codeforces Round #494 (Div. 3)

A. Polycarp's Pockets

题意

输入

输出

样例

题解

过题代码

B. Binary String Constructing

题意

输入

输出

样例

题解

过题代码

C. Intense Heat

题意

输入

输出

样例

题解

过题代码

D. Coins and Queries

题意

输入

输出

样例

题解

过题代码

E. Tree Constructing

题意

输入

输出

样例

题解

过题代码

内容目录