喜大普奔琛琛终于用博客了
发一个链接 各位可以去膜拜一下
我可以赌上3升节操告诉你的是 , 虽然琛琛在博客中很谦虚 , 但他完全不是这样
我相信他写的东西一定很有(wu)用(liao)
还有个令人激动的好消息
我的另外一个好朋友也开了个博客, 他以前用的是似乎是CSDN然后被琛琛封杀了来着
据他说还没有一篇文章,但我相信他能写出不错的东西的
这套题做了很久，又被见题就秒的一眼琛虐了。。。
B
题意
现在有很多个城市，有一个首都。首都到某些城市有火车线路。现在要你删掉一些火车站，满足每个城市到首都最短路的线路不会增加。问最多删多少个
思路
这个还是比较水的。跑一次SPFA，看看有多少个火车站到首都的最短路可以被替代。只是要注意一个火车站可能连了多条路
Read on →给定一个n个数的序列，每个数均不超过c. 然后m次查询，每次查询l到r内出现了偶数次的数的数目。 （n,m,c <= 10^5)
恩，一眼就看到是分块。
将n个数分成根号n块，统计每两个块之间有多少个数出现了偶数次。
查询的时候块内O（1）出借，块边缘暴力，对于数i，二分出块内i出现的次数Ci,与块边缘的出现次数Di更新解
这个算法常数感人.
应该存在更优的解法: 比如按位置建主席树, 统计某个值域的出现次数, 查询的时候相减就好了. (纯属嘴巴)
看到标题就直接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的取值在一定的范围内，我们可以构建一颗线段树优化时间。
而显然对于每个点都新建一颗树是不可能的，就想到了主席。
这个故事告诉我们，代码的实现是一条艰辛而漫长的道路，嗯。
