526互联

HHKB Programming Contest 2023(AtCoder Beginner Contest 327)

发布时间 2023-11-04 22:32:42作者: 洛绫璃

HHKB Programming Contest 2023(AtCoder Beginner Contest 327)

A - ab

int main() {
    IOS;
    string s;
    cin >> n >> s;
    bool f = false;
    for (int i = 1; i < n; ++i)
        if (s[i - 1] == 'a' && s[i] == 'b') f = true;
        else if (s[i] == 'a' && s[i - 1] == 'b') f = true;
    cout << (f ? "Yes" : "No");
    return 0;
}

B - A^A

int main() {
    IOS;
    cin >> n;
    int f = -1;
    for (int i = 1, j = 1; true; ++i, j = 1) {
        ll s = 1;
        for (; j <= i && s <= n / i; ++j) s *= i;
        if (j <= i || s > n) break;
        if (s == n) { f = i; break; } 
    }
    cout << f;
    return 0;
}

C - Number Place

int a[9][9], f[9];

int main() {
    IOS;
    rep (i, 0, 8) rep (j, 0, 8) cin >> a[i][j], --a[i][j];
    bool g = true;
    rep (i, 0, 8) {
        memset(f, 0, sizeof f);
        rep (j, 0, 8) {
            f[a[i][j]] |= 1, f[a[j][i]] |= 2;
            f[a[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3]] |= 4;
        }
        rep (j, 0, 8) if (f[j] != 7) g = false;
    }
    cout << (g ? "Yes" : "No");
    return 0;
}

D - Good Tuple Problem

判断二分图

int h[N], to[M], ne[M], tot;
int a[M >> 1], color[N];

void add(int u, int v) {
    ne[++tot] = h[u];
    to[h[u] = tot] = v;
}

bool dfs(int x, int c) {
    color[x] = c;
    for (int i = h[x], y = to[i]; i; y = to[i = ne[i]]) {
        if (color[y] == c) return false;
        if (!color[y] && !dfs(y, -c)) return false;
    }
    return true;
}

int main() {
    IOS;
    cin >> n >> m;
    rep (i, 1, m) cin >> a[i];
    rep (i, 1, m) cin >> k, add(a[i], k), add(k, a[i]);
    bool f = true;
    rep (i, 1, n) {
        if (color[i]) continue;
        if (!dfs(i, 1)) { f = false; break; }
    }
    cout << (f ? "Yes" : "No");
    return 0;
}

E - Maximize Rating

dp

$x_k = \textstyle \sum_{i=1}^{k} 0.9^i$
$y_k = \frac{1200}{ \sqrt{k} } $
$d_k = max(\textstyle \sum_{i=1}^{k} 0.9^i \times Q_i)$
$ans = max(\frac{d_k}{x_k} - y_k)$

int a[N];
double x[N], y[N], d[N];

int main() {
    IOS;
    cin >> n; x[0] = 0, y[0] = 1;
    double ans = -1500, z = 1;
    rep (i, 1, n) {
        cin >> a[i], x[i] = z + x[i - 1], z *= 0.9, y[i] = 1200 / sqrt(i);
        d[i] = -1500;
        per (j, i, 1) {
            d[j] = max(d[j], d[j - 1] * 0.9 + a[i]);
            ans = max(ans, d[j] / x[j] - 1200 / y[j]);
        }
    }
    cout << precision(6) << ans;
    return 0;
}