A. The Miracle and the Sleeper

题意

让你在一个区间内找一对数，使得较大的数对较小数取模后的结果最大，输出最大值。

大概思路

直接贪心地取最大值r，再取max(l, r / 2 + 1)即可，这样返回的取模后的值一定是二者差值

参考代码

void solve(){
    int l, r;
    std::cin >> l >> r;

    std::cout << r % std::max(l, (r) / 2 + 1) << "\n";
}

B. Scenes From a Memory

题意

给你一个不含0的纯数字字符串，让你删除若干个数之后，剩下的数（不改变顺序）是个非质数（1或者合数），求剩下的字符串最短长度以及该字符串

大概思路

一眼望去还以为是数位dp，但是其实是还算简单的分类讨论。

• 如果原字符串里含有“1”，“4”，“6”，“8”，“9”，那么直接输出这个数就行，字符串长度为1。
• 如果原字符串中有任何一种字符超过1个，那么输出两个该字符就行，字符串长度为2。
• 如果原字符串中出现了2或者5，且不是字符串第一个，那么直接输出前一个数字，以及2或5即可，字符串长度为2。

特判完上面两句后，原字符串的构成就只剩下“2”，“3”，“5”，“7”的排列组合了。

我们直接对剩下所有可能的情况手动打表如下（“-”代表被排除的情况）：

可以发现，所有可能情况中，只有27和57是合数，而题目又说给定字符串必定有解，因此我门只需要判断字符串中2或者7的出现情况来选择输出。

参考代码

void solve(){
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    std::map<char, int> cnt;

    for (auto &c : s) {
        if (c == '1' || c == '4' || c == '6' || c == '8' || c == '9') {
            std::cout << 1 << '\n' << c << "\n";
            return;
        }
        cnt[c]++;
    }
    std::cout << 2 << "\n";

    std::string no5, no2;
    for (auto &[k, v] : cnt) {
        if (v >= 2) {
            std::cout << k << k << '\n';
            return;
        }
    }

    for (int i = n - 1; i >= 0; i--) {
        if ((s[i] == '2' || s[i] == '5') && i != 0) {
            std::cout << s[i - 1] << s[i] << "\n";
            return;
        }
    }

    if (cnt.count('2')) {
        std::cout << "27\n";
    } else {
        std::cout << "57\n";
    }
}

C. Rings

题意

给定一个01字符串，让你选两个不同的区间（区间长度大于等于字符串总长度的一半），使得区间内的二进制串，一个是另一个的倍数（倍数非负）

大概思路

贪心一下，注意到“0111101”和“111101”相等（倍数关系为1），以及“1111010”和“111101”成倍数关系，那么我们只要找到字符串中出现0的位置，然后根据位置决定贪心地向左还是贪心地向右取端点即可。

比如11111111101111，那我们取(1,9),(1,10)显然可行，如果是1111011111111，那么取(5,13),(6,13)即可。

要注意特判奇数且只有一个0的情况，比如1111110111111，那么我们可以取(1,7),(7,13)。

然后就剩全1情况了，直接输出(1, n - 1), (2, n)即可。

参考代码

void solve(){
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    for (int i = 0; i < n / 2; i++) {
        if (s[i] == '0') {
            std::cout << i + 1 << " " << n << " " << i + 1 + 1 << " " << n << "\n";
            return;
        }
    }
    for (int i = n / 2 + (n & 1); i < n; i++) {
        if (s[i] == '0') {
            std::cout << 1 << " " << i + 1 << " " << 1 << " " << i << "\n";
            return;
        }
    }

    for (auto &c : s) {
        if (c == '0') {
            std::cout << 1 << " " << (n + 1) / 2 << " " << (n + 1) / 2 << " " << n << "\n";
            return;
        }
    }

    std::cout << 1 << " " << n - 1 << " " << 2 << " " << n << "\n";
}

D1. Two Hundred Twenty One (easy version)

题意

史迪奇喜欢和他的朋友斯帕克一起试验不同的机器。今天他们又做了一台机器。

这台机器的主要部件是沿着一条直线排列的 $n$ 根棒子，编号从 $1$ 到 $n$ 包括在内。每根棒子都必须带有数量等于 $1$ 或 $-1$ 的电荷(否则机器将无法工作)。这台机器工作的另一个条件是，所有棒上电荷的符号变量之和必须为零。

从形式上看，小棒可以表示为一个由 $n$ 个数字组成的数组，这些数字表示电荷的特征： $1$ 或 $-1$ 。那么条件必须成立： $a _ 1 - a _ 2 + a _ 3 - a _ 4 + \ldots = 0$ 或 $\sum\limits _ {i=1}^n (-1)^{i-1} \cdot a _ i = 0$ 。

斯帕克用电流给所有 $n$ 根小棒充电，但不幸的是，这些小棒并没有正确充电(电荷的符号变量和不为零)。朋友们决定只把部分棒子留在机器里。斯帕克有 $q$ 个问题。在第 $i$ 个问题中，斯帕克问：如果机器中只有编号为 $l _ i$ 至 $r _ i$ 的小棒，那么从机器中取出最少多少根小棒才能使剩余小棒上电荷的符号变量和为零？也许朋友们弄错了，符号变量和已经为零。在这种情况下，你根本不需要移走电棒。

如果小棒的数量为零，我们就假定电荷的符号变量和为零，也就是说，我们总是可以移除所有的小棒。

帮助你的朋友，回答斯帕克的所有问题！

大概思路

看题意有点抽象，实际上就是问你，给定区间，至少删几个数，才能让区间按顺序一次带上正负一交替的权值，求和后为0。

假设字符串长度为偶数，那么我们纸上手玩一下样例，容易发现，按照每两个为一组的话，“++”和“–”造成的贡献都为0，而“+-”会提供+2的贡献，“-+”会提供-2的贡献。因此，我们可以先分区间左端点为奇数和偶数的两种情况，两两分组，前缀和收集贡献。再进行进一步分析。

当区间长度为奇数时，必然要删奇数个数，考虑能不能只删一个数。我们将删数的位置定在字符串最右边，那么向左移动这个删数指针，对总的答案影响很小。

假设从左往右分组，有一组造成正贡献的“+-”，那么当删数指针移动到该组左边的“+”字符上时，该组的贡献会产生什么变化？答案是该组会变成“-*”，要么造成0贡献，要么造成负贡献。

也就是说，删数指针从右往左走时，会将指针右边的每个组的贡献取反（或者置0（或者，把0贡献变成0或正或负））

当区间为偶数时，原区间带权求和已经为0时，显然时不需要删数的，输出0。

当区间为偶数时，原区间带权求和不为0时，最少可以删两个数

yysy我真不会，这规律我蒙出来的。(甚至还非常丢脸的贴了个树状数组代替前缀和)

• 当区间长度为奇数时，存在一个位置，删除它后，区间正负权值和为0
• 当区间长度为偶数，且区间权值和不为0时，存在两个位置，删除它后，区间正负权值和为0
• 当区间长度为偶数，且区间权值和已经为0时，不需要操作。

参考代码

template<typename T>
struct BIT {
	std::vector<T> C;
	int n;
	BIT(int n_) {//下标从1开始
		C.clear();
		C.resize(n_ + 1);
		n = n_;
	}
	BIT() {}
	BIT(const BIT& bit) {
		n = bit.n;
		C = bit.C;
	}
	T getsum(int x) {//获取[1, x]的和		O(logn)
	    T s = 0;
	    while (x) {
	        s += C[x];
	        x -= (x &- x);
	    }
	    return s;
	}
	void add(int x, T key) {//单点增加x的值	O(logn)
	    while (x <= n) {
	        C[x] += key;
	        x += (x &- x);
	    }
	}
};
//附：想区间修改，区间查询的话，可以用这个维护差分数组（不过都只支持加减）
//区间推平，区间加乘，等操作，请换线段树


void solve(){
    int n, q;
    std::cin >> n >> q;
    std::string s;
    std::cin >> s;

    std::vector<bool> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = (s[i] == '+');
    }

    BIT<int> J(n), O(n);
    for (int i = 0; i + 1 < n; i += 2) {
        int v = 0;
        if (a[i] != a[i + 1]) {
            v = (a[i] == 1 ? 1 : -1);
        }
        J.add(i + 1, v);
    }

    for (int i = 1; i + 1 < n; i += 2) {
        int v = 0;
        if (a[i] != a[i + 1]) {
            v = (a[i] == 1 ? 1 : -1);
        }
        O.add(i + 1, v);
    }

    while (q--) {
        int l, r;
        std::cin >> l >> r;
        l--;
        
        if ((r - l) & 1) {
            std::cout << 1 << "\n";
            continue;
        }

        int sum;
        if (l & 1) {
            sum = O.getsum(r) - O.getsum(l);
        } else {
            sum = J.getsum(r) - J.getsum(l);
        }

        std::cout << (sum == 0 ? 0 : 2) << "\n";
    }
}