C. 冰冰的异或

思路

可以通过相同的数异或得到。

至少需要通过 得到，因此如果 ，那么集合 为 。

如果 ，那么可以通过 与 进行异或运算得到 。

可以通过相邻的两个数异或 相互得到，例如 这些数是相邻的，可以通过异或 互相转换。

因此，令 为不大于 的最大的二次幂，若 ，那么可以通过异或运算得到的数的范围至少为 。

如果 恰好为 ，那么无论怎么样都无法运算得到 ，否则则可以通过如 的运算得到 。

因此，如果 恰好为 ，集合 为 ，否则为 。

复杂度

时间复杂度 ，空间复杂度

代码实现

// Problem: 冰冰的异或
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/93218/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int unsigned long long

void solve()
{
    int n;
    cin >> n;
    if (n <= 2) {
        cout << 1 << '\n';
        return;
    }
    // 枚举最大的不大于n的2^i
    for (int i = 63; i >= 0; i--) {
        if ((n >> i) & 1) {
            int w1 = 1ull << i;
            int w = 1ull << (i + 1);
            if (w1 == n)
                cout << w1 << '\n';
            else
                cout << w << '\n';
            return;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

D. 冰冰的分界线

思路

点的数量不是很多，所以可以枚举 可能的情况从而计算出所有的分界线。

两点之间的分界线，实则是两点相连的直线的中垂线，必然会经过 。

主要分为两种情况：

1， 该情况中垂线没有斜率，表示为 ，该情况下不重复的 的总数，即为这种情况的分界线数量，可以用 存所有的 ，最后 的大小即为该情况分界线数量。

2， 该情况中垂线存在斜率，两点相连直线的斜率 ，通过垂直的两条直线斜率积为 的性质，可以得到中垂线的斜率为 ，对应的截距即为 。 求出所有中垂线的斜率和截距后，把斜率和截距作为二元组，按斜率从小到大排序，如果斜率相等按截距从小到大排序，这样排序之后，斜率和截距都相等的二元组就必然在连续的一段，计算这些段的段数即为该情况分界线的数量。

两种情况分界线数量之和即为答案。

复杂度

时间复杂度 ，空间复杂度

代码实现

// Problem: 冰冰的分界线
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/93218/D
// Memory Limit: 512 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

const int N = 1e8 + 5;
const double eps = 1e-5;

int n;
int x[N], y[N];

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    for (int i = 1; i <= n; i++)
        cin >> y[i];

    set<int> all1;
    vector<array<double, 2>> all2;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (y[i] == y[j]) {
                all1.insert(x[i] + x[j]);
            } else {
                double mx = (x[i] + x[j]) / 2.0;
                double my = (y[i] + y[j]) / 2.0;
                double k = x[j] != x[i] ? -1.0 * (x[j] - x[i]) / (y[j] - y[i]) : 0;
                // 如果x坐标相同斜率为0
                double b = my - k * mx;
                all2.push_back({ -k, b });
            }
        }
    }
    int ans = all1.size();
    sort(all2.begin(), all2.end());
    for (int i = 0; i < all2.size(); i++) {
        int j = i;
        // 斜率和截距都要近似相等
        while (j < all2.size() && fabs(all2[i][0] - all2[j][0]) <= eps
            && fabs(all2[i][1] - all2[j][1]) <= eps) {
            j++;
        }
        ans++;
        i = j - 1;
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

E. 冰冰的 GCD

思路

先预处理出 的所有情况，然后对于每个查询查预处理的结果计算，然后输出即可。

因为 的计算和排列 中下标大于 的元素相关，所以按下标从 到 的顺序计算 。

计算完 之后，枚举 的所有因数 ，设置 ，表示已经计算过的 中，存在因子 的数的最小下标为 。

通过上面的处理，在遍历到 时，就可以枚举 的因子 ，找出 的最小值 ，如果后面存在与 最大公约数不为 的数，那么 就是第一个满足 的 ，，否则 会是设定的无穷大值（ 初始化时都设定为无穷大），此时 。在计算完 后也是同理，枚举 的因子相应的更新 。

，该式子可以变式为 。（这里的 表示数组 中 所在的下标）

可以发现， 实际上计算 有多少个倍数在 中的下标不小于 ，所以可以从 到 枚举 ，然后再枚举 的倍数 ，看有多少个 ，这样做的复杂度是 ，不会超时。

复杂度

时间复杂度 ，其中 的复杂度是预处理 的， 的复杂度是预处理 的。

空间复杂度

代码实现

// Problem: 冰冰的 GCD
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/93218/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

const int N = 1e5 + 5;

int n, m;
int a[N], b[N], c[N], f[N], g[N], id[N];

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++)
        cin >> c[i];

    memset(id, 0x3f, sizeof(id));
    int inf = id[0];
    for (int i = n; i >= 1; i--) {
        int x = b[i];
        int mi = inf;
        for (int j = 1; j <= x / j; j++) {
            if (x % j == 0) {
                if (j != 1)
                    mi = min(mi, id[j]);
                mi = min(mi, id[x / j]);
            }
        }
        if (mi == inf)
            f[i] = b[i];
        else
            f[i] = __gcd(b[i], b[mi]);

        for (int j = 1; j <= x / j; j++) {
            if (x % j == 0) {
                id[j] = min(id[j], i);
                id[x / j] = min(id[x / j], i);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        id[a[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            g[i] += id[j] >= c[i];
        }
    }

    while (m--) {
        int x;
        cin >> x;
        cout << g[f[x]] << '\n';
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}