枚举+一定的空间想象力 题目描述 边长为\(1\)正方体(自行脑补),有一只蚂蚁要从上表面上的一点出发爬往下表面的某一点,规定蚂蚁只能沿正方体表面爬行,要求编程求出一条从起点到终点的最短距离。 起点和...
数学
洛谷 P3723 [AH2017/HNOI2017]礼物 题解【FFT】【函数】
卷积轻松想出来了但是挂在了别的推导上。 这个题也是HBOI2017啊 题目描述 我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了,他决定买一对情侣手环,一个留给自己,一个送给她。每个手环上各...
洛谷 P3338 [ZJOI2014]力 题解【多项式】【FFT】
理解了一些关于卷积的东西。 题目描述 给出\(n\)个数\(q_i\),给出\(F_j\)的定义如下: \[F_j=\sum_{i<j}\frac{q_iq_j}{(i-j)^2}-\sum_{i>j}\frac{q_iq_j}{(i-j)^2}\] 令\(E_i=\frac{F_i}{q_i}\)...
快速傅里叶变换 FFT 学习笔记【多项式】【FFT】
一、多项式 多项式的定义 多项式是多个单项式的和。(这是人教版七年级上册的定义)形如(x^2),(6y^5+5y^2+17)这样的式子就是多项式。 多项式的乘积 多项式乘积可以类比两个数相乘。...
hdu 5194 DZY Loves Balls 题解【组合数学】【概率期望】【打表/找规律】【枚举】
这个题的做法实在是太多了,在我打完暴力水过后发现这个题的很多解法都是非常有价值的。 Description There are \(n\) black balls and \(m\) white balls in the big box. Now, DZY st...
幻魔皇 题解【数列】【递推】【斐波那契树】
这个题暴力分倒是挺多的……正解也不是很难想 问题描述 幻魔皇拉比艾尔很喜欢斐波那契树,他想找到神奇的节点对。 所谓斐波那契树,根是一个白色节点,每个白色节点都有一个黑色节点儿子...
神炎皇 题解【数学】【gcd】【欧拉函数】
怎么才能想到可以这样推啊……数学题做少了orz。 问题描述 神炎皇乌利亚很喜欢数对,他想找到神奇的数对。 对于一个整数对\((a,b)\),若满足\(a+b\le n\)且\(a+b\)是\(ab\)的因子,则成为...
完全背包问题 题解【有后效性的DP】【最短路】【背包】【同余】
后效性处理+背包合法性转化…又是玄学操作,不过感觉对DP的理解又深入了一些。 题目描述 有\(n\)种物品,物品的体积分别为\(V_1,V_2,\dots,V_n\),且每种物品的数量都可以看做是无限多的...
锦标赛游戏 题解【竞赛图】【递推】【排列组合】【构造】
解决竞赛图问题是需要一些技巧的。 问题描述 \(\text{YJC}\)很喜欢玩游戏,今天他决定和朋友们玩锦标赛游戏。 锦标赛游戏的规则是这样的:一共有\(i(1\le i\le n)\)个人参与游戏,每个...
Tenka1 Programmer Contest 2018 C – Align 题解【贪心】【数学】
感觉这个贪心证明挺不错的。 Problem Statement You are given \(N\) integers; the \(i\)-th of them is \(A_i\). Find the maximum possible sum of the absolute differences between...