标签 离线 下的文章
- 首页
- 离线
「Codeforces 1139F」Dish Shopping
题目链接：Codeforces 1139F
有 $m$ 个人居住在一个城市里，在这个城市里总共出售 $n$ 道菜。第 $i$ 道菜的价格为 $p_i$、标准值 $s_i$、美味值 $b_i$。第 $j$ 人的收入为 $inc_j$、首选的美味值 $pref_j$。
第 $j$ 个人会买第 $i$ 道菜当且仅当 $p_i \le inc_j \le s_i$ 且 $\vert b_i - pref_j \vert \le (inc_j - p_i)$。
请求出每个人会买多少道菜。
数据范围：$1 \le n, m \le 10 ^ 5$，$1 \le p_i, s_i, b_i, inc_i, pref_i \le 10 ^ 9$。
「Codeforces 1139E」Maximize Mex
题目链接：Codeforces 1139E
在一所学校中有 $n$ 个学生和 $m$ 个俱乐部。俱乐部从 $1$ 到 $m$ 标号。每个学生拥有一个潜力值 $p_i$，且属于第 $c_i$ 个俱乐部。
刚开始每个学生都恰好属于一个俱乐部，后来学校举办了一次技能测试，这场测试持续了 $d$ 天。每天上午都会有恰好一个学生离开他的俱乐部。一个学生一旦离开就不会再次加入任何一个俱乐部。每天下午，每个俱乐部需要选出一个人，以此组成一个 $m$ 个人的队伍来参加比赛。一支队伍的能力为队员潜力值的 $\text{mex}$（即最小的未出现过的非负整数）。学校想知道每一天能组成的队伍的能力最大值。
数据范围：$1\le m \le n \le 5000$，$0 \le p_i < 5000$，$1 \le c_i \le m$，$1 \le d \le n$。
「CodeChef GERALD07」Chef and Graph Queries
题目链接：CodeChef GERALD07
大厨有一个无向图 $G$。顶点从 $1$ 到 $n$ 标号，边从 $1$ 到 $m$ 标号。
大厨有 $q$ 对询问 $L_i, R_i$。对于每对询问，大厨想知道当仅保留编号 $X$ 满足 $L_i \le X \le R_i$ 所在的边时，图 $G$ 中有多少了连通块。
注意数据可能包含自环和重边！
本题有 $T$ 组数据。
数据范围：$1 \le T \le 10 ^ 3$，$1\le n, m, q \le 2\times 10 ^ 5$，$1\le L_i \le R_i \le M$，所有的 $n, m, q$ 的和均不超过 $2\times 10 ^ 5$。
「BZOJ 2120」数颜色
题目链接：BZOJ 2120
墨墨购买了一套 $n$ 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：
Q l r：询问从第 $l$ 支画笔到第 $r$ 支画笔中共有几种不同颜色的画笔。R p c：把第 $p$ 支画笔替换为颜色 $c$。
数据范围：$1\le n,m\le 5\times 10^4$，$1\le c\le 10^6$。
「Codeforces 594D」REQ
题目链接：Codeforces 594D
今天的数学课上，老师告诉 Vovochka 正整数的欧拉函数 $\varphi(n)$ 是计算小于等于 $n$ 且与 $n$ 互质的正整数的函数，$1$ 和任意正整数互质所以 $\varphi(1)=1$。
现在老师给了 Vovochka 一个数列 $a_1,a_2,\dots,a_n$，要求回答 $q$ 个询问 $l_i,r_i$，计算 $\varphi\left(\prod_{i=l}^r a_i\right)$ 的值，答案对 $10^9 + 7$ 取模。这个问题对二年级学生来说太难了，所以你决定帮助 Vovochka。
数据范围：$1 \le n,q \le 2 \times 10 ^ 5$，$1 \le a_i \le 10 ^ 6$。