CodeChef上一道有趣的网络流题目

这是一道2016年二月CodeChef上的一道题目,叫做Call Center Schedule

题目大意是这样的:

一个电话公司有 P 个员工,一个星期有 D 天,每天需要工作 H 个小时。每个员工在每个小时只能做参加会议和与客户通话两件事情中的一件,或者不做。

现在要为安排一个和客户通话的时间表,要求满足

  • 每个人每天最多花费 N 个小时在参加会议和通话上
  • 第 i 个人每周最多花费 Li 个小时和客户通话
  • 每个人每天在 LTbegin 到 LTend 的时间内至少要有 1 小时没有被安排任务
  • 对于第 i 天第 j 个小时,恰好有 Ri, j 个人可以和客户通话

另外,开会的时间表已经安排完成,如果 Fk, i, j 是 0 则表示第 k 个人在第 i 天的第 j 个小时开会,如果是 1 则表示他可以被安排去和客户通话。

时限是 2s,最多 5 组数据,并且 1 \leq N \leq H \leq 70, 1 \leq D, P \leq 70, 1 \leq L_i \leq ND, 0 \leq R_{i, j} \leq 15, F_{k, i, j} \in \{0, 1\}, 1 \leq LT_{begin} \leq LT_{end} \leq N

(more…)

Read More

CodeChef February 2016. Weird Sum 题解

这是 CodChef February Challenge 2016 上的一题,题目链接在这里:WRDSUM

给定一个整数 n(n \geq 2),考虑其质因子分解 n = p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}

g = \text{gcd}(k_1, k_2, \cdots, k_r)m_i = \frac{k_i}{g}

定义函数 F(n) = p_1^{m_1}p_2^{m_2}\cdots p_r^{m_r}

现在给定一个整数 N(N \leq 10^{2016}),你需要计算

 S = F(2) + F(3) + \cdots + F(N)

答案对 998244353 取模

(more…)

Read More

BZOJ-3435. [Wc2014]紫荆花之恋

强强和萌萌是一对好朋友。有一天他们在外面闲逛,突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了,无数的花瓣以肉眼可见的速度从紫荆树上长了出来。

仔细看看的话,这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点,每个节点上有一个可爱的小精灵,新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物,每个小精灵 i 都有一个感受能力值 r_i,小精灵 i,j 成为朋友当且仅当在树上 ij 的距离 \text{dist}(i,j) \leq r_i+r_j,其中 \text{dist}(i,j) 表示在这个树上从 ij 的唯一路径上所有边的边权和。

强强和萌萌很好奇每次新长出一个叶子节点之后,这个树上总共有几对朋友。

我们假定这个树一开始为空,节点按照加入的顺序从 1 开始编号。由于强强非常好奇,你必须在他每次出现新结点后马上给出总共的朋友对数,不能拖延哦。

【输入格式】

第一行包含一个整数,表示测试点编号。

第二行包含一个正整数 n,表示总共要加入的节点数。

我们令加入节点前的总共朋友对数是 \text{last_ans},在一开始时它的值为 0

接下来 n 行中第 i 行有三个非负整数 ai,ci,ri,表示结点 i 的父节点的编号为 a_i \oplus (\text{last_ans} \bmod 10^9)(其中 \oplus 表示异或,\text{mod} 表示取余,数据保证这样操作后得到的结果介于 1i-1 之间),与父结点之间的边权为 c_i,节点 i 上小精灵的感受能力值为 r_i

注意 a_1=c_1=0,表示 1 号节点是根结点,对于 i>1,父节点的编号至少为 1

【输出格式】

包含 n 行,每行输出 1 个整数,表示加入第 i 个点之后,树上有几对朋友。

【数据范围】

n \leq 10^51 \leq c_i \leq 10^4a_i \leq 2\times 10^9r_i \leq 10^9,时限 12s

(more…)

Read More

多项式除法及求模

问题是这样的:给定一个 n 次多项式 A(x) 和一个 m(m \leq n) 次多项式 B(x),要求求出两个多项式 D(x), R(x),满足

 \begin{equation} \label{div0} A(x) = D(x)B(x) + R(x) \end{equation}

并且 deg D \leq degA - degB = n - mdegR < m

在解决这个问题之前你需要掌握多项式求逆,利用快速傅里叶变换可以在 \mathcal O(n\log n) 的复杂度内求出这个问题的解

多项式除法在很多问题中都有应用,例如多项式的扩展欧几里得算法、线性递推的优化等等

(more…)

Read More

BZOJ-3557. [Ctsc2014]随机数

这是 CTSC2014 一道陈老师的可怕题目!

露露、花花和萱萱最近对计算机中的随机数产生了兴趣。为大家所熟知的是,由计算机生成的随机数序列并非真正的随机数,而是由一定法则生成的伪随机数。

某一天,露露了解了一种生成随机数的方法,称为 Mersenne twister。给定初始参数 m \in \mathbb Z^+x \in \mathbb Z \cap [0, 2^m) 和初值 M_0 \in \mathbb Z \cap [0, 2^m),它通过下列递推式构造伪随机数列 {M_n}

 \begin{equation*} M_n = \left \{ \begin{aligned} &2M_{n-1}& ~2M_{n-1} < 2^m \\ (2M_{n-1} &-2^m) \oplus x & ~2M_{n-1} \geq 2^m \\ \end{aligned} \right. \end{equation*}

其中 \oplus 是二进制异或运算(C/C++ 中的 ^ 运算)。而参数 x 的选取若使得该数列在长度趋于无穷时,近似等概率地在 \mathbb Z \cap (0, 2^m) 中取值,就称 x 是好的。例如,在 m > 1x=0 就显然不是好的。

在露露向伙伴介绍了 Mersenne twister 之后,花花想用一些经典的随机性测试来检验它的随机性强度。为此,花花使用计算机计算了一些 M_k

但细心的萱萱注意到,花花在某次使用二进制输入 k 时,在末尾多输入了 l0。她正想告诉花花这个疏忽,然而花花已经计算并记录了错误的 M_k 值而没有记录 k 的值。虽然这其实不是什么致命的问题,但是在萱萱告诉花花她的这个疏漏时,作为完美主义者的花花还是恳求萱萱帮她修正 M_k 的值。萱萱便把这个任务交给了他的 AI ——你!

【输入格式】

输入文件 random.in 的第一行包含一个正整数 m,第二行为二进制表示的 x(共 m 个数,从低位到高位排列),第三行为二进制表示的 M_0(排列方式同 x),第四行包含一个整数 type

接下来分为两种可能的情况:

  1. type = 0(萱萱记下了花花的输入):则第五行包含一个整数,表示萱萱记下来的正确的 k 值。
  2. type = 1(萱萱未能记下花花的输入):则第五行为 l,第六行输入花花计算出错误的二进制表示的 M_k

【输出格式】

输出文件 random.out 仅一行,为一个 m 位的 01 串,表示你求得的正确的 M_k(同样要求从低位到高位排列)

【数据范围】

对于 type = 0 的部分,m, k \leq 10^6

对于 type = 1 的部分,m \leq 10^3, k \leq 10^{18}, l \leq 10x 是“好的”

每个数据点时限 20s,并且开启编译器优化

(more…)

Read More

BZOJ-2780. Sevenk Love Oimaster

题目给出 n 个字符串 s_1, s_2, \cdots, s_n,以及 m 个询问 q_1, q_2, \cdots, q_m,每个询问是一个字符串,要求计算 q_i 在多少个 s_1, s_2, \cdots, s_n 中出现过

例如 s_1=abcabc, s_2=ca, s_3=a,那么 abcs_1 中出现过,as_1, s_2, s_3 中出现过

数据范围:1 \leq n \leq 10^4, 1\leq q \leq 6\cdot 10^4, \sum_{i=0}^n |s_i| \leq 10^5, \sum_{i=0}^m |q_i| \leq 3.6 \cdot 10^5

题目连接:BZOJ-2780SPOJ-JZPGYZ

(more…)

Read More