snowflak3的小博客

[NOIP2001 提高组] 一元三次方程求解 题目描述 有形如：$a x^3 + b x^2 + c x + d = 0$  这样的一个一元三次方程。给出该方程中各项的系数（$a,b,c,d$ 均为实数），并约定该方程存在三个不同实根（根的范围在 $-100$ 至 $100$ 之间），且根与根之差的绝对值 $\ge 1$。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 $2$ 位。 提示：记方程 $f(x) = 0$，若存在 $2$ 个数 $x_1$ 和 $x_2$，且 $x_1 < x_2$，$f(x_1) \times f(x_2) < 0$，则在 $(x_1, x_2)$ 之间一定有一个根。 输入格式 一行，$4$ 个实数 $a, b, c, d$。 输出格式 一行，$3$ 个实根，从小到大输出，并精确到小数点后 $2$ 位。 样例 #1 样例输入 #1 11 -5 -4 20 样例输出 #1 1-2.00 2.00 5.00 提示 【题目来源】 NOIP 2001 提高组第一题 题解 注意到题目 提示：记方程 $f(x)...

滑动窗口 /【模板】单调队列 题目描述 有一个长为 $n$ 的序列 $a$，以及一个大小为 $k$ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。 例如，对于序列 $[1,3,-1,-3,5,3,6,7]$ 以及 $k = 3$，有如下过程： 输入格式 输入一共有两行，第一行有两个正整数 $n,k$。 第二行 $n$ 个整数，表示序列 $a$ 输出格式 输出共两行，第一行为每次窗口滑动的最小值 第二行为每次窗口滑动的最大值 样例 #1 样例输入 #1 128 31 3 -1 -3 5 3 6 7 样例输出 #1 12-1 -3 -3 -3 3 33 3 5 5 6 7 提示 【数据范围】 对于 $50%$ 的数据，$1 \le n \le 10^5$； 对于 $100%$ 的数据，$1\le k \le n \le 10^6$，$a_i \in...

P1866 编号 题目描述 太郎有 $N$ 只兔子，现在为了方便识别它们，太郎要给他们编号。兔子们向太郎表达了它们对号码的喜好，每个兔子 $i$ 想要一个整数，介于 $1$ 和 $M_i$ 之间（可以为 $1$ 或 $M_i$）。当然，每个兔子的编号是不同的。现在太郎想知道一共有多少种编号的方法。 你只用输出答案对 $10^9+7$ 取余的结果即可。如果这是不可能的，就输出 $0$。 输入格式 第一行是一个整数 $N$。 第二行 $N$ 个整数 $M_i$。 输出格式 一个整数，表示方案总数。 样例 #1 样例输入 #1 1225 8 样例输出 #1 135 提示 数据范围及约定 对于全部数据，$1 \le N \le 50$，$1\le M_i\le 1000$。 题解 分析 排列组合，可以推出结果 每个兔子拿到的数字都不能相同，说明第一个兔子如果选择了1，第二个就不能选1了，我们可以从小到大排列 这组数据就为3 5 8 我们拿取他们的数字，于是就有 $C_{3}^{1}C_{5-1}^{1}C_{8-2}^{1}=C_{3}^{1}C_{4}^{1}C_{6}^{1}...

P3367 【模板】并查集 题目描述 如题，现在有一个并查集，你需要完成合并和查询操作。 输入格式 第一行包含两个整数 $N,M$ ,表示共有 $N$ 个元素和 $M$ 个操作。 接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$ 。 当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。 当 $Z_i=2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出 Y ；否则输出 N 。 输出格式 对于每一个 $Z_i=2$ 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。 样例 #1 样例输入 #1 123456784 72 1 21 1 22 1 21 3 42 1 41 2 32 1 4 样例输出 #1 1234NYNY 提示 对于 $30%$ 的数据，$N \le 10$，$M \le 20$。 对于 $70%$ 的数据，$N \le 100$，$M \le 10^3$。 对于 $100%$ 的数据，$1\le N \le 10^4$，$1\le M \le 2\times 10^5$，$1 \le X_i,...

P1217 回文质数 做题过程 质数(素数判断)回文，按照提示可以先找出 $[a,b] (5 \le a < b \le 100,000,000)$范围内的回文数，再进行质素判断。 先学习多个素数判断 朴素素数筛法 1234567public static boolean isPrime(int num) { if (num <= 1) return false; for (int i = 2; i * i <= num; i++) { if (num % i == 0) return false; } return true;} 欧拉筛 从2开始4 6 8 10 12 14 16 18 都是2的倍数,且都不是素数,我们就可以直接标记为不是素数 1234567891011121314public static boolean[] eulerSieve(int n) { boolean[] isPrime = new boolean[n + 1]; ...