POI1998

POI1998未完整解决的有：abs算法错误okn算法不太优美以至于无法实现gra比最优解多一步题号核心算法具体细节mal数形结合+递推以左下角为(0,0)建立坐标系，考虑一个点a,b存在一个洞（称为yes(a,b)）的条件为存在i使得b的第i个二进制位为0，b的第i个二进制位为1，故问题转化为求所有a,b使a,b,a+x,b+y∈[0,2^n-1]andyes(a,b)andyes(a+x,b+y)使用递推解决：f[I,0..1,0..1]表示第i位至第n位，a是否得到了了前n-1位的进位，b是否得到了前n-1位的进位的方案数。初始f[n+1,0,0]=1Ans=f[1,0,0]wie三角剖分树+树形DP首先，以每个三角形为点，有公共边的三角形连一条边，那么必然将形成一棵树，即三角剖分树，三角剖分树有很多优美的性质，这里不多说。考虑本题中三角形A与三角形B(x,y,z){即我们选出的三角形}，它们相交当且仅当三角形A的某条边E满足x,y,z不在E的同侧。对应到三角剖分树，点A与三角形B相交当且仅当x至y或y至z或z至x的路经需要经过点A，这里所说的x是指三角形(x-1,x,x+1)，由三角剖分的性质可以证明若该三角形不存在那么选取x点必然不是最优的。综上所述，我们的算法就很简单了：1.构建三角剖分树。（方法见集训队解题报告）2.在三角剖分树找到三个点使它们之间的路经经过的点数尽量多，基础的树形DP。sum构造当|s|n*(n-1)/2或s与n*(n-1)/2奇偶性不同时无解，否则ifs0thens:=-s且求出解取反。fill(dat,1)i:=n-1;whiles+2*in*(n-1)/2dodat[i]:=-1;dec(i)s:=s+2*iend;dat[(n*(n-1)/2-s)/2]:=-1abs树的括号序列仔细读题，就会发现所谓的ab串就是树的括号序列（括号序列见牛书P288），而我们要求的则是这些树在它给的变换规则下，本质不同的有多少棵。变化规则：对于任一棵子树，将其儿子从某处分成两份，交换其顺序。不仔细分析可能误以为就是最小表示法，实际上这个变化规不能将任一棵树转化为其最小表示法的形式。我的做法是每次选出最小的子树j，递归处理j后面的和j前面的，然后将j作为第一棵子树，j后面的紧跟j后面，j前面的放在j后面的后面，这样可以比直接求最小表示多对几个点。标准做法的话，波兰文看不懂，算了吧。sie最短路+模拟直接按题意模拟即可。row并查集所有的相同字母（包括0,1）的对应位置取值相等并且方程左右的对应位置取值相等，相等关系具有传递性，故我们使用并查集，每个位置作为一个元素，将所有取值要求相等的位置所对应的集合合并，那么有以下几种情况：1.左右长度不等，ans=02.1与0被合并至一个集合，ans=03.设k=不包含1与0的集合的个数，ans=2^k注意考虑0与1均未出现的情况。pak贪心+归并排序对于容器从小到大考虑，首先将体积为i的方案与已有方案利用归排合并，然后若当前的方案不足T[i]个则无解，否则选取前T[i]个加两合并作为下一次的方案。ple动态规划简单的二维背包，值得注意的是需要使用扩展型转移，即对于当前状态f[j,k]，当前物品a,b,w，转移至f[j+a,k+b]时需判断若j+aa0(所需要氧气)，那么转移至f[a0,k+b]，k+b判断同理。okn暂放模型转化+并查集设矩形左界x1，右界x2，下界y1，上界y2，对于每一个点(x,y)，x:=min(max(x,x1),x2)y:=min(max(y,y1),y2)这相当于把原图压缩至矩形内，而我们的目标则是求这个压缩图形的不连通部分的个数。若该图形是简单图（无重边），那么我们只需求连通块个数即可，有重边的情况下我们需要删除掉重复次数是偶数的便边，由于重边必然只在矩形边界上，我们只需要开一个HASH即可。综上，算法如下：1.压缩图形。2.对于原图每条边，若该边在矩形内，合并所连接的两个点。3.对于矩形上的经过次数为奇数次的边，合并左右端点。4.Ans=元素个数大于一的集合个数ukl贪心首先依次扫描过去，若遇到操作i与之前的操作j相同，且操作的变量相等，那么i可取代j。之后，对于每个变量，计算出它的最后一个操作是必须的，而若一个操作是必须的则其使用的两个变量对应的操作也是必须的。递归求出所有必须的操作即可。可以使用Hash优化第一步中的查找。ban负进制转化+高精题意很清楚，即求一个数的负2进制表示。-k进制求法也是用短除法，只要保证商*(-k)+余数=上次的商0=余数k。可以证明十进制数与-k进制数是一一对应的，无解当且仅当转化出来的数位数多于100。pro并查集+常数优化尝试思考复杂度低于n^2的算法，但没有收获。n^2的算法很简单，枚举每对长方形，若它们相交则将它们所属的集合合并，最后答案=集合个数。细节：1.相交判断法。x轴射影相交且y轴射影相交。线段(a,b)(c,d)相交=(a=d)and(b=c)2.注意若仅有一个点相交不算相交。3.考虑到相交的判断常数较大，不妨先判断它们是否已属于同一个集合，效率可大大提高。gra二分+递归略差于最优解。如果A不会说谎，那么直接二分就可以，所以我们的关键在于尽早让A说谎并且被我们发现。设F[i]表示确定被猜数在这2^i个数里面，但是我们不知道A是否已经撒过谎时，我们需要的最小猜测次数。f[i]=min(max(f[j],i)+i-j+1)这个转移方程的意义如下：我们猜测i-j次并在这i-j次中相信A，这时我们再询问一次剩下的2^j个数，有2种情况：1.回答否，若被猜数不在2^j个数中，那么A在i-j次中撒了谎，否则A这次撒了谎，无论如何，我们对2^i个数直接二分即可。2.回答是，若被猜数不在2^j个数中，那么A说了撒了两次谎，矛盾。故被猜数在2^j个数中且A一直到现在都未说谎。不过这样做需要16步，答案应为15，考虑中。gon图论+图与树间的转化如果A在一个环中，由题目条件不存在三元环，易证B永远无法抓到A。又由图连通，故考虑使用无向图的缩点。1．求出所有2-强联通分量并缩点。（称为黑点，其余点称为白点。）2．若存在某黑点i使得dis(A,i)dis(B,i)，无解。3．设AB路径的偏向A的中点为C，Ans=dis(B，C)+以B为根时子树C的深度naj贪心+数据结构从牛书上看来的贪心算法：每次选择最小的一个单词，删除之并加入它可以扩展出的k个单词。若单词超出N个，则保留较小的N个，并更新答案。若当前N个单词的和大于等于最优答案，则退出。当然我们需要合理的数据结构，比如说最大-最小堆，平衡树，或二分+move之类的。lam模型转化+LDS将坐标系向左旋转45度，那么折线就要求x,y均不降，以x为第一关键字，y为第二关键字排序，那么一条折线就对应一个不降子序列。根据最小链覆盖=最长反链，故求出最长下降子序列的长度即可。令人惊讶的是，波兰人在那时候就知道卡中间快排……