Visits: 295

AtCoder Grand Contest 044

Pay to Win

倒着考虑，记忆化搜索一下即可。

#define ll __int128
const int o[3] = {2,3,5};
const ll inf = 1e18;
ll n, a[3], d;
map<ll, ll> p;

inline ll f(ll x) {
    if (!x) return 0;
    if (p.find(x) != p.end()) return p[x];
    p[x] = d * x;
    for (int i = 0; i < 3; i++) {
        int k = o[i];
        if (!(x % k)) p[x] = min(p[x], f(x / k) + a[i]);
        else {
            int t = x % k;
            p[x] = min(p[x], f(x / k) + a[i] + t * d);
            p[x] = min(p[x], f(x / k + 1) + a[i] + (k - t) * d);
        }
    }
    return p[x];
}

inline void solve() {
    rd(n), rd(a[0], a[1], a[2]), rd(d);
    p.clear();
    print(f(n));
}

int main() {
    int T;
    rd(T);
    while (T--) solve(); 
    return 0;
}

Joker

直接暴力 01BFS 求最短路即可，即每次去掉一个数之后松弛周围需要松弛的点。

这样复杂度看上去是 $\mathcal O(n^4)$ 的，但是仔细分析之后会发现，由于每个点最短路最长也是 $\mathcal O(n)$ 的，而每次松弛必然会变短，因此每个点最多松弛 $\mathcal O(n)$ 次，总时间复杂度为 $\mathcal O(n^3)$。

const int N = 507;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int n, a[N*N], d[N][N], ans;
bool v[N][N];

inline void F(int z, int &x, int &y) {
    x = (z - 1) / n + 1, y = (z - 1) % n + 1;
}

int main() {
    rd(n), rda(a, n * n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            d[i][j] = min(min(i, n + 1 - i), min(j, n + 1 - j)), v[i][j] = 1;
    for (int i = 1, x, y; i <= n * n; i++) {
        F(a[i], x, y);
        ans += --d[x][y], v[x][y] = 0;
        deque<pi> q;
        q.pb(mp(x, y));
        while (q.size()) {
            x = q.front().fi, y = q.front().se, q.pop_front();
            for (int o = 0; o < 4; o++) {
                int X = x + dx[o], Y = y + dy[o];
                if (X < 1 || X > n || Y < 1 || Y > n) continue;
                if (d[X][Y] > d[x][y] + v[X][Y]) {
                    d[X][Y] = d[x][y] + v[X][Y];
                    if (v[X][Y]) q.pb(mp(X, Y));
                    else q.push_front(mp(X, Y));
                }
            }
        }
    }
    print(ans);
    return 0;
}

Strange Dance

基本上就是 这题。

反向建 012Trie，S 操作就是交换所有点的 $1,2$ 子树，打个 lazy tag 即可；R 操作就是抽出一条从根开始的全 $2$ 链，将链上的 $0 \to 1$，$1 \to 2$，$2 \to 0$。

const int N = 6377292 + 7;
int n, m, trie[N][3], num[N], tot = 1, ans[N];
bool tag[N];
char s[N];

void build(int p, int d, int o, int x) {
    if (d == n) return num[p] = x, void();
    for (int i = 0; i < 3; i++)
        build(trie[p][i] = ++tot, d + 1, o * 3, x + i * o);
}

inline void spread(int p) {
    if (tag[p]) {
        swap(trie[p][1], trie[p][2]), tag[p] = 0;
        for (int i = 0; i < 3; i++) tag[trie[p][i]] ^= 1;
    }
}

void dfs(int p, int d, int o, int x) {
    if (d == n) return ans[num[p]] = x, void();
    spread(p);
    for (int i = 0; i < 3; i++)
        dfs(trie[p][i], d + 1, o * 3, x + i * o);
}

int main() {
    rd(n), build(1, 0, 1, 0), rds(s, m);
    for (int i = 1; i <= m; i++)
        if (s[i] == 'S') tag[1] ^= 1;
        else {
            int p = 1;
            for (int i = 0; i < n; i++, p = trie[p][0])
                spread(p),
                swap(trie[p][0], trie[p][1]),
                swap(trie[p][0], trie[p][2]);
        }
    dfs(1, 0, 1, 0);
    for (int i = 0, k = pow(3, n); i < k; i++)
        print(ans[i], " \n"[i==k-1]);
    return 0;
}

Guess the Password

交互题。

每次询问可以得到一个串与答案的最长公共子序列。

于是先搞出每个字符有多少个，然后把所有子序列归并起来即可。

const string str = "QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm1234567890";
int n;
vector<string> ss;

inline int ask(const string& s) {
    cout << "? " << s << endl;
    int x;
    cin >> x;
    return x;
}

string merge(int l, int r) {
    if (l == r) return ss[l];
    int mid = (l + r) >> 1;
    string sl = merge(l, mid), sr = merge(mid + 1, r), s;
    for (int i = 0, j = 0, k = n - sl.size(); i <= (int)sl.size(); i++) {
        if (i == (int)sl.size()) {
            while (j < (int)sr.size()) s += sr[j++];
            break;
        }
        while (j < (int)sr.size() && ask(s + sr[j] + sl.substr(i)) == k - 1)
            s += sr[j++], --k;
        s += sl[i];
    }
    return s;
}

int main() {
    for (char c : str) {
        string s(128, c);
        int t = 128 - ask(s);
        if (t) ss.pb(s.substr(0, t));
        n += t;
    }
    string ans = merge(0, ss.size() - 1);
    cout << "! " << ans << endl;
    return 0;
}

Random Pawn

首先显然从 $a$ 最大值的位置断开。

发现跟 这题 很像，区别在于多了个 $b_i$。

即现在的式子为
$$
f_i = \max(a_i, \frac{f_{i-1} + f_{i+1}}{2} – b_i)
$$
考虑找到 $c_{1\dots n}$ 满足 $c_i = \frac{c_{i-1}+c_{i+1}}{2} – b_i$。

则令 $g_i = f_i – c_i$，$v_i = a_i – c_i$，就变成了
$$
g_i = \max(v_i, \frac{g_{i-1} + g_{i+1}}{2})
$$
就是上面那题了，求个凸包即可。

const int N = 2e5 + 7;
int n;
__int128 A[N], B[N], a[N], b[N], c[N];
ld ans;
vi s(1, 0);

inline bool pd(int i, int j, int k) {
    return (a[j] - a[i]) * (k - i) <= (a[k] - a[i]) * (j - i);
}

int main() {
    rd(n), rda(A, n), rda(B, n);
    int p = max_element(A + 1, A + n + 1) - A;
    for (int i = p; i <= n; i++) a[i-p] = A[i], b[i-p] = B[i];
    for (int i = 1; i <= p; i++) a[n-p+i] = A[i], b[n-p+i] = B[i];
    for (int i = 2; i <= n; i++)
        c[i] = 2 * (c[i-1] + b[i-1]) - c[i-2], a[i] -= c[i], ans += c[i];
    for (int i = 1; i <= n; i++) {
        while (s.size() > 1u && pd(s[s.size()-2], s.back(), i)) s.pop_back();
        s.pb(i);
    }
    for (ui i = 1; i < s.size(); i++) {
        int l = s[i-1], r = s[i];
        for (int k = l + 1; k < r; k++)
            ans += 1.0L * ((k - l) * a[r] + (r - k) * a[l]) / (r - l);
        ans += a[r];
    }
    printf("%.12Lf\n", ans / n);
    return 0;
}

Name-Preserving Clubs

咕。