当前位置:首页 >> 学科竞赛 >>

POI1997


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 贪心+队列优化 每经过一个车站,就把前面买的比这里贵的油全部卖 掉,然后再在该加油站把油加满。行驶时,优先使用当前有 的最便宜的油。当然我们需要维护一个油价递增的队列来降 低时间复杂度。 逆向思维. 设 d[i,j,c]为真当且仅当[i,j)的子串可以 合成字母 c. 递推时可枚举分裂位置 k: 对于某个规则 A1A2A3, 如果 d[i,k,A2]与 d[k,j,A3]均为真, 则 d[i,j,A1]为 真. 即: 2 d[i,j,A1] = d[i,j,A1] OR (A[i,k,A ] AND A[k,j,A3]) 2 2 3 3 状态有 cn 个, 转移有 c n 个, 总 O(c n )。 g[i,j]为[I,j)的子串最少可以合成几个 S, 直接动态规 2 划即可, 时间复杂度为 O(n ). 优化:最多只有 26 个字母, 因此可以用位运算加速 e[A2,A3]表示可以分裂得到 A2A3 的字符集 d’[I,j]表示所有 c 对应的 d[i,j,c]所组成的二进制数 2 3 时间复杂度降为 O(c n ). 首先简述题意:找出最大的高度 H,使得存在一个最小 的稳定高度集合,它们能够组合出且只能够组合出不超过 H 的稳定高度。 类似数学归纳法的递推,程序简单,但很巧妙。 奠基:第 1 个数必然要取,并且显然可行。 递推:前 K 个数取出某个最小的集合{h[1],h[2]……h[m]}, 且能且只能组合出不超过 h[k]的稳定高度。 若对于 h[k+1],存在某个高度 x 满足 h[k]<x<h[k+1] 且 x=h[i]+h[j]{i<=k j∈1..m} 那么 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 应该就够了, 而且也通过了所有数据。 每次找出最重的人和最轻的人,若它们可以搭一条船则

gen

动态规划+位运算

add

递推

rek 暂放

递归

ali

动态规划

kaj

贪心

搭一条船,否则最重的人单独搭一条船。 因为 w<=200,故使用 hash 的时间复杂度为 o(200)。 lic3 动态规划 数。 f[-1,0]=1 f[0,0]=1 f[i,j]=f[i-1,j]+f[i-2,j-i] ans{需要高精} = ∑f[n,i+1..n*(n+1)/4] rez tro 动态规划 补集转化 F[i,j]{刚好在 Int64 内}表示前 i-j-special 集合的个

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:求出强连通分量。

wia

图论


相关文章:
POI1997
POI1997 未完整解决的有: rek 算法似乎有问题,而且比较难写 题号 lic 核心算法 动态规划 具体细节 f[i,j,k,0..1]表示第 i 个至第 j 个单词,其中第 i...
更多相关标签:
请回答1997 | 蜜桃成熟时1997 | 张玉宁1997 | 家有喜事1997 | 美丽人生 1997 电影 | 601997 | 洛丽塔1997 | 1997年属什么 |