Visits: 2322

AtCoder Grand Contest 020

Move and Win

答案只与 $a,b$ 是否同奇偶有关。

int main() {
    int n, a, b;
    rd(n, a, b);
    prints((a ^ b) & 1 ? "Borys" : "Alice");
    return 0;
}

Ice Rink Game

倒序考虑即可。

const int N = 1e5 + 7;
int n;
ll a[N], l = 2, r = 2;

int main() {
    rd(n), rda(a, n);
    for (int i = n; i; i--) {
        l = ((l - 1) / a[i] + 1) * a[i], r = r / a[i] * a[i];
        if (l > r) return print(-1), 0;
        r += a[i] - 1;
    }
    print(l, r);
    return 0;
}

Median Sum

设所有元素之和为 $s$。

考虑每个非空非全的子集与它的补集之和都等于 $s$，加上全集 $s$ 后的中位数，就是最小的 $\ge \lceil \frac s2 \rceil$ 且存在的子集和。

bitset 优化背包时间复杂度 $\mathcal O(\frac{n^3}{w})$。

const int N = 2e3 + 7;
int n, a[N], s;
bitset<N*N> b;

int main() {
    rd(n), rda(a, n), b[0] = 1;
    for (int i = 1; i <= n; i++) b |= b << a[i], s += a[i];
    s = (s + 1) >> 1;
    while (!b[s]) ++s;
    print(s);
    return 0;
}

Min Max Repetition

题意

• 设 $a,b$ 为正整数，定义 $f(a,b)$ 表示满足下列条件的字符串：
  • $f(a,b)$ 由恰好 $a$ 个 A 和恰好 $b$ 个 B 构成。
  • $f(a,b)$ 最长的字符全相同的子串是满足上述条件的所有字符串中最短的。
  • $f(a,b)$ 是满足上述条件的所有字符串中字典序最小的。
• 给定 $c,d$，求 $f(a,b)[c:d]$。
• $a,b \le 5 \times 10^8$，$d-c+1 \le 100$，多组数据组数 $T\le 10^3$。

题解

最长的字符全相同的子串的长度为 $k = \max(\lceil\frac{a}{b+1}\rceil,\lceil\frac{b}{a+1}\rceil)$。

贪心的构造串可以发现答案为 $(\texttt{A}^k\texttt{B})^{\infty}$ 的某个前缀加上 $(\texttt{A}\texttt{B}^k)^{\infty}$ 的某个后缀，二分出分界点即可，时间复杂度 $\mathcal O(T(\log(a+b) + (d-c)))$。

代码

int a, b, c, d, k;

inline bool pd(int o) {
    if (!o) return 1;
    if (!(o % (k + 1))) return pd(o - 1);
    int x = a - (o - o / (k + 1)), y = b - o / (k + 1);
    return y <= 1ll * (x + 1) * k;
}

inline void solve() {
    rd(a, b), rd(c, d);
    k = (max(a, b) - 1) / (min(a, b) + 1) + 1;
    int l = 0, r = a + b;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (pd(mid)) l = mid;
        else r = mid - 1;
    }
    for (int i = c; i <= min(l, d); i++)
        printc(i % (k + 1) ? 'A' : 'B');
    for (int i = max(c, l + 1); i <= d; i++)
        printc((a + b - i + 1) % (k + 1) ? 'B' : 'A');
    prints("");
}

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

Encoding Subsets

题意

• 对于一个 $0/1$ 串，我们可以将其按如下方式编码：
  • $0/1$ 串 $0$ 可以被编码为 $\texttt{0}$，$0/1$ 串 $1$ 可以被编码为 $\texttt{1}$。
  • 若 $0/1$ 串 $A$ 可以被编码为 $P$，$0/1$ 串 $B$ 可以被编码为 $Q$，则 $0/1$ 串 $AB$ 可以被编码为 $PQ$。
  • 若 $0/1$ 串 $A$ 可以被编码为 $P$，对于 $k \ge 2$，$0/1$ 串 $A^k$ 可以被编码为 $\texttt{(}P\texttt{x}k\texttt{)}$。
• 显然一个 $0/1$ 串可能有多种编码方案。
• 定义 $0/1$ 串 $A$ 是 $0/1$ 串 $B$ 的子集，当且仅当 $A$ 和 $B$ 长度，且对于所有 $A_i = 1$ 的 $i$ 满足 $B_i = 1$。
• 给定 $0/1$ 串 $S$，求出所有 $S$ 的子集的编码方案数之和。
• $|S| \le 100$，答案对 $998244353$ 取模。

题解

考虑对于一个固定的 $0/1$ 串如何求解方案数，考虑区间 DP，设 $f_{l,r}$ 表示将区间 $[l,r]$ 编码的方案数，$g_{l,r}$ 表示将区间 $[l,r]$ 编码成单个字符或由一个括号括起来（允许嵌套）的方案数，则转移有：
$$
f_{l,r}=\sum_{k=l}^{r-1}g_{l,k} f_{k+1,r}
$$

$$
g_{l,r}=\sum_{d|r-l+1} [d为[l,r]的循环节]f_{l,l+d-1}
$$

考虑原问题，直接拿字符串来定义状态，在 $g$ 的转移中枚举 $d$ 后对划分出的子串取并进行转移即可。

由于状态数并不多，时间复杂度 $\mathcal O(能过)$。

代码

map<string, modint> f, g;

modint F(string s);

modint G(string s) {
    if (g.find(s) != g.end()) return g[s];
    int n = s.size();
    modint ans;
    for (int d = 1; d < n; d++) {
        if (n % d) continue;
        string t = "";
        for (int i = 0; i < d; i++) {
            bool c = 1;
            for (int j = i; j < n; j += d) c &= s[j] - '0';
            t += c + '0';
        }
        ans += F(t);
    }
    return g[s] = ans;
}

modint F(string s) {
    if (f.find(s) != f.end()) return f[s];
    int n = s.size();
    modint ans;
    for (int i = 1; i <= n; i++)
        ans += G(s.substr(0, i)) * F(s.substr(i, n));
    return f[s] = ans;
}

int main() {
    string s;
    rds(s);
    f[""] = 1, g[""] = 1, g["0"] = 1, g["1"] = 2;
    print(F(s));
    return 0;
}

Arcs on a Circle

题意

• 有一个周长为 $c$ 的圆。
• 你有 $n$ 条弧，第 $i$ 条弧的弧长为 $l_i$。
• 对于每条弧，你会在圆上随机一个位置作为它的中点放置。
• 求圆上每个点都被至少一条弧覆盖的概率。
• $n \le 6$，$c \le 50$。

题解

考虑断环为链，以最长弧的一端为端点断开这个环。

由于所有的弧长都是整数，所以我们不关心所有弧起始点的小数部分，我们只关心小数部分之间的大小关系。

我们可以暴力枚举这个大小关系，于是问题变成：在区间 $[0,nc)$ 上，有一条已知长度的从 $0$ 开始的线段，另外还有 $n-1$ 条已知长度，且起点 $\bmod n$ 确定的线段，要求这些线段覆盖整个区间的方案数。

考虑状压 DP，设 $f_{i,j,s}$ 表示当前在点 $i$，已经覆盖到了点 $j$，使用的线段集合为 $s$ 的方案数，转移时考虑 $i+1$ 是否为某个线段的起点即可。

由于我们一开始选择的是最长的线段，因此因为断开了环而断开的线段在开头处不会有贡献，可以直接忽略掉。

时间复杂度 $\mathcal O((n-1)!n^2c^22^{n-1})$。

代码

int n, m, k, l[7], p[7], f[307][307][135];

inline int work() {
    memset(f, 0, sizeof(f));
    f[0][l[n]*n][0] = 1;
    for (int i = 1; i < n * m; i++)
        for (int j = i; j <= n * m; j++)
            for (int s = 0; s <= k; s++)
                if (f[i-1][j][s]) {
                    f[i][j][s] += f[i-1][j][s];
                    int x = i % n;
                    if (!x || s >> (x - 1) & 1) continue;
                    f[i][min(n*m,max(j,i+l[p[x]]*n))][s|1<<(x-1)] += f[i-1][j][s];
                }
    return f[n*m-1][n*m][k];
}

int main() {
    rd(n, m), rda(l, n), k = (1 << (n - 1)) - 1;
    sort(l + 1, l + 1 + n), iota(p + 1, p + n, 1);
    ll ans = 0, cnt = 1;
    for (int i = 1; i < n; i++) cnt *= i * m;
    do ans += work();
    while (next_permutation(p + 1, p + n));
    printf("%.20Lf\n", 1.0L * ans / cnt);
    return 0;
}