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 P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

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

难度:\(6.5\)

  • 题目描述

给定一个长度为 \(n\) 的正整数序列 \(\{a_i\}\),有 \(m\) 次操作。格式如下:

1 l r x 将区间 \([l,r]\) 中的所有数变为 \(x\)。

2 l r x 查询区间 \([l,r]\) 中数字 \(x\) 的出现次数。

  • 输入格式

第一行两个正整数 \(n,m\),表示序列长度和操作次数。

第二行 \(n\) 个正整数,第 \(i\) 个数为 \(a_i\),表示序列初始值。

接下来 \(m\) 行每行四个正整数,表示操作,含义如题目所示。

  • 输出格式

对于每个询问,输出一行一个正整数表示答案。

  • 样例 1 输入

  • 样例 1 输出

  • 数据规模与约定

对于 \(20\%\) 的数据,\(1 \leq …

YZOJ P4621 [CSP-S 2019 四校联训 Round 1]生日悖论

YZOJ P4621 [CSP-S 2019 四校联训 Round 1]生日悖论

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

难度:\(5.0\)

  • 题目描述

一共有 \(N\) 种数字,所以按照包含数字的集合分类,可能有 \(2^N\) 类不同的集合。每个集合包含一种特定的数字的概率都是 \(\displaystyle\frac{1}{2}\) 。

随机取其中 \(k\) 个集合,请你帮忙算一下其中存在两个集合完全相同的概率。

  • 输入格式

一行两个整数 \(N,k\) 。

  • 输出格式

两个正整数,分别表示概率(最简分数)的分子和分母。分别对 \(10^6+3\) 取模吧。

  • 数据规模与约定

\(1 \leq N \leq 10^{18}\),\(2 \leq k \leq 10^{18}\) 。

 

 

Source: CodeForces 711E ZS and The Birthday Paradox

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

  • 样例输入


Read the rest

YZOJ P4587 斐波那契数列

YZOJ P4587 斐波那契数列

时间限制:1234MS      内存限制:43210KB

难度:\(6.5\)       (既然是自己搬的题还是正常一点吧w)

  • 题目描述

定义模意义下的递推数列 \(f_n=\left\{ {\begin{array}{*{20}{c}} 1&{,n \le 2}\\ {{f_{n – 1}} + {f_{n – 2}}}&{,n > 2} \end{array}} \right.\),其中模数为 \(1000000009\) 。

给定整数 \(c\)(\(0 \leq c < 1000000009\)),求出它最早出现在数列的哪个位置,并输出下标。

若 \(c\) 永远不会出现在此数列的任一位置,则输出 \(-1\) 。

  • 输入格式

多组数据。

第一行一个正整数 \(T\) (\(0 < T \leq 100\)) 表示 \(T\) 组数据。

接下来 \(T\) 行每行一个数表示每组数据的 \(c\) 。

  • 输出格式

对于每组数据,输出一行一个数表示答案。

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 5104…

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\) 的事件,输出一行单个整数,表示该问题的答案。

  • 样例输入


Read the rest

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\) 。

 

 

 …