@Dmaxiya 2018-08-17T10:22:53.000000Z 字数 5287 阅读 1081

Educational Codeforces Round 31

Codeforces

Contests 链接：Educational Codeforces Round 31
过题数：4
排名：93/7946

A. Book Reading

题意

$Luba$ 需要 $t$ 秒才能看完一本书，接下来的 $n$ 天时间里，第 $i$ 天需要花 $a_i$ 秒的时间工作，工作的时间不能看书。问她最少需要多少天才能看完书（每一天有 $86400$ 秒）。

输入

第一行有两个整数 $n,t~(1\leq n\leq100,1\leq t\leq10^6)$ ，第二行包含 $n$ 个数字 $a_1,a_2,\cdots,a_n~(0\leq a_i\leq86400)$ 。数据保证答案一定不大于 $n$ 。

输出

输出 $Luba$ 看完整本书需要的最少天数。

样例

输入	输出
2 2 86400 86398	2
2 86400 0 86400	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 = 100000 + 100;
int n, t, tmp;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &t) != EOF) {
        int ans = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &tmp);
            t -= (86400 - tmp);
            if(t <= 0 && ans == 0) {
                ans = i;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. Japanese Crosswords Strike Back

题意

对一个长度为 $x$ 的 $01$ 串， $n$ 为其中连续的 $1$ 的段数，第 $i$ 段连续的 $1$ 的个数为 $a_i$ ，例如 $01$ 串 $010111011$ ，它的 $n$ 就是 $3$ ， $a_i$ 的集合为 $\{1,3,2\}$ 。给定 $x,n$ 以及 $a_1,a_2,\cdots,a_n$ 的值，判断是否只存在唯一的满足条件的 $01$ 串。

输入

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

输出

如果只有唯一的 $01$ 串满足条件，则输出 $YES$ ，否则输出 $NO$ 。

样例

输入	输出
2 4 1 3	NO
3 10 3 3 2	YES
2 10 1 3	NO

题解

要判断只存在唯一的 $01$ 串满足条件，只需要判断 $a_1,a_2,\cdots,a_n$ 这些连续的 $1$ 的段以及段之间的间隔定为 $1$ 个 $0$ 是否正好等于 $x$ 即可，即判断 $n-1+\sum_{i=1}^na_i=x$ 是否为真。

过题代码

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

C. Bertown Subway

题意

有 $n$ 个城市，这个城市之间的道路满足以下两个条件：

对于第 $i$ 个城市，都有唯一一条从这个城市出发的道路，这条道路的终点是 $p_i$ ，允许出现 $p_i=i$ 的情况；

对于第 $i$ 个城市，都有唯一一条到达这个城市的道路，这条道路的起点为 $j$ 且 $p_j=i$ 。

问在最多修改两条道路的情况下，使得有序对 $(x,y)$ 的数量最多，如果图上存在从 $x$ 到 $y$ 的道路，则存在一个有序对 $(x,y)$ 。

输入

第一行为一个整数 $n~(1\leq n\leq10^5)$ ，第二行为 $n$ 个整数 $p_1,p_2,\cdots,p_n$ 。

输出

输出最多修改两条道路的情况下，图上最多的有序对数量。

样例

输入	输出	提示
3 2 1 3	9	可以将 $p_2$ 改为 $3$ ，将 $p_3$ 改为 $1$ ，这样就可以有 $9$ 个有序对 $(1,1),(1,2),(1,3),$ $(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)$ 。
5 1 5 4 3 2	17	可以将 $p_2$ 改为 $4$ 而将 $p_3$ 改为 $5$ 。

题解

对于按照题给方式生成的 $p$ 序列，一定是一个 $1-n$ 的排列，其中最多修改两条道路，相当于将排列中的两个环合并成一个环，由于有序对的数量等于环上节点数量的平方，所以应该将两个最多节点的环合并，如果只有一个环，则直接输出 $n^2$ 。

过题代码

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

D. Boxes And Balls

题意

有 $n$ 个箱子，最初在第 $1$ 个箱子里有 $n$ 种颜色的球，第 $i$ 种颜色的球的个数为 $a_i$ ，其他的箱子都是空的，可以通过以下的操作将第 $i$ 种颜色的求放入编号为 $i$ 的箱子里：

选择任意一个非空的箱子，将其中的所有的球从箱子里取出；

选择 $k$ 个空着的箱子（刚刚被取出球的箱子也可以被包括在其中），将刚刚取出的所有球分配到想分配的箱子中， $k$ 可以为 $2$ 或者 $3$ 。

某次操作的代价是从箱子中取出的球的总个数，而所有操作的代价等于每次操作的代价的和。问要将第 $1$ 个箱子中的所有的球都放到相应的箱子中，最少需要多少代价。

输入

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

输出

输出最少需要的代价。

样例

输入	输出
3 1 2 3	6
4 2 3 4 5	19

题解

可以从另一个方向考虑这个问题：将 $\sum_{i=1}^na_i$ 个球分到 $i$ 个箱子里使得第 $i$ 个箱子里的球的个数等于 $a_i$ ，每次只能拆成 $2$ 个或者 $3$ 个数字，每次拆的花费为 $x$ ， $x$ 表示被拆的数字，画出这棵树就可以发现这是一棵哈夫曼树，每个节点的子节点数为 $3$ ，如果 $n$ 为偶数，只要再加一个 $a_{n+1}=0$ 的节点即可。

过题代码

#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
struct Node {
    LL num;
    Node() {}
    Node(LL n) {
        num = n;
    }
};
bool operator<(const Node &a, const Node &b) {
    return a.num > b.num;
}
priority_queue<Node> que;
int n;
LL num;
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) {
        if(n == 1) {
            scanf("%I64d", &num);
            printf("0\n");
            continue;
        } else if(n == 2) {
            scanf("%I64d", &num);
            LL tmp;
            scanf("%I64d", &tmp);
            printf("%I64d", tmp + num);
            continue;
        }
        LL ans = 0;
        while(!que.empty()) {
            que.pop();
        }
        if(n % 2 == 0) {
            que.push(Node(0));
        }
        for(int i = 0; i < n; ++i) {
            scanf("%I64d", &num);
            que.push(Node(num));
        }
        while(que.size() != 1) {
            Node tmp1 = que.top();
            que.pop();
            Node tmp2 = que.top();
            que.pop();
            Node tmp3 = que.top();
            que.pop();
            Node tmp4(tmp1.num + tmp2.num + tmp3.num);
            ans += tmp4.num;
            que.push(tmp4);
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

Educational Codeforces Round 31

A. Book Reading

题意

输入

输出

样例

题解

过题代码

B. Japanese Crosswords Strike Back

题意

输入

输出

样例

题解

过题代码

C. Bertown Subway

题意

输入

输出

样例

题解

过题代码

D. Boxes And Balls

题意

输入

输出

样例

题解

过题代码

内容目录