T1.触不可及
简要题意
给定一个长度为 \(n\) 的序列 \(a\)。你每次可以删除一段长度为 \(2\)的幂的 \(a\)的区间（删除后两边合并）。你可以操作任意多次，但操作的区间长度必须互不相同。操作之后，你希望序列的最大子段和最大。输出该最大子段和。
\(n<1e3,abs(a[i])>=1e6\)
题解
唐氏题，直接区间\(dp\)，设\(dp[i][j]\)为\(1-i\)中，删除的状压为\(j\)可以形成的最大答案（注意：不一定要从\(1\)开始或者到\(i\)结束），有:
\[初始化：dp[i][0]=max(0,max(dp[i-1][0]+a[i],a[i])) \]\[转移：枚举2的次幂k,dp[i][j]=max(dp[i][j],dp[i-(1<<k)][j异或(1<<k)]) \]用时\(30min\)，期望得分\(100\)，实际得分\(100\)。
T2.璀璨冒险人
简要题意
有一个三个柱子的汉诺塔，\(n\)个圆盘，给定初始圆盘的位置，求都放在第三根柱子上的最小操作次数。
\(n \le 10^7, 1\le a_i \le 3\)。
题解
《具体数学》题，设\(dp[i][1/2/3]\)为把前\(i\)小的圆盘放到\(1/2/3\)号柱子上的操作次数。
转移，不妨设第\(i+1\)个圆盘在第一个柱子上（其他情况同理），有:
\[dp[i+1][1]=dp[i][1],dp[i+1][2]=dp[i][3]+2^{i-1},dp[i+1][3]=dp[i][2]+2^{i-1} \]也可以从大到小枚举，先找到第一个不在三号柱子上的圆盘，再递归处理。
用时\(1h20min\)，做的时候唐氏了，期望得分\(100\)，实际得分\(100\)。
T3.蜃楼
简要题意
给定 \(n\)，对每个 \(i=1,2,…,n\)，你有\(a_i\)个面值为\(i\)的硬币，问你能用这些硬币凑出多少种金额。
\(n \le 100,0\le a_i \le 10^9\)。
题解
设\(\sum_{i=1}^{n}a_i\times i\)为\(s\)，显然每个金额能否凑成的\(01\)串关于\(s/2\)对称。
并且观察到这个东西有周期并且周期不长，题解说是\(2n^3\)的，那么只需要计算\(2n^3\)内的答案即可。
计算使用多重背包二进制分组优化+bitset优化，复杂度\(O(n^4\log n/w)\)。
用时\(2h\)，期望得分\(0\)，实际得分\(0\)。
T4.我以渺小爱你
简要题意
定义一个\(3-hypergraph\)是一个由三个点构成的集合，\(BC_k\)为\(k\)个两两不同的点\(v_1,v_2,......,v_k\)和两两不同的集合\(e_1,e_2,......,e_k\)，满足\(v_i \in e_i \cap e_{i\bmod k+1}\)
有\(n\)个点，构造尽可能多的\(3-hypergraph\)，满足没有\(BC_2,BC_3,BC_4\)。
\(n<=1893\)，构造得分计算方式较为复杂。
题解
条件等价于把每个集合\({x,y,z}\)拆成三条边\((x,y),(y,z),(z,x)\)后图中不包含四元环。
构造一张特殊的图\(ER_q\)，其中的点为\(\bmod q\)意义下的所有不同的三维直线，边为两条直线垂直则连边。
易证\(ER_q\)中点数为\(q^2+q+1\)边数为\(\frac{1}{2}q(q+1)^2\)且没有四元环。
构造方案为\(ER_q\)中的所有三角形。
用时\(40min\)，期望得分\(5\)，实际得分\(5\)。
标签：得分,le,题意,day6,题解,24noip,100,dp,十连测 From： https://www.cnblogs.com/wangwenhan/p/18463073