12.12模拟赛总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
琦爷就是神！
挂的太惨了，不过确实都不会
真的都不会啊！！
--------------------------------------------------------------------
题号大概是SuperOjP1022~P1024
--------------------------------------------------------------------
T1:
考虑DP，显然可以用BFS序来转移，因此就是搜索=_=
假设f(x)表示状态x的期望步数，那么有：
f(x) = 1/6 * f(x) + 1/3 * f(r) + 1/3 * f(g) + 1/6 * f(b) + 1
其中f(r)表示:
若可以移动一个颜色为r的，那么f(r)为答案最小的一个拿法的期望步数(f(r) = min{f(r') | r'是从x这个状态拿走一个颜色为r的可以转移到的状态})
如果不能移动，那么f(r) = f(x)
f(g)也是同理
暴力转移，哈希去重即可
另外有一些优化，比如除了中间那个积木，其他的积木的顺序是没有影响的，除了第一层之外，其它层的顺序也是没有影响的
--------------------------------------------------------------------
T2:
Orz zrq 碾标算大爷
首先令b[i] = (b[i] - a[i]) mod 4
这样问题就变成了从0开始加，每次选一个区间加一模4，加成b数组，最小操作次数
我考试的时候想了一个DP，貌似是错的呢
假设有常数k,表示如果不模4，最后的数组最大的数不超过4*(k+1)
考试的时候我k取的1（不会证，事实上也是错的..）
后来证明即使k取到20也还是wa完，但是随机数据性能炒鸡好，拍了4000+组完全不出错，怀疑出题人故意卡这个算法=_=
我的DP:
f(x,i) 表示前i个，最后一个如果不模为4*i+b[i]的答案
为了方便，令g(x)=4*x + b[x]
转移:f(x,i) = min{ (g(x) < g(x-1)) ? f(x,j) : f(x,j) + (g(x) - g(x-1)) | 0 ≤ j ≤ k}
其中(a ? b : c)表示如果a成立，那么结果为b，否则为c
琦爷法：
如果不模b，那么最后第i个点的高度为l[i] = 4*k + b[i]
易得结论:答案r = ∑(i=1,n) [l[i] > l[i-1]] * (l[i]-l[i-1])
其中[x]表示若x成立，值为1，否则为0
首先令l=b
每次操作为把一个区间的l[i]加4
把l差分化:令l[i] = l[i]-l[i-1]
那么r=∑(l[i]>0) l[i]
每次操作是把l[i]加4，把l[j]减4，其中i<j
显然，除非l[i] < 0且l[j] > 0,答案不会减少
因此只考虑l[i] < 0且l[j] > 0的情况
易得，假如选了i,j这两个点，那么要令r=r-(|l[i]|+l[j]-4)
因此只有当|l[i]|+r[i]>4时答案才会变小
那么只有这三种情况才有意义:
l[i] r[i]
-2 3
-3 2
-3 3
我们可以记录t(x)表示到当前位置，前面-x出现了多少次
我们应该优先让-3匹配2，因为把2减4之后变成了-2，而-2又可以和3匹配，相当于把-3和3匹配了
于是方法就是每次遇到一个数x，如果是负数，就令t(x)=t(x)+1
否则如果是2，如果t(3)>0,那么令t(3)=t(3)-1,令t(2)=t(2)+1，更新答案
如果是3,如果t(3)>0,就令t(3)=t(3)-1,令t(1)=t(1)+1 (其实不用记录t(1),因为用不到),并更新答案
否则如果t(2)>0,就令t(2)=t(2)-1,令t(1)=t(1)+1 ,并更新答案
虽然分析很复杂，但是实现很简单呢~
--------------------------------------------------------------------
T3:
没仔细看题解，似乎就是把一个菱形的情况大讨论一下呢
因为菱形一定是最优的，但是可能会被边界卡住
然后就搞一搞看怎么是最优的，贪心就好了
--------------------------------------------------------------------
评论 (0)
