题解

题目 给出一个长度为 $n$ 的 $k$ 进制数，可能含有前导 $0$，你需要实现以下 $4$ 种操作，共 $m$ 次。 1 x y：将第 $x$ 位上的数改为 $y$； 2 l r：将第 $l$ 位到第 $r$ 位升序排列； 3 l r：将第 $l$ 位到第 $r$ 位降序排列； 4 l r：求第 $l$ 位到第 $r$ 位所组成的 $k$ 进制数转为 $10$ 进制数的结果，结果对 $998 …

Jayun 发布于 2022-10-18 16:11:14

00

题目 城市中有一条长度为 $n$ 的道路，每隔 $1$ 的长度有一个公交车站，车站的编号从 $0$ 到 $n$，市政府在 $0$ 号车站的位置。 城市中同时有 $n$ 趟公交线路，第 $i$ 条公交线路的起点站为 $i-1$。公交车站 $i(0\leq i\leq n)$ 有两个属性 $c_i$ 和 $v_i$，代表从这个公交车站出发的公交车的性质。 $c_i$ 代表这个从 $i$ 出发的公交车， …

Jayun 发布于 2022-10-17 21:14:51

00

题目 有 $n$ 个正整数 $a_n$。现在有一个下标集合 $S$，初始时为空，你需要依次实现 $q$ 次操作： 每次操作会给定一个整数 $x(1\leq x\leq n)$，如果当前 $x$ 不在下标集合 $S$ 中，则在 $S$ 中加入 $x$，否则删去 $x$。 每次操作过后，你都需要计算下面这个式子的值： $$\sum_{i<j,i,j\in S}[\gcd(a_i,a_j)=1]$ …

Jayun 发布于 2022-10-17 15:08:31

00

题目大意 给定 $n$ 个数，求出选 $k$ 数的异或和之和，模 $998244353$。 分析 对于每一二进制位，肯定只有异或值为 $1$ 才有贡献，那么就枚举这一位上取 $1$ 的个数为 $x$，那么取 $0$ 的个数对应地就为 $k-x$，这一位的贡献就为 $\binom{\text{count}(1)}{x}\cdot\binom{\text{count}(0)}{k-x}$。 代码 co …

Jayun 发布于 2022-10-17 14:48:05

00

题目大意 删除最少数，使得数组最大子段和小于 $S$ 。 分析 $S<0$ 显然只统计小于 $S$ 的数的个数。 最大子段和是可以根据 $f_i=\max (f_{i-1},0)+1$ 达到 $\mathcal{O}(n)$ 扫的。尽量避免带修等问题，就考虑一边扫一边微调：当扫到正数时，当前最大子段和是否大于等于 $S$ ，是则删除若干最大值；当扫到负数时，需要若干个最小 …

Jayun 发布于 2022-10-07 07:26:41

00