裂项

约瑟夫环问题

约瑟夫环问题

设 $J_{n, m}$ 表示规模分别为 $n, m$ 的约瑟夫问题的答案。我们有如下递归式

这个也很好推。从 0 开始数 $m$ 个，让第 $m-1$ 个人出局后剩下 $n-1$ 个人，计算出在 $n-1$ 个人中选的答案后，再加一个相对位移 $m$ 得到真正的答案。

题目说是从 $k$ 开始报数，所以答案再加上 $k$。

时间复杂度 $\Theta(n)$：

1
2
3
4
5
int res = 0;
for (int i = 2; i <= n; ++i) {
    res = (res + m) % i;
}
cout << ((res + k - 1) % n + 1) << '\n';

时间复杂度 $\Theta(k\log n)$：

1
2
3
4
5
6
7
8
9
10
int josephus(int n, int k) {
    if (n == 1) return 0;
    if (k == 1) return n - 1;
    if (k > n) return (josephus(n - 1, k) + k) % n;  // 线性算法
    int res = josephus(n - n / k, k);
    res -= n % k;
    if (res < 0) res += n;  // mod n
    else res += res / (k - 1);  // 还原位置
    return res;
}

2024 CCPC 济南 D. Hero of the Kingdom

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void eachT() {
    ll p = read(), a = read(), b = read();
    ll q = read(), c = read(), d = read();
    ll m = read(), t = read();

    ll res = 0;
    int cnt = 0;
    while (t >= b + d) {
        //++cnt;
        ll x = m / p;
        if (x == 0) break;
        ll lun = min(((x + 1) * p - m + ((q - p) * x) - 1) / ((q - p) * x), t / ((a + c) * x + (b + d)));
        if (lun == 0) {
            x = min(x, (t - (b + d)) / (a + c));
            lun = 1;
        }
        if (x == 0) break;

        m += lun * ((q - p) * x);
        t -= lun * ((a + c) * x + (b + d));
    }
    printf("%lld\n", m);
    //cerr << "cnt = " << cnt << endl;
}

2024 杭电多校 9005 - 怪物猎人

[[../contests/2024 杭电多校 /2024-08-16：2024“钉耙编程”中国大学生算法设计超级联赛（9）|2024-08-16：2024“钉耙编程”中国大学生算法设计超级联赛（9）]]

赛时代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void eachT() {
    ll k = read(), x = read(), y = read();

    ll mx = max(x, y);
    ll mn = min(x, y);

    if (x == y) {
        if (((k + x - 1) / x) & 1) {
            printf("Yes\nNo\n");
        }
        else {
            printf("No\nYes\n");
        }
        return;
    }

    ll m = k / mx;
    if (m * mx == k) {   // WA: m * k == mx
        m--;
    }
    if ((m + 1) * mn >= k) {
        if (m & 1) {
            printf("No\nYes\n");
        }
        else {
            printf("Yes\nNo\n");
        }
        return;
    }
    printf("Yes\nYes\n");
}

优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void eachT() {
    ll k = read(), x = read(), y = read();

    if (x > y) swap(x, y);

    ll m = (k + y - 1) / y;
    if (m * x >= k) {
        if (m & 1) {
            printf("Yes\nNo\n");
        }
        else {
            printf("No\nYes\n");
        }
    }
    else {
        printf("Yes\nYes\n");
    }
}

2024 杭电多校 9007 - 小猫钓鱼

[[../contests/2024 杭电多校 /2024-08-16：2024“钉耙编程”中国大学生算法设计超级联赛（9）|2024-08-16：2024“钉耙编程”中国大学生算法设计超级联赛（9）]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
signed main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        set<int>a;
        int tmp;
        for (int i = 1; i <= n; i++) {
            cin >> tmp;
            a.insert(tmp);
        }
        for (int i = 1; i <= n; i++) {
            cin >> tmp;
        }
        int pr = n - a.size();
        int only = a.size() - pr;
        if (pr) {  // WA : pr % 2 != 0
            cout << "shuishui" << endl;
        }
        else {
            cout << "sha7dow" << endl;
        }
    }
    return 0;
}

2024 杭电多校 8007 - cats 的 k-xor

已知在 $k$ 进制下 $a\operatorname{xor} b=c$，其中 $\operatorname{xor}$ 定义为不进位加法。求可能 $k$ 的数量。([[../contests/2024 杭电多校 /2024-08-12：2024“钉耙编程”中国大学生算法设计超级联赛（8）|2024-08-12：2024“钉耙编程”中国大学生算法设计超级联赛（8）]])

思路 $k\mid a+b-c$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
ll a = read(), b = read(), c = read();
ll v = a + b - c;
if (v < 0) {
    printf("0\n");
}
else if (v == 0) {
    printf("-1\n");
}
else {
    auto solve = [&](ll x) {
        ll A = a, B = b, C = c;
        while (A || B || C) {
            if ((A % x + B % x) % x != C % x) {
                return 0;
            }
            A /= x, B /= x, C /= x;
        }
        return 1;
    };

    int ans = 0;
    for (ll i = 2; i * i <= v; ++i) {
        if (v % i) continue;
        ans += solve(i);
        if (i * i != v) ans += solve(v / i);
    }
    if (v > 1) ans += solve(v);
    printf("%d\n", ans);
}

2024 牛客多校 3A - Bridging the Gap 2

[[../contests/2024 牛客多校 /2024-07-23：2024 牛客暑期多校训练营 3#A - Bridging the Gap 2|2024-07-23：2024 牛客暑期多校训练营 3]]

题意 $n$ 个人在河的一侧，第 $i$ 个人有体力值 $h_{i}$ 有且仅有一艘能容纳 $L$ 到 $R$ 个人的船，问是否能将所有人从河的左侧运送到右侧。

解 最后一趟一定运 $R$ 个人最优，前面几轮尽可能地 $R$ 人去，$L$ 人回，每次净运 $R-L$ 个人。能运满的来回数 $t=\left\lfloor \frac{n-R}{R-L} \right\rfloor$，可能会多出一趟，不到 $R$ 人去，但 $L$ 人回，这个判断称作最后一个来回 $f$。

前 $t$ 个来回，每个来回消耗体力 $R+L$，最后一个来回，去 $n - R - t(R - L)+L$ 人，回 $L$ 人，消耗体力 $n - R - t(R - L)+2L$，最后一趟消耗体力 $R$，这样就得到了总的需要消耗的体力值。

再看能消耗的体力值。设总轮数 $l=2(t+f)+1$，首先如果体力值 $h{i} \geqslant l$，置 $h{i} \leftarrow l$。每个人只会跑奇数趟，置 $h{i}$ 向下取为奇数，现在能消耗的体力值即是 $\sum h{i}$。能够证明总是能够消耗尽的。

只需判断是否满足需要消耗的体力值 $\geqslant$ 能消耗的体力值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ll n = read(), L = read(), R = read();
int flag = 0;
ll sum = 0;
ll t1 = (n - R) / (R - L);
if ((n - R) % (R - L)) {
    flag = 1;
}
ll lun = 2 * (t1 + flag) + 1;
for (int i = 1; i <= n; i++) {
    int x = read();
    if (!(x & 1)) x -= 1;
    if (x > lun) x = lun;
    sum += x;
}
ll lhs = 0;
if (flag) lhs = (n - R - t1 * (R - L)) + 2 * L;
lhs += t1 * (R + L) + R;
cout << (lhs <= sum ? "Yes" : "No") << "\n";

2024 牛客多校 7I. Fight Against the Monster

题意 需要造出若干台战争机器对抗怪兽。每台机器有战斗和创造功能：

  • 战斗：使怪兽血量减 1，然后失去所有功能；
  • 创造：$m$ 台机器同时使用，在这之后会产生 $k\ (k \leqslant m)$ 台新的战争机器，原先的 $m$ 台机器失去创造功能。

怪兽的初始血量为 $h$，其血量不超过 $0$ 时就会死亡。求最初至少需要多少台战争机器才能打败怪兽。

称能继续创造的机器是有用的，每次创造操作相当于减少了 $m-k$ 台有用的机器，同时打出 $m$ 点伤害，最后一次创造剩下的 $k$ 台机器，还可以打 $k$ 点伤害。设总共创造了 $x$ 次恰好打败怪物，则 $m(x+1)+k \geqslant h$。最初需要的机器数是 $m+x(m-k)$。另一种情形是只创造 $x-1$ 次，设 $mx+k+r=h$，最初需要的机器数是 $m+(x-1)(m-k)+r$。

1
2
3
4
5
6
7
int m, k, h;
cin >> m >> k >> h;
int x = (h - k) / m;
int del = h - k - x * m;
int ans1 = m + (x - 1) * (m - k) + del;
int ans2 = m + x * (m - k);
cout << (h == 0 ? 0 : min(ans1, ans2)) << endl;

2024 牛客多校 - 10H. All-in at the Pre-flop

[[../contests/2024 牛客多校 /2024-08-15：2024 牛客暑期多校训练营 10|2024-08-15：2024 牛客暑期多校训练营 10]]

题意 两个玩家在一场公平的游戏里互相全押。当赢家筹码不少于输家时，游戏立即结束；否则输家向赢家支付等同于赢家筹码的筹码。问两个玩家的胜率。

思路 注意到 $\cfrac{a}{a+b}$ 的二进制表示第 $i$ 位是 $1$ 当且仅当第 $i$ 轮 $a>b$。答案为 $\cfrac{a}{a+b},\cfrac{b}{a+b}$。

CF1937D. Pinball

题意 有一个长度为 $n$ 的一维网格。网格的第 $i$ 个单元格包含字符 $s_i$ ，是 < 或 >。当弹球放在其中一个格子上时，它会按照以下规则移动：

  • 如果弹球位于第 $i$ 个格子上且 $s_i$ 为 <，则弹球在下一秒会向左移动一个单元格；
  • 如果 $s_i$ 为 >，则向右移动一个单元格；
  • 弹球移动后，字符 $s_i$ 会反转。

对于每个 $i$，求弹球放置在第 $i$ 格时离开网格的时长。

思路 设起始向左走，且从左边出，答案为

式中 $x=\min\lbrace l,r \rbrace$ 是左右侧会使得弹球反向移动的字符个数的较小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int n;
string s;
cin >> n >> s;

vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
    if (s[i] == '<') a[i] = 1;
    else a[i] = -1;
}

vector<array<int, 2>> cnt(n + 1);  // 前 i 位中 > 和 < 的个数
vector<ll> l, r;
l.push_back(0), r.push_back(0);
for (int i = 1; i <= n; i++) {
    cnt[i] = cnt[i - 1];
    if (s[i] == '<') {
        cnt[i][0]++;
        l.push_back(i);
    }
    else {
        cnt[i][1]++;
        r.push_back(i);
    }
}

auto prel = l, prer = r;
for (int i = 1; i < l.size(); i++) prel[i] += prel[i - 1];
for (int i = 1; i < r.size(); i++) prer[i] += prer[i - 1];

vector<ll> ans(n + 1);
for (int i = 1; i < prel.size(); i++) {
    ll suml = prel[i] - prel[cnt[i][0]];
    ll sumr = prer[cnt[i - 1][1]] - 0;
    ans[i] = (suml - sumr) * 2 + a[i] * i;
}
for (int i = prel.size(); i <= n; i++) {
    ll suml = prel.back() - prel[cnt[i][0]];
    ll sumr = prer[cnt[i - 1][1]] - prer[i - prel.size()];
    ans[i] = n + 1 + (suml - sumr) * 2 + a[i] * i;
}
for (int i = 1; i <= n; i++) {
    cout << ans[i] << " \n"[i == n];
}

CF920E. Eat the Chip (1600)

题意 象棋中两个兵，谁会吃掉谁？

思路 考虑极左点和极右点。

1
2
3
4
5
6
7
8
9
10
11
12
13
scanf("%d %d %d %d %d %d", &h, &w, &x1, &y1, &x2, &y2);
if (x1 >= x2) { printf("Draw\n");
} else if (x2 - x1 & 1) {
    ll l1 = max(y1 - (x2-x1)/2, 1), r1 = min(y1 + (x2-x1)/2, w);
    ll l2 = max(y2 - (x2-x1)/2, 1), r2 = min(y2 + (x2-x1)/2, w);
    if (l1 <= l2 + 1 && r1 >= r2 - 1) printf("Alice\n");
    else printf("Draw\n");
} else {
    ll l1 = max(y1 - (x2-x1)/2, 1), r1 = min(y1 + (x2-x1)/2, w);
    ll l2 = max(y2 - (x2-x1-1)/2, 1), r2 = min(y2 + (x2-x1-1)/2, w);
    if (l2 <= l1 + 1 && r2 >= r1 - 1) printf("Bob\n");
    else printf("Draw\n");
}

VJspr2B - Disc District

题意 求在半径为 $r$，圆心为原点的圆外的到原点的（欧几里得）距离最小的点．

思路 设 $(x,y)$，即是求满足 $d^2=x^2+y^2>r^2$ 的最小的 $d$．一方面，上式等价于 $d^2\geqslant r^2+1$；另一方面，取 $(1,r)$，$d^2=r^2+1$．因此 $d^2$ 的最小值是 $r^2+1$，点的坐标可取 $(1,r)$．

VJwin14A - Points on Plane

题意 在平面上的放置 $n$ 个整点，任意整点的距离大于 $1$，求它们的直角坐标的最大值的最小值．

思路 $\lceil\sqrt{n}\rceil-1=\big\lfloor\sqrt{n-1}\big\rfloor$．

注意 直接使用 sqrt() 函数有精度问题，需要手写一个．

评注 乱搞是一种做 CF 思维题的好方法！

在第四种数据中，输出结果为 $987654321$，非常巧妙的数字．说明什么？出题人可能是先出了输出数据，再据此反推出了输入的 $975461057789971042$．于是，这道题很有可能存在一个 $\Theta(1)$ 的通项公式，可以快速算出结果，并根据答案反推输入．

打开计算器，很容易发现：$987654321^2+1=975461057789971042$，即答案为 $\sqrt{n-1}$．

或者：$\lfloor\sqrt{975461057789971042}\rfloor=987654321$，即答案为 $\lfloor\sqrt{n}\rfloor$．

又或者：$\lceil\sqrt{975461057789971042}\rceil-1=987654321$，即答案为 $\lceil\sqrt{n}\rceil-1$．

显然，第一式不一定能得到整数解，由题意知答案为整数，所以是错的．把其他三组数据带进第二式，发现也有误．而第三式是都符合的．于是你可以快乐地 $\rm AC$ 这道题．

事实上，经过推导，正确答案也是 $\lceil\sqrt{n}\rceil-1$．

VJwin11J - 真是签到题目吧（红包发红包）

  • 题意 一个抢红包系统的规则：假如现在有 $w$ 元，那么能抢到的钱就是 $[0,w]$ 等概率均匀随机出的一个实数 $x$．现在红包发了一个 $w$ 元的红包，有 $n$ 个人来抢，问第 $k$ 个人期望抢到多少钱？对 $10^9+7$ 取模．
  • 思路 答案为 $\displaystyle\frac{w}{2^k}\bmod10^9+7$．

CF922A. Brick Wall

  • 题意 将尺寸为 $k \times 1$ 或 $1 \times k~(k \geq 2)$ 的条状砖块填满尺寸为 $n \times m$ 的砖墙，求所有砖块的水平长度与垂直长度之差之和的最大值．
  • 思路 $\displaystyle n\cdot\lfloor\frac m2\rfloor$．