AtCoder Beginner Contest 338 A~F

A.Capitalized?（模拟）

题意：

给一个字符串 $s$ ，询问 $s$ 的第一个字母是不是大写，并且其他字母都是小写。

分析：

使用 $A SC II$ 码，单独判断第一个字母，循环判断其他字母即可。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int main() {
    string s;
    cin >> s;
    int flag = 1;
    if (s[0] >= 'A' and s[0] <= 'Z') {
        for (int i = 1; i < s.size(); i++) {
            if (s[i] >= 'a' and s[i] <= 'z')
                continue;
            else {
                flag = 0;
                break;
            }
        }
        if (flag)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

B.Frequency（模拟）

题意：

给一个字符串 $s$ ，请找出出现次数最多的字符，如果存在多个，输出字典序最小的字符。

分析：

统计每个字母出现次数，按照字典序遍历即可。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int main() {
    string s;
    cin >> s;
    vector<int> cnt(1005, 0);
    int maxval = 0;
    for (int i = 0; i < s.size(); i++) {
        cnt[s[i] - 'a']++;
        maxval = max(maxval, cnt[s[i] - 'a']);
    }
    for (int i = 0; i < 26; i++) {
        if (maxval == cnt[i]) {
            cout << (char) (i + 'a') << endl;
            return 0;
        }
    }
    return 0;
}

C.Leftover Recipes（循环枚举）

题意：

给出 $n$ 种菜，每种菜有 $q_i$ 克。做一份 $A$ 类菜，每种菜需要 $a_i$ 克，做一份 $B$ 类菜，每种菜需要 $B_i$ 克。菜只能做整数份，询问最多能做多少份菜。

分析：

由于 $n$ 很小，所以可以枚举 $A$ 类菜做了几份， $B$ 类菜做了几份，预处理出 $A$ 类菜最多做多少份，循环枚举即可。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
LL q[15], a[15], b[15];
int n;

int main() {
    cin >> n;
    LL minval = 1e9;
    for (int i = 1; i <= n; i++)
        cin >> q[i];
    for (int i = 1; i <= n; i++)
        cin >> a[i], minval = min(minval, a[i] == 0 ? (LL) 1e18 : q[i] / a[i]);
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    LL ans = 0;
    for (int i = 0; i <= minval; i++) {
        LL minval = 1e18;
        for (int j = 1; j <= n; j++)
            minval = min(minval, b[j] == 0 ? (LL) 1e18 : (q[j] - i * a[j]) / b[j]);
        ans = max(ans, minval + i);
    }
    cout << ans << endl;
    return 0;
}

D Island Tour（思维）

题意：

给出 $n$ 座桥，第 $i$ 座桥和第 $i + 1$ 座桥相连，第 $n$ 座桥和第 $1$ 座桥相连，每两座相邻的桥之间距离为 $1$ 。现在有一个旅游团从 $x_1$ 出发，要依次走过 $x_1,x_2 \dots x_m$ 座桥，现在要选择废弃一座桥，并使得旅游团的行走距离最短。输出最短的行走距离。

分析：

在桥不废弃的情况下，从 $x_j$ 到 $x_{j+1}$ 有顺时针和逆时针两种走法，如果一个方向中所需要走的桥有任意一座被废弃，都要选择走另外一个方向。同时所要走的桥的序号是连续的，所以可以在差分数组上对要走的区间进行修改。最后统计差分数组的前缀和即可。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int MAXN = 2e5 + 5;
LL n, m, a[MAXN];
LL sum[MAXN];

int cal(int l, int r) {
    if (l <= r)
        return r - l;
    return r - l + n;
}

void change(int l, int r, int d) {
    if (l <= r) {
        sum[l] += d;
        sum[r] -= d;
    } else {
        sum[l] += d;
        sum[n + 1] -= d;
        sum[0] += d;
        sum[r] -= d;
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a[i];
    for (int i = 1; i < m; i++) {
        change(a[i], a[i + 1], cal(a[i + 1], a[i]));
        change(a[i + 1], a[i], cal(a[i], a[i + 1]));
    }
    LL ans = 1e18;
    for (int i = 1; i <= n; i++)
        ans = min(ans, sum[i] += sum[i - 1]);
    cout << ans << endl;
    return 0;
}

E Chords（思维）

题意：

在一个圆上以相等的间隔放置 $\times n$ 个点，从某一点开始顺时针方向编号为 $\times n$ ，圆上有 $n$ 条弦，第 $i$ 条弦连接 $a_i,b_i$ 。保证 $a_i$ ， $b_i$ 各不相同。
询问圆上的弦是否有交集。

分析：

首先将弦抽象成数轴上的线段，弦不相交就是线段不相交。如果两条线段 $x, y$ 相交那么一定满足 $a_x < a_y < b_x < b_y$ 。那么枚举 $a_x$ ， $b_x$ ，用 $ST$ 表，线段树等方法查询区间内最大值是否大于 $b_x$ 即可。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 4e5 + 5, M = 22;
int n, a[maxn], b[maxn];
int st[maxn][M + 2];

int ask(int l, int r) {
    if (l > r)
        return -1e9;
    int k = log2(r - l + 1);
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        if (a[i] > b[i])
            swap(a[i], b[i]);
        st[a[i]][0] = max(st[a[i]][0], b[i]);
    }
    for (int j = 1; j < M; j++)
        for (int i = 1; i + (1 << j) - 1 <= 2 * n; i++)
            st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
    for (int i = 1; i <= n; i++)
        if (ask(a[i] + 1, b[i] - 1) > b[i]) {
            cout << "Yes" << endl;
            return 0;
        }
    cout << "No" << endl;
    return 0;
}

F Negative Traveling Salesman（状压 dp）

题意：

给出 $n$ 个点， $m$ 条边的有向图，第 $i$ 条边连接 $u_i$ ， $w_i$ ，边权为 $w_i$ ，并保证没有负环。任选一个点作为起点，询问至少遍历所有点一次的最小权值和。

分析：

$f [i] [j]$ 表示当前访问的点集是 $i$ ，且当前在 $j$ 点的最小花费，先用 $f l oy d$ 预处理出点与点之间的最小距离，再状压枚举状态转移： $f [s t a t e ∣ (1 << j)] [j] = min (f [s t a t e ∣ (1 << j)] [j], f [s t a t e] [i] + d i s [i] [j]);$ 。最后统计所有点都被遍历的最小值即可。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 1 << 20;
const int INF = 1e9;
int f[maxn][22];
int dis[22][22];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < maxn; i++)
        for (int j = 0; j < n; j++)
            f[i][j] = INF;
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dis[i][j] = INF;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        dis[u][v] = w;
    }
    for (int i = 0; i < n; i++) {
        f[1 << i][i] = 0;
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    int ans = INF;
    for (int state = 1; state < maxn; state++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                f[state | (1 << j)][j] = min(f[state | (1 << j)][j], f[state][i] + dis[i][j]);
            }
        }
    }
    for (int j = 0; j < n; j++)
        ans = min(ans, f[(1 << n) - 1][j]);
    if (ans > INF / 2)
        cout << "No" << endl;
    else {
        cout << ans << endl;
    }
    return 0;
}