P1024 一元三次方程求解
[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)...
P1886 滑动窗口
滑动窗口 /【模板】单调队列 题目描述 有一个长为 $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 编号
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 并查集
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 筛法
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]; ...