分类： 二分

[ARC092D] Two Sequences

[ARC092D] Two Sequences

Time Limit: 3 sec / Memory Limit: 256 MB

难度：\(4.0\)

  • Problem Statement

You are given two integer sequences, each of length \(N\): \(a_1, \cdots ,a_N\) and \(b_1, \cdots ,b_N\).

There are \(N^2\) ways to choose two integers \(i\) and \(j\) such that \(1 \leq i,j \leq N\). For each of these \(N^2\) pairs, we will compute \(a_i+b_j\) and write it on a sheet of paper. That is, we will write \(N^2\) integers in total.

Compute the XOR of these \(N^2\) integers.

给定两个长度为 \(n\) 的正整数数组 \(a,b\) ，求 \(\forall 1 \leq i,j \leq n\)，\(a_i+b_j\) 在二进制下的异或和 。

  • Input

\(n\) 和两数组 \(a,b\) 。

  • Output

答案。

  • Sample Input

  • Sample Output

  • Constraints

\(1 \leq …

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 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 P4259 [FJWC 2019] 不同的缩写

YZOJ P4259 [FJWC 2019] 不同的缩写

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

出题人：E.Space      难度：\(6.1\)

  • 题目描述

在这个游戏中一共有 \(n\) 个角色。你需要编写一些关于这些角色的对话内容。

你打算用角色名字的一个非空子序列来作为它的简称。

当然，不同的角色要用不同的字符串作为简称，否则你就变量重名了。

你想确定一个简称的分配方案使得所有角色中最长的简称尽量短。

  • 输入格式

第一行一个正整数 \(n\)。

接下来 \(n\) 行，每行一个由小写字母组成的字符串，代表一个角色的名字。

不同的角色可能会有相同的名字。

  • 输出格式

如果不存在一种分配简称的方案满足条件，输出 \(-1\)。

否则第一行输出一个正整数，表示最长的简称的最小长度。

接下来 \(n\) 行每行一个字符串，按顺序表示每个角色的简称。

若有多种方案满足条件，那么你可以输出任意一种。

  • 样例输入

  • 样例输出

  • 数据规模与约定

保证 \(n \leq 300\) ，每个名字的长度不超过 \(300\)。

 

 

 …

[校内训练20161216] T2 版本管理git

[校内训练20161216] T2 版本管理git

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

难度：\(7.0\)

  • 题目描述

在工程的开发中，我们常常用 \(Git\) 进行版本的管理。这个方式具体来说是这样的：刚开始只有一个版本 \(0\)，表示最初始的情况，也就是空的项目；接下来一个用户可以对某一个版本 \(p\) 的项目进行修改，得到一个新的版本 \(i\)。这样，一个工程就产生了许多不同的版本，而管理员可以选择一些优秀的，将其合并到主版本中。

\(F\) 公司有一个项目 \(U\)，这个项目由一个字符串构成。版本 \(0\) 为空串。有 \(n\) 个开发者按顺序对这个项目进行了修改，其中第 \(i\) 个开发者将第 \(p_i ( 0 \le p_i < i)\) 个版本的开头添加上一个字符 \(c_i (1 \le c_i \le m)\) 作为新的版本 \(i\)。

作为项目的总负责人，你希望对这些版本进行评价。对一个字符串 \(S\)，称串 \(S\) 是串 \(T\) 的超前缀，当且仅当串 \(S\) 是串 \(T^{*}\) 的前缀。 \(T^{*}\) 表示 \(T\) 重复无限次得到的一个无限长度的串，如若 \(T = abcd\)，则 \(T^{*} = abcdabcdabcd \cdots\)。我们称串 \(S\) 的 “\(kitty\) 长度” 为 \(l\)，当且仅当存在一个长度为 \(l\) 的串 \(T\) 使得 \(S\) 是 \(T\) 的超前缀，且不存在小于 \(l\) 的串 \(T’\) 使得 \(S\) 是 \(T’\) 的超前缀（定义空串的 \(kitty\) 长度为 \(0\)）。你需要做的就是对每一个版本求出其的 \(kitty\) 长度（设版本 \(i\) 的 \(kitty\) 长度为 \(kitty(i)\)）。

在实际运营中，有两种情况，我们用一个数 \(k \in \{0,1\}\) 表示。在 \(k = 0\) 的情况中， 你可以等候开发者进行所有修改后，再进行计算；但在 \(k = 1\) 的情况中，开发者希望能够实时得到自己修改得到的版本的 \(kitty\) 长度，你需要实时计算出每个版本的 \(kitty\) 长度。

  • 输入格式

第一行包含三个整数 \(n,m,k\)。

接下来 \(n\) 行，其中第 \(i\) 行包含两个整数 \(p^{′}_{i}; c^{′}_{i}\)，其中：

如果 \(k = 0\) ，则 \(p_i = p^{′}_{i}\)，\(c_i = c^{′}_{i}\)；

如果 \(k = 1\)，则 \(p_i = p^{′}_{i} \oplus kitty(i …

YZOJ P3216 行商

YZOJ P3216 行商

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

难度：\(4.0\)

  • 题目描述

有 \(n\) 个货物，每个货物都有各自的重量 \(w_i\) 和价值 \(c_i\)，但是载重量仅为 \(m\) 。

挑选出一些货物，总重量不超过 \(m\)，使价值之和最大。

  • 输入格式

第一行，两个整数 \(n\)，\(m\)；

接下来 \(n\) 行，每行两个整数 \(w_i\)，\(c_i\) 。

  • 输出格式

一个整数 \(ans\) 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

 \(1 \leq n \leq 10^6\)，\(1 \leq m \leq 4^{31}\)，\(1 \leq w_i \leq 3\)，\(1 \leq c_i \leq 10^9\) 。

 

 

 …

[SDOI2012]任务安排

[SDOI2012]任务安排

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

难度： \(7.1\)

  • 题目描述

按顺序给定 \(N\) 个子任务，每个任务用时 \(t_i\) ，费用系数 \(f_i\)。

可以把连续的若干个（或一个）子任务合成为一个大任务，大任务的用时和费用系数分别为其中每个子任务的用时之和与费用系数之和。开始一个大任务之前需要准备时间 \(S\)，一个大任务的费用为他的 完成时刻 \(\times\) 费用系数 ，问按顺序执行完所有的大任务后，最小的费用和为多少。

形式化的，将 \(N\) 个任务划分成若干个块，每一组任务 \(M_i\) 花费代价 \((T+\sum{t_j}+S) \times \sum{f_j}\)，\(j \in M_i\)，\(T\) 为执行到这个任务之前花费的时间，求执行完所有任务的最小代价和。

  • 输入格式

第一行一个整数 \(N\) ；

而后 \(N\) 行中，第 \(i\) 行包含一个可能为负的整数 \(t_i\) 和一个非负整数 \(f_i\) 。

  • 输出格式

一个整数，表示最小的代价和。

  • 样例输入

  • 样例输出

  • 样例说明

如果分组方案是 \(\{1,2\}\)、\(\{3\}\)、\(\{4,5\}\)，则完成时间分别为 \(\{5,5,10,14,14\}\)，费用 \(C=\{15,10,30,42,56\}\)，总费用就是 \(153\) 。

  • 数据规模与约定

对于 \(20\%\) 的数据，\(1 \leq N \leq 1000\) ；

对于另外 \(40\%\) 的数据， \(1 \leq N \leq 300000\) ；

对于前 \(60\%\) 的数据，\(0 \leq t_i \leq 2^8\) ；

对于后 \(40\%\) 的数据，\(1 \leq N \leq 100000\)，\(-2^8 \leq t_i \leq 2^8\) ；

对于 \(100\%\) 的数据， \(0 \leq S, f_i …