ABC-341

A - Print 341

给定一个正整数 $N$，打印一个由 $N$ 个 0 和 $N+1$ 个 1 组成的字符串，其中 0 和 1 交替出现。

void solve() {
    int n;cin >> n;
    string a = "";
    for (int i = 1;i <= n;i++) {
        a += "10";
    }
    a += "1";
    cout << a << '\n';
}

B - Foreign Exchange

有 $N$ 个国家，编号为 $1$ 至 $N$。对于每个 $i=1,2,\dots ,N$，高桥有 $A_i$ 个单位的 $i$ 国货币。

高桥可以重复下面的操作任意多次，可能为零：

• 首先，在 $1$ 和 $N-1$ 之间选择一个整数 $i$。
• 然后，如果高桥至少有 $S_i$ 个单位的 $i$ 国货币，他就执行一次以下操作：
  • 支付 $S_i$ 个单位的 $i$ 国货币，获得 $T_i$ 个单位的 $(i+1)$ 国货币。

打印出高桥最终可能拥有的 $N$ 国货币的最大单位数。

由 获得 Ti 个单位的 (i+1) 国货币 容易知道，肯定是一级一级向下传递的，所以直接贪心即可。

#define int long long
void solve() {
    int n;cin >> n;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    vector<pair<int, int>> s(n + 1);
    for (int i = 1;i <= n - 1;i++) {
        cin >> s[i].first >> s[i].second;
    }

    for (int i = 1;i <= n - 1;i++) {
        int bei = a[i] / s[i].first;
        a[i + 1] += bei * s[i].second;
    }
    cout << a[n] << '\n';
}

C - Takahashi Gets Lost

给定一个操作字符串和一个地图，若图上 . 按照操作字符串做完操作 位置全程在 . 上，则算是一个答案

char s[510][510];
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
void solve() {
    int h, w, n;cin >> h >> w >> n;
    string t;cin >> t;

    for (int i = 1;i <= h;i++) 
        for (int j = 1;j <= w;j++) 
            cin >> s[i][j];
    
    int ans = 0;
    for (int i = 2;i <= h - 1;i++) {
        for (int j = 2;j <= w - 1;j++) {
            bool ok = true;
            if (s[i][j] == '.') {
                int x = i, y = j;
                for (int k = 0;k < n;k++) {
                    int op = -1;
                    if (t[k] == 'U') {
                        op = 0;
                    } else if (t[k] == 'D') {
                        op = 1;
                    } else if (t[k] == 'L') {
                        op = 2;
                    } else if (t[k] == 'R') {
                        op = 3;
                    }
                    x += dx[op];
                    y += dy[op];
                    if (s[x][y] == '#') {
                        ok = false;break;
                    }
                }
                if (ok)ans++;
            }
        }
    }
    cout << ans << '\n';
}

D - Only one of two

给出 $n,m,k(1\le n\ne m\le {10}^8,1\le k\le {10}^{10})$，数组 $a$ 由 $n$ 的倍数和 $m$ 的倍数且不包含 $n\times m$ 的倍数组成的序列求 $a[k]$

#define int long long
void solve() {
    int N, M, K;
    cin >> N >> M >> K;
    int low = 1, high = 1e18, ans = -1;

    while (low <= high) {
        int mid = (high + low) / 2;
        //lcm(a,b)=(a / __gcd(a, b)) * b
        int count = mid / N + mid / M - 2 * (mid / ((N / __gcd(N, M)) * M));
        if (count >= K) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    cout << ans << '\n';
}

Solution

二分

能被 $N$ 和 $M$ 中的一者整除的数有 $\lfloor \frac{X}{N}\rfloor +\lfloor \frac{X}{M}\rfloor -2\times \lfloor \frac{X}{L}\rfloor$ 个。

官方题解：

将 $N$，$M$ 的最小公倍数记为 $L$。
则在正整数 $X$ 以下中，能被 $N$ 和 $M$ 同时整除的数有 $\lfloor \frac{X}{L}\rfloor$ 个。因此，在 $1$ 到 $X$ 之间，能被 $N$ 和 $M$ 中的一者整除的数有 $\lfloor \frac{X}{N}\rfloor +\lfloor \frac{X}{M}\rfloor -2\times \lfloor \frac{X}{L}\rfloor$ 个。

此外，由于这个数目是关于 $X$ 单调递增的，因此“答案要求在 $X$ 以下”和“在 $1$ 到 $X$ 之间，能被 $N$ 和 $M$ 中的一者整除的数至少有 $K$ 个”即 $\lfloor \frac{X}{N}\rfloor +\lfloor \frac{X}{M}\rfloor -2\times \lfloor \frac{X}{L}\rfloor \ge K$ 是等价的。

因此，可以利用二分搜索来解决这个问题。在这个问题的限制下，答案一定不会超过 $2\times {10}^{18}$，因此可以将搜索范围设为 0 到 $2\times {10}^{18}$。

答案小于等于 $2\times {10}^{18}$ 的证明如下：不失一般性，设 $N<M$。设 $N$，$M$ 的最大公约数为 $g$，$N=ng$，$M=mg$（$1\le n<m$，$n$，$m$ 是整数）。则有

$$\lfloor \frac{X}{N}\rfloor +\lfloor \frac{X}{M}\rfloor -2\times \lfloor \frac{X}{L}\rfloor >\frac{X}{N}+\frac{X}{M}-\frac{2X}{L}-2=\frac{(m+n-2)X}{gnm}-2$$

当 $X=2\times {10}^{18}$ 时，在问题的限制下有 $\frac{m+n-2}{n}\ge 1$，$\frac{X}{gm}\ge 2\times {10}^{10}$，因此有

$$\frac{X}{N}+\frac{X}{M}-\frac{2X}{L}-2=\frac{(m+n-2)X}{gnm}-2\ge 2\times {10}^{10}-2$$

因此，在问题的限制下，在 $X$ 以下一定至少有 $2\times {10}^{10}-2$ 个符合条件的数，特别地也就至少有 $K$ 个符合条件的数。实际上，对于当前限制，上限为 $N=5\times {10}^7$，$M={10}^8$，$K={10}^{10}$ 时，答案为 ${10}^{18}-5\times {10}^7$。

具体来说，可以首先设定 $L=0,R=2\times {10}^{18}$，然后只要 $R-L\ge 2$，就重复以下步骤：

1. 设 $X=\lfloor \frac{L+R}{2}\rfloor$。
2. 判断 $\lfloor \frac{X}{N}\rfloor +\lfloor \frac{X}{M}\rfloor -2\times \lfloor \frac{X}{L}\rfloor \ge K$，如果成立，则设 $R=X$，否则设 $L=X$。

最终得到的 $R$ 就是答案。

在固定 $X$ 时，判断 $\lfloor \frac{X}{N}\rfloor +\lfloor \frac{X}{M}\rfloor -2\times \lfloor \frac{X}{L}\rfloor \ge K$ 的复杂度为 $O(1)$，而重复的次数最多也只有 $60$ 次，因此非常高效。因此，这个问题可以用二分搜索很好地解决。

E - Alternating String

A string consisting of 0 and 1 is called a good string if two consecutive characters in the string are always different.

给你一个长度为 $N$ 的 字符串 $S$ ，由 0 和 1 组成。将给出 $Q$ 个查询，必须按顺序处理。
查询有两种类型：

• 1 L R：s[l-r] ^= 1
• 2 L R：print(isGood(s[l-r]))

Solution

#algo/ds/线段树

线段树

(待更 $\dots$)