弦图染色问题

关于弦图和弦图的各类应用,陈丹琦的论文中已经介绍的非常清楚。 弦图与区间图 接下来我将用自己的语言解释一下弦图的染色问题 先来说几个概念 子图: 图$G=(V,E),G'=(V',E'),V'\subseteq V,E'\subseteq E$,则认为G'是G的一个子图 诱导子图:图$G=(V,E) …
BZOJ1188 分裂游戏

题目传送门 Description 有n堆石子,每次可以选三堆(i,j,k),满足i<j<=k,从i中取出一颗石子,在j和k中各放入一颗,发现有先手必胜的策略,问第一步有多少种取法并输出字典序最小的一组 Solution 一道博弈论的题目,可以发现对于每一堆石子,数量不是关键,关键在于奇 …

其实我也不是很会这种玄学的东西。。。 不过这东西貌似可以支持很多字符串操作。。。 求一个字符串中本质不同子串的数量  SPOJ Disubtr 先预处理出后缀数组,然后求出将后缀排完序后的相邻两个后缀的LCP, $Ans=\sum n-sa[i]-h[i]$ #include<bits/std …
codeforces 679A - Bear and Prime 100

题目传送门 写道交互题刷刷存在感。。 题目大意 通过少于等于20次询问来判断一个数是不是质数,对于每一次询问,你都可以询问一个数字,然后系统会告诉你这个询问的数字是不是那个数字的约数。难度不大,直接上代码,单纯为了体验一下交互题的写法。。。 code #include<cstdio> # …
BZOJ1941  Hide and Seek

题目传送门 Solution: 可能是我写KDtree最后一道题了,主要是重新理解了KDtree点到块的距离在针对最大值和最小值的不同计算方式。 结合前面的两篇: 1、插入 2、求最大(小)点对 3、求k远点对 也只会这些操作了,可能还是我太菜。 Code: #include<cstdio …
BZOJ4520 K远点对

题目传送门 Solution: 一直想知道KDtree怎么求K远点对(可能是我比较菜),原来只是用一个堆来维护,其实也是一道模板题。 Code: #include<cstdio> #include<algorithm> #include<cstring> #inc …
BZOJ2648 SJY摆棋子

题目传送门 开坑!!kdtree Solution: 先来简单的讲一下kdtree,是一个支持n维空间的插入和查询K远点对的数据结构,其本质就是经过优化的暴力搜索,至于建树过程(百度百科里介绍的很清楚),我们就以二维为例:平面内有(2,1),(3,2),(5,7),(6,4),(9,6)这些点,我们 …
BZOJ1789Y型项链

题目传送门 Solution: 先考虑,如果只有两串项链,则显然,将它们同时删到最长公共前缀是最优的。可问题一共有三串,则对第三串的处理,我们可以先一直拆,然后再补到和最长公共前缀相同,其实你可以画一棵trie树来证明这个是对的。(显然此题和1830是完全一样的两题,水水双倍经验) Code: #i …

题目大意 不包含4或8,且至少包含3个连续数字的数为合法的手机号码。问l,r区间内合法的手机号码有几个? Solution 这题是很显然的数位DP。当然,如果直接套dp方程可能会显得麻烦,所以还是用记忆化搜索。思路直接描述有点困难,所以直接看代码和注释。 代码 #include<cstdio …