分类： 算法

YZOJ P4444 [APIO2019]路灯

YZOJ P4444 [APIO2019]路灯

时间限制：5000MS      内存限制：524288KB

难度：\(7.0\)

  • 题目描述

一辆自动驾驶的士正在 \(Innopolis\) 的街道上行驶。该街道上有 \(n+1\) 个停车站点，它们将街道划分成了 \(n\) 条路段。每一路段都拥有一个路灯。当第 \(i\) 个路灯亮起，它将照亮连接第 \(i\) 与第 \(i+1\)个站点的路段。否则这条路段将是黑暗的。

出于安全性的考虑，自动驾驶的士只能行驶在被照亮的路段上。换言之，的士能从站点 \(a\) 出发到达站点 \(b\) \((a<b)\) 的条件是：连接站点 \(a\) 与 \(a+1\)，\(a+1\) 与 \(a+2, \cdots ,b-1\) 与 \(b\) 的路段都被照亮。

在经过一些意外故障或修理之后，街道上的路灯可能是亮起的，也可能是熄灭的。

现在给定 \(0\) 时刻时，街道上路灯的初始状态。之后 \(1,2,\cdots,q\) 时刻，每时刻会发生下列两种事件之一：

\(toggle i\)：切换第 \(i\) 个路灯的状态。具体地说，若路灯原来亮起，则现在将熄灭；若路灯原来熄灭，则现在将亮起。

\(query a b\)：自动驾驶的士部门的负责人想知道，从 \(0\) 时刻起到当前时刻，有多少个时刻满足：自动驾驶的士能够从站点 \(a\) 出发到达站点 \(b\) 。

请你帮助自动驾驶的士部门的负责人回答他们的问题。

  • 输入格式

第一行包含两个整数 \(n\) 和 \(q\) \((1 \leq n,q \leq 300000)\) —- 表示路灯的数量与时刻数。

第二行包含一个字符串 \(s\) 表示路灯的初始状态 \((\left|s\right| = n)\)， \(s_i\) 为 \(1\) 表示第 \(i\) 个路灯初始时亮起； \(s_i\) 为 \(0\) 表示第 \(i\) 个路灯初始时熄灭。

接下来 \(q\) 行每行描述一个时刻的事件。第 \(i\) 行描述时刻 \(i\) 所发生的事件。

\(toggle i\) \((1 \leq i \leq n)\)：该时刻切换了第 \(i\) 个路灯的状态。

\(query a b\) \((1 \leq a < b \leq n+1)\)：计算从 \(0\) 时刻起到该时刻，共有多少个时刻满足的士能从站点 \(a\) 出发到达站点 \(b\) 。

至少有一个时刻的事件是 \(query\) 。

  • 输出格式

对于每个 \(query\) 的事件，输出一行单个整数，表示该问题的答案。…

YZOJ P2967 收割

YZOJ P2967 收割

时间限制：4000MS      内存限制：524288KB

难度：\(7.0\)

  • 题目描述

兔有 \(n\) 个甘蔗，兔将它们种成一排。

每天早上，第 \(i\) 个甘蔗会长高 \(a_i\) 米，但如果达到 \(b_i\) 米，就不会继续长高，而是维持在 \(b_i\) 米。

兔收割了 \(m\) 次甘蔗，第 \(i\) 次收割在第 \(t_i\) 天的晚上，他收割了 \([l_i, r_i]\) 中的所有甘蔗。收割后，这些甘蔗的高度变为 \(0\) 米，但第二天还会继续按照原来的规则生长。

请你求出兔每天收割了多少甘蔗。

  • 输入格式

第一行 \(n, m\) ；

接下来 \(n\) 行，每一行 \(a_i, b_i\) ；

接下来 \(m\) 行，每一行 \(t_i, l_i, r_i\)，保证输入的 \(t_i\) 严格递增。

  • 输出格式

输出 \(m\) 行表示兔每次收割的甘蔗的高度之和。

  • 样例输入

  • 样例输出

  • 数据规模与约定

存在 \(30\%\) 数据，保证所有甘蔗都不会长到 \(b_i\) 米；

存在 \(30\%\) 数据，保证每次收取的是所有萝卜；

存在 \(60\%\) 数据，\(n \leq 50000\)；

对于所有数据 \(n \leq 300000\) ，\(m \leq 100000\) ，\(t_i,a_i,b_i \leq 10^9\) 。

 

 

 …

YZOJ P3069 字符串匹配

YZOJ P3069 字符串匹配

时间限制：4000MS      内存限制：262144KB

难度：\(7.0\)

  • 题目描述

给出两个串 \(A\) 和 \(B\)，串中仅包含小写字母和字符 *，其中 * 能匹配任意的小写字母（也可以匹配 *）。

请你求出如果以 \(A\) 为模板串，那么有哪些 \(i\) 使得 \(B[i,i+\left|A\right|)\) 可以与  \(A\) 匹配？

  • 输入格式

第一行 \(A\)，第二行 \(B\) 。

  • 输出格式

按照从小到大输出所有 \(i\) 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于所有数据，\(\left|A\right|, \left|B\right| \leq 500000\) 。

 

 

 …

YZOJ P2050 [FJOI2013]圆形游戏

YZOJ P2050 [FJOI2013]圆形游戏

时间限制：8000MS      内存限制：262144KB

难度：\(8.0\)

  • 题目描述

在一个无穷大的桌面上有 \(n\) 个圆形，保证任意两个圆相离或者相含，不存在相切或相交。现在 Alice 和 Bob 在玩一个圆形游戏，以 Alice 为先手，双方以如下步骤轮流游戏：

1，选定一个圆 \(A\)，把 \(A\) 以及所有完全在 \(A\) 内部的圆都删除；

2，如果在自己回合无法找到可删除的圆，则输掉比赛。

假设 Alice 和 Bob 都非常聪明，请问最终谁能够取得胜利？请编程输出最终获胜的人。

  • 输入格式

输入数据的第一行为一个正整数 \(T\)，表示数据组数。

接下来 \(T\) 组数据，对于每组数据，第一行包含 \(1\) 个正整数 \(n\)，表示圆形的个数。

之后 \(n\) 行，每行为 \(3\) 个整数 \(x\)、\(y\) 和 \(r\) ，分别表示圆形的圆心坐标以及圆的半径。

  • 输出格式

假设 Alice 最后获胜，则输出一行 “Alice”（不包括引号），否则输出 “Bob” 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

\(100\%\) 的数据满足 \(T \leq 100\)，\(n \leq m20000\)，\(\left|x\right|, \left|y\right|, r \leq 10^8\) 。

 

 

 …

YZOJ P2966 染色

YZOJ P2966 染色

时间限制：2000MS      内存限制：131072KB

难度：\(7.0\)

  • 题目描述

你有 \(n\) 只猫，每一只猫认识另一些猫。但若 \(a\) 猫认识 \(b\) 猫，\(b\) 猫不一定会认识 \(a\) 猫。

现在，你需要将每一只猫染成红色或绿色。你是否可以通过染色让每一只猫都认识偶数只和自己同色的猫呢？

  • 输入格式

第一行 \(n\)；

接下来 \(n\) 行，每行第一个数 \(d_i\) 表示猫 \(i\) 认识的猫的个数，后面跟着 \(d_i\) 个数表示认识的猫是哪些。

  • 输出格式

达不到要求，输出 Impossible。

否则第一行输出红色猫的个数，第二行输出哪些猫是红色（那么其他猫就是绿色）

可以输出任意方案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(100\%\) 的数据，\(n \leq 2000\) 。

 

 

 …

YZOJ P3942 gss2加强版

YZOJ P3942 gss2加强版

时间限制：2000MS      内存限制：524288KB

难度：\(7.0\)

  • 题目描述

给你 \(n\) 个数，你需要支持一下两种操作。

U x y：将第 \(x\) 个数修改成 \(y\) ；

Q x y：计算从第 \(x\) 个数至第 \(y\) 个数中不同数的和并输出。如对于一段数 \(1,2,3,2,7\)，它的值是 \(13=1+2+3+7\) 。

  • 输入格式

第一行 \(n\) 表示数的个数；

第二行包含这 \(n\) 个数；

第三行 \(m\) 表示操作次数；

接下来 \(m\) 行每行三个数表示题目描述的操作。

  • 输出格式

对于每个 Q 操作返回一个值。

  • 样例输入

  • 样例输出

  • 数据规模与约定

所有的输入均在 int  以内。

\(n \leq 100000 , m \leq 100000\)

 

 

Source： BZOJ 2883…

YZOJ P3451 [SDOI2013]随机数生成器问题

YZOJ P3451 [SDOI2013]随机数生成器问题

时间限制：1000MS      内存限制：262144KB

难度：\(6.0\)

  • 题目描述

有一个随机数生成器，可以生成 \(0\) ~ \(p-1\) 之间的伪随机整数。在生成之前，需要设定一个随机数种子 \(k\) （\(0 \leq k < p\)），则生成器第 \(1\) 次生成的整数为 \(k\)。该随机数生成器有 \(2\) 个参数 \(a, b\)，如果第 \(i\) 次生成的整数为 \(x\)，则第 \(i+1\) 次生成的整数为 \((ax+b) \bmod p\) 。

现给定整数 \(t\) ，我们的问题是，该随机数生成器至少需要生成多少个数，才能生成得到 \(t\)？

对于给定的 \(p,a,b,k,t\) ，请计算要使随机数生成器生成整数 \(t\)，所需生成数的次数的最小值。

  • 输入格式

多组数据。第一行一个整数 \(T\) 表示数据组数，\(T \leq 50\) 。

接下来 \(T\) 行，每行五个整数 \(p,a,b,k,t\) 表示一组数据，其中 \(0 \leq a,b,k,t < p\) 。

  • 输出格式

对于每组数据，将随机数生成器的最小生成次数输出到文件中。

如果该随机数生成器无法生成整数 \(t\)，输出 \(-1\) 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(20\%\) 的数据，\(p \leq 100\) 。

对于另外 \(30\%\) 的数据，\(a=1\) 。

对于另外 \(30\%\) 的数据，\(b=0\) 。

对于 \(100\%\) 的数据，\(p \leq 10^9\) 且 \(p\) 是质数。

 

 …

YZOJ P3056 三角形最大面积

YZOJ P3056 三角形最大面积

时间限制：1000MS      内存限制：262144KB

出题人：chj2001         难度：\(4.5\)

  • 题目描述

给定平面上 \(n\) 个点，定义 \(f(A,B,C)=\frac{1}{2} \left| x_A(y_B-y_C)+x_B(y_C-y_A)+x_C(y_A-y_B) \right|\) 。

每次操作都会将坐标系顺时针旋转 \(\frac{\pi}{9}\) 弧度，直到与原坐标系重合。

计算每次操作前 \(f\) 的最大值，并输出所有最大值的总和。

  • 输入格式

第一行输入一个正整数 \(n\)，表示点的数量；

接下来 \(n\) 行，每行两个整数 \(x_i, y_i\) 表示最开始建立的坐标系下点的坐标。

  • 输出格式

输出所有 \(f\) 最大值的总和。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(100\%\) 的数据，\(3 \leq n \leq 10000, -10000 \leq x_i, y_i \leq 10000\) 。

 

 

 …

YZOJ P2905 [PA2014]Druzyny

YZOJ P2905 [PA2014]Druzyny

时间限制：1000MS      内存限制：131072KB

难度：\(8.0\)

  • 题目描述

在之前的某次校内训练中，zzx 出了一道神奇的题目：给出 \(n\) 个人，要求将所有人分成若干个组，第 \(i\) 个人所在的组的人数必须在 \([l_i, r_i]\) 之间，判断是否存在可行解。

OI组的神犇们决定把这题改造一下：

dick32165401：改成只有编号连续的的一段才可以分一组。

runzhe2000：判定可行解可能会被爆搜水过，最大化分的组数就不那么容易水过了。

E.Space：不仅要最大化组数，还要求出最大化组数的方案数。

ct：数据范围就出100万好了。

于是这题就被这么造好了。

  • 输入格式

第一行 \(n\)，\(1 \leq n \leq 1000000\) 。

接下来 \(n\) 行，每行 \(l_i,r_i\)，\(1 \leq l_i \leq r_i \leq 1000000\) 。

  • 输出格式

若不存在合法的方案，仅输出一行 \(-1\) 。

否则输出一行两个整数，分别表示组数的最大值和组数取最大值的方案数模 \(10^9+7\) 。

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 3711

膜拜上方所有dalao %%%%%%%%%%%%%%%%%%

像我这种菜鸡看到这种神仙题只会爆零QAQ…

YZOJ P3098 [JLOI2016]成绩比较

YZOJ P3098 [JLOI2016]成绩比较

时间限制：100MS      内存限制：131072KB

难度：\(6.0\)

  • 题目描述

G系共有 \(n\) 位同学，\(m\) 门必修课。这 \(n\) 位同学的编号为 \(0\) 到 \(n-1\) 的整数，其中B神的编号为 \(0\) 号。

这 \(m\) 门必修课编号为 \(0\) 到 \(m-1\) 的整数。一位同学在必修课上可以获得的分数是 \(1\) 到 \(U_i\) 中的一个整数。如果在每门课上 A 获得的成绩均小于等于 B 获得的成绩，则称 A 被 B 碾压。

在B神的说法中，G系共有 \(k\) 位同学被他碾压（不包括他自己），而其他 \(n-k-1\) 位同学则没有被他碾压。D神查到了B神每门必修课的排名。这里的排名是指：如果B神某门课的排名为 \(R\)，则表示有且仅有 \(R-1\) 位同学这门课的分数大于B神的分数，有且仅有 \(n-R\) 位同学这门课的分数小于等于B神（不包括他自己）。

我们需要求出全系所有同学每门必修课得分的情况数，使其既能满足B神的说法，也能符合D神查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。

你不需要像D神那么厉害，你只需要计算出情况数模 \(10^9+7\) 的余数就可以了。

  • 输入格式

第一行包含三个正整数 \(n, m, k\)，分别表示G系的同学数量（包括B神），必修课的数量和被B神碾压的同学数量。

第二行包含 \(m\) 个正整数，依次表示每门课的最高分 \(U_i\) 。

第三行包含 \(m\) 个正整数，依次表示B神在每门课上的排名 \(R_i\) 。保证 \(1 \leq R_i \leq n\)。

数据保证至少有 \(1\) 种情况使得B神说的话成立。\(n \leq 100, m \leq 100, U_i \leq 10^9\) 。

  • 输出格式

输出仅包括一行一个整数，表示成绩情况数对 \(10^9+7\) 取模的结果。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(30\%\) 的数据，\(n, m \leq 20\)，\(U_i \leq 100\)；

对于 \(100\%\) 的数据，\(n,m \leq 100\)，\(U_i \leq 10^9\)，\(1 \leq R_i \leq n\)，\(0 \leq k < n\) …