重生学神有系统

    其他超参数的选择，激活函数的选择、损失函数的选择……也有诸多可用的方法、方案。

    除了一些前世接触过的方法，江寒自己也有过许多奇思妙想，琢磨出来不少乱七八糟的超参数选择方案。

    这次做fcn模板，索性将它们全都编写成函数，塞到了模板代码中，用以备选。

    除此之外，还要解决过拟合问题。

    过拟合是机器学习的一道难关，一旦发生这种现象，就会导致训练好的模型，在训练集上表现优秀，而在陌生数据集上表现欠佳。

    这是无论如何都要避免的。

    要想避免过拟合，通常的做法有:扩大学习规模、降低网络规模、对权重参数规范化，以及非常激进的dropout方法等。

    扩大学习规模，就是尽可能收集更多数据，进行训练。

    kaggle的这场比赛中，官方提供了足足20万条训练数据，这意味着不怎么需要在这方面下功夫了。

    如果提供的训练数据较少，那么往往就需要人为扩展训练数据。

    比如:将图像略微旋转、平移、翻转、缩放、加入噪点像素……

    降低网络规模，的确可以减轻过拟合，但同时也削弱了学习能力，所以一般不作为优先选项。

    权重正规化也叫正则化（regularization），就是在未规范化的代价函数上，附加一个权重绝对值的和，使得网络倾向于学习少量的、重要度较高的权重。

    这一办法，江寒在这个模板中，也作为备选项加以实现了。

    至于dropout方法，做法是按照给定的概率p，随机删除全连接网络中部分隐藏神经元，以达到简化网络，降低过拟合的效果。

    虽然挺简单，但江寒并不准备现在就用出来。

    这至少也价值一篇三区以上的论文，用在这种小比赛中，未免有些浪费。

    江寒将自己知道的、能想到的方法、方案，全都罗列出来，编制成函数，放进了模板代码中。

    然后将代码复制了130份，稍作修改，让它们分别使用不同的超参数设定策略。

    这样，就出炉了130种候选的训练方案。

    江寒将这些方案连同训练数据包，一起上传到了自己放在车库中的服务器和五台工作站中，然后指挥它们开足马力，同步进行训练。

    如果光靠笔记本电脑，这130份代码一个一个训练过去，怕不得两、三个月之后，才能轮一遍

    现在就简单了，大约明天晚上，这130多份方案，就能得到初步的训练结果。

    到时候根据反馈，从中选择一个表现最好的，全力训练就可以了。

    这种做法，和有些人选男/女朋友的原则差不多。

    广泛培养，层层选拔，然后择优录取。

    至于选剩下的怎么办

    先备着呗，反正又不吃草料……

    搞定这些事情之后，时间已经夜里10点半。

     




第256章 扩展欧几里得算法，以及增强线段树
    “七八点钟足够了。”熊磊率先表示赞同。

    朱达昌也点了点头，又说:“玩的太晚，两位老师也会不放心。”

    江寒笑问:“你们下午都这么有时间……今天不往回走了吗”

    朱达昌回答:“高老师预定了火车卧铺，是夜里10点发车。”

    李山河点了点头，说:“要等8、9个小时的车，这么长时间，不玩点什么也太无聊了。”

    熊磊解释说:“我爸爸的车实在不能凑合了，准备买台全新的高尔夫6，明天就去4s店提车，所以只能晚一天回去。”

    江寒了然一笑，熊爸爸那辆二手车，动不动就趴窝，的确早该换换了。

    想了想，对李山河、朱达昌说:“我不一定能送你们上车，今晚我可能就得往回走了。”

    “这么急吗好不容易来一趟松江，不好好玩一玩”李山河问。

    江寒坦然点头，说:“我是坐方便车来的，别人什么时候往回走，我就什么时候跟回去，总不能让别人将就我吧”

    其实要什么时候回去，还不是他一句话的事情

    但夏雨菲明天有课……

    “诶如果唱k的话，能不能让夏雨菲同学也来呀”朱达昌突发奇想。

    “就是的，江寒，你和夏雨菲好像挺熟悉的，帮忙邀请一下呗。”李山河也力促。

    江寒一阵无语。

    别说，还真可以考虑一下。

    小媳妇这次出来，光跟着自己跑前跑后了，也没玩好……

    也不知道她有没有意愿出来散散心

    江寒想了想，没把话说死:“好吧，比完赛我打电话问一声，能不能约出来，我可不敢保证哦。”

    听了江寒的话，其他人都十分期待，毕竟夏雨菲不光长得好看，在学校里也是有名的唱歌好听。

    但其实，江寒已经决定，顺便也叫苗清澜和关浩一声，愿意来的话，就一起热闹热闹。

    而且，出门在外的，指导教师们也不可能彻底放手，肯定都会跟着。

    这样的话，就不太好去一些环境太复杂的场所了……

    时间将到8点，赛场封锁就被解除，选手们再次鱼贯入场。

    其他流程和昨天大同小异。

    比赛正式开始。

    江寒拿到题之后，习惯性地全部浏览了一遍，然后从头开始做。

    今天的三道题，难度比day1高多了。

    但说实话，并没有超过他的预计，都属于那种稍微花点心思就能解决的类型。

    第一题是同余方程。

    【问题描述】:求关于x的同余方程ax≡1（modb）的最小正整数解。

    输入数据是两个正整数a和b，要求输出方程的最小正整数解x0。

    比如:输入3和10，输出就是7。

    数据范围:

    对于40%的数据，2≤b≤1000；

    对于60%的数据，2≤b≤50000000；

    对于100%的数据，2≤a≤2000000000，2≤b≤2000000000；

    输入的数据保证一定有解。

    江寒一打眼就看出来了，这是一道数论题。

    只要明白同余方程是怎么回事，就很容易理清思路。

    ，即ax的乘积除以b，余数为1。

    所以，对于任意给定的a、b，可以用穷举法暴力搜索，开始，每次递增1，很容易就能找出一个最小的x，使得方程成立。

    但因为a、b的取值范围特别巨大，这样做，会导致至少limitexceeded，即时间超限）。

    要想得到全部分数，必须想办法缩减运算时间。

    如果能找到这个算式中隐藏的规律，问题自然迎刃而解。

    当然，这需要拥有一点数论功底，才能办得到。

    江寒先观察了一下方程。

    原式等价于ax-，因为k值可以为负数，所以又可以看做ax+。

    显而易见，a与b一定互质，所以原式可转化为，这里gcd表示两个整数的最大公约数……

    咦

    这不就是扩展欧几里得的标准形式吗

    这样就简单了啊！

    欧几里得算法也叫辗转相除法，用于求最大公约数，属于小学奥数常见内容。

    有个基本性质:gcd=gcd。

    而扩展欧几里德算法，则用来已知a，b，求解方程的解。

    根据数论中的相关定理，解是一定存在的。

    所以，这道题只要用上扩展欧几里德算法，就能很轻松找到一组，使得等式成立。

    接下来，江寒根据算法，只花了五分钟，就编写出了对应的代码。

    其中的递归函数exgcd，就是扩展欧几里德算法的一种实现。

    用上了这种方法之后，编程难度大大降低，一共只用了10来行代码，就完成了解答。

    然后一调试……

    江寒就无语地发现，求解出来的x0，居然有时候会出现负值。

    这就不符合题意了。

    那么……为什么会产生这种情况呢

    江寒想了想，拿过一张草稿纸，简单地推理了一



第257章 NOIP中最难的题型
    本届noip的压轴题，一如既往的难度爆表。

    题目:疫情控制。

    （ps :由于题目较长，编辑后添加，不算字数）

    【问题描述】（梗概）:

    有 n 个城市，用 n-1 条路互连，构成了一棵树。

    1 号城市是树中的根节点，现在，根节点上爆发了一种危害性极高的传染病。

    为了不让疫情扩散到边境城市，也就是叶子节点，于是派出医疗队，在一些城市建立检查点。

    目标:从1 号城市到边境城市的每一条路径上，都至少要有一个检查点。

    医疗队可以在有路互连的城市间移动，并在城市中建立检查点。

    一支队伍只能在一个城市建立检查点，边境城市也可以建立检查点，但1 号城市不能建立检查点。

    医疗队移动所需时间，等于道路的长度，单位是小时。

    一个城市可以驻扎多个医疗队，不同的医疗队可以同时移动。

    现在，一些城市中已经驻扎有医疗队。

    求解:最少需要多少个小时，才能控制住疫情。

    【输入数据】:

    第一行，一个整数 n，表示城市个数；

    接下来的 n-1 行，每行 3 个整数:u、v、w，表示从城市 u 到城市 v 有一条长为 w 的道路。

    数据保证输入的是一棵树，且根节点编号为 1。

    下一行，一个整数 m，表示医疗队的个数。

    再下一行，有 m 个整数，分别表示 m个医疗队所驻扎的城市编号，其中任意m≠1。

    【输出格式】:

    只有一个整数，表示控制疫情需要的最少时间，如果无法控制疫情则输出-1。

    题目后面，还给出了一些输入输出的样例和解释。

    最后，是这道题的数据范围。

    对于 20%的数据，2≤ n≤ 10；

    对于 40%的数据，2 ≤n≤50， w大于0小于 105；

    对于 60%的数据，2 ≤ n≤1000，w大于0小于 106；

    对于 80%的数据，2 ≤ n≤10，000；

    对于 100%的数据，2≤m≤n≤50，000，w大于0小于 109。

    这很可能是最近几年来最难的一道题，思考难度超大。

    即使在noip历史上，也足可以排进难度榜三甲。

    而且有个很恶心的条件，不能停留在根节点。

    写代码的时候，一不小心就容易出错。

    至于解题思路……

    江寒全力开动脑筋，花了10分钟时间，才理顺了过来。

    医疗队可以同时移动，说明需要的总时间，取决于移动距离最长的医疗队。

    根据题意，需要最小化最大值。

    不能用模拟的办法，容易超过时限。

    江寒看懂题意后，第一个念头就是二分答案。

    求最大化最小值，最小化最大值，一般都可用二分答案。

    然后，可以在二分之后，使用贪心策略，将所有的医疗队尽可能上提。

    但是，数据范围太大了，直接一个个“上提”，肯定会导致tle（超时）。

    所以必须优化一下。

    这种”往上提“的问题，一般可以用倍增法来优化。

    具体到这道题里，可以用dfs（depth first search，深度优先搜索）算法，将需要用到的数值预处理一下，然后再倍增。