Processing math: 0%

YZOJ P4611 区间加多项式(YJC 的数组/多项式?)

YZOJ P4611 区间加多项式(YJC 的数组/多项式?)

时间限制:4444MS      内存限制:1048576KB

难度:7.2

  • 题目描述

由于本题之前被*了,所以现在数据就是随便造的,可能会因为太水又被艹     //给出题人留点面子吧qwq

YJC 在 AK 了一场校内之后,对其中的一题(P2036 「A Simple Data Structure Problem II 」)产生了兴趣。

于是他出了一题加强版(P4316 「ASDSP VII —— YJC树」),然而,他还是觉得这个加强版太简单啦!!!

所以,这次,他不仅把 K \leq 5 往后面加了三个零变成了 K \leq 5000 ,还对询问做了一点修改!

喜欢差分的 YJC 有一个长度为 N 的数组 c,初始值都为 0,下标编号为 1, 2, \cdots, N

现在 YJC 忙着 AK CSP-S2019,没空验证数据的正确性,所以只能把这个重任交给了你 —— ******,希望你能写一个程序帮他实现以下的几个操作:

opt=1,给定 L, R,输出 \sum\limits_{i=L}^R c_i 的值对 998244353 取模后的结果;

opt=0,给定 L, R 以及 K 次多项式 f(x)=\sum\limits_{k=0}^K a_kx^k,对 c_L, c_{L+1}, \cdots, c_R 分别加上 f(1), f(2), \cdots, f(R-L+1) 的值。

  • 输入格式

第一行两个正整数 N, Q ,分别表示区间范围 [1, N] 及询问数 Q

接下来,每行(除了每个 opt=0 操作的下一行)的第一个数 opt 表示操作类型。

opt=0,则接下来有两个正整数 L, R 表示操作的区间 [L, R]。紧接着下一行的第一个整数 K 表示多项式的最高次数为 K ,接下来 K+1 个整数 a_0, a_1, \cdots, a_K 分别表示多项式 f(x)= \displaystyle\sum\limits_{k=0}^K a_kx^k 的系数;

opt=1,则接下来有两个正整数 L, R 表示询问的区间 [L, R]

因为 YJC 忙着 AK CSP-S2019(之前说过了),所以他一不小心把数据给加密了。

记 …

YZOJ P4578 [CSP-S 2019 四校联训 Round 1]树上排列

YZOJ P4578 [CSP-S 2019 四校联训 Round 1]树上排列

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

难度:7.0

  • 题目描述

给定一颗 n 个点的树。每个点都一个正整数点权 A_i,你需要支持以下两种操作:

1、询问点 x 和点 y 之间的路径上的所有点(包括点 x 和点 y )的点权是否构成一个从 1 开始的排列。

2、将 A_x 修改为 y

  • 输入格式

第一行一个正整数 T 表示数据组数。

接下来一行输入两个正整数 n,q 表示数的点数和询问个数。

接下来一行 n 个正整数,第 i 个正整数表示 A_i 的初值。

接下来 n-1 行每行两个正整数 u,v 表示树上的一条边 (u,v)

接下来 n 行每行三个正整数 tp,x,y 表示一个操作,其中 tp 表示操作种类。

  • 输出格式

对于每一个操作 1 如果符合条件,输出 Yes ,否则输出 No 。…

YZOJ P4444 [APIO2019]路灯

YZOJ P4444 [APIO2019]路灯

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

难度:7.0

  • 题目描述

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

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

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

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

toggle i:切换第 i 个路灯的状态。具体地说,若路灯原来亮起,则现在将熄灭;若路灯原来熄灭,则现在将亮起。

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

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

  • 输入格式

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

第二行包含一个字符串 s 表示路灯的初始状态 (\left|s\right| = n)s_i1 表示第 i 个路灯初始时亮起; s_i0 表示第 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 300000m \leq 100000t_i,a_i,b_i \leq 10^9

 

 

 …

YZOJ P3069 字符串匹配

YZOJ P3069 字符串匹配

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

难度:7.0

  • 题目描述

给出两个串 AB,串中仅包含小写字母和字符 *,其中 * 能匹配任意的小写字母(也可以匹配 *)。

请你求出如果以 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 个整数 xyr ,分别表示圆形的圆心坐标以及圆的半径。

  • 输出格式

假设 Alice 最后获胜,则输出一行 “Alice”(不包括引号),否则输出 “Bob” 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

100\% 的数据满足 T \leq 100n \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 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万好了。

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

  • 输入格式

第一行 n1 \leq n \leq 1000000

接下来 n 行,每行 l_i,r_i1 \leq l_i \leq r_i \leq 1000000

  • 输出格式

若不存在合法的方案,仅输出一行 -1

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

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 3711

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

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

YZOJ P3706 [APIO2018]新家

YZOJ P3706 [APIO2018]新家

时间限制:5000MS      内存限制:1048576KB

难度:7.0

  • 题目描述

五福街是一条笔直的道路,这条道路可以看成一个数轴,街上每个建筑物的坐标都可以用一个整数来表示。

小明是一位时光旅行者,他知道在这条街上,在过去现在和未来共有 n 个商店出现。第 i 个商店可 以使用四个整数 x_i , t_i , a_i , b_i 描述,它们分别表示:商店的坐标、商店的类型、商店开业的年份、商店关闭的年份。

小明希望通过时光旅行,选择一个合适的时间,住在五福街上的某个地方。他给出了一份他可能选择的列表,上面包括了 q 个询问,每个询问用二元组 (坐标,时间)表示。第 i 对二元组用两个整数 l_i , y_i 描述,分别表示选择的地点 l_i 和年份 y_i

现在,他想计算出在这些时间和地点居住的生活质量。他定义居住的不方便指数为:在居住的年份,离 居住点最远的商店类型到居住点的距离。类型 t 的商店到居住点的距离定义为:在指定的年份,类型 t 的所有营业的商店中,到居住点距离最近的一家到居住点的距离。我们说编号为 i 的商店在第 y 年在营业当且仅当 a_i \leq y \leq b_i 。注意,在某些年份中,可能在五福街上并非所有 k 种类型的商店都有至少一家在营业。在这种情况下,不方便指数定义为 -1

你的任务是帮助小明求出每对(坐标,时间)二元组居住的不方便指数。

  • 输入格式

第一行包含三个整数 n,kq ,分别表示商店的数量、商店类型的数量和(坐标,时间)二元组的数量(1 \le n, q \le 3 \times 10^5 , 1 \le k \le n

接下来 n 行,每行包含四个整数 x_i , t_i , a_ib_i 用于描述一家商店,意义如题面所述 (1 \le x_i , a_i , b_i \le 10^8 , 1 \le t_i \le k, a_i \le b_i)。

接下来 q 行,每行包含两个整数 l_iy_i ,表示一组(坐标,时间)查询 (1 \le l_i , y_i \leq 10^8 )。

  • 输出格式

输出一行,包含 q 个整数,依次表示对于 q 组(坐标,时间)询问求出的结果。…