A

数学

问一个数能否表示成。如果能，则，检查这个即可

void solve() {
    int n;
    cin >> n;
    int t = sqrt(n);
    if (t * (t + 1) == n) {
        cout << "YES";
    } else {
        cout << "NO";
    }
}

B

概率 数论

找出一对，保证数据是随机生成的。这种问题，先考虑偶数，然后就会发现，由于是随机生成，所以较大时全是奇数的概率很低，可以忽略不计。所以设定一个阈值，大于这个阈值，认为一定存在至少两个偶数，有解；小于这个阈值，暴力枚举全部个数对，检查

void solve() {
    int n;
    cin >> n;
 
    vi a(n + 1);
    vi t;
    t.reserve(n);
    rep(i, 1, n) {
        cin >> a[i];
        if (a[i] % 2 == 0) {
            t.push_back(a[i]);
        }
    }
 
    if (n <= 5000) {
        rep(i, 1, n) {
            rep(j, i + 1, n) {
                if (gcd(a[i], a[j]) != 1) {
                    cout << a[i] << ' ' << a[j] << '\n';
                    return;
                }
            }
        }
        cout << -1 << '\n';
    } else {
        cout << t[0] << ' ' << t[1] << '\n';
    }
}

C

转化 贪心

每次可以选一个01交替的子序列，反转其中的0和1。问最少多少次操作可以把整个串变成01交替的？

这里有一个重要思想：01串反转问题类似异或，每个位置多次操作是无意义的，只有操作0次和1次的区别。所以我们可以把需要反转的位拿出来，每次操作修改一个子集，然后这部分修改的位置，就应该是最终结果了。

所以直接把和目标串不同的位置全拿出来，组成一个新串，在这个串上操作就行。目标串是01交替的，有两种（0开头和1开头），对这两种分别计算，取最小值。

对于不同位置组成的新串，就转化到一个经典问题：把这个串分解成数量尽可能少的子序列，每个子序列都是01交替的，我们每次操作一个子序列即可。这个贪心经典做法是：维护0结尾和1结尾的01交替串的个数，每次一个0，可以单独拿出来作为一个01交替串的开始，也可以接到一个1结尾的01串后面，对于一个1也同理，可以单拿出来，也可以接到一个0结尾的串后面。那想要01串个数最少，肯定凹尽可能接到已有的01串后面，而不是单开一个。模拟这个过程，计算0结尾和1结尾的01串个数，加到一起就是拆出来的最少的01子序列个数。

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    string t;
    t.reserve(n);
    rep(i, 0, n - 1) {
        if (i % 2) {
            t += '1';
        } else {
            t += '0';
        }
    }
 
    string a;
    rep(i, 0, n - 1) {
        if (s[i] != t[i]) {
            a += s[i];
        }
    }
    int ans = inf;
    int c1 = 0, c0 = 0;
    for (char c : a) {
        if (c == '1') {
            if (c0) {
                c0--;
            }
            c1++;
        } else {
            if (c1) {
                c1--;
            }
            c0++;
        }
    }
    ans = min(ans, c0 + c1);
 
    t = "";
    rep(i, 0, n - 1) {
        if (i % 2) {
            t += '0';
        } else {
            t += '1';
        }
    }
    a = "";
    rep(i, 0, n - 1) {
        if (s[i] != t[i]) {
            a += s[i];
        }
    }
    c1 = 0, c0 = 0;
    for (char c : a) {
        if (c == '1') {
            if (c0) {
                c0--;
            }
            c1++;
        } else {
            if (c1) {
                c1--;
            }
            c0++;
        }
    }
    ans = min(ans, c0 + c1);
 
    cout << ans << '\n';
}

F

博弈 思维 打表

有严谨证明的方法，但不会。打表到大概就能观察出来。

定性证明的话，就是至少要往右走次，这是省不了的。然后对手为了让路程尽可能长，会制造一些结构让小小红必须上下移动，然后花五次操作能制造一次，所以加上

void solve() {
    int x;
    cin >> x;
    cout<<x-1+x/5<<'\n';
}

G

排序 贪心

天平两侧，分别放了一些砝码。问最少拿走几个能改变天平的状态。如果平衡，随意拿走一个都可以改变。如果不平衡，显然要从重的那边拿，优先拿重的，计算拿几个之后状态改变。

int a[N], b[N];
void solve() {
    int n, m;
    cin >> n >> m;
 
    int sa = 0, sb = 0;
    rep(i, 1, n) {
        cin >> a[i];
        sa += a[i];
    }
    rep(i, 1, m) {
        cin >> b[i];
        sb += b[i];
    }
 
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + m);
 
    int ans = 0;
    if (sa == sb) {
        cout << 1 << '\n';
    } else if (sa < sb) {
        for (int i = m; i >= 1 && sa < sb; i--) {
            sb -= b[i];
            ans++;
        }
        cout << ans << '\n';
    } else {
        for (int i = n; i >= 1 && sa > sb; i--) {
            sa -= a[i];
            ans++;
        }
        cout << ans << '\n';
    }
}

H

计算几何 二分/三分/数学公式

给两个点，在轴上找到一个点，使得三个点组成三角形面积等于，误差不超过即可

如果两个定点形成的线段和轴平行，需要特判，此时所有三角形面积都一样，所以随意计算一个三角形面积，等于的话，可以选轴上任意点，否则无解。

否则，两个定点所在直线把轴分成两边，这两边，随着的移动，面积是一个凹函数，可以二分或者三分解决。但这需要找到直线和轴交点。

另一个写起来更快的方法是，考虑三角形面积公式

带入就是，这方程只有是未知数，拆开绝对值有两个解，分别对应我们上面说的直线两侧。直接计算即可。（顺带一提，这个公式若第三个点是原点，会退化成，求两个点相对第三个点的向量，即可用这个更简单的形式）

需要注意的是，精度要求是，用这三个点计算出的面积误差不超，的精度还要更高才能保证。

void solve() {
    int xa, xb, ya, yb;
    cin >> xa >> ya >> xb >> yb;
 
    int s = xa * yb - xb * ya;
    if (ya == yb) {
        if (abs(s) != 4) {
            cout << "no answer\n";
        } else {
            cout << fixed << setprecision(9) << 0 << '\n';
        }
    } else {
        int k = ya - yb;
        db x = (4.0 - s) / k;
        cout << fixed << setprecision(9) << x << '\n';
    }
}

I

线性基 构造方案 状压

构造一个序列，其中。使得

这种每个都二选一的问题，可以先假设每个位置都是一个初始值，也就是选，然后每个位置可以选择是否变化，也就是异或上。想要操作后整体异或等于0，也就是我们新增的这些异或起来等于

到这一步问题就转化成了，给一个序列，选任意个元素异或起来，问能否等于一个定值？上线性基即可。

难点在于还需要输出方案，也就是每个是否被选中。线性基查询时，是从高到低异或上了一些二进制位上的基，那么如果能记录每个基，是序列里哪些元素异或得到的，不就可以得到方案了？

考虑对每个基维护一个，第位为1，表示这个基，包含序列里的。插入时，最开始，接下来每经过一个基，由于我们把和这一位的基异或了，等于把这个基包含的所有元素都加入了，所以需要异或上这个基的。

这又有问题，序列长度，难道也有这么多位？即使用加速复杂度也爆炸了。很重要的一点是，虽然元素总数很多，但线性基里只有个元素，所以每个基即使是多个元素组合得到的，也只会是这个元素的组合，我们的只用30位左右就够了。这30位里的第位不再代表，而是中第个成功插入线性基的元素。

想实现这个思路，我们需要给插入线性基的这30个元素编号，最好是两次插入扫描，第一次记录哪些元素插入线性基成功了，给这些元素编号，第二次只将这些能成功插入的元素，插入线性基，插入时根据编号构造。

class LinearBasis {
    private:
        static const int MN = 40;
        long long a[MN + 1], tmp[MN + 1], pos[MN + 1];
        int sz;
        bool flag;
 
    public:
        LinearBasis() : sz(0), flag(false) {
            memset(a, 0, sizeof(a));
            memset(tmp, 0, sizeof(tmp));
        }
 
        bool insert(long long x, int mask) {
            for (int i = MN; i >= 0; i--) {
                if (x & (1LL << i)) {
                    if (!a[i]) {
                        a[i] = x;
                        pos[i] = mask;
                        sz++;
                        return 1;
                    }
                    x ^= a[i];
                    mask ^= pos[i];
                }
            }
            flag = true;
            return 0;
        }
 
        bool check(long long x) {
            for (int i = MN; i >= 0; i--) {
                if (x & (1LL << i)) {
                    if (!a[i]) return false;
                    x ^= a[i];
                }
            }
            return true;
        }
 
        int check1(long long x) {
            int res = 0;
            for (int i = MN; i >= 0; i--) {
                if (x & (1LL << i)) {
                    x ^= a[i];
                    res ^= pos[i];
                }
            }
            return res;
        }
 
        long long queryMax(long long res = 0) {
            for (int i = MN; i >= 0; i--) {
                res = max(res, res ^ a[i]);
            }
            return res;
        }
 
        long long queryMin() {
            if (flag) return 0;
            for (int i = 0; i <= MN; i++) {
                if (a[i]) return a[i];
            }
            return 0;
        }
 
        long long queryKth(long long k) {
            long long res = 0;
            int cnt = 0;
 
            k -= flag;
            if (!k) return 0;
 
            for (int i = 0; i <= MN; i++) {
                for (int j = i - 1; j >= 0; j--) {
                    if (a[i] & (1LL << j)) {
                        a[i] ^= a[j];
                    }
                }
                if (a[i]) tmp[cnt++] = a[i];
            }
 
            if (k >= (1LL << cnt)) return -1;
 
            for (int i = 0; i < cnt; i++) {
                if (k & (1LL << i)) {
                    res ^= tmp[i];
                }
            }
            return res;
        }
 
        int getsz() {
            return sz;
        }
};
void solve() {
    int n;
    cin >> n;
    vi a(n + 1), b(n + 1);
    rep(i, 1, n) {
        cin >> a[i];
    }
    rep(i, 1, n) {
        cin >> b[i];
    }
 
    LinearBasis lb;
    int sum = 0;
    vi d(n + 1);
 
    vi in;
    rep(i, 1, n) {
        d[i] = a[i] ^ b[i];
        sum ^= a[i];
        if (lb.insert(d[i], 0)) {
            in.push_back(i);
        }
    }
 
    lb = LinearBasis();
    int cnt = 0;
    for (int x : in) {
        lb.insert(d[x], 1ll << cnt);
        cnt++;
    }
 
    if (lb.check(sum)) {
        int res = lb.check1(sum);
        vi vis(n + 1);
        rep(i, 0, 40) {
            if (res >> i & 1) {
                vis[in[i]] = 1;
            }
        }
 
        rep(i, 1, n) {
            if (!vis[i]) {
                cout << a[i] << ' ';
            } else {
                cout << b[i] << ' ';
            }
        }
        cout << '\n';
    } else {
        cout << -1 << '\n';
    }
 
}

另一种类似的做法是，记录当前基是由哪些基组成的，并且每个基记录，自己独有的那一位，是序列中哪个元素贡献的，也可以查询方案。查询到的方案，第位是1表示这个基包含第个基独有的那个元素，然后再去查第个基独有的元素是哪个。

此外，异或高斯消元也可以可以一步到位构造方案，也是先跑一次线性基，把插入线性基的元素拿出来，形成一个的矩阵，代表一个异或方程组，消元后，剩余的自由位就是方案包含的元素。

J

倍增 完全二叉树

一个完全二叉树个点（除了最后一层都是满的），每次问所在层有多少个点。

每一层由多少个点是可求的，除了最后一层就是2的幂，最后一层可能不满，需要减去少的点数。于是只需要快速确定深度，二叉树是堆式存储的，除2就能得到父亲的编号，一直除二直到根节点1即可，每次查询只需要时间

void solve() {
    int n, q;
    cin >> n >> q;
 
    int mxd = 0;
    int nn = n;
    while (n != 1) {
        n >>= 1;
        mxd++;
    }
 
    int dif = (int)pow(2, mxd + 1) - 1 - nn;
    rep(i, 1, q) {
        int x;
        cin >> x;
        int d = 0;
        while (x != 1) {
            x >>= 1;
            d++;
        }
        int ans = pow(2, d);
        if (d == mxd) {
            ans -= dif;
        }
        cout << ans << '\n';
    }
}