WHZ0325's Space

【网络流24题】火星探险问题

题目描述给定 $p\times q$ 个位置，每个位置可能平坦无障碍、有障碍或有石块，$n$ 个探测车从左上角 $(1,1)$ 出发，每次只能往右或往下走，到达 $(q,p)$，输出使采集岩石最多时每辆车的行走方案。 $n,p,q\le 35$。算法分析难点在于如何表示取走石块，将每个......

Posted by WHZ0325 on 2019-05-03

【NOI 2010】能量采集

题目描述栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。栋栋的植物种得非常整齐，一共有 $n$ 列，每列有 $m$ 棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一......

Posted by WHZ0325 on 2019-05-03

【ZJOI 2007】报表统计

题目描述维护一个初始长度为 $n$ 的非负整数序列，支持一下三种操作：在初始第 $i$ 个整数后面插入一个整数，若初始第 $i$ 个整数后面已经插入过其它整数，则将该整数插入到这些整数的最后面。查询整个序列中相邻两个元素之间差值的最小值。查询整个序列中任意两个元素之间差值的最小值......

Posted by WHZ0325 on 2019-05-02

【APIO 2015】巴邻旁之桥

题目描述一条东西走向的穆西河将巴邻旁市一分为二，分割成了区域 $A$ 和区域 $B$。每一块区域沿着河岸都建了恰好 $1000000001$ 栋的建筑，每条岸边的建筑都从 $0$ 编号到 $1000000000$。相邻的每对建筑相隔 $1$ 个单位距离，河的宽度也是 $1$ 个单位长度......

Posted by WHZ0325 on 2019-05-02

【SHOI 2015】超能粒子炮·改

题目描述有 $t$ 组数据，每组数据给定 $n,k$，求 $\sum_{i=0}^kC_n^i\mod 2333$ 的值。 $t\le 100000$，$n,k\le 10^{18}$。算法分析感觉可能是套路题…… 设 $f[n][k]=\sum_{i=0}^kC_n^i\mod 23......

Posted by WHZ0325 on 2019-05-01

【国家集训队 2011】礼物

题目描述有 $n$ 件礼物，打算送给 $m$ 个人，其中送给第 $i$ 个人的礼物数量为 $w_i$，求送出礼物的方案数，输出答案模 $p$ 的结果，无解输出 $Impossible$。设 $p=p_1^{c_1}p_2^{c_2}p_3^{c_3}\dots p_t^{c_t}$，$......

Posted by WHZ0325 on 2019-04-29

【CTSC 2017】吉夫特

题目描述给定一个长度为 $n$ 的序列 $A$，求有多少个子序列满足所选下标集合为 ${b_1,b_2,\dots,b_k}$ 时 $a_{b_1}\ge a_{b_2}\ge\dots\ge a_{b_{k-1}}\ge a_{b_k}$ 且 $\prod_{i=2}^kC_{a_{i......

Posted by WHZ0325 on 2019-04-28

【清华集训 2016】组合数问题

题目描述$t$ 组数据，每组数据给定 $n,m$ 和 $k$，求对于所有的 $0\le i\le n$，$0\le j\le \min(i,m)$ 有多少对 $(i,j)$ 满足 $C_i^j$ 是 $k$ 的倍数。 $1\le n,m\le 10^{18}$，$1\le t,k\le ......

Posted by WHZ0325 on 2019-04-26

【音乐】山海

我看着天真的我自己出现在没有我的故事里等待着我的回应一个为何至此的原因他明白他明白我给不起于是转生向山里走去他明白他明白我给不起于是转生向大海走去我听着那少年的声音在还有未来的过去渴望着美好结局却没能成为自己却没能成为自己 ......

Posted by WHZ0325 on 2019-04-22

【SDOI 2010】古代猪文

题目描述给定两个整数 $n,g$，求 $g^{\sum_{k|n}C_n^k}\mod 999911659$ 的值。$1\le n,g\le 10^9$。算法分析当 $g$ 与模数 $999911659$ 互质时，根据欧拉定理得 $g^{\sum_{k|n}C_n^k}\mod 999......

Posted by WHZ0325 on 2019-04-18

【WC 2010】重建计划

题目描述给定一棵 $n$ 个节点的树，每条边有其对应的价值 $v_i$，要求一条路径，长度满足在 $[L,U]$ 内且路径上的边权总和与边数之比最大，输出这个最大值，结果保留三位小数。 $n\le 100,000$，$1\le L\le U\le n-1$，$v_i\le 10^6......

Posted by WHZ0325 on 2019-04-11

【TJOI 2015】弦论

题目描述给定一个字符串，求它的第 $k$ 小子串，$t=0$ 表示不同位置的相同子串算作一个，$t=1$ 表示不同位置的相同子串算作多个，无解输出 $-1$。 $n\le 5\times 10^5$，$t\in {0,1}$，$k\le 10^9$。算法分析利用后缀自动机的性质求解。 ......

Posted by WHZ0325 on 2019-03-25

【AHOI 2008】逆序对

题目描述给定一个由 $[1,k]$ 之间的数字组成的长度为 $n$ 序列，其中有一些位置上的数不可见，标记为 $-1$，求这个序列的最少逆序对数。 $n\le 10000$，$k\le 100$。算法分析首先需要发现一个结论：要使逆序对数最少，从前到后依次填写的不可见的数字一定单调不下......

Posted by WHZ0325 on 2019-03-24

【CF 981D】Bookshelves

题目描述给定一个长度为 $n$ 的数列 $a_i$，将其划分为 $k$ 个连续的子段，每一段和相与的值最大是多少。 $1\le k\le n\le 50$，$0\lt a_i\le 2^{50}$。算法分析看到相与的值最大，考虑按位贪心，定义 $f_{i,j}$ 表示将前 $i$ 个数......

Posted by WHZ0325 on 2019-03-23

【ZJOI 2012】波浪

题目描述由 $[1,n]$ 组成的排列，求其波动强度大于 $m$ 的概率，结果保留 $k$ 位小数。定义波动强度为每个数与其相邻数的差的绝对值之和。 $n\le 100$，$k\le 30$，$m\le 2147483647$。算法分析求波度强度大于 $m$ 的概率，我们可以求出每个波......