1932(div3)

A. Thorns and Coins

给出一个字符串，其中 . 代表平地，@ 代表金币，* 代表障碍，可以前进一格或者跳着走一格(即可以越过不超过 1 个障碍物)求能吃到的金币最大是多少

void solve() {
    int n;cin >> n;string s;cin >> s;
    int cnt = 0;
    for (int i = 0;i < s.size();i++) {
        if (s[i] == '@')cnt++;
        if (i + 1 < s.size() && s[i] == '*' && s[i + 1] == '*') {
            break;
        }
    }
    cout << cnt << '\n';
}

B. Chaya Calendar

给定一个数组，必须按照数组所给出的顺序进行，遇到的数字代表年份，所以后面遇到的不能比前面小，如果遇到了后面的比前面小的情况，按照 $a_i\times k$ 直到严格大于前面的数字，后面的同理，输出最后一个数。

int x = 0;
for (int i = 0; i < n; i++) {
	int a;
	std::cin >> a;
	x = x - x % a + a;
}
std::cout << x << "\n";

void solve() {
    int n;cin >> n;vector<int> a(n);for (auto& i : a)cin >> i;
    int now = a[0];
    for (int i = 1;i < n;i++) {
        int k = 1;
        while (a[i] <= now) {
            k++;
            if (a[i] * k > now)
                a[i] *= k;
        }
        now = a[i];
    }
    cout << now << '\n';
}

C. LR-remainders

给定一个长度为 $n(1\le n\le 2\times {10}^5)$ 数组 $a(1\le a_i\le {10}^4)$，模数 $m(1\le m\le {10}^4)$，命令字符串 $s(L|R)$，处理命令规则：

• 输出 $a_1\times a_2\times \cdots \times a_{a.size()}(\mathrm{mod}m)$
• s[i]='L' 从数组中删除最左边的元素，s[i]='R' 删除最右边的元素。

每次删除后数组 $a$ 长度会减少 1，处理完后 $a$ 为空。给出输出过程的结果。

若按照描述来做，数据范围小的时候是可以的，但是 x[i] 最大可以达到 ${10}^4\times {10}^4\times \dots (2\times {10}^5\mathrm{个})={10}^{8\times {10}^5}$ 远远大于了计算机能存储的。

for (int i = 1;i <= n;i++)//前缀积
	x[i] = x[i - 1] * a[i];

int l = 1, r = n;
for (int i = 0;i < n;i++) {
	cout << (x[r] / x[l - 1]) % m << ' ';
	if (s[i] == 'L') l++;
	else r--;
}

我于是想到了逆元来解决，但是似乎没有做出来 (待更 $\dots$)

void solve() {
    int n, m;cin >> n >> m;
    vector<int> a(n);
    for (int i = 0;i < n;i++) {
        cin >> a[i];
    }
    string s;cin >> s;
    int l = count(s.begin(), s.end(), 'L'), r = l;
    vector<int> ans(n);
    int num = 1;
    for (int i = n - 1;i >= 0;i--) {
        if (s[i] == 'L') {
            num = num * a[--l] % m;
        } else {
            num = num * a[r++] % m;
        }
        ans[i] = num;
    }
    for (int i = 0;i < n;i++)cout << ans[i] << " \n"[i == n - 1];
}

(待更 $\dots$)