T1

简要题意 \(n\le 10^3 , \sum K_i\le3\times10^5\) 思路 首先容易想到一个暴力DP，\(f_{l,r,x}\) 表示区间中最大值为 \(x\) 的最大值 稍微想亿下可以发现如果这个位置选的不是区间最大值的话，答案一定不优 所以我们可以直接 \(f_{l,r}\) ......

题意 给定 \(n\) 个数，你需要把每个数分成两组，使得： 没有组为空。 两个组内所有数的按位或相等。 Sol 不难发现，当某一位上全是 \(1\) 的数被分在了一个集合内时，方案一定不合法。 考虑容斥计算这个东西。 对于每一位，建一个点。考虑把所有数抽象成边，对于当前 \(a_i\) 如果第 \ ......

简要题意 给定一棵有根树，操作分别为：将某个点到根路径上全部点颜色改为 \(c\)；询问某个点到根路径上不同颜色数。 \(n\le10^5\) 思路 考虑对修改根号重构，那对于某次询问的路径，实际上就是前面有至多 \(\sqrt m\) 个相同颜色段，再拼上后面一段树上的颜色，也就是和修改中点的最深 ......

想不到一点/ll 想不到一点/ll 首先考虑全是 1 的情况，不难想出一个贪心策略，每次选择深度最深的需要被覆盖的节点，然后倍增找到他的 $d$ 级祖先，记 $d$ 级祖先为 $p$，操作一次 $p$。容易发现这样一定不劣，因为这个节点一定要被干掉，操作 $p$ 的后代显然不如操作 $p$ 能处理的 ......

题意 给一棵树，带点权（可为负），单点修改，求直径，求过某一点的直径 \((n<=100000)\) 思路 发现强制过某一点，可以转化为单点改成正无穷，求直径 于是就只用考虑单点修改求直径 考虑点分树，在每个重心维护到他的最长链，和不同子树中的次长链，全部答案取个max即可（但是被卡常） code ......

首先枚举宝藏所在的点，设为根 \(rt\)，考虑如果在某个时刻访问了若干个点，但是没有确定宝藏位置，那么满足什么条件。首先求出这些点的 LCA，设为点 \(p\)，\(p\) 不可以是 \(rt\)。我们发现这时候我们已经确认了宝藏到 \(p\) 的距离，而且知道它不属于 p 的哪些子树（所有存在被 ......

题意 给定一个矩阵，你需要支持： 循环左移 循环右移 循环下移 循环上移 按行置换求逆 按列置换求逆 Sol 前 \(4\) 个操作是 \(trivial\) 的。 如何处理后两个操作？ 考虑设一个三元组：\((x, y, A_{xy})\)。 每次操作，对于每一个元素都能确定操作后另外某个元素。 ......

给定一个图，求 \(s\) 到 \(t\) 的最短路，其中路径的长度是其长度前 \(k\) 大边的长度和。\(n, k \le 1000, m\le 2000\)。 做法 枚举被算入的最小边权 \(w\)，所有小于 \(w\) 的边权都可以视为 \(0\)，而我们需要确保大于等于 \(w\) 的边至 ......

第1题 二进制整除 查看测评数据信息 交换二进制数相邻两个位置的数字，需要花费1元的代价。 读入整数n以及n位二进制数(也许有前导0)，你需要依次回答n个独立的问题，第i个问题(1<=i<=n)是这样的： 假如要使得读入的二进制数是2^i的倍数，至少需要花费多少元的代价？如果不可能，则输出-1。 注 ......

LANDSAT/LC08/C02/T1_L2 metadata dictory 元数据字典2023年12月20日星期三 by xrkvar image=ee.ImageCollection('LANDSAT/LC08/C02/T1_L2').first();print("image",image); ......

第1题 询问"好数" 查看测评数据信息 如果整数a = b^2 或者 a = b^3，其中正整数b>=1， 那么a就是"好数"。 即：如果a是平方数或者立方数，那么a就是"好数"。 现在有n个询问，第i个询问给出一个整数x[i]，表示询问1至x[i]范围内有多少个"好数"。 输入格式 第一行，一个整 ......

\(n=2^{2024}\) 时最优方案为 \(2,2,\cdots ,4\) 此时 \(\lambda_0=\frac{1}{1012}\) 则 \(\lambda_{\min}\geq \lambda_0\)。对于 \(\lambda =\frac{1}{1012}\) 构造，令 \(n=\pr ......

把原题做法 GF 的系数进行 OEIS，发现那个三角形就是 Catalan 数的 GF 复合上一个 \(xy(1-x)\) 的形式。 更为奇妙的是，OEIS 下面竟然给出了一个通项公式，\(T(n,k)=(-1)^{n-k}{k\choose n-k}C_k\)，其中 \(C\) 是 Catalan ......

你有一个二进制串长度为N，串内包含0 和1 两个数字。现在用一种特殊的算法对该串进 行加密，加密方式是给定一个整数K 满足1 ≤ K ≤ N。对于该串内每个长度为K 的区间，计 算出该区间内数字的和，放进一个新序列里。新序列一共有N −K + 1 项，第i 项代表原序列 中第i 项到第i + K − ......

容易想到将询问离线下来，按 \(v\) 从大到小排序，这样后面的修改一定不会对前面的修改造成影响。然后可以用并查集把已修改过的点缩起来。注意到 \(m\) 会到 \(2\times 10^7\)，应该使用基数排序，复杂度为 \(\mathcal O(\frac{m \max{v_i}}{base} ......

T1 KAMEN 只能说一言难尽。 60pt暴力模拟每一个石头往下掉的情况。 在这里，我并没有打暴力，而是用set存储了每一列的X和O的石子分布情况。当前节点的位置在(x, y)，寻找x列中比y大的第一个位置在ny(这里可以用upper_bound)，那么石子在这一列能往下掉到的位置就是（x, ny ......

CSP-S 2023 T1 题解 很简单，我们只需要暴力枚举五位密码，每次判断拨一个齿轮和两个齿轮能达到的状态数，如果等于 \(n\)，答案 \(+1\)。时间复杂度 \(O(10^5 \times 5n)\)。 code #include <iostream> #include <algorith ......

https://sch-exam-z.oxcoder.com.cn/#/confirm?identifyNumber=150302198409170514&examNumber=15904898073&eid=51368&type=3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ......

洛谷传送门 LOJ 传送门 考虑把边按到达时间排序，然后从前往后扫并做一个 dp。 设 \(f_u\) 表示 \(1\) 到达 \(u\) 的最晚出发时间。那么对于一条边 \((u, v, a, b)\)： 若 \(u = 1\)，则 \(f_v = \max(f_v, x)\)； 否则 \(f_v ......

今年的 \(CSP−J\) 对本蒟蒻来说有点难度。。。 A [CSP-J 2023] 小苹果 题目描述 小 Y 的桌子上放着 \(n\) 个苹果从左到右排成一列，编号为从 \(1\) 到 \(n\)。 小苞是小 Y 的好朋友，每天她都会从中拿走一些苹果。 每天在拿的时候，小苞都是从左侧第 \(1\) ......

生成树 (tree) 题目描述 给定一棵 \(n\) 个节点的树。 定义这棵树的生成完全图为一个 \(n\) 个节点的完全图，图中两点 \(u,v\) 的边权为这两点在树上简单路径上的边权和。 请你求出这张完全图的最小生成树和最大生成树，分别输出两种生成树的边权之和。 输入格式 第一行输入一个正整数 ......

题意 给定长度为 \(n\) 的序列 \(S\)。 \(A\)，\(B\) 两人轮流取连续 \(k\) 个数，保证 \(n \equiv 1\pmod k\)。 \(A\) 使最终数字更小，\(B\) 使最终数字更大。 问取到数的和。 Sol 直接考虑每次选哪些数，怎么选显然是不好做的。 不难发现 ......

感觉难度还好？ A - Intercity Travelling 点击查看代码 #include<bits/stdc++.h> #define int long long using namespace std; const int inf=1e18,mod=998244353,i2=(mod+1) ......

雷老师的正偏态分布 题意：给出一个长度为 \(n\) 的 \(a\) 数组，其中 \(1 \le a_i \le V , 1 \le i \le n\) 。统计其中的满足平均数严格小于中位数且大小为奇数的子集数量，\(n \le 100 , V \le 800\)，时限 \(4\) s 。 输入： ......

给定正整数 \(n\) ，计算 \(n\) 个元素的集合 \(\{1,2,3,...,n\}\)，所有非空子集和的乘 积取模 \(998244353\) 后的结果 \(n \leq 200\) 我的第一思路是考虑能不能通过 \(i-1\) 个元素的情况推出 \(i\) 个元素的情况，然后寄掉了，遂看 ......

#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef long long LL; const int N = 2505; vector<int> G ......

原题 题意 有一块 \(n\times m\) \((1\le n,m\le 14)\) 的蛋糕，每个位置上有一个权值 \(a_{i,j}\) \((1\le a_{i,j}\le 1000)\)，现在你要把它切开。每次你可以平行与某一边界把蛋糕切开，所以共有 \(n-1\) 个可以竖着切的位置，以 ......

[洛谷传送门](https://www.luogu.com.cn/problem/P9520 "洛谷传送门") [LOJ 传送门](https://loj.ac/p/3685 "LOJ 传送门") 观察可得，若存在合法解，则一定存在一种解，使得每个人都不停顿地从起点走到终点。 因为如果一个人走到一半 ......

图中不存在横插边，$u \rightsquigarrow v$ 可拆成 $u \rightsquigarrow \operatorname{lca}(u, v) \rightsquigarrow v$ 计算。 对 $u \rightsquigarrow \operatorname{lca}(u, v ......

题目链接 背包 首先想到背包，$f_{i,j}$ 为前 $i$ 个数和为 $j$ 的方案数，但时间复杂度为 $O(n\cdot 20000000)$，会炸。 如果背包跑的时候只跑到当前的 $sum$，就能得到常数的优化，但仍然不足以通过。 插板法 先来考虑一个更简单的问题，每个 $a_i$ 只有下界 ......