2023年7月30日发(作者：)

POI1997

未完整解决的有：

rek 算法似乎有问题，而且比较难写

题号

lic

核心算法

动态规划

具体细节

f[i,j,k,0..1]表示第i个至第j个单词，其中第i个单词只使用了右边k个字母，0..1表示第i个选x还是选y，组成的回文串个数。通过枚举第j个选x或选y，并判断k与l[j]的长度来转移。

g[I,j,k,0..1]表示第i个至第j个单词，其中第j个单词只使用了左边k个字母，0..1表示第j个选x还是选y，组成的回文串个数。通过枚举第i个选x或选y，判断k与l[i]的长度来转移。

初值f[i,i,k,0..1]以及g[i,i,k,0..1]为0或1，直接判断即可。

时间复杂度(nL)^2，务必将转移思考清楚再写。

简单的动态规划。

细节：

1. 用天数*1000000+权和表示状态，以简化程序。

2. 无聊的话可以用队列优化。

xor满足结合律与交换律，故我们可以用n^2的时间计算出结果与哪些输入有关，故题目转化为求区间[a,b]中，对应的二进制在这些位上的1的个数为奇数的数的个数。

s[a,b]=s [0,b)-s [0,a)+check(b)

以[0,10100101)为例, 可以分解为若干集合:

0*******

100*****

101000**

10100100

在一个包含k个未确定输入的集合中，如果还有未知数k-1还未确定，则解有2种. 如果所有未知数均已确定, 那么k若已确定的位置满足条件则有2个解，否则0个解。

故统计后进行高精度计算即可。

确定棋子范围(-40..10040)，因为2^40>10^12。

1. 快速减少棋子个数。

利用公式3*f[i]=f[i-2]+f[i+2]，将棋子个数不少于3的位置用队列保存，使用类似SPFA的算法处理。

2. 求解。

repeat

有相邻的，f[i+2]=f[i+1]+f[i]

有大于1的，2*f[i]=f[i-2]+f[i+1]（同第1步）

until 满足要求。

每次选择余下度数(设为k)最多的点，将其与余下度数

多的k个点连边

tan 动态规划

xor xor性质+统计

sko 构造+调整

lot 贪心+归并排序 简要证明如下：

无解必然是在连了若干条边后，剩余度数最大的点无边可连，而该贪心算法能保证剩余最大度数尽量小，因此得证。

值得注意的是，每次连边后，有若干个点度数减了1，这样就要重新排序。

使用归并排序可以达到n^2的复杂度，使用线段树可以达到nlogn的复杂度。

pal 贪心+队列优化 每经过一个车站，就把前面买的比这里贵的油全部卖掉，然后再在该加油站把油加满。行驶时，优先使用当前有的最便宜的油。当然我们需要维护一个油价递增的队列来降低时间复杂度。

gen 动态规划+位运算 逆向思维. 设d[i,j,c]为真当且仅当[i,j)的子串可以合成字母c. 递推时可枚举分裂位置k: 对于某个规则A1A2A3, 如果d[i,k,A2]与d[k,j,A3]均为真, 则d[i,j,A1]为真. 即:

2d[i,j,A1] = d[i,j,A1] OR (A[i,k,A] AND A[k,j,A3])

2233状态有cn个, 转移有cn个, 总O(cn)。

g[i,j]为[I,j)的子串最少可以合成几个S，直接动态规2划即可, 时间复杂度为O(n).

优化：最多只有26个字母, 因此可以用位运算加速

e[A2,A3]表示可以分裂得到A2A3的字符集

d’[I,j]表示所有c对应的d[i,j,c]所组成的二进制数

23 时间复杂度降为O(cn).

递推 首先简述题意：找出最大的高度H，使得存在一个最小的稳定高度集合，它们能够组合出且只能够组合出不超过H的稳定高度。

类似数学归纳法的递推，程序简单，但很巧妙。

奠基：第1个数必然要取，并且显然可行。

递推：前K个数取出某个最小的集合{h[1],h[2]……h[m]}，且能且只能组合出不超过h[k]的稳定高度。

若对于h[k+1]，存在某个高度x满足

h[k]

那么Ans=h[k]并退出。

否则若h[k+1]不可由h[k+1]=h[i]+h[j]推出，就将h[k+1]加入集合{h[1]..h[m]}。

将棋盘分割出的小棋盘按顺时针1，2，3，4编号。若一个棋盘中没有格子，那么蚂蚁只能从进入的小棋盘相邻的顶角出去。例如从1进入，那么只能从右上和左下出去。

否则，分成4份递归处理，然后将它们连起来。

f[I,j,k]表示得到i个金币，j个银币，k个铜币的最少步数，然后利用广搜即可求出答案。

关键在于每种钱币数量的限制，最易证明的上界为4+4*4=17，但我猜想7应该就够了，而且也通过了所有数据。

每次找出最重的人和最轻的人，若它们可以搭一条船则add

rek

暂放

递归

ali 动态规划

kaj 贪心 搭一条船，否则最重的人单独搭一条船。

因为w<=200，故使用hash的时间复杂度为o(200)。

lic3 动态规划 F[i,j]{刚好在Int64内}表示前i-j-special集合的个数。

f[-1,0]=1 f[0,0]=1

f[i,j]=f[i-1,j]+f[i-2,j-i]

ans{需要高精} = ∑f[n,*(n+1)/4] O(n^2)

f[i]=max(f[j]+(i-j),f[i-1]) {区间(i,j)存在}

同色三角形统计难度较大，考虑统计非同色三角形

Ans = n*(n-1)*(n-2)/6-∑di*(n-di-1)/2

di表示第i个点的度数。

朴素算法：枚举每个点，DFS出它只走agree的边能到达的点，以及这些点通过disagree的边能到达的点，若点集有重合，则该点不可信。

时间复杂度O(nm)。

优化1：若i不可信，j相信i，则j不可信。

优化2：搜索过程中发现i不可信则直接退出。

优化3：从大到小枚举（越小的数越容易是祖先）。

优化4：求出强连通分量。

rez

tro

动态规划

补集转化

wia 图论