Codeforces Round #265 (Div.1)
VictorWonder
posted @ 2014年10月22日 19:52
in Codeforces
with tags
解题报告
, 1843 阅读
其实本来是懒得发题解的，因为找到了一份很有用的题解，不过感觉如果不写题解的话，还是不太好（主要是为了骗点点击）。
大神saffah的中文题解：
Problem 2A
给定一个二进制高精度数，求其+1后有多少位改变了
比赛的时候傻傻地打了模拟，后来发现只要数一下末尾有多少个1，再特判一下1的个数与整体长度是否相同就可以了。
Problem 2B
简单的模拟题，考试的时候打萎了，忘了判断是否读到了最后一位（如果读到了最后一位，就不需要将那个阅读器关闭，答案要减一）
Problem 1A
找到一个字典序最小的串使得其不含有长度大于1的回文串
从右往左找，对于每个位置都判断一下， 将这一位的字母往后枚举，再特判是否构成回文串，如果不构成回文串则输出
Problem 1B
判断给定的三维坐标各位交换之后能否构成一个立方体
枚举每一种情况再判断一下就可以了，考试的时候打萎了，判断的常数略大导致超时
Problem 1C
由于每次替换都是将一个数字替换成一组数字，所以从后往前走，判断一个数将会被转化成为什么，但是由于转化成的数太大，所以必须要取模，取模的同时需要注意记录下10^(长度)取模后的结果，否则计算最终答案的时候将会出现问题
Problem 1D
这道题我是看saffah的题解才看明白的，简单的来说就是动态规划求解期望值，要注意的是，函数f[i][j]表示当前装备的等级为j，还能够打i次怪所能够获得的钱的期望值
Problem 1E
这道题是我唯一能够理解并且自己搞出来的1E，题目就是求一条最短路，所以用堆优化的dijkstra就行了，但是由于边权过大，所以我们需要用高精度数保存，然而，点的数目太多，就算是每一个结点压62位也会爆内存，所以，必须要用主席树维护二进制的高精度数
那么就变成了这样的一个问题：找到从位置k开始往右的第一个0的位置t、将k到t-1内的所有数都置为0，然后将t位置上的数改成1
要注意的是，由于是dijkstra，所以肯定是要比较大小的，于是，主席树的每个结点都维护一个hash值，然后用hash值进行大小判断
最后，提供出题人的一个很有用的小优化：开始建出一棵全为0和一棵全为1的树，然后将区间的值用0覆盖的时候就不需要用什么lazy标记，只要用全为0的树的那个结点覆盖掉原有结点就行了
TAT，考试的时候只做出了2A和2B，结果2B还被卡了，rating狂降，真是太悲伤了。
Code:
评论 (0)
