距NOIP2017 72 天

And in my dreams, I meet the ghosts of all the people who’ve come and gone

在梦中又遇见那些来了又走的人

-High Hopes , KODALINE

本地的高中,所谓的重点班是提前开始上课的,很早。中考考完以后,便离开了那条老街,搬到了市东郊区的一个安静的角落。从此每天便早早起床,晚上很晚回家。

7月末八月初,从日照回来之后,晚上便去十楼的机房呆着。每天在机房颓废,刷题,吃外面小摊上的煎饼果子。偶尔写一些博客。有时候和学长一起打一打模拟赛,联机颓一会游戏,学习一些新的知识。

晚上回家会晚半个小时,学校里寂静的一片,只剩下我们几个人。骑车骑在路上,几乎没有什么人了,昏黄的街灯把已经不那么绿的树叶的影子投在沥青的马路上,市郊灯光很暗,晚上回家可以看到满天的星星,南面是发紫的天空,北面有闪烁不定的大熊星座。有时不自觉的想起⌈Ghost Stories⌋里面几首歌的旋律。

夜晚清新又寂静,想起那条老街,那家奶茶店,还有斑驳树叶影子和黄色白色灯光交错投下的人行道。

八月底的考试炸上了天,被班主任叫去谈话。心态比较爆炸,每天翻来覆去的想,在纠结。

大概我是属于那种比较在意的人吧,高一入学,想当然的认为一切都要完美的对待,可现实总是这么残酷。

每一天都在想,军训过的也挺纠结。没事就在塑胶跑道上面发呆,垂头丧气。果然各类活动和评优都没有我,淡淡的就回家了,放假了。

军训完回家的那一个下午倒头便睡,好久没有睡过那么长时间了。不知怎的,上了高一之后,就很少做梦了。这次却梦见了许多小学和初一做梦会梦到的东西,无声的,只有画面,也很像⌈盗梦空间⌋里所说的,记不清楚为什么就到了那个地方。

梦见了实验中学一直在现在第一实验小学的操场上,还是小学时代梦到过的,满地土渣,长着半米多高的草,南面长满参天大树的那个像工地一样的操场。南面入口还是被破败的砖墙和生着褐绣的绿皮铁丝网包围了起来。只有一座11层高的教学楼。走廊像那些快捷酒店,狭小无窗,结构错综复杂,走廊之间斜斜的交错着。没有想到教室,我在暖黄色的走廊中一直寻找着什么。进了数个洗手间、电梯,却又一直没有停下来,直到在一个东西向的走廊里看见淡黄色的墙上挂着几幅卫星全景图,才反应过来,这是一小的后操场,可东面又是潍河大堤。

还是那个熟悉的操场,好像在里面走,又好像在外面,从东面沿着一条坑坑洼洼,满是车辙和花花绿绿的塑料袋、垃圾的土路,骑着山地车,从位于东面的实验中学过来。还有那个熟悉的人,站在布满垃圾的大门口前,却永远看不清楚她的脸。

接着又是一个黑夜,在一条没有街灯的,四周布满了高高的树的沥青路上骑着山地车。前方,地面微微向上倾斜,好似这属于潍河大堤附近的一条路。后面有一个模模糊糊的骑着山地车的人影。好似我前面有一个减速带,我就从路的左面绕了过去。

下意识回头一看,居然是蔺神,还是穿着那身军训服,帽子遮住了上半张脸,露出那种惯常的不屑的神情,吓得我出了一身冷汗..

醒来已经是四点多了,既然是放假,不如放纵一下自已,去实验中学看看吧。大概,还有陪我长大的,生活了七年的老街?

为什么叫它老街,可能是因为它西面,发生了太多的故事了。

[SCOI2005]繁忙的都市

城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市C的道路是这样分布的:城市中有n个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连接。这些道路是双向的,且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值,分值越小表示这个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的要求:

1.改造的那些道路能够把所有的交叉路口直接或间接的连通起来。

2.在满足要求1的情况下,改造的道路尽量少。

3.在满足要求1、2的情况下,改造的那些道路中分值最大的道路分值尽量小。

任务:作为市规划局的你,应当作出最佳的决策,选择那些道路应当被修建。

大意就是用最小的代价把N个点的图变成连通图(要求1、2)

那么,N个点的联通图最小需要N-1条边,这显然是一个MST的题。

根据要求3,显然使用并查集维护的Kruskal更优。

那这就是个MST的裸题了……QnQ这么简单为什么还要发题解

关于s,可以知道它肯定是N-1 (N是点数)
 

CYOI第九届欢乐赛 BT

将一个二进制数最右边的1之前的部分去掉余下部分称为这个数的二进制尾部,例如6(110)2的二进制尾部为2(10)2  40(101000)2的二进制尾部为8(1000)2

写一程序计算A到B之间所有数的二进制尾部总和

输入

输入文件仅一行包含两个用空格隔开的整数AB,其中1≤A≤B≤1015

输出

输出文件仅一行包含一个整数表示要求的二进制尾部和。注意答案不超过64位二进制整数Pascal中的int64C/C++中的long long。

样例

Input

5 9

Output

13

 

大体思路就是计算出A-B中有多少个数的Lowbit是Kdec 然后把所有的 K 和 个数 相乘即可。

每隔四个数出现一次lowbit为2的数

每隔八个数出现一次lowbit为4的数

依此类推 则有

所以还需要打一个lowbit的表就行了

 

#洛谷 多米诺骨牌

多米诺骨牌有上下2个方块组成,每个方块中有1~6个点。现有排成行的
上方块中点数之和记为S1,下方块中点数之和记为S2,它们的差为|S1-S2|。例如在图8-1中,S1=6+1+1+1=9,S2=1+5+3+2=11,|S1-S2|=2。每个多米诺骨牌可以旋转180°,使得上下两个方块互换位置。 编程用最少的旋转次数使多米诺骨牌上下2行点数之差达到最小.

对于图中的例子(图挂了看luogu),只要将最后一个多米诺骨牌旋转180°,可使上下2行点数之差为0

设计状态f[n][k]为前n个骨牌翻转达到 上sum-下sum=k的最少翻转次数
则根据规则,第i个牌可以翻转或不翻转,

dp[i][k+upx[i]-downx[i]]=min(dp[i-1][j+5000],dp[i][k+upx[i]-downx[i]]);  //不翻转
dp[i][k-upx[i]+downx[i]]=min(dp[i-1][j+5000]+1,dp[i][k-upx[i]+downx[i]]); //翻转

最后找差值最小就行了,注意考虑对称
else if (minx==abs(i-5000)) ans=min(dp[n][i],dp[n][rever]);

 

 

Excited卡常数技巧

技巧1:编译优化

 

    1.使用inline

    inline函数只是对编译器的一个建议,最后是不是真正成为内联函数,还是要看Compiler。

    inline的使用是有所限制的,inline只适合函数体内代码简单的函数使用,不能包含复杂的结构控制语句例如while、switch,并且内联函数本身不能是递归函数

 

    2.使用rigister

    register关键字只是对编译器的一个建议,最后是不是真正存放在寄存器内,还是要看Compiler。

    使用register修饰的变量不能占太大的内存空间,或者不能使用太多register变量

    使用register修饰的变量不能用&取地址(没有内存地址)

    使用register修饰的变量不能为全局变量

    建议在循环变量和快速读入(又叫读入优化)的时候使用

 

技巧2:调用优化

 

    1.不传参

    明了简单。多用全局变量少传参。

    在STL Sort+自定义bool cmp()函数的双关键字升序排序和手写双关键字升序排序中,传参比较少的手写函数在200000数据的时候可以快0.07~0.1s,相当于跑四五次sort的时间了。(对此结果有疑问的,留下邮箱,发送测试文件夹)

 

    2.void类型的函数不写return

    玄学吧这个大概是(为什么好说倒装句山东人???)

 

    3.如果某变量只在一个函数中用到,尽量开成局部变量

    玄学。

 

技巧3:执行优化

 

    1.手写 不用STL

    不解释了吧。有些时候STL很慢,相见lrj紫书

 

    2.

 

    3.使用Fill (#include<iterator>)和 memset (#include<cstring>)

 

    这两个东西比for赋值要快。

 

    4.循环展开

 

    5.a[0]=a[1]=1;比a[0]=1; a[1]=1;快?

 

    玄学吧……应该没多大效果

 

    6.读入优化

这个没负数,自己加吧。

 

 

    7.运算优化

    double除法比int除法快

    bool运算比算术运算快

    减法比加法乘法快

    尽量快速幂

 

    8.可能的话,空间换时间

 

    9.不是很确定的方法

    &比return快???

Tarjan – 求解有向图的强连通分量 (SCC)

Robert E Tarjan是一个神人。

关于Tarjan求强连通分量的Blog一抓一大把,这里就推荐几篇吧:

#1   #2  #3 

看了这三篇我感觉差不多理解了。

然而还有一些问题

 

1.关于出栈怎么写

 

反正我是这么写的。

 

 

2.关于 Case 2 (牵扯Low定义的问题) 为什么不能改为  

可以看一下StackOverFlow ,和 POJ的 One Way Traffic这道题

StackOF上面给了一个证明,这里引述一下。

 

In tarjan’s dfs search getting lowlink(u):

lowu=min(low, low) (v isn’t visited)

or

lowu=min(low, dfn) (v is still in the stack)

My question is, is it still ok to replace dfnv for lowv in the second case? I know this is incorrect, but I failed finding a counter-example. Could anyone help explain this?

 

 

It’s correct, actually.

The proof of correctness depends on two properties of low. The first is that, for all v, there exists w reachable from v such that dfn<= lowv <= dfnv. The second is that, when determining whether v is a root, we have for all w reachable from v that low<= dfnw.

We can prove inductively that the first property still holds by the fact that, if there’s a path from u to v and a path from v to w, then there’s a path from u to w. As for the second, let low be the original array and low’ be yours. It’s not hard to show that, for all v, at all times, low’v <= lowv, so at the critical moment for v, for all w reachable from v, it holds that low’<= low<= dfnw.

I imagine that the algorithm is presented the way it is to avoid the need to consider intermediate values of low.

 

tarjan算法中low的标准定义是low= min ( dfnu , lowv , dfnw );

 

3.

有任何问题及时补充

欢迎评论来分享您的看法

A Set of Good Problems

One Way Traffic

Starry Night

Raucous Rockers

间谍网络

烹调方案

Cow Tours

关押罪犯

Mayan游戏

立体图

牛救援Cow Rescue

道路值守

所驼门王的宝藏

大陆争霸

HH的项链

Snake’s Round 2 Calculating

洛谷月赛 浮游大陆的68号岛

幻想迷宫 (原型:Codeforces Round 124 B:Infinity Maze)

过河

靶形数独

障碍路线Obstacle Course

玉米田迷宫Corn Maze

新魔法药水

O(n^3)O(n)标算 树网的核

#洛谷 尼克的任务

尼克的一个工作日为N分钟,从第一分钟开始到第N分钟结束。当尼克到达单位后他就开始干活。如果在同一时刻有多个任务需要完戍,尼克可以任选其中的一个来做,而其余的则由他的同事完成,反之如果只有一个任务,则该任务必需由尼克去完成,假如某些任务开始时刻尼克正在工作,则这些任务也由尼克的同事完成。如果某任务于第P分钟开始,持续时间为T分钟,则该任务将在第P+T-1分钟结束。

写一个程序计算尼克应该如何选取任务,才能获得最大的空暇时间。

好毒啊

 

好毒……毒……瘤

 

 

排一遍序,从后向前枚举每个任务的开始时间。如果和i相同则进行转移:        (f[i]表示以i时间开始的最小总工作时间)

f[此开始时间]=min { f[所有这个开始时间的任务对应的结束时间] } + 所有这个开始时间的任务中对应的延续时间 

如果f[d]没有任务可以开始做,则f[d]=f[d+1];

最后用总时间减去f[1]即可。

IOI1998 Starry Night 夜空繁星

BFS,超级麻烦

推荐A这道模拟方块转换

高高的星空,簇簇闪耀的群星形态万千。一个星座(cluster)是一群连通的星组成的非空连通星系,这里的连通是指水平,垂直或者对角相邻的两个星星。一个星座不能是另一个更大星座的一部分, 星座可以相似(similar)。如果两个星座有相同的形状,而且包括相同数目的星体,那么不管其方向性如何,就算相似。一般而言,星座可能的方向有八个,如图所示。(图片搬运自Luogu Online Judge)

 

 

懒癌了,我就贴上来吧……我用了一个特殊的表来判断是不是相似

详见代码

 

 

 

 

USACO 低价购买 Buy Low

这貌似是一道求最长下降序列的线性DP。

首先最长下降序列的状态转移方程是最简单的了QAQ

 

 

当然了f[i]默认值是1;

或者可以这样

 

接下来是统计方案 如果不计重的话貌似很好办,但要是计重的话,就应该倒推,如果前面的元素k和目前的元素i相等,那么f[k]==f[i],{这是因为统计了最长下降序列(如果是不上升序列的话还要稍微改动一下i对答案的贡献)}

所以k对答案的贡献应是和i相等的,这时可以把i对答案的贡献去掉了,因为以i结尾的组合把i换为k都成立这是由于由k结尾的最长下降序列的方案数只取决于k前面的几个元素(不同元素的组合)而与k无关

 

从而得出整个状态转移方程:

注意这里n初始化为1,组合数必定大于等于1

所以,完成了全部程序: