A

题解

知识点：数学。

注意到 \(n\) 为奇数时，不考虑连续性，一共有 \(\lceil \frac{n}{2} \rceil ^2\) 个格子，接下来证明一定能凑成方块。

从下往上从大到小摆，第 \(1\) 层摆 \(1 \times \lceil \frac{n}{2} \rceil\) 的矩形，第 \(i\geq 2\) 层显然可以成对摆放 \(1 \times \lceil \frac{n-i}{2} \rceil\) 和 \(1\times (\lceil \frac{n}{2} \rceil -\lceil \frac{n-i}{2} \rceil)\) 的矩形。

\(n\) 为偶数时，总数最多构成 \(\lceil \frac{n}{2} \rceil ^2\) 大小的方形，和奇数情况一样，但会最后多一个最长的矩形。

时间复杂度 \(O(1)\)

空间复杂度 \(O(1)\)

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

bool solve() {

    int n;

    cin >> n;

    cout << (n + 1) / 2 << '\n';

    return true;

}

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    cin >> t;

    while (t--) {

        if (!solve()) cout << -1 << '\n';

    }

    return 0;

}

B

题解

知识点：枚举。

显然根据鸽巢原理，合法的串长度不会超过 \(100\) ，对每位向前枚举 \(100\) 位即可。

时间复杂度 \(O(100\cdot n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int a[100007];

bool solve() {

    int n;

    cin >> n;

    for (int i = 1;i <= n;i++) {

        char ch;

        cin >> ch;

        a[i] = ch - '0';

    }

    ll ans = 0;

    for (int i = 1;i <= n;i++) {

        vector<int> cnt(10);

        int vis = 0, mx = 0;

        for (int j = i;j >= 1 && i - j + 1 <= 100;j--) {

            if (cnt[a[j]] == 0) vis++;

            cnt[a[j]]++;

            mx = max(mx, cnt[a[j]]);

            if (mx <= vis) ans++;

        }

    }

    cout << ans << '\n';

    return true;

}

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    cin >> t;

    while (t--) {

        if (!solve()) cout << -1 << '\n';

    }

    return 0;

}

C

题解

知识点：贪心，枚举。

一个 \(0\) 能被修改成任意数字，它能影响到自己到下一个 \(0\) 之前的所有前缀和的贡献（下一个 \(0\) 能继续调整，所以不纳入这个 \(0\) ）。

我们统计两个 \(0\) 中间（包括左边的 \(0\) ，但不包括右边的）前缀和种类，然后把 \(0\) 调整成能将最多数量的一种前缀和变为 \(0\) 即可。

从后往前枚举，最左边一段左侧没有 \(0\) 因此只有前缀和为 \(0\) 的才有贡献。

时间复杂度 \(O(n \log n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int a[200007];

ll sum[200007];

bool solve() {

    int n;

    cin >> n;

    for (int i = 1;i <= n;i++) cin >> a[i], sum[i] = sum[i - 1] + a[i];

    int ans = 0, mx = 0;

    map<ll, int> mp;

    for (int i = n;i >= 1;i--) {

        mp[sum[i]]++;

        mx = max(mp[sum[i]], mx);

        if (a[i] == 0) {

            ans += mx;

            mx = 0;

            mp.clear();

        }

    }

    ans += mp[0];

    cout << ans << '\n';

    return true;

}

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    cin >> t;

    while (t--) {

        if (!solve()) cout << -1 << '\n';

    }

    return 0;

}

D

题解

方法一

知识点：构造。

首先设 \(d\) 的尾 \(0\) 数为 \(k\) ，如果 \(a\) 或 \(b\) 的尾 \(0\) 数小于 \(k\) ，那么一定无解。因为 \(d\) 的因子包括 \(2^k\) ，而 \(a\) 或 \(b\) 的因子或以后也不会包括 \(2^k\) ，因为尾部有 \(1\) 。

如果有解，我们考虑用 \(x\) 把 \(a\) 和 \(b\) 同步，又要保证能被 \(d\) 整除。因此我们可以从第 \(k\) 位开始到第 \(29\) 位，如果 \(x\) 第 \(i\) 位为 \(0\) 则用 \(d\) 的第一个 \(1\) 通过加法填充这位，即 \(x + d \cdot 2^{i-k}\) ，这只会影响第 \(i\) 位之后的位，之前的不会影响。

于是我们把 \(a,b\) 前 \(30\) 位同步，于是一定有 \(a|x = b|x = x\) ，且或以后能被 \(d\) 整除。

时间复杂度 \(O(1)\)

空间复杂度 \(O(1)\)

方法二

知识点：数论，构造。

方法一得到的结论是： \(x\) 前 \(30\) 位除去 \(k\) 个尾 \(0\) 都用 \(d\) 加成 \(1\) 。设后 \(30\) 位为 \(p\) 于是 \(x = p\cdot 2^{30} + (2^{30} - 2^k)\) 。

我们尝试直接求出这个 \(p\) ：

\[\begin{aligned}
p\cdot 2^{30} + (2^{30} - 2^k) &\equiv 0 & &\pmod d\\
p\cdot 2^{30-k} + (2^{30-k} - 1) &\equiv 0 & &\pmod{\frac{d}{2^k}}\\
p &\equiv \bigg(\frac{1}{2} \bigg)^{30-k} - 1 & &\pmod{\frac{d}{2^k}}\\
p &\equiv \bigg(\frac{\frac{d}{2^k}+1}{2} \bigg)^{30-k} - 1 + \frac{d}{2^k} & &\pmod{\frac{d}{2^k}}\\
\end{aligned}
\]

时间复杂度 \(O(1)\)

空间复杂度 \(O(1)\)

代码

方法一

#include <bits/stdc++.h>

#define ll long long

using namespace std;

bool solve() {

    int a, b, d;

    cin >> a >> b >> d;

    int k = __builtin_ctz(d);

    if (k > __builtin_ctz(a) || k > __builtin_ctz(b)) return false;

    ll x = 0;

    for (int i = k;i < 30;i++) if (!(x & (1 << i))) x += (ll)d << (i - k);

    cout << x << '\n';

    return true;

}

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    cin >> t;

    while (t--) {

        if (!solve()) cout << -1 << '\n';

    }

    return 0;

}

方法二

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int qpow(int a, int k, int P) {

    int ans = 1;

    while (k) {

        if (k & 1) ans = 1LL * ans * a % P;

        k >>= 1;

        a = 1LL * a * a % P;

    }

    return ans;

}

bool solve() {

    int a, b, d;

    cin >> a >> b >> d;

    int k = __builtin_ctz(d);

    if (k > __builtin_ctz(a) || k > __builtin_ctz(b)) return false;

    d >>= k;

    ll x = (qpow((d + 1) / 2, 30 - k, d) - 1 + d) % d * (1LL << 30) + (1 << 30) - (1 << k);

    cout << x << '\n';

    return true;

}

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    cin >> t;

    while (t--) {

        if (!solve()) cout << -1 << '\n';

    }

    return 0;

}

巴特西

Codeforces Round #833 (Div. 2) A-D.md

A

题解

代码

B

题解

代码

C

题解

代码

D

题解

方法一

方法二

代码

方法一

方法二

最新文章

热门文章