A.Supermarket—签到

题意：m 个超市，第 i 个超市买 b 千克苹果需要花费 a 元，也就是说 a/b 元可以买 1 千克苹果，现在需要 n 千克苹果，问最少花多少钱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    while (cin >> n >> m) {
        int a[n], b[n];
        double minn = 100;
        for (int i = 0; i < n; ++i) {
            cin >> a[i] >> b[i];
            minn = min(minn, a[i] * 1.0 / b[i]);
        }
        cout << fixed << setprecision(7) << minn * m << endl;
    }
    // system("pause");
    return 0;
}

B.Perfect Number—暴力打表

题意：给出整数 k 请找出满足条件的第 k 小的数：各个数位上的数之和为 10 的数

思路：先尝试本地打表就可以发现最大不超过 1e9，而时间给出 2000 ms，直接暴力枚举找满足条件的数存储起来，然后 O(1) 查询即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

bool check(int x) {
    int sum = 0;
    while (x) {
        sum += (x % 10);
        x /= 10;
    }
    return (sum == 10);
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    vector<int> vec;
    for (int i = 19; i <= 1e9; ++i) {  //2000ms最多1e9运算量
        if (check(i)) vec.push_back(i);
        if (vec.size() == 10000) break;
    }
    int k;
    while (cin >> k)
        cout << vec[k - 1] << endl;
    // system("pause");
    return 0;
}

C.Seat Arrangements—前缀和

题意：教室有 n 排座位，每有 m 个座位，将教室看做 n*m 的矩阵，. 代表一个空座位，* 代表座位被占用，现在需要在同一行或者同一列中找到连续的 k 个空座位，两种座位方式被认为是不同的当存在一个座位的位置不一样，请问有几种安排座位方式

思路：直接爆搜 TLE，注意因为是同一行或者同一列，所以我们可以借助前缀和，空座位存 1，被占座位存 0，分别为维护座位所在行和所在列的前缀和，那么如果某一行连续的 k 个座位的前缀和之差等于 k 则说明找到一个座位方式。还需要注意的是当 k 等于 1 的时候，只需要找横向或者竖向一个方向即可，否则会出现重复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e3 + 100;

char s[maxn][maxn];
int ver[maxn][maxn], hor[maxn][maxn];  //第i行第j列

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m, k;
    while (cin >> n >> m >> k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                cin >> s[i][j];
                if (s[i][j] == '*') {
                    ver[i][j] = ver[i - 1][j];
                    hor[i][j] = hor[i][j - 1];
                } else {
                    ver[i][j] = ver[i - 1][j] + 1;
                    hor[i][j] = hor[i][j - 1] + 1;
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {	//枚举横向起点
            for (int j = 1; j + k - 1 <= m; ++j) {
                if (hor[i][j + k - 1] - hor[i][j - 1] == k) ++ans;
            }
        }
        if (k != 1) {  //特判1的情况
            for (int j = 1; j <= m; ++j) {	//枚举竖向起点
                for (int i = 1; i + k - 1 <= n; ++i) {
                    if (ver[i + k - 1][j] - ver[i - 1][j] == k) ++ans;
                }
            }
        }
        cout << ans << endl;
    }
    // system("pause");
    return 0;
}

D.Substring—拓扑排序+DP

题意：有 n 个点 m 条边组成的有向图（可能存在自环），每个点对应一个小写字母，定义一个路径的权值为路径上出现次数最多的字母的数量，求出这个有向图中最大权值的路径的权值，如果为无限大输出 -1

思路： 参考博客  涉及找环借助拓扑排序，因为字母只有 26 个所以整个图最多由 26 个状态，我们可以用 dp[i][ch] 维护经过 i 点是字母 ch 的出现最大次数，这样在拓扑过程中保证走的是一条路径，所以可以用当前点的状态向其连接的点转移：设当前操作是从节点 x 走向节点 y，我们将 26 个字母的状态全部从 x 转移 y 去

  • 若 val[y]!=j就是字母不同，要么 y 节点还是保持原先路径走来的字母最大次数要么就是选择从当前 x 节点走来的字母的最大次数 dp[y][j]=max(dp[y][j],dp[x][j])

  • 否则的话节点 y 的字母和现在扫描到的字母相同，那么选择从 x 节点走来后这个字母的出现次数就要 +1，即 dp[y][j]=max(dp[y][j],dp[x][j]+1)

找环就统计拓扑了几个点，小于 n 说明有环输出 -1，否则答案就是每个点的每个状态中的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 100;

int val[maxn], in[maxn], dp[maxn][30];  //dp[i][ch]表示经过i点是字母ch出现的最大次数
vector<int> G[maxn];
char s[maxn];

signed main() {
    // ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin >> n >> m;
    scanf("%s", s + 1);
    for (int i = 1; i <= n; ++i) {
        val[i] = s[i] - 'a' + 1;
        dp[i][val[i]] = 1;  //初始化边界经过自身
    }
    while (m--) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        ++in[y];
    }
    queue<int> que;
    for (int i = 1; i <= n; ++i) {
        if (in[i] == 0)
            que.push(i);
    }
    int cnt = 0;
    while (!que.empty()) {  //每次取入度为0的点向其他向相邻的点走保证是一条路上的(相当于是从每条路的终点向起点走)
        int p = que.front();
        que.pop();
        ++cnt;                               //统计dp过的点数
        for (auto e : G[p]) {                //向其他方向走并转移dp
            for (int i = 1; i <= 26; ++i) {  //各个字母
                if (val[e] == i)             //下一个点可以当前点+1
                    dp[e][i] = max(dp[e][i], dp[p][i] + 1);
                else
                    dp[e][i] = max(dp[e][i], dp[p][i]);
            }
            --in[e];
            if (in[e] == 0) que.push(e);
        }
    }
    if (cnt < n)  //有环
        cout << -1 << endl;
    else {
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= 26; ++j)
                ans = max(ans, dp[i][j]);
        }
        cout << ans << endl;
    }
    // system("pause");
    return 0;
}