Educational Codeforces Round 36

Codeforces

Contests 链接：Educational Codeforces Round 36
过题数：3
排名：1280/5237

A. Garden

题意

$Luba$ 要给 $k$ 个花园浇花，他有 $n$ 中浇花器可以选择，如果用第 $i$ 种浇花器浇花，他每秒可以浇连续的 $a_i$ 个花园，且不能浇到花园外面，现在问他要选择哪种浇花器，浇花的时间最少，输出最少时间。

数据范围

$(1\leq n,k\leq100)\\(1\leq a_i\leq100)$

题解

求出 $\min(\frac{k}{a_i})$，其中 $k \% a_i = 0$。

过题代码

#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 <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 200;
int n, k;
int num[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &k) != EOF) {
        int Min = INT_MAX;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
            if(k % num[i] == 0) {
                Min = min(Min, k / num[i]);
            }
        }
        printf("%d\n", Min);
    }
    return 0;
}

B. Browser

题意

$Luba$ 在上网，现在有 $n$ 个标签，编号为 $1$ 到 $n$，定义 $a$ 为最小的翻开着的标签编号，$b$ 为最大的翻开着的标签的编号，如果现在他的光标在第 $i$ 个标签上，他下一步可以将标签移动到 $\max(i-1,a)$ 或者 $\min(i+1,b)$，他下一步还可以将区间 $[a,i-1]$ 或者 $[i+1,b]$ 内的所有标签关闭，最初所有标签的状态都为翻开。问，现在他的光标在 $pos$ 上，如果他想要只关闭 $[l,r]$ 外的标签，最少需要做几步操作。

数据范围

$1\leq n\leq100\\1\leq pos\leq n,1\leq l\leq r\leq n$

题解

按 $l=1$，$r=n$，$pos$ 与 $l,r$ 的相对关系，贪心地分类讨论。

过题代码

#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 <functional>
#include <iomanip>
using namespace std;
#define LL long long
int n, pos, l, r;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d%d", &n, &pos, &l, &r) != EOF) {
        if(l == 1) {
            if(r == n) {
                printf("%d\n", 0);
            } else {
                if(pos <= r) {
                    printf("%d\n", r - pos + 1);
                } else {
                    printf("%d\n", pos - r + 1);
                }
            }
        } else {
            if(r == n) {
                if(pos >= l) {
                    printf("%d\n", pos - l + 1);
                } else {
                    printf("%d\n", l - pos + 1);
                }
            } else {
                if(pos >= l) {
                    if(pos <= r) {
                        printf("%d\n", r - l + min(pos - l, r - pos) + 2);
                    } else {
                        printf("%d\n", pos - l + 2);
                    }
                } else {
                    printf("%d\n", r - pos + 2);
                }
            }
        }
    }
    return 0;
}

C. Permute Digits

题意

给定两个数字 $a$ $b$，求将 $a$ 的每个位置上的数字排列后，能够得到的不大于 $b$ 的最大的数字，题目保证有解。

数据范围

$1\leq a,b\leq10^{18}$

题解

一遍深搜。

过题代码

#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 <functional>
#include <iomanip>
using namespace std;
#define LL long long
char a[50];
LL ten[20];
int dig;
LL b, ans;
int num[50];
bool dfs(int depth, LL tmp) {
    if(depth == -1) {
        ans = tmp;
        return true;
    }
    for(int i = 9; i >= 0; --i) {
        if(num[i] != 0) {
            if(tmp + ten[depth] * i <= b) {
                --num[i];
                if(dfs(depth - 1, tmp + ten[depth] * i)) {
                    return true;
                }
                ++num[i];
            }
        }
    }
    return false;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    ten[0] = 1;
    for(int i = 1; i <= 18; ++i) {
        ten[i] = ten[i - 1] * 10;
    }
    while(scanf("%s%I64d", a, &b) != EOF) {
        memset(num, 0, sizeof(num));
        dig = 0;
        for(int i = 0; a[i]; ++i) {
            ++num[a[i] - '0'];
            ++dig;
        }
        --dig;
        dfs(dig, 0);
        printf("%I64d\n", ans);
    }
    return 0;
}

D. Almost Acyclic Graph

题意

问在一个 $n$ 个节点，$m$ 条边的有向图上，能不能最多删掉一条边，使得这张图变成一个无环图。

数据范围

$2\leq n\leq500\\1\leq m\leq\min(n\times(n - 1),10^5)$

题解

最暴力的做法，是将每一条边都删掉一次，删掉之后，拓扑排序判断是否还存在环，但是对于拓扑排序而言，删掉一条边，相当于将一个点的入度减一，如果有多条边指向同一个节点，删掉它们的操作相当于都是将这个节点的入度减一，所以只要将每个点的入度减一，再进行拓扑排序即可。

过题代码

#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 <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 600;
int n, m, u, v;
int deg[maxn], in[maxn];
bool ins[maxn];
queue<int> que;
vector<int> G[maxn];
bool topsort() {
    memcpy(in, deg, sizeof(deg));
    for(int i = 1; i <= n; ++i) {
        if(in[i] == 0) {
            que.push(i);
        }
    }
    while(!que.empty()) {
        int x = que.front();
        que.pop();
        int len = G[x].size();
        for(int i = 0; i < len; ++i) {
            int pos = G[x][i];
            --in[pos];
            if(in[pos] == 0) {
                que.push(pos);
            }
        }
    }
    for(int i = 1; i <= n; ++i) {
        if(in[i] > 0) {
            return false;
        }
    }
    return true;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        for(int i = 1; i <= n; ++i) {
            G[i].clear();
        }
        for(int i = 0; i < m; ++i) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            ++deg[v];
        }
        bool f = false;
        for(int i = 1; i <= n; ++i) {
            --deg[i];
            f = topsort();
            if(f) {
                break;
            }
            ++deg[i];
        }
        if(f) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}