A – Grid game

竖的横的上下分开填。

// CF1103A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

int n, ux, uy, dx, dy;
char str[MAX_N];

int main()
{
    scanf("%s", str + 1), n = strlen(str + 1);
    ux = 1, uy = 1, dx = 0, dy = 1;
    for (int i = 1; i <= n; i++)
        if (str[i] == '0')
            printf("%d %d\n", ux, uy), uy = uy % 4 + 1;
        else
            printf("%d %d\n", (dx >> 1) + 3, dy), dx = (dx + 1) % 4, dy = (dy + 1) % 4 + 1;
    return 0;
}

B – Game with modulo

一共有 60 次询问机会，我们可以分两个 30 次：第一个 30 次用来询问最高位前的一位，第二个 30 位用来补全我们对 \(a – 1\) 的猜测。

// CF1103B.cpp
#include <bits/stdc++.h>

using namespace std;

char cmdlet[20];

bool readStatus() { return scanf("%s", cmdlet + 1), cmdlet[1] != 'e'; }

bool query(int x, int y)
{
    printf("? %d %d\n", x, y), fflush(stdout);
    scanf("%s", cmdlet + 1);
    return cmdlet[1] == 'x';
}

void answer(int x) { printf("! %d\n", x), fflush(stdout); }

int main()
{
    while (readStatus())
    {
        int highest_digit = -1;
        for (int i = 0; i <= 30; i++)
            if (query(i == 0 ? 0 : 1 << (i - 1), 1 << i))
            {
                highest_digit = i - 1;
                break;
            }
        int ans = highest_digit == -1 ? 0 : (1 << highest_digit);
        for (int i = highest_digit - 1; i >= 0; i--)
            if (!query(ans, ans | (1 << i)))
                ans |= (1 << i);
        ans++, answer(ans);
    }
    return 0;
}

C – Johnny Solving

神仙构造题！

我们可以考虑先来解决 PATH 的情况：我们可以直接进行暴力的 DFS。如果暴力 DFS 无解，那么可以说明此时搜索树的分叉已经超过了 \(k\)，所以我们可以用这个性质来解决 CYCLES 的情况。如果分叉超过了 \(k\)，我们要找到一个长度大于 3 且不为 3 的倍数的环，考虑一个子树的一个叶子 \(u\) 有除了回到父亲的两条返祖边，我们称这两个祖先为 \(a, b, dep[a] < dep[b]\)，父亲称为 \(fa\)。我们可以证明 \(dep[b] – dep[a] + 2, dep[u] – dep[a] + 1, dep[u] – dep[b] + 1 \bmod 3\) 为三个不同的值，所以一定存在不为三的倍数的环。构造完成。

// CF1103C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2.5e5 + 200, MAX_M = 5e5 + 200;

int n, m, k, head[MAX_N], current, dep[MAX_N], up[MAX_N];
bool flag;
vector<int> lf;

struct edge
{
    int to, nxt;
} edges[MAX_M << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void dfs(int u, int fa)
{
    up[u] = fa, dep[u] = dep[fa] + 1;
    if (dep[u] >= (n + k - 1) / k && (!flag))
    {
        flag = true, puts("PATH");
        printf("%d\n", dep[u]);
        for (int v = u; v; v = up[v])
            printf("%d ", v);
        return (void)(puts(""));
    }
    bool leaf = true;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa && dep[edges[i].to] == 0)
            dfs(edges[i].to, u), leaf = false;
    if (leaf)
        lf.push_back(u);
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, u, v; i <= m; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    dfs(1, 0);
    if (flag)
        return 0;
    puts("CYCLES");
    for (int loop_idx = 1; loop_idx <= k; loop_idx++)
    {
        int pt = lf[loop_idx - 1];
        flag = false;
        vector<int> pos;
        for (int i = head[pt]; i != -1; i = edges[i].nxt)
        {
            if (pos.size() != 2)
                pos.push_back(edges[i].to);
            if (edges[i].to == up[pt] || (dep[pt] - dep[edges[i].to] + 1) % 3 == 0)
                continue;
            printf("%d\n", dep[pt] - dep[edges[i].to] + 1);
            for (int p = pt; p != up[edges[i].to]; p = up[p])
                printf("%d ", p);
            puts(""), flag = true;
            break;
        }
        if (flag)
            continue;
        sort(pos.begin(), pos.end(), [](int a, int b) { return dep[a] < dep[b]; });
        printf("%d\n", dep[pos[1]] - dep[pos[0]] + 1);
        int p = pos[1], neck = pos[0];
        while (p != up[neck])
            printf("%d ", p), p = up[p];
        puts("");
    }
    return 0;
}

D – Professional layer

我们可以发现其 \(\gcd\) 的质因数不超过 12 个，所以我们可以在设计 DP 状态的时候来状压这个质因子即可，然后在算一个 \(i\) 表示集合大小。我们发现 \(i\) 可能会很大，然而我们已经知道这个质因子的个数不超过 12 个，所以我们可以把一些相同的数字给压缩起来，最后转移的时候批量转移。

// CF1103D.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200, MAX_M = 12;

typedef long long ll;

const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, m;
ll k, ai[MAX_N], ei[MAX_N], d, f[13][1 << MAX_M];
vector<ll> primes;
map<ll, vector<int> /**/> mp;
bool valid[1 << MAX_M];

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

int main()
{
    scanf("%d%lld", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &ai[i]), d = gcd(ai[i], d);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &ei[i]);
    for (ll i = 2; 1LL * i * i <= d; i++)
        if (d % i == 0)
        {
            primes.push_back(i);
            while (d % i == 0)
                d /= i;
        }
    if (d > 1)
        primes.push_back(d);
    m = primes.size();
    for (int i = 1; i <= n; i++)
    {
        ll tmp = 1;
        for (int j = 0; j < m; j++)
            while (ai[i] % primes[j] == 0)
                ai[i] /= primes[j], tmp *= primes[j];
        mp[tmp].push_back(ei[i]);
    }
    memset(f, 0x3f, sizeof(f)), f[0][0] = 0;
    ll ans = INF;
    for (auto &curt : mp)
    {
        ll u = curt.first;
        sort(curt.second.begin(), curt.second.end());
        if (1LL * curt.second.size() > m)
            curt.second.resize(k);
        for (int stat = 0; stat < (1 << m); stat++)
        {
            ll tmp = u, acc = 1;
            for (int j = 0; j < m; j++)
                if (stat & (1 << j))
                    while (tmp % primes[j] == 0)
                        tmp /= primes[j], acc *= primes[j];
            valid[stat] = (acc <= k);
        }
        for (auto cost : curt.second)
        {
            bool vis = false;
            for (int i = m - 1; i >= 0; i--)
                for (int stat = 0; stat < (1 << m); stat++)
                    if (f[i][stat] < INF)
                        for (int substat = (stat + 1) | stat; substat < (1 << m); substat = (substat + 1) | stat)
                            if (valid[substat ^ stat] && f[i + 1][substat] > f[i][stat] + cost)
                                vis = true, f[i + 1][substat] = f[i][stat] + cost;
            // no where to relax;
            if (!vis)
                break;
        }
    }
    for (int i = 0; i <= m; i++)
        if (f[i][(1 << m) - 1] < INF)
            ans = min(ans, 1LL * f[i][(1 << m) - 1] * i);
    if (ans == INF)
        puts("-1");
    else
        printf("%lld\n", ans);
    return 0;
}