CodeChef APRIL15
感觉好像很久没有写文章了的样子，今天趁机水一发好了。
第一次做CodeChef的Long Challenge，看着别人一个个将自己超过但自己就是赶不上他们的感觉真得是很不爽啊……
因为题面有中文版的，所以题目大意就不讲了，主要还是讲我自己做题的经过。
另：因为有三道题我自己都还没有做出来，所以暂时先空着，等这两天做出来之后再补全。
代码就不发了，CC上都能看。
Problem A-BROKPHON
直接枚举每个数，看看是否和前面或者后面的一样就行了。
Problem B-CHEFLCM
就是求N的约数个数，直接$\sqrt{n}$枚举就行了。
Problem C-PIANO1
依旧是直接模拟就行了，枚举每个位置，看看能弹多少个音阶，这道题因为中文题面出来得比较迟，所以做得相对要晚一些。
Problem D-CSEQ
首先我们考虑小数据，可以转化成DP的题目，我们先定义m=r-l+1，然后我们就推出了DP的方程，f[i][j]=f[i-1][j]+f[i][j-1]，答案就是f[n][m]，接着，我们发现这好像就是给你一张n*m的网格图，从只能往右往下走，求从左上角走到右下角的方案数的DP方程，我们都知道这个东西是可以转化成组合数学问题的，最后问题就简化成了求$\dbinom{n+m}{m}$，根据Lucas定理加上逆元，暴力求一下就行了。
Problem E-DIVLAND
这是一道挑战题，用CodeChef的话讲应该叫做marathon？或者就是叫challenge，我没有做，感觉网络流可搞的样子，但是数据太大了，最后就弃坑了（本来今天下午打算打一下的，后来感觉反正也拿不了多少分就没搞了）。
Problem F-CARLOS
我们首先发现，如果对于每种置换方案都连一条边的话，我们会构成一张图，图上x和y两点间的最短路（如果存在的话）就是将x变成y或将y变成x需要的最少步数，我们先用floyd预处理，然后开始DP，假设第i个位置的字母是c[i]，f[i][j]表示第i个位置变成j需要的最少步数，那么f[i][j]=$\min_{k=1}^{k<=j} (f[i-1][k]+g[c[i]][j])$，其中g[c[i]][j]表示从c[i]变成j的步数，开始我以为是$O(nm^2)$的（m是字符集大小），后来发现我们同时枚举j和k（即我们不需要额外枚举k，枚举j的时候统计一下最小值就行了）就能做到$O(nm)$了。
Problem G-FRMQ
区间最小值，没有修改操作，最常见的做法当然是线段树，但是这道题的查询次数很多，有一亿次，必须要做到$O(1)$才行，开始打了ST表，结果被卡常数，接着以为要根据数据生成方式解方程什么的，后来感觉还是不靠谱，于是和Claris一起拼命卡常数，内建函数都用上了，还是没有卡过去，后来灵机一动，将二维数组的第一维和第二维换了一下，结果就过了（ST表第二维只有17的大小，第一维却是序列长度的大小）。不知道正解是不是这个。
Problen H-DEVVOTE
本来打算这道题就放弃的，后来还是觉得不甘心，花了一天左右的时间终于想了出来。首先，我们注意到这道题目数据范围只有36，因此我们可以打表。用Claris的话说，这种题目你当传统题来做就输了。n$\leqslant$7的情况还是很好做的，搜索一下就行了。然后我们考虑n$\leqslant$18的情况，我们可以DP，用一个数组a[]记录被投了x次的人有多少个，并且用一个last记录上次搜到了哪一个，然后递归一下就行了，至少能跑到22，之后我的电脑就再也没有跑出来了。这个时候，我灵光一闪，突然想起了陈老师冬令营时候讲了的DP of DP，用一个大的DP表示小的DP的所有状态，然后进行转移。这是可行的，这道题的方案数实际上就是将36进行整数划分的方案数，算了一下好像是一万七千九百左右，加上last，最多就乘个36，还是可以接受的。对于每种状态，我们开hash来存，我开始开了一千万大小的hash表，结果WA了，后来改到五千万还是出了问题，改到六千万的时候才跑出了正解，但不管怎样，总算是过了。
Problem I-BWGAME
想了很久，只会n$\leqslant$7的暴搜做法，最后懒得坑了。
Problem J-LPARTY
题目都没有看完，慢慢坑着吧。
2015年7月14日 21:43
CodeChef 的 challenge 题，AKA 脑洞题，评分方法是，每个程序有一个绝对分数（但出题人一定保证任何在时限内能跑完的代码都不能达到整个数据的最优解），然后最高的人拿100.0，其他人按自己最高分的那次提交的绝对分数占最高分的百分比计分。
一般是不会允许你用一些现成的算法跑完的——数据规模就这么故意设计的，或者这个题本身找最优解不存在多项式算法……
要开脑洞的地方就是，怎么去设计策略瞎搞（反正各种瞎贪心就对了，当然辅以一些暴力）
2023年1月05日 18:55
CodeChef is a popular online programming platform that hosts coding competitions. The site was founded in 2009 by Directi, a technology company based in Mumbai, India. codeChef hosts Full Spectrum Hemp Oil monthly programming competitions known as Cook-Offs and Ladders. The competitions are open to all programmers from around the world and are rated by skill level. The top performers in each competition are awarded prize money.