P17749 题解

Rosing · 2026-10-24 15:53:21 · 题解

出题人来啦。

我们设 a_i\in\{0,1\} 表示是否操作点 i，易知最优方案中每个点至多操作一次。

点 i 最终为黑，需要被翻转奇数次：a_{i-1}\oplus a_i\oplus a_{i+1}=1。

相邻两式异或得：a_{i-1}=a_{i+2}。

所以：a_i=a_{i+3}。

即操作序列以 3 为周期。

因此：

• 若 3\nmid n，则所有 a_i 相等，代入得 a_i=1，答案为 n。

• 若 3\mid n，每个周期长为 3，且每周期内 1 的个数为奇数。最少每周期放一个 1，答案为 \frac n3。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
    int T,n;
    cin >> T;
    while (T--)
    {
        cin >> n;
        if (n % 3 == 0) cout << n / 3 << '\n';
        else cout << n << '\n';
    }
    return 0;
}