Codeforces Round #460 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #460 (Div. 2)
过题数：3
排名：2001/13616

A. Supermarket

题意

有 $n$ 个超市，每个超市里的苹果价格为 $a$ 元每 $b$ 千克，现在要买 $m$ 千克的苹果，问最少需要花费多少元。

输入

第一行为两个整数 $n,m~(1\leq n\leq5000,1\leq m\leq100)$，接下去 $n$ 行每行两个整数 $a,b~(1\leq a,b\leq100)$。

输出

输出要买 $m$ 千克苹果的最小花费，与标准答案误差在 $10^{-6}$ 内都认为程序是正确的。

样例

题解

对每一个超市计算一次 $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 <algorithm>
using namespace std;
#define LL long long
int n, m;
double a, b;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        double ans = INT_MAX;
        for(int i = 0; i < n; ++i) {
            scanf("%lf%lf", &a, &b);
            ans = min(ans, a / b * m);
        }
        printf("%.10f\n", ans);
    }
    return 0;
}

B. Perfect Number

题意

如果一个数字各个位上的数字和等于 $10$，那么这个数字就是“完美数”，现在给定数字 $k$，求第 $k$ 小的“完美数”。

输入

输入只包含一个整数 $k~(1\leq k\leq10000)$。

输出

输出第 $k$ 小的“完美数”。

样例

题解

打表预处理，打表到 $2\times10^7$ 可以得到最小的 $10000$ 个答案。

过题代码

#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 <algorithm>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n, cnt;
int ans[maxn];
bool judge(int x) {
    int tmp = 0;
    while(x != 0) {
        tmp += x % 10;
        x /= 10;
    }
    return tmp == 10;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    cnt = 1;
    for(int i = 1; i <= 20000000; ++i) {
        if(judge(i)) {
            ans[cnt++] = i;
        }
    }
    while(scanf("%d", &n) != EOF) {
        printf("%d\n", ans[n]);
    }
    return 0;
}

C. Seat Arrangements

题意

在一个 $n\times m$ 的字符矩阵里，问在同一行或者同一列内总共能找到多少个连续的 $k$ 个 .。

输入

第一行为三个整数 $n,m,k~(1\leq n,m,k\leq2000)$，接下去 $n$ 行每行 $m$ 个字符，每个字符只可能是 . 或者 *。

输出

输出答案。

样例

题解

直接按照题意横着、竖着各扫一次，注意特判 $k=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 <algorithm>
using namespace std;
#define LL long long
const int maxn = 2000 + 100;
int n, m, k, ans;
char str[maxn][maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d", &n, &m, &k) != EOF) {
        ans = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%s", str[i]);
            int tmp = 0;
            for(int j = 0; j < m; ++j) {
                if(str[i][j] == '.') {
                    ++tmp;
                } else {
                    tmp = 0;
                }
                if(tmp >= k) {
                    ++ans;
                }
            }
        }
        for(int j = 0; j < m; ++j) {
            int tmp = 0;
            for(int i = 0; i < n; ++i) {
                if(str[i][j] == '.') {
                    ++tmp;
                } else {
                    tmp = 0;
                }
                if(tmp >= k) {
                    ++ans;
                }
            }
        }
        if(k == 1) {
            ans /= 2;
        }
        printf("%d\n", ans);
    }
    return 0;
}

D. Substring

题意

在一个 $n$ 个节点 $m$ 条边的有向图上，每个节点上都有一个小写字母，定义一条路径的权值为这条路径上所有节点的字符出现次数的最大值，输出图上所有路径的最大权值。

输入

第一行为两个整数 $n,m~(1\leq n,m\leq3\times10^5)$，第二行为一个字符串 $s~(|s|=n)$，第 $i$ 个小写字母表示第 $i$ 个节点上的字符，接下去 $m$ 行每行两个整数 $x,y~(1\leq x,y\leq n)$，表示从节点 $x$ 到节点 $y$ 有一条边。给出的图可能有自环、重边。

输出

如果最大权值为无穷大，则输出 $-1$，否则输出最大权值。

样例

题解

如果图上存在环则输出 $-1$，用拓扑排序判环，用一个 $dp[i][j]$ 数组记录到达第 $i$ 个节点时，字符 $j$ 出现的最大次数，$dp$ 的转移可以在拓扑排序的同时进行。

过题代码

#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 <algorithm>
using namespace std;
#define LL long long
const int maxn = 300000 + 100;
int n, m, u, v, ans;
char str[maxn];
int deg[maxn], dp[maxn][26];
vector<int> G[maxn];
queue<int> que;
int id(char ch) {
    return ch - 'a';
}
bool topsort() {
    for(int i = 1; i <= n; ++i) {
        if(deg[i] == 0) {
            que.push(i);
            int w = id(str[i]);
            ++dp[i][w];
        }
    }
    while(!que.empty()) {
        int tmp = que.front();
        que.pop();
        int len = G[tmp].size();
        for(int i = 0; i < len; ++i) {
            int pos = G[tmp][i];
            --deg[pos];
            if(deg[pos] == 0) {
                que.push(pos);
            }
            for(int j = 0; j < 26; ++j) {
                int d = (id(str[pos]) == j);
                dp[pos][j] = max(dp[pos][j], dp[tmp][j] + d);
            }
        }
    }
    for(int i = 1; i <= n; ++i) {
        if(deg[i] != 0) {
            return true;
        }
    }
    return false;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF){
        ans = 0;
        for(int i = 1; i <= n; ++i) {
            G[i].clear();
            deg[i] = 0;
            for(int j = 0; j < 26; ++j) {
                dp[i][j] = 0;
            }
        }
        scanf("%s", str + 1);
        for(int i = 0; i < m; ++i) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            ++deg[v];
        }
        if(topsort()) {
            printf("-1\n");
            continue;
        }
        for(int i = 1; i <= n; ++i) {
            for(int j = 0; j < 26; ++j) {
                ans = max(ans, dp[i][j]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}