来自 [成 博炜] 的全部文章

弦图染色问题

关于弦图和弦图的各类应用,陈丹琦的论文中已经介绍的非常清楚。 弦图与区间图 接下来我将用自己的语言解释一下弦图的染色问题 先来说几个概念 子图: 图$G=(V,E),G’=(V’,E’),V’\subseteq V,E’\subseteq E$,则认为G’是G的一个子图 诱导子图:图$G=(V,E),G’=(V’,E’),V’\subseteq V E={ (u,v)|u,v\in V,(u,v)\in E } $,则认为G’是G的一个诱导子图 团: 图G的一个子图$G’=(V’,E’)$,G’是关于V’的完全图 极 ......

BZOJ1188 分裂游戏

题目传送门 Description 有n堆石子,每次可以选三堆(i,j,k),满足i<j<=k,从i中取出一颗石子,在j和k中各放入一颗,发现有先手必胜的策略,问第一步有多少种取法并输出字典序最小的一组 Solution 一道博弈论的题目,可以发现对于每一堆石子,数量不是关键,关键在于奇偶,如果一堆石子有偶数个,则后手可以每次模仿先手在这堆石子上的操作,如果是奇数个则不一定。我们可以通过预处理出每一堆石子的sg函数(sg函数的求解只与n有关,与每堆石子的数量无关),对于一堆数量为偶数个的石子,可以不管,对于奇数个,则先将ans异 ......

后缀数组:从入门到不会

其实我也不是很会这种玄学的东西。。。 不过这东西貌似可以支持很多字符串操作。。。 求一个字符串中本质不同子串的数量  SPOJ Disubtr 先预处理出后缀数组,然后求出将后缀排完序后的相邻两个后缀的LCP, $Ans=\sum n-sa[i]-h[i]$ #include<bits/stdc++.h> using namespace std; char ch[1000000]; int x[1000000],y[1000000],sa[1000000]; int n,m,c[1000000],l,rank[1000000],h[1000000]; int main() { int cas; scanf("%d",&cas); while (cas--) { memset(c,0,siz ......

codeforces 679A – Bear and Prime 100

题目传送门 写道交互题刷刷存在感。。 题目大意 通过少于等于20次询问来判断一个数是不是质数,对于每一次询问,你都可以询问一个数字,然后系统会告诉你这个询问的数字是不是那个数字的约数。难度不大,直接上代码,单纯为了体验一下交互题的写法。。。 code C++ #include<cstdio> #include<algorithm> #include<cstring> using namespace std; char ch[10],cnt=0; const int prim[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,4,9,25,49}; int main() { for (int i ......

BZOJ1941 Hide and Seek

题目传送门 Solution: 可能是我写KDtree最后一道题了,主要是重新理解了KDtree点到块的距离在针对最大值和最小值的不同计算方式。 结合前面的两篇: 1、插入 2、求最大(小)点对 3、求k远点对 也只会这些操作了,可能还是我太菜。 Code: C++ #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,m,ansmn,ansmx,opt,k1,k2,D,root,ans; struct node { int l,r,mn[2],mx[2],d[2]; }t[800010]; inline int read() { int ans=0, ......

BZOJ4520 K远点对

题目传送门 Solution: 一直想知道KDtree怎么求K远点对(可能是我比较菜),原来只是用一个堆来维护,其实也是一道模板题。 Code: C++ #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define ll long long using namespace std; priority_queue<ll,vector<ll>,greater<ll> > Q; int n,m,k1,k2,D,k,root; ll ans; struct node { int l,r; ll mn[2],mx[2],d[2]; }t[100010]; ll sqr(ll x) { return x*x; } inline ......

BZOJ2648 SJY摆棋子

题目传送门 开坑!!kdtree Solution: 先来简单的讲一下kdtree,是一个支持n维空间的插入和查询K远点对的数据结构,其本质就是经过优化的暴力搜索,至于建树过程(百度百科里介绍的很清楚),我们就以二维为例:平面内有(2,1),(3,2),(5,7),(6,4),(9,6)这些点,我们先按x坐标排序,然后取中间点为分割点,将整个二维平面以经过该点平行与y轴的直线一分为二,其中左边有(2,1),(3,2)两个点,我们再按y坐标排序,取中间点,再将左边平面以经过该点平行于x轴的直线一分为二,右边也是如此,递归下去,并记录每个节点 ......

BZOJ1789Y型项链

题目传送门 Solution: 先考虑,如果只有两串项链,则显然,将它们同时删到最长公共前缀是最优的。可问题一共有三串,则对第三串的处理,我们可以先一直拆,然后再补到和最长公共前缀相同,其实你可以画一棵trie树来证明这个是对的。(显然此题和1830是完全一样的两题,水水双倍经验) Code: C++ #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int len[4]; char ch[4][100]; int main() { int ans=1e9; for (int i=1;i<=3;i++) { ......

BZOJ3065 带插入区间K小值

题目传送门 题目大意 带插入、修改的区间k小值在线查询。 题解 调了一下午,最后发现错误如下 正确的: C++ if (t[rt[k]].sum*alpha>max(t[rt[lson[k]]].sum,t[rt[rson[k]]].sum)) { if (tmp) { if (lson[k]==tmp) rebuild(lson[k]); else rebuild(rson[k]); tmp=0; } } else tmp=k; 12345678910 if (t[rt[k]].sum*alpha>max(t[rt[lson[k]]].sum,t[rt[rson[k] ......

BZOJ4521手机号码

题目大意 不包含4或8,且至少包含3个连续数字的数为合法的手机号码。问l,r区间内合法的手机号码有几个? Solution 这题是很显然的数位DP。当然,如果直接套dp方程可能会显得麻烦,所以还是用记忆化搜索。思路直接描述有点困难,所以直接看代码和注释。 代码 #include&lt;cstdio&gt;; #include&lt;algorithm&gt;; #include&lt;cstring&gt;; using namespace std; long long l,r; long long num[20][10][10][2][2][2]; int a[20]; long long dfs(int len,int p1,int ......