SGU 103 Traffic Lights

题意

http://www.nocow.cn/index.php/Translate:Sgu/103
翻译版,这里不重复劳动了

思路

这个题的可怕之处不是有多难想,而是虽然基本模型很简单就是图上最短路,但是这回有许多许多的限制条件。
正确地计算当前灯的状态是这个题最大的难点,我采用的方法是(其实我写跪了,李大神给我捞上来的):首先把到这个路口已经消耗的时间减去题目给的初始时间,我叫他有效时间,接下来把这个有效时间模上两种颜色的灯持续时间之和,剩下的时间是对灯的状态真正有影响的时间,接下来分别脑内模拟一下站在这个路灯时如果是紫色最后会怎么变,如果是蓝色会怎么变,然后基本就可以写出这个时间和最终颜色的关系了,还可以得到最终这个颜色还能再持续多长时间,这两条非常重要,一定要搞对。
接下来的难点就是计算从当前点移动到下一个点之前等待两点灯的颜色同步的时间,算这个就要依赖于上面的两个值:当前颜色和当前颜色还剩多长时间,假设我们要从A点移动到B,已经走了tim时间,那么我们就要分别计算A点和B点在tim时的这两个数据,然后如果AB在tim时颜色正好相等,那么无需等待直接通行,所以等待时间为0,如果颜色不同呢?只要看A和B哪个剩余的时间短,这个就是等待时间了。要是剩余的时间又一样?那就要脑内模拟一下了,然后发现我们可以再比较A的下一颜色和B的下一颜色谁的持续时间短,等待时间就是剩余时间+最短的持续时间。如果下一个颜色还一样,那就比较下下个颜色。要是还一样?对不起,hehe了,走别的吧~(所以说这个题很sxbk)
接下来是最段路部分,我们把权值设定为走到这个点要花多少时间,从当前点走到下一个点时,下一个点的可能值就是(当前点已用时间+等待两个点的灯同步的时间+路上消耗的时间),以此为基准进行松弛操作。

接下来上代码

 

Codeforces 118D Caesar's Legions

题意

给你两种士兵,n1个A和n2个B,同种士兵是一样的,不分先后,然后你最多能把k1个A排到一起k2个B排到一起,问你有多少种有效排法。

思路

动态规划,建一个三维dp数组,其实是一个二维的表,每个格子有两个值,dp[i][j]表示截至目前只使用i个A,j个B来进行排列,dp[i][j][0]表示以A结尾的排列序列个数,dp[i][j][1]表示以B结尾的排列序列个数,之后我们来转移状态,对于当前的以A结尾的排列,我们可以再其末尾加1~k2个B,构成新的以B结尾的排列,所以我们就可以把dp[i][j+k][1]更新了(k表示加几个B)。同样的,用B结尾排列个数的值更新之后的A结尾排列个数的值,把这个表这样逐步打好,最后输出dp[n1][n2][0]+dp[n1][n2][1]即可。

接下来上代码

 

CodeForces 347C Alice and Bob

题意

两个人互相玩,他们先搞一个集合,里面几个不同的数,接下来随便挑俩作差,如果差的绝对值集合里没有,就给这个差的绝对值加进去,直到集合加不进去值为止,没招的那位就跪了。

思路

写几个数模拟一下就会发现,游戏结束时,集合里面是所有的初始几个值的最大公约数的倍数,举个例子init={2,6,8},gcd=2,final={2,4,6,8},利用这个规律我们就可以知道最终集合有几个元素,最终元素个数减去初始元素个数就是这场比赛将在多少手之后结束,接下来判断奇偶就可以判断谁赢了。

接下来上代码

 

从零开始,把Raspberry Pi打造成双栈11n无线路由器,支持教育网原生IPv6

准备工作

  1. Raspberry Pi一块
    • 要求已经刷写好了Raspbian系统,关于系统的刷写/无显示器配置这种事情,请参照这里,这里不想多说。
  2. USB无线网卡一枚,一个合格的USB无线网卡最好是不用USB HUB就能稳定运作的,插上之后,在终端机中输入ifconfig输出内容中应该有出现wlan0字样。
    • 无论你有没有现成的USB无线网卡,都请查看USB无线网卡对RPi兼容性列表来确定自己的USB无线网卡是不是支持RPi,如果是杂牌的话,要想办法看到自己的USB无线网卡的芯片型号,然后对照这个表里面有同样型号的无线网卡的兼容性说明。如果你现在无线网卡的芯片在这个表里面不是针对Raspbian out of box的,买买买,不要停~
    • AP功能是一定要有的,如果有11n的话更好(后面会讲如何设置),目前来说直到RPi 2 Model B都没有实装USB 3.0所以没有必要买ac的无线网卡。
    • 我用的是Tenda W311U+,这款有个天线,不过貌似也没啥太大的效果,用起来蛮稳定,速度一般(即使打开了11n机能)
  3. 外网,这篇教程针对的是没有认证的,原生支持IPv6的教育网,有固定IP。
    • 如果你的网络需要认证客户端的话,可以找个借口(用mac什么的)把认证取消,取消不了的话。。。别折腾了~(当然如果你真想折腾,openwrt社区里面会有dalao提供linux的模拟验证客户端,但是这个不在本文讨论之列)
    • 如果你是ADSL用户,本文没有拨号设定,IPv6也需要tunnel,这种情况,建议移步这里
    • 如果你不想折腾IPv6有关机能,忽略本文的IPv6部分即可,同样的,不想开11n的话,也可以忽略本文的11n设定部分。
  4. 确定你的有线无线网卡代号,在终端机中输入ifconfig就可以看到当前连接的所有网络接口,有线网络一般是eth开头,RPi的自带网卡一般是eth0,你连接的无线网卡一般是wlan开头,只插一个的话就是wlan0,这个是给内网用的。下文中的eth0和wlan0就是这么来的,如果不一样的话请自行翻译~

开工!先来配置IPv4无线路由

配置网络接口

在终端机中输入sudo emacs /etc/network/interfaces打开网络接口配置文件,狂按Ctrl+k清除全部内容,然后写入一下内容,完成后按Control+x,Control+c,y保存退出(放弃更改的话Ctrl+x,Ctrl+c,n,yes<换行键>)。

配置好之后,随便ping个网站看看能不能通外网,可以的话继续~

配置外网DNS

终端机中输入sudo emacs /etc/resolv.conf,在里面按下面的样子加上你需要的DNS地址

安装必要的软件包

这里假定你已经可以流畅的链接你的apt软件源了,如果官方源慢的要死就需要换源了,换源教程在这里
按你的需要在终端机中(有选择性地)输入如下命令:

编译工具

即便装了一堆也有可能发生有软件包装不了的情况,不过本文提到的需要编译的软件基本都能过。

编辑器

这俩选一个,或者都不选用系统自带地nano,我用emacs,我不想挑起战争~

AP与IPv4机能

 

IPv6机能

软件包

本文使用NPD Proxy和DHCPV6实现IPv6机能。

编译安装npd6

配置hostapd以使用无线网卡软AP

在终端机中输入sudo emacs /etc/default/hostapd,打开之后找DAEMON_CONF="",把这行首的#去掉,然后把这句话改成DAEMON_CONF="/etc/hostapd/hostapd.conf",保存退出。
在终端机输入sudo mkdir /etc/hostapd,然后sudo emacs /etc/hostapd/hostapd.conf,把文件内容(有的话清除,没有的话就从头写)改成(请仔细看注释有选择性地写~):

打开系统的IPv4转发功能

在终端机中输入sudo emacs /etc/sysctl.conf,直接在文件头写入以下内容:

然后退出回到终端机输入sudo sysctl -q让修改立即生效。

配置DHCP服务器实现内网IPv4地址自动分配

终端机中输入sudo emacs /etc/udhcpd.conf,你需要去掉下面这些行首的#来解除注释,然后按照自己的配置方法修改,注意要和interfaces文件里面wlan0的地址设定一致:

写一个bash脚本来一键打开无线路由机能,开机自动启动

在终端机输入emacs ~/router.sh,接下来写入:

保存,然后修改一下权限让他可以执行,输入sudo chmod 755 ~/router.sh就可以了。
接下来输入sudo emacs /etc/rc.local,在文件的末尾的exit 0这行上面,添加sudo /home/pi/router.sh保存退出。

重启测试

输入sudo reboot,不出意外的话重启之后你的设备可以正常连接你创建的无线网络上网了,802.11g,仅支持IPv4网络。
接下来会将IPv6和802.11n机能的开启,如果你有需要的话可以继续阅读。

配置IPv6实现无线双栈网络

查询外网IPv6地址和网关

Mac下可以插有线网络的话直接在设置里查看就可以了,Windows的话,命令行中输入ipconfig -all,如果你直接在RPi上看,终端机输入ifconfig就够了。纪录2001开头的IPv6地址和网关地址(我这里是fe80开头,有的情况下是2001开头,这个没关系,网关显示什么就记下来什么),Windows下IPv6地址后面可能会显示/64这个是prefix长度,这个也要记下来。

E560B6BE-A1F7-4730-B090-A06977F53DE8

修改sysctl.conf打开IPv6转发

终端机中输入sudo emacs /etc/sysctl.conf,然后添加:

改写router.sh,加入IPv6配置信息

在终端机输入emacs ~/router.sh,接下来写入:

注意,上面这些东西加在service这行前面,上面这5行中,2001:250:3000:3cc6:ba27:ebff:fee6:ce6c是我查到的公网IPv6地址,这个要原样打进去,/64和/126也不能变(除非你的网络非常特殊,64可能要改成你查到的perfix长度,126是不能动的,防止错乱),接下来2001:250:3000:3cc6:1::/80这个是你内网用的IPv6地址,前面四段要和你查到的公网地址保持一致,后面的那一段是你的内网网段,填1就可以了(当然你换什么填什么),接下来那个fe80开头的地址换成你查到的网关地址,这样就搞定了。

配置radvd

radvd的作用是使内网客户端能自动获取IPv6地址。终端机中输入sudo emacs /etc/radvd.conf然后写入:

注意上面的2001开头地址要换成你刚才设定好的内网地址。

配置npd6

npd6是邻居发现代理,是让内网客户端可以自动获取IPv6地址的。终端机中输入sudo emacs /etc/npd6.conf然后写入:

原文件中可能会用好多注释,不过没关系你只要对照上面把有效部分修改好就行了,注意2001开头那个地址要填你自己的

配置DHCPv6

DHCP是啥不用我多说了吧。终端机中输入sudo emacs /etc/wide-dhcpv6/dhcp6s.conf然后写入:

重启测试

sudo reboot,IPv6配置至此结束,没有异常的话在这里应该可以看到下图了吧。

D6A7F186-4E98-448E-A1E3-9E66BE9B4630

配置802.11n机能

检查无线网卡支持哪些802.11n机能

在终端机中输入iw list | less之后你应该会看到一堆,我们只关注开头Capabilities的这部分,一般长得像这样:

你要把这一段记下来,之后按q键结束。

修改hostapd配置文件增加802.11n机能支持

sudo emacs /etc/hostapd/hostapd.conf然后修改两行:

你去要重点关照的就是ht_capab这一行,这一行输入的越全面,你得到的速度就越快。
我在下面引用了官方文档的配置802.11n的部分,你可以对照这个和记好的iw list数据决定填什么,填好之后保存。sudo service hostapd reboot如果提示成功,说明配置没有问题,这个时候应该可以享受到高速度了,如果FAIL了,请仔细检查ht_capab是不是填写错了,如果实在不行,就删掉不确定的项,牺牲一些速度吧。
hostapd详细的配置方法可以参照官方文档,其实hostapd可以支持802.11ac的,但是问题在于USB2.0的传输速率使得在RPi上用ac没有意义。

收工

至此本文的目的已经达到,have fun!

本文系hahaschool原创,转载必须注明出处。

 

CodeForces 484B Maximum Value

在lower_bound之后如果加入了多余的判断(判断pos的位置等等),就会T,如果没有用unique来压缩输入,就会T。

总觉得很寸,应该是数据做的有漏洞。

解法的思路就是先从小到大排序,然后从第一项开始,借用素数筛法的思路,对于每个数检查以这个数的倍数为终点的各个区间,然后找出每个区间之内离终点最近的数,更新答案。找终点的过程使用了二分搜索,STL自带的lower_bound和upper_bound就能很好地工作,使用upper_bound的话还有一个小窍门就是把搜索目标设成目标-1,这样的话搜索完落在的点就和lower_bound是一样的了。

CodeForces 463C Gargari and Bishops

最后还是没有了尊严,去看题解了。。。
http://blog.csdn.net/kenden23/article/details/38959141

这个题告诉我们了关于交叉坐标和对角线的性质,要想很好地做过需要很多优美的姿势-_-#。

CodeForces 475B Strongly Connected City

强联通分量的题,建图搞定了就搞定了。关于scc的算法可以翻我的图论标签找一下我写的一篇tarjan算法总结。

ZOJ 3686 A Simple Tree Problem

被这道题玩得相当惨。。。这道题是一个DFS+线段树的题。

首先这个题是在一棵传统树上面进行大规模的区间读写操作,这是线段树的玩法,但是怎么玩呢?
这个时候DFS就派上用场了,我们通过DFS得到DLR遍历,把dfs时进入一个节点是时间记下来,出去一个节点的时间记下来,就可以得到这个节点的子树在DLR遍历中的区间的开始与结束标号,这样就相当于把2维的树降到一维了。
之后得到了一个一维的数组,就可以开线段树,这里涉及区间更新,还要加开懒惰标记。
这种把树压成线然后再搞是一种很常用很好的姿势!

其实这道题卡死我的就是懒惰标记这里。我原来一直在用zkw线段树,但是因为是自下向上操作没有递归,所以我就根本不知道怎么下手写懒惰标记了,鼓捣2天未果,orz各路大神的适配zkw线段树的懒惰标记是给rmq准备的,不适合这个题,没办法研究递归版本了。

递归版本的话,实现懒惰标记的思路就是:
1.更新时,如果发生了目标区间与当前区间相交的情况,首先把当前节点的懒惰标记下传给下一层,然后再去更新下一层,更新完下一层后,用更新好的下一层更新自身。如果目标区间完全包括当前区间,这个时候就不用往下走了,首先更新自己的值,然后更新自己位置的懒惰标记。
2.查询时,如果目标区间和当前区间相交,这时候需要下传当前节点的懒惰标记,然后进入下一层接着查询,如果目标区间完全包括当前区间,直接更新答案。
3.下传时,我们只操作当前节点的子节点,不可以操作当前节点(否则就重复操作啦),注意我们只下传了一层,所以不仅要操作下面一层的值,还要操作下面一层的懒惰标记,同时清空当前节点的懒惰标记。

Scroll to top