12.12模拟赛总结

琦爷就是神!
挂的太惨了,不过确实都不会
真的都不会啊!!
--------------------------------------------------------------------
 
题号大概是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:
没仔细看题解,似乎就是把一个菱形的情况大讨论一下呢
因为菱形一定是最优的,但是可能会被边界卡住
然后就搞一搞看怎么是最优的,贪心就好了
--------------------------------------------------------------------