about 3 years ago

喜大普奔琛琛终于用博客了

    发一个链接  各位可以去膜拜一下

http://clos.logdown.com

我可以赌上3升节操告诉你的是 , 虽然琛琛在博客中很谦虚 , 但他完全不是这样

我相信他写的东西一定很有(wu)用(liao)

还有个令人激动的好消息

我的另外一个好朋友也开了个博客, 他以前用的是似乎是CSDN然后被琛琛封杀了来着

据他说还没有一篇文章,但我相信他能写出不错的东西的

http://mambacrose.logdown.com

 
over 2 years ago

起源

自从 考出翔之后就开始想要发狠搞学习啥的... 然后就做了最新的一套题... 然后就没有然后了... 突然有种做这套题虚度人生的感觉.

Read on →
 
almost 3 years ago

今年NOIP怎么说还是很有意思的,不管从哪点来说。

Read on →
 
about 3 years ago

求满足 的最小的 .

这个就是个典型的问题 , 也就是我们今天所讨论的东西

Read on →
 
about 3 years ago

题意

给定一个n个节点的无权树,要在这棵树上选一些点建什么站,使得每个节点到他最近的站的距离不超过k

Read on →
 
about 3 years ago

很想来写点这个方面的东西。

的值 ,n,m ,p

怎么求呢

Read on →
 
about 3 years ago

这套题做了很久,又被见题就秒的一眼琛虐了。。。

B

题意

现在有很多个城市,有一个首都。首都到某些城市有火车线路。现在要你删掉一些火车站,满足每个城市到首都最短路的线路不会增加。问最多删多少个

思路

这个还是比较水的。跑一次SPFA,看看有多少个火车站到首都的最短路可以被替代。只是要注意一个火车站可能连了多条路

Read on →
 
over 3 years ago

给定一个n个数的序列,每个数均不超过c. 然后m次查询,每次查询l到r内出现了偶数次的数的数目。 (n,m,c <= 10^5)

恩,一眼就看到是分块。

将n个数分成根号n块,统计每两个块之间有多少个数出现了偶数次。

查询的时候块内O(1)出借,块边缘暴力,对于数i,二分出块内i出现的次数Ci,与块边缘的出现次数Di更新解

这个算法常数感人.

应该存在更优的解法: 比如按位置建主席树, 统计某个值域的出现次数, 查询的时候相减就好了. (纯属嘴巴)

 
over 3 years ago

看到标题就直接CLICK进去了,看完题目觉得压力山大。。。

题目讲的是这样一个意思:
n个方格,每个方格六个权值a,b,w,l,r,p

1.你现在可以将这个方格染成黑白两种颜色,如果这个方格染成黑色获得b的开心值,染成白色则有w的开心值。
2.如果对于某个 白格子j 满足 1< j < i,且 l[i] < a[j] < r[i] ,则会减少p的开心值。
要你求出最大的开心值。

显然第一眼看到就是最小割,源汇点分别表示黑白两种颜色,每个点向其连边,容量分别为b,w

这个题主要比较特别的,也比较烦人的就是条件2,对此有一个特别的方法:
对于每个点i,新建一个点i',i向i'连一条容量为p的边。
如果j是关于i的符合题意的点,i'向j连一条边。

这样整个图就初步构完了。 然而发现构图是O(N方)的,不满足条件。
由于a的取值在一定的范围内,我们可以构建一颗线段树优化时间。

而显然对于每个点都新建一颗树是不可能的,就想到了主席。

这个故事告诉我们,代码的实现是一条艰辛而漫长的道路,嗯。