11D_Beyonder's Blog

传送门 ↬\looparrowright↬ 题目描述 W\text{W}W 公司有 mmm 个仓库和 nnn 个零售商店。第 iii 个仓库有 aia_iai​ 个单位的货物；第 jjj 个零售商店需要 bjb_jbj​ 个单位的货物。 货物供需平衡，即 ∑i=1mai=∑j=1nbj\sum\limits_{i=1}^{m}a_i=\sum\limits_{j=1}^{n}b_ji=1∑m​ai​=j=1∑n​bj​。 从第 iii 个仓库运送每单位货物到第 jjj 个零售商店的费用为 cijc_{ij}cij​ 。 试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。 输入格式 第 111 行有 222 个正整数 mmm 和 nnn，分别表示仓库数和零售商店数。 接下来的一行中有 mmm 个正整数 aia_iai​，表示第 iii 个仓库有 aia_iai​ 个单位的货物。 再接下来的一行中有 nnn 个正整数 bjb_jbj​，表示第 jjj 个零售商店需要 bjb_jbj​ 个单位的货物。 接下来的 mmm 行，每行有 nnn 个整数，表示从第 iii 个 ...

传送门 ↬\looparrowright↬ 题目描述 G\text{G}G 公司有 nnn 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 nnn 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。 输入格式 第一行一个正整数 nnn，表示有 nnn 个仓库。 第二行 nnn 个正整数，表示 nnn 个仓库的库存量。 输出格式 输出最少搬运量。 输入输出样例 输入 #1 5 17 9 14 16 4 输出 #1 11 说明/提示 1≤n≤1001 \leq n \leq 1001≤n≤100。 分析 建立最小费用最大流模型。 首先设一个超级源点 sss，和一个超级汇点 ttt。每个仓库和其相邻仓库之间建双向边，搬运一个货物产生的费用为 111，边的容量为 +∞+\infty+∞。设所有仓库库存的平均值为 x‾\overline{x}x，仓库 iii 的库存为 stockistock_istocki​，货物分配完成后，每个仓库的库存都为 x‾\overline xx。若 stocki>x‾stock_i>\overlin ...

传送门 ↬\looparrowright↬ 题目背景 第二次世界大战期间，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的两名飞行员，其中一名是英国飞行员，另一名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。 题目描述 一共有 nnn 个飞行员，其中有 mmm 个外籍飞行员和 (n−m)(n - m)(n−m) 个英国飞行员，外籍飞行员从 111 到 mmm 编号，英国飞行员从 m+1m + 1m+1 到 nnn 编号。 对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。 输入格式 输入的第一行是用空格隔开的两个正整数，分别代表外籍飞行员的个数 mmm 和飞行员总数 nnn。 从第二行起到倒数第二行，每行有两个整数 u,vu, vu,v，代表外籍飞行员 uuu 可以和英国飞行员 vvv 配合。 输入的最后一行保证为 -1 -1，代表输入结束。 输出格式 本题存在 Special Judge\text{Special J ...

D. Quadratic Form ↬\looparrowright↬ 题目描述 Bobo has a positive-definite n×nn \times nn×n matrix AAA and an nnn-dimension vector bbb. He would like to find x1,x2,…,xnx_1, x_2, \dots, x_nx1​,x2​,…,xn​ where x1,x2,…,xn∈Rx_1, x_2, \dots, x_n \in \mathbb{R}x1​,x2​,…,xn​∈R, ∑i=1n∑j=1naijxixj⩽1\sum\limits_{i = 1}^n \sum\limits_{j = 1}^n a_{ij} x_i x_j \leqslant 1i=1∑n​j=1∑n​aij​xi​xj​⩽1 and ∑i=1nbixi\sum\limits_{i = 1}^n b_i x_ii=1∑n​bi​xi​ is maximum. It can be shown that (∑i=1nbixi)2=PQ\left(\sum\limi ...

传送门 ↬\looparrowright↬ Problem Description On the beaming day of 60th anniversary of NJUST, as a military college which was Second Artillery Academy of Harbin Military Engineering Institute before, queue phalanx is a special landscape. Here is a m×nm\times nm×n rectangle, and this one can be divided into m×nm\times nm×n squares which are of the same size. As shown in the figure below. 01–02–03–04 ||||&|| &|| 05–06–07–08 ||||&|| &|| 09–10–11–12 Consequently, we have (m+1)×(n+1)(m ...

传送门 ↬\looparrowright↬ In most professional sporting events, cheerleaders play a major role in entertaining the spectators. Their roles are substantial during breaks and prior to start of play. The world cup soccer is no exception. Usually the cheerleaders form a group and perform at the center of the field. In addition to this group, some of them are placed outside the side line so they are closer to the spectators. The organizers would like to ensure that at least one cheerleader is located o ...

传送门 ↬\looparrowright↬ 题目背景 一年一度的“跳石头”比赛又要开始了! 题目描述 这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 nnn 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。 为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 mmm 块岩石（不能移走起点和终点的岩石）。 输入格式 第一行包含三个整数 len,n,mlen,n,mlen,n,m，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 len≥1len\geq 1len≥1 且 n≥m≥0n\geq m\geq 0n≥m≥0。 接下来 nnn 行，每行一个整数，第 iii 行的整数 di(0<di<len)d_i( 0 < d_i < len)di​(0<di​<len)， 表示第 iii 块岩石与起点的距离 ...

阶 要定义原根，先要引入数论中阶的概念。 阶的定义 设 a,m∈N+a,m\in\mathbb{N^+}a,m∈N+，且 a⊥ma\perp ma⊥m，使 ax≡1(modm)a^x\equiv 1\pmod max≡1(modm) 成立的最小正整数 xxx，称为 aaa 模 mmm 的阶，记为 ordma\text{ord}_maordm​a。 阶的性质 说明：描述阶的性质时，默认 a,m∈N+a,m\in\mathbb{N^+}a,m∈N+，且 a⊥ma\bot ma⊥m，即 ordma\mathrm{ord}_m aordm​a 存在。 性质1 an≡1(modm)a^n\equiv 1\pmod man≡1(modm) 的充要条件为 ordma∣n\mathrm{ord}_ma|nordm​a∣n。 证明 设 ordma=x\mathrm{ord}_ma=xordm​a=x。 首先证明充分性。设 n=pxn=pxn=px，其中 p∈N+p\in\mathbb{N^+}p∈N+。则 $a^n\equiv a^{px}\equiv1\pmod m$；即 an≡1(modm)a^n ...

引入 有卢卡斯定理，(nm)≡(n mod Pm mod P)×(⌊nP⌋⌊mP⌋)(modP)\begin{pmatrix}n\\m\end{pmatrix}\equiv\begin{pmatrix}n\bmod P\\m\bmod P\end{pmatrix}\times\begin{pmatrix}\left\lfloor\frac{n}{P}\right\rfloor\\\left\lfloor\frac{m}{P}\right\rfloor\end{pmatrix}\pmod P(nm​)≡(nmodPmmodP​)×(⌊Pn​⌋⌊Pm​⌋​)(modP)。卢卡斯定理的适用条件是：PPP 为质数。对于 PPP 是一般正整数的情况，可以使用扩展卢卡斯定理计算 Cnm(modP)C_n^m\pmod PCnm​(modP)。 算法分析 原问题的转化 要求 Cnm mod PC_n^m\bmod PCnm​modP，首先对 PPP 进行质因数分解，即 P=p1k1p2k2⋯pcntkcntP=p_1^{k_1}p_2^{k_2}\cdots p_{cnt}^{k_{cnt}}P=p ...

传送门 ↬\looparrowright↬ Problem Description Xiao Ming likes counting numbers very much, especially he is fond of counting odd numbers. Maybe he thinks it is the best way to show he is alone without a girl friend. The day 2011.11.11 comes. Seeing classmates walking with their girlfriends, he couldn’t help running into his classroom, and then opened his math book preparing to count odd numbers. He looked at his book, then he found a question : Cn0C_n^0Cn0​+++Cn1C_n^1Cn1​+++Cn2C_n^2Cn2​+++⋯+\cdots+⋯+ ...