【JZOJ5017】拍苍蝇 题解题目大意 平面大小为 $Xp \cdot Yp$,上面有 n 只苍蝇,每只坐标为 (xi, yi)。 然后给出一个 $k$ 个顶点的多边形(可能为凹),你要将多边形放在平面上,规定顶点必须在整点上,且不能有苍蝇在多边形内或多边形上。 求方案数。 $Xp, Yp \le 500, n \le Xp \cdot Yp$ $k \le 10^4$ 小测试点 1.5s,大测试点 3s。 Mar 16 OI/XCPC 算法_FFT/NTT, 算法_几何 Comments
【Hackerrank University2】【JZOJ5008】Querying Sums on Strings 题解题目大意 $n,~m,~k,~q~<=~1e5$ $\sum |w|<=1e5$ 1s, 512M Mar 14 OI/XCPC 算法_字符串, 算法_根号平衡 Comments
猎奇!THUWC2017试机题A题目大意 一个长度为 $n$ 的序列,选择一个长度为 $k$ 的子序列,使得字典序最小。 $O(n \log n)$ 会被卡,要求线性。 (这题其实挺正常挺经典的。。。) Mar 10 OI/XCPC 算法_神奇的脑洞 Comments
【JZOJ4155】传送 题解题目大意 你在一个有 n 个点的环上,环上点按逆时针顺序标号为 0 到 n-1。你一开始在 0 号点。 你在每一回合可以使用 k 种传送中的一种,第 i 种传送会将你按逆时针方向移动 a[i] 个点。 有 m 个限制条件,对于每个限制条件 (xi, yi),要求不能在第 xi 步之后在 yi 号点上。 你要求出经过 L 步之后在 0 号点的方案数模 998244353。 n <= 65536 且 n 为 2 的幂。 L <= 1e9, m <= 15, k <= 1e5 时限 2s。 Mar 9 OI/XCPC 算法_FFT/NTT Comments
【hihocoder1455】Rikka with Tree III 题解题目大意 现在有一颗 n 个点的有根树,每个点有点权 w[i]。在树上每一条从 $u$ 到 $v$ 的简单路径都能得到一个序列:按照顺序把经过的点的权值写下来,这个序列定义为 $A_{u,v}$,注意 $A_{u,v}$ 可能不等于 $A_{v,u}$。 序列 $B$ 在树上出现过当且仅当存在 $u, v$ 满足 $B$ 是 $A_{u,v}$ 的子序列。 整数 d 在树上出现过当且仅当存在以 d 为公差的长度不小于 3 的等差数列在树上出现过。 问有多少个正整数 d 在树上出现过。 n<=5e4, 1<=w<=n, 时限 2s。 Mar 7 OI/XCPC 算法_位运算, 算法_莫队/分块 Comments
【hdu5382】GCD?LCM! 题解题目大意 令 $f(n)=\sum_{i=1}^n\sum_{j=1}^n~[~gcd(i,j)+lcm(i,j)≥n~]$,求 $S(n)=\sum_{i=1}^nf(i)$。 多组询问,$T \le 10^5,n \le 10^6$。 Mar 5 OI/XCPC 算法_数论, 算法_神奇的脑洞 Comments
【CF763B】Timofey and rectangles 题解题目大意 平面上有 $n$ 个矩形,每个矩形的边长都是奇数。并且矩形之间不会相交或者包含。 现在你要用四种颜色去染这些矩形,使得相邻的矩形不同色。请给出一种染色方案,或者输出无解。 $n \le 5\times 10^5$。 Mar 5 OI/XCPC 算法_构造题 Comments
【codejam2008 Round1A】Numbers 题解题目大意 求 $(3+\sqrt 5)^n$ 的整数部分最后三位。 $n \le 2 \times 10^9$ Mar 2 OI/XCPC 算法_矩阵乘法, 算法_神奇的脑洞 Comments
【JZOJ4941】宝石魔术 题解题目大意 有 Q 种操作。 1、加入一个魔力为 x 的宝石; 2、删去一个魔力为 x 的宝石(保证操作合法); 3、询问有多少种选取宝石的方法,使得选取的魔力和为 x;(不同下标的宝石视为不同,即两种方法不同当且仅当两种方法选取的宝石有不同) 4、询问有多少种选取宝石的方法,使得选取的魔力和为 x。(不同魔力的宝石视为不同,即两种方法不同当且仅当某一种魔力值的宝石数量不同) Q, x<=10^4,时限 3s。 Feb 22 OI/XCPC 算法_DP, 算法_多项式/生成函数 Comments
【JZOJ4970】B 题解题目大意 给定 $N, M, K$,数组 $a[N][M], b[N]$。定义 求第 $K$ 大的 $c[i]$。 $N \le 250000$ 且 $N$ 为质数,$2 \le m \le 4$ $0 \le a_{ij} < 1024,\ 0 \le b < m$ Feb 16 OI/XCPC 算法_FFT/NTT, 算法_数论 Comments
【CF762E】Radio stations 题解题目大意 数轴上有 n 个广播站。第 i 个广播站坐标为 x[i],信号半径为 r[i],频率为 f[i]。 规定两个广播站 i 和 j(i< j)是可互相到达的,当且仅当 min(r[i], r[j])<=|x[i]-x[j]| 规定两个广播站 i 和 j(i< j)是互相干扰的,当且仅当 i 和 j 可互相到达,且 |f[i]-f[j]|<=k 求有多少对广播站互相干扰。 n<=10^5, k<=10 x[i], r[i]<=10^9, f[i]<=10^4 Jan 26 OI/XCPC 算法_偏序关系 Comments
【WC2017四校联考5】B君的宴请 题解题目大意 n 把椅子排成一个环。 现在要撤掉一部分,使得只剩下恰好 k 把椅子,并且剩下的任意两把椅子原先不相邻。 若两种方案可以经过旋转、翻转互相等价,则认为本质相同。 求本质不同的方案数 $\bmod 10^9+7$ Jan 25 OI/XCPC 算法_群论 Comments