A

堆贪心

多个三角形，每一个都可以吧一个直角边减小一个整数，减小总量加起来不能超过，问最后所有斜边之和最小多少？

考虑一个三角形，随着直角边变小，斜边变小的速度是越来越慢的，所以贪心的想，每次减少，那选择减小的那个三角形，应该是减小后斜边变小最多的。

这就是一个经典贪心了，如果能执行的次数不多，就可以堆贪心，吧所有三角形按照，减小一单位直角边，斜边的减小量排序，每次取出斜边减小量最大的。如果执行的次数很多，或是可以减小的不是整数，而是实数的话，则可以二分间接量，一般就是函数的导数之类的，检查把每个东西都操作到的导数为的代价是否超过限制，对这道题的话，就可以考虑二分

这里很小，并且每次减小的都是整数，直接堆模拟就可以

void solve() {
	int n, w;
	cin >> n >> w;

	vi x(n + 1), y(n + 1);
	set<pair<db, int>>s;
	rep(i, 1, n) {
		cin >> x[i] >> y[i];
		s.insert({x[i] * 1.0 / y[i], i});
	}

	while (w && s.size()) {
		auto [tan, id] = *s.begin();
		s.erase(s.begin());
		y[id]--;
		w--;
		if (y[id] > 0) {
			s.insert({x[id] * 1.0 / y[id], id});
		}
	}

	db ans = 0;
	rep(i, 1, n) {
		ans += sqrt(x[i] * x[i] + y[i] * y[i]);
	}
	cout << fixed << setprecision(10);
	cout << ans;
}

B

组合数学 球盒模型

一串球，相邻球之间有线段，现在需要决定每一个球是在左右哪个盒子里，要求最后露在盒子外面的线段数为，左侧盒子恰好有个球，右侧盒子恰好有个球

思考一下放的方案是什么样的：遍历到号球，几个球在左边，几个球在右边，这里跨越了一次左右，产生了一个露在外面的线段，然后可能时再几个球再左边。可以发现露在外面的线段数，只和左右两个盒子里有几段连续的球有关，而和每一段球具体多少个无关。

所以为了满足线段数的约束，首先可以让每一段都只有一个，这样形成了一个骨架，满足了的要求，接下来，再把剩下的还没用的球，分配到这这骨架上的每一段上，左侧盒子需要有个，那么假设骨架上已经有个了，剩下就是还要安排个球到左侧，有个位置，可以有空的盒子，这就是球盒问题，，直接带入即可，右侧同理。

还需要考虑1号球是在左右哪边，如果为奇数，骨架上两侧的段数相同，1号球在左侧还是右侧方案数都一样，直接乘二。如果为偶数，两侧的段数不一样，分类讨论，加起来。

然后还有一些特殊情况需要特判，比如，这说明只有一段，方案数为1，如果，线段数为0，但是两边都有球，这根本不可能，方案数为0。，球全在一遍，但中间有线段，这也不可能，方案数为

void solve() {
    int n, x, t;
    cin >> n >> x >> t;
    if (t == 0) {
        if (x == 0 || x == n)cout << 1 << '\n';
        else cout << 0 << '\n';
        return;
    }
 
    if (x == 0 || x == n) {
        cout << 0 << '\n';
        return;
    }
 
    int ans, y, z, cntl, cntr;
    if (t % 2) {
        y = (t + 1) / 2;
        cntl = x - y;
        cntr = n - x - y;
        ans = C(cntl + y - 1, y - 1) * C(cntr + y - 1, y - 1) % M2;
        ans = ans * 2 % M2;
    } else {
        y = t / 2, z = y + 1;
        cntl = x - y;
        cntr = n - x - z;
        ans = C(cntl + y - 1, y - 1) * C(cntr + z - 1, z - 1) % M2;
 
        swap(y, z);
        cntl = x - y;
        cntr = n - x - z;
        ans += C(cntl + y - 1, y - 1) * C(cntr + z - 1, z - 1) % M2;
        ans %= M2;
    }
    cout << ans << '\n';
}

C

线段树

线段树上每个节点都有是否被破坏两个状态，每次查询，计算访问到的未被破坏的节点个数，如果一个点被破坏了，即使对应的区间，被查询区间完全包含，也需要往下暴力递归两个儿子。

显然可以在每个节点维护一个，记录这个点是否被破坏，然后执行查询时累加访问到的节点的，并且如果到了一个被完全包含的节点，但显示被破坏了，则需要计算从这一点往下暴力递归的答案。

注意，为了保证复杂度正确，遇到了被破坏的点，我们不能真的去往下暴力递归，而是要查询出这个点往下递归的代价，这个代价显然是可合并的，也就是一个点的代价，可以从左右儿子的代价推出来。考虑线段树维护。

关键是如何写合并，如果一个点的被破坏了，往下递归，如果左儿子没有被破坏，左儿子的代价就是，直接返回，如果左儿子被破坏了，则代价是，从左儿子往下递归的代价，这属于子问题，应该在前已经计算好了，返回这个值，右儿子同理。

修改时，递归到要修改的节点，把即可，接下来的代价更新都在时自动完成

struct Tree {
#define ls u<<1
#define rs u<<1|1
    struct Node {
        int l, r, v, sum;
 
        Node operator+(const Node &o) {
            Node res;
            res.l = l;
            res.r = o.r;
            res.sum = 0;
            if (v)res.sum++;
            else res.sum += sum;
            if (o.v)res.sum++;
            else res.sum += o.sum;
 
            return res;
        }
    } tr[M << 2];
 
    void pushup(int u) {
        tr[u].sum = 0;
        if (tr[ls].v)tr[u].sum++;
        else tr[u].sum += tr[ls].sum;
        if (tr[rs].v)tr[u].sum++;
        else tr[u].sum += tr[rs].sum;
    }
 
    void build(int u, int l, int r) {
        tr[u] = {l, r, 1, 0};
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
        pushup(u);
    }
 
    void modify(int u, int l, int r, int val = 0) {
        if (l <= tr[u].l && tr[u].r <= r) {
            tr[u].v = 0;
            return;
        } else {
            int mid = (tr[u].l + tr[u].r) >> 1;
            if (mid >= l)    modify(ls, l, r, val);
            if (r > mid) modify(rs, l, r, val);
            pushup(u);
        }
    }
 
    int query(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r) return  (tr[u].v) ? 1 : tr[u].sum;
        int mid = (tr[u].l + tr[u].r) >> 1;
        int res = tr[u].v;
        if (l <= mid)res += query(ls, l, r);
        if (r > mid)res += query(rs, l, r);
        return res;
    }
} t;
void solve() {
    int n;
    cin >> n;
    t.build(1, 1, n);
    rep(i, 1, n) {
        int op, l, r;
 
        cin >> op >> l >> r;
        if (op == 1) {
            t.modify(1, l, r);
        } else {
            cout << t.query(1, l, r) << '\n';
        }
    }
}

D

网格图最短路

网格图上，初始一些点是黑的，每秒会往周围四个点扩散，有些点是障碍物，直到某一时刻才解锁，可以被染色，问所有点都染色需要多久？

开始考虑模拟扩散，每次只让所有点扩散一秒，然后每一秒开始前解锁这一秒能解锁的点，如果一秒过去没有任何点被染色，说明都在等着下一次解锁，则直接跳到下一次解锁。但这样实现太麻烦，耽误了很多时间，最后还是转化到最短路模型了。

最短路可以直接优先队列+bfs，或者严谨一点写个。这里分析前者，优先队列每次弹出最小的点，然后这个点区松弛周围四个点，松弛操作是，也就是可能已经可以扩散到了，但是还没解锁，则必须等到解锁是才能染色。注意优先队列默认是大根堆，想实现小根堆需要传入比较函数，或者把距离取负。

最后遍历所有点，检查最晚被染色的点的染色时间。

void solve() {
	int n, m, a, b;
	cin >> n >> m >> a >> b;
	vvi d(n + 1, vi(m + 1, inf));
	vvi T(n + 1, vi(m + 1));

	int cnt = 0;
	priority_queue<array<int, 3>>q;
	rep(i, 1, a) {
		int x, y;
		cin >> x >> y;
		d[x][y] = 0;
		cnt++;
		q.push({-d[x][y], x, y});
	}


	rep(i, 1, b) {
		int x, y, t;
		cin >> x >> y >> t;
		T[x][y] = t;
	}

	while (q.size()) {
		auto [dis, x, y] = q.top();
		dis *= -1;
		q.pop();

		rep(i, 0, 3) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx < 1 || nx > n || ny < 1 || ny > m)continue;

			int nd = max(T[nx][ny], d[x][y] + 1);
			if (nd < d[nx][ny]) {
				d[nx][ny] = nd;
				q.push({-d[nx][ny], nx, ny});
			}
		}
	}

	int ans = 0;
	rep(i, 1, n) {
		rep(j, 1, m) {
			ans = max(ans, d[i][j]);
		}
	}
	cout << ans;
}

E

并查集 倒序

水位不断上升，每秒会淹没一些城市。城市构成一个图。每次上涨之后，问当前图中未被淹没的点构成的子图，大小不小于的连通块个数。

断边不好做，考虑倒着来，维护加边，加边用并查集维护很简单。现在问题就是还需要维护大小不小于的连通块个数。这考虑在合并时更新连通块个数，先把要合并的两个集合的贡献删去，再把合并后的连通块的贡献加入。

这里在实现上还有坑点，就是我们每次考虑一个点，去把它和相邻点连接起来，由于我们在合并时更新连通块个数，需要我们对相邻点的连通块情况，以及对答案的贡献，也进行初始化。这在实现上最好是，先把这一秒露出水面的点取出来，都进行初始化后，再连边，合并。

int f[N], sz[N], h[N], H[N];
int n, m, x, d, ans;
int find(int x) {
    if (f[x] == x)return x;
    return f[x] = find(f[x]);
}
 
void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) {
        if (sz[x] >= d) {
            ans--;
        }
        if (sz[y] >= d) {
            ans--;
        }
        f[x] = y;
        sz[y] += sz[x];
        if (sz[y] >= d) {
            ans++;
        }
    }
}
void solve() {
    cin >> n >> m >> x >> d;
    vector<pii>a;
    rep(i, 1, n) {
        cin >> h[i];
        a.push_back({h[i], i});
        f[i] = i;
        sz[i] = 1;
    }
    sort(a.begin(), a.end());
 
    vvi g(n + 1);
 
    rep(i, 1, m) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    rep(i, 1, x) {
        cin >> H[i];
    }
 
 
    vi res(x + 1);
 
    for (int i = x; i >= 1; i--) {
        vector<pii> b;
        while (a.size() && a.back().first > H[i]) {
            auto [_, u] = a.back();
            if (sz[u] >= d)ans++;
            b.push_back(a.back());
            a.pop_back();
        }
        while (b.size()) {
            auto [_, u] = b.back();
            b.pop_back();
            for (int v : g[u]) {
                if (h[v] > H[i]) {
                    merge(u, v);
                }
            }
        }
        res[i] = ans;
    }
    rep(i, 1, x) {
        cout << res[i] << '\n';
    }
}

G

模拟

地面上一些裂缝，给出每一秒走的距离，脚掌有一定长度，问猜到的裂缝个数？

先计算出所有裂缝位置，然后模拟走路过程中，每一秒的脚掌位置，检查脚掌对应的区间内是否有裂缝点，由于距离可能很大，考虑二分。

void solve() {
    int n, m, l;
    cin >> n >> m >> l;
 
    int pre = 0;
    vector<int>p;
    rep(i, 1, n) {
        int x;
        cin >> x;
        pre += x;
        p.push_back(pre);
    }
 
    pre = 0;
    auto check = [&](int l, int r)->bool{
        int p1 = upper_bound(p.begin(), p.end(), l) - p.begin();
        int p2 = lower_bound(p.begin(), p.end(), r) - p.begin() - 1;
        return p1 <= p2;
    };
    bool ans = 0;
    ans |= check(0, l);
    rep(i, 1, m) {
        int x;
        cin >> x;
        pre += x;
        ans |= check(pre, pre + l);
    }
    if (ans)cout << "YES";
    else cout << "NO";
}

H

可行性dp

每一步要么减法，要么异或，问操作完的最大值。注意到值域和操作次数并不大，可以的可行性，表示这个值能否得到，最后从大到小扫描，找到第一个

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];
    }
 
    vi f(3000);
    f[0] = 1;
    rep(i, 1, n) {
        vi g(3000);
        rep(j, 0, 2048) {
            int nxt = max(0ll, j - a[i]);
            g[nxt] |= f[j];
            nxt = j ^ b[i];
            g[nxt] |= f[j];
        }
        swap(f, g);
    }
 
    rep1(i, 2500, 0) {
        if (f[i]) {
            cout << i;
            return;
        }
    }
}

I

构造

这其实是个CF原。构造一个排列，使得任意长度为3的子数组，至少存在两个数不互质。原题是，不符合要求的子数组个数不超过6个，更宽松一点。

先考虑这个原

任意长度为3的子数组，所以可以考虑每三个数，安排两个不互质的，也就是这样，那么这需要我们找到一个长度至少的序列，相邻元素不互质的对数不超过6个。

说到互质，都先考虑最简单的不互质的东西：偶数，显然可以把所有偶数都加入这个序列，这就有了，那么类似地，还可以把所有的倍数也加入这个序列（注意前面枚举偶数已经用过的不能再用，我们要构造排列），这加起来肯定有了，唯一的不互质的地方是交界处。剩下就是把这个序列顺序填入所有里的位置，的位置则随便填还没用过的数字。

这样只有一个位置不合法。

然后这题加强了，要求不存在位置不合法，还是可以沿用这个思路，现在唯一的问题是交界处不合法，那么要是在中间再插入别的数，让都和这个数不互质不就可以了？那最容易的得到的这样的数就是，于是构造填入的序列时，先枚举的倍数，再枚举的倍数，再枚举的倍数，注意一个数只能用一次，只有第一次枚举到时才加入。

对于这一点，要么开个数组记录每个元素是否被用过，更好的实现是，先枚举所有模余的，再枚举模余的，再枚举模余的，填到b位置。剩下的就是模余的，填到位置

void solve() {
    int n;
    cin >> n;
    if(n==3||n==5){
        cout<<-1;
        return;
    }
    // 模拟 Python 的 f = lambda x: list(range(x, n + 1, 6))
    auto f = [&](int x) {
        vector<int> res;
        for (int i = x; i <= n; i += 6) res.push_back(i);
        return res;
    };
 
    vector<int> a = f(1);
    vector<int> a5 = f(5);
    a.insert(a.end(), a5.begin(), a5.end()); // a = f(1) + f(5)
 
    vector<int> b = f(3);
    vector<int> b0 = f(6); 
    vector<int> b2 = f(2);
    vector<int> b4 = f(4);
    b.insert(b.end(), b0.begin(), b0.end());
    b.insert(b.end(), b2.begin(), b2.end());
    b.insert(b.end(), b4.begin(), b4.end());
 
    vector<int> ans;
    // 模拟 while len(b) >= 2: ans += [a.pop(), b.pop(), b.pop()]
    while (b.size() >= 2 && !a.empty()) {
        ans.push_back(a.back()); a.pop_back();
        ans.push_back(b.back()); b.pop_back();
        ans.push_back(b.back()); b.pop_back();
    }
 
    // 打印结果：ans + 剩下的 a + 剩下的 b
    for (int x : ans) cout << x << " ";
    for (int x : a) cout << x << " ";
    for (int x : b) cout << x << " ";
    cout << endl;
}

J

拆贡献 循环卷积

代价分为两部分，一个是循环移位，一个是凯撒加密，首先最优肯定是先循环移位，再对每个位置分别凯撒加密，不存在这两种交替进行还更优秀的策略。

考虑枚举移位次数，假设，那么剩下的代价就是

剩下就是凯撒加密的开销，变成的代价是对这种带取模的问题，我们计数时不好处理，一般都转化为，对于部分很好计数，对于后面的部分，再转化成的计数

也就是

最后这个的计算，是经典卷积问题。卷积就是可以对有的贡献，所以想用卷积来处理这个判断大小的问题，可以让这个大于号成立时，都是就好了。

，这里的取值都有种，最朴素的想法是，每次枚举这种组合，分别卷积。更快的做法是，枚举，然后一次性考虑所有的，这样只用卷积次

于是枚举，然后构建一个串中,每个字符是否等于的序列，再构建一个串中，每个字符是否等于小于的01序列，然后卷积这两个序列。我们想要的是一次卷积，求出所有位移量的答案，那么也就是需要让

，对产生贡献。

注意这里模，如果，则无事发生，如果，则意味着

普通的卷积只能满足对的位置产生贡献，而不是，想实现这一点，需要特殊的卷积手段，经典手段是把序列反转，也就是，那么在这个新的序列里，下标对应原序列的

那么卷积后，

的位置

如果，则对应下标为。

如果，则对应下标为

所以位移量的答案，分别在两个位置，这就是所谓的循环卷积，下标可以取模，折回来，所以每个答案对应的是两个位置。

这样，我们可以计算对于每个，时，每个位移量的答案，累加到每个中，最后根据上面的式子计算，取最小值就行，整体复杂度，是大于的最小的，这是卷积在实现上所规定的，必须拓展值域到

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
 
    int n;
    string s, t;
    cin >> n >> s >> t;
 
    int L = 1;
    while (L < 2 * n) {
        L <<= 1;
    }
    Poly::init(L);
 
    int sum = 0;
    for (int i = 0; i <= n; i++) {
        sum += (t[i] - 'a') - (s[i] - 'a');
    }
 
    vector<int>cnt(n + 1);
    for (int c = 0; c < 26; c++) {
        vector<int>a(n + 1), b(n + 1);
        for (int i = 1; i <= n; i++) {
            if (s[i - 1] - 'a' == c) {
                a[n - i + 1] = 1;
            }
            if (t[i - 1] - 'a' < c) {
                b[i] = 1;
            }
        }
        vector<int>res = Poly::multiply(a, b, L);
        for (int i = 1; i <= n; i++) {
            cnt[i] += res[i];
            if (i + n < L)cnt[i] += res[i + n];
        }
    }
 
    long long ans = 1e18;
    for (int i = 1; i <= n; i++) {
        ans = min(ans, sum + i - 1 + 26ll * cnt[i]);
    }
    cout << ans;
 
 
    return 0;
}

L

模拟

void solve() {
	int m, n, z;
	cin >> m >> n >> z;

	z %= (m + n);
	if (z && z <= m)cout << "0";
	else cout << "1";
}

K

矩阵快速幂优化dp

一个人每次p概率加a，1-p概率加b。另一个人p概率加c，1-p概率加d。问达到z的最后一次操作，是先手的概率。

先考虑朴素，状态记录当前最后一次操作是谁，表示元素和，最后一次操作是先手还是后手进行的，的概率。

转移显然，由于都不超过50，加上很大，考虑矩阵快速幂优化,转移可以写成一个不超过的矩阵，复杂度