IEEExtreme 校内预选赛体会

试题

  • 题01:POJ 题目4031 http://poj.org/problem?id=4031
  • 题02:POJ 题目3766 http://poj.org/problem?id=3766
  • 题03:POJ 题目3820 http://poj.org/problem?id=3820
  • 题04:POJ 题目3097 http://poj.org/problem?id=3097
  • 题05:POJ 题目3859 http://poj.org/problem?id=3859
  • 题06:POJ 题目3452 http://poj.org/problem?id=3452
  • 题07:POJ 题目2995 http://poj.org/problem?id=2995
  • 题08:POJ 题目3884 http://poj.org/problem?id=3884
  • 题09:POJ 题目4000 http://poj.org/problem?id=4000
  • 题10:POJ 题目3988 http://poj.org/problem?id=3988

体会

我太弱了(第一声)

北京工业大学程序设计竞赛集训队一群有梦想的年轻人希望能在萌新的带领下走向人生巅峰

地址

OpenJudge – BJUT ACM(已结束)

体会

这是我自高一OI退役以后所参加的第一场算法竞赛。题目总共八道,送分的水题占了一半,考验选手能力的题目只有 C(单向链表的去重函数补写)、D(最大子段和)、E(平衡游戏,欧拉回路问题,HDU5882)、G(邻接表问题)。不过相较于 NOIP 复赛和省选而言,这几道题目的难度是远远没有达到的,不仅没有对多种算法、数据结构与数论的要求,也没有削弱题目结构的特点以模糊解题方向。

很惭愧,告别算法竞赛这么久,几乎完全忘记了之前所学的内容,以至于只完成了水题和平衡游戏。在 C 题的算法实现过程中,由于没有充分考虑到连续的重复元素输入,导致了去重不充分的情况出现。同时由于在 for 循环中大量使用break;以致于破坏了内存结构,并且没有在删除节点后进行 free 操作,导致了内存分配不合理。在 D 题的算法实现过程中,没有仔细读题而误解了命题人的用意,错误的将区间由硬币输入序理解为硬币价格序。对于 G 题,没有彻悟题意并简化模型,而是采用的暴力的方式,最终收获了 TLE、CE。

赛后经过与 licw 的讨论,终于明白了此题的神秘。根据题面,“定义:如果一个队伍里面,可以找到三个人,这三个人任意两两相互认识,或者任意两两相互不认识,那么这个队伍是缺乏创新力的;否则,这个队伍是富于创新力的。”假设我们现在有用户{a,b,c,...},那么对于用户a来说,剩下的人可以被分成“与A相识”和“与A不识”两个部分。由于鸽巢定理,我们易知,当n >= 6时,人群中至少存在三人且三个人任意两两相互认识或者任意两两相互不识。即对于任意n >= 6的情况,都是
Uncreative 的。所以我们只需要对n <= 6的情况进行判断即可。

在不可信网络下基于iodine建立DNS隧道

场景

不受信任的公共网络(如安装了审计设备的内网)、开启了WEB Portal认证的网络(如CMCC、ChinaNet)等。
注意:Win下直接使用iodine需要安装OpenVPN并且可能存在兼容性问题,建议通过虚拟机连接服务器然后开启端口转发。此外,网络速率与质量不会很高,延迟也会达到上百或数百毫秒。

原理

通过iodine将数据包封装为DNS请求,直接传输或通过DNS递归传输给自建的服务器再传送至互联网。当然,这个隧道只是联通了客户机与服务器,如果需要连接互联网,我们需要将本机通过位于服务器上的SS或SSH Tunnel等服务代理出去。

步骤

  • 获取iodine服务端与客户端,拥有一个公网IP地址的VPS服务器及域名。
  • 建立一个NS记录,如a.example.com值为b.example.com.
  • 建立一个A记录b.example.com,值为SERVER_IP
  • 服务端:执行iodined -f a.example.com,设置一个连接密码。
  • 客户端:执行iodine a.example.com,输入连接密码。
  • 完成连接,通过ipconfig(win)或ifconfig(Xnix)等命令即可看到一个名为dnsX的网络接口(X为连接序数,可以有多个DNS隧道在运行)。
  • 扩展

    iodine初步研究 – 小西的博客 | Xiaoxi’s Blog
    iodine README
    GitHub – yarrick/iodine: Official git repo for iodine dns tunnel

    毕业

    高考就这样结束了。
    我们终于抹去痕迹,离开这里,只留下在附中最美的记忆。

    总的来说,这是我高中三年以来发挥最好的一次——虽然仍有失误与遗憾。
    没有附中,我就不会取得这样的成绩。
    三年相伴,一生深情。

    None

    如果神明让我选择,
    我希望能“预知未来”
    还是“记住过去”?
    我选择后者。

    人类因为看不到未来,
    所以以为未来有无限可能性;
    因为能记住过去,
    所以会以回忆为食粮,
    让自己不断成长为一个更好的人。

    我们都是会出生、会死亡的凡人。
    我们用尽全力,
    也留不下那些注定要消逝的东西。
    但至少,
    我希望你所珍视过的东西,
    能以它最美好、最光彩夺目的姿态
    存在于你的记忆里。

    最后我要说,
    是我过去遇到的人们
    成就了今天的我。
    谢谢你们。

    ——Ocrine

    Status

    掠过两人之间的风
    捎来不知来处的寂寞
    哭泣过后眺望的天空
    有种格外的通透
    对温柔、笑容以及梦想的讲述方式都一无所知
    我只是跟随着你 做你的影子

    只要一点点时间就好
    再给我一点点时间就好
    真的只要一点点就好
    只要一点点时间就好
    再给我一点点时间就好

    我们是时间旅行者
    追逐时光的攀缘者
    厌倦了与时间的躲猫猫
    逃避时间的流逝
    喜极而泣 抑或是含泪欢笑
    都是因为你听从了内心的声音啊

    想要实现的梦想到今天就满100个了
    拿出一个来跟未来某天做交换吧
    平日里不曾交谈过的人
    今天放学后却对我说“明天见”
    偶尔有这种小惊喜也不错

    只要一点点时间就好
    再给我一点点时间就好
    真的只要一点点就好
    只要一点点时间就好
    再给我一点点时间就好

    我们是时间旅行者
    你的故事早已熟稔于心
    在比我记得我的名字 还要久远的以前
    你所不存在的那个世界 一定也存在着什么意义
    但是你所不存在的那个世界 就像没有暑假的八月
    你所不存在的那个世界 就像没有笑容的圣诞老爷爷
    你所不存在的那个世界啊

    我们是时间旅行者
    追逐时光的攀缘者
    厌倦了与时间的躲猫猫
    逃避时间的流逝
    别来无恙
    我这里一切都好

    我们是时间旅行者
    追逐时光的攀缘者
    厌倦了与时间的躲猫猫、逃避时间的流逝
    你真是个爱哭鬼啊
    我试图去阻止那眼泪落下
    但是你拒绝了我

    用那不断落下的泪滴
    喜极而泣 抑或是含泪欢笑
    都是因为我听从我内心的声音啊。
    ——《なんでもないや (movie ver.)》