[总结]2017年4月4日的考试

好像是历年CQOI

心路历程

首先拿着卷子看一遍。。。
咦最后面的题目分值更重?
咦第四题好像很熟悉的样子?

感觉第四题很可做啊,其他题感觉也可以骗分啊,
先把第四题搞了!
然后卷子下来5分钟我就开始码第四题的费用流了,(JeremyGuo这时以为我在做第一题,然后看我那么快就开始码了,于是他觉得第一题很可做。。于是他就努力想了30分钟就AC了。。)

咦过不了样例2???
调一波,于是30min过去了
咦我的思路好像完全错了。。。
突然感觉有点怂。。重新想了一遍发现已经过去1h
好像搞到了一个解法。。写出来还是wa掉第二组样例?
思路又错了?先试试别的写法。。
然后又过去40分钟。。
哇塞我连边时写错了一个细节!手残可以卒千年啊啊啊啊!
改过来就过样例了,感觉对拍很难写呀。。又比较自信就没写对拍

看看好像比较可做的第二题。。
斜率优化?二分?但是那么多二次函数家在一起怎么二分(傻了。。二次函数加二次函数还是二次函数啊。。)
感觉5道题有点怂啊。。貌似暴力可以有40分?
然后。。我突然脑洞了。。。
这题可以写粒子群!(PSO)

前两个星期我搜题解时看到PSO,于是顺便看了一眼别人写的粒子群算法的博客,马上就被这算法的玄学正确性和简洁性吓到了,感觉好神奇啊!然后JeremyGuo看到我在看粒子群觉得这算法好神奇啊然后顺手用这个算法AC了一道题

虽然已经想到一个搞出中点后再每段上二分的方法(这其实几乎就是正解。。),但是觉得好像有很多细节啊。。写出来也可能挂
PSO再OI中没被用过吧。。写一个?
好吧写一个!(激动)
代码非常简单,没有细节,20min就写完过样例了。

然后第一题?数学?数位DP?Trie?(你满脑子都是什么。。)
枚举?貌似这个数字比intmax还大了。。
感觉不是很可做,先码个暴力吧
10min完事

11点了,还有两道题没搞
看一下第五题吧。。
想了15min,毫无头绪,感觉这题不是我力所能及的,写暴力吧。。
暴力又wa了,30min才写完调完

看最后没写程序的第三题
感觉。。。先二进制枚举接那些任务,然后用DP判定?(啊啊啊已经很接近了啊)
就那么写吧。。
写这题速度奇慢,考试快结束的时候智商日常下线。。写着写着又觉得细节暴多。。
感觉写不出来了,现在只有20min了,放弃吧
总得再这题写点骗分啊。。干脆直接输出接全部任务的收入吧!

最后20min,鉴于第四题没写对拍,虽然信心满满还是检查一下
突然发现第一题可以打表!赶快5min打了应该有70分。
文件输入输出。。
结束了,交了

开始评测

第一题爆了?文件输入输出没写是什么鬼。。加上后70分
第二题PSO拿到40分。。后面大一点的数据精度不够
第三题直接输出接全部任务的收入拿到10分蛤蛤蛤蛤
第四题AC,但是何老师好像没有改分值,120->100分
第五题暴力wa了??? 0分

事后

JeremyGuo究极大神A了三题还说我们D他不要脸。。
SunIsMe暴力写的比我好多啦。。然后多拿了40分暴力
Ender好像和第一题数学题杠了3个小时,最后没杠出来。。爆炸了,节哀
Ender:”我已经吧所有数字的前6位的规律找出来了!但是就是找不出最后一位的规律啊!”

这次考试考得是重庆原题,难度应该差不太多吧。。但是第4题好像讨论过?
代码正确性还是不够。。暴力又写挂一个,以后写暴力都得小心点了。。
写暴力时有点太急躁了,写着写着有时又会去想其他题目的解法,写一道题就要专心写,不要太贪或三心二意
对题目的取舍这次把握得比较好吧?
后来发现,只要打2h+,第一题100分的表是可以用暴力打出来的。。
一开始见到自己熟的题还是不要太激动了,其他题目也要分点时间想一下,想不出来想点能拿很多分的非正解也是可以的

还是有些小遗憾啊。。暴力写挂一个,PSO没达到我的期望

重头戏:如何用PSO(粒子群算法)AC第二题!

组装

数轴上有 m 个生产车间可以生产零件。一共有 n 种零件，编号为 1~n。第 i 个车间的坐
标为 xi，生产第 pi种零件（1<=pi<=n）。你需要在数轴上的某个位置修建一个组装车间，把
这些零件组装起来。为了节约运输成本，你需要最小化cost(1)+cost(2)+…+cost(n)，其中 cost(x)
表示生产第 x 种零件的车间中，到组装车间距离的平方的最小值。
数据范围 N<=10000,M<=100000,Xi<100000

结题报告

先来形象地解释一下什么是粒子群,以下文字由Hineven原创

粒子群算法是一种进化算法,其大题思路是模拟大自然中鸟群捕食的思维模式,每一只鸟会记住自己亲眼所见的食物最充足(局部最优)的地方,也知道整个鸟群所发现的食物最多的地方(全局最优)。
每只鸟的动量都会受到这两个’最优’位置的影响,它整体上会选择向这两点靠近,从而寻找一个食物更充足的位置,而食物最充足的位置往往就在附近。

先在,每一只鸟变成了一个粒子,鸟群所处的三维空间升级到/退化到K维空间(这意味着空间中的每个点/粒子代表K个实数描述的决策方案),粒子动量受’自我意识’和’群体意识’以及随机性的影响在空间内移动,每个粒子存在’惯性’系数保证在每个时刻速度不会过量突变,模拟粒子飞行,粒子们可以有效地搜索一个连续的K位函数f在该空间内的最大/最小/某一个值。
但是,粒子群可能陷入一个局部最优解,所有粒子被吸入一个巨大的函数波谷中无法脱身,现在可以选择:
1.变异,极小几率地使一个粒子的位置或动量发生较大的随机变化。
2.重新初始化粒子群进行新一波搜索

我不是很服啊。。粒子群表现这么差。。
于是把每个粒子的质量改大到2.5,还是wa掉两个点,(就是差最后0.0001可能四舍五入刚好在中间然后差了一点就爆了,为什么不SPJ!)
JeremyGuo来调了一波自我意识等参数(面向数据编程),还是wa掉两个点。。
调了三十分钟的参数。。依然wa掉两个点
然后JeremyGuo放弃了。。
记得一次看遗传算法时看到有’变异’操作让遗传算法不会陷入最优解?
粒子群也适用么?
于是我在每次迭代时给每个例子加上一个很小几率发生的’变异’时间,让它的动量变成与原来反向
试了一下,果断AC啊啊玄学啊啊啊!!!

然后乱改了一下其他参数,发现10个点至少能AC7个,质量取到1.8~2.x就能直接AC全部数据!
神啊!
然后就在OJ上吧这题用粒子群过了
从来没想到这种比较无脑的神奇进化算法也能进入ACM!好像我们OJ内没有人尝试过粒子群算法!

以后记得质量开到2左右,考试时就算想不出正解就可以写个PSO又简单又愉快地骗分了!

代码很简单,实现无细节!

代码

#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
using std :: vector;
const int MAXN = 10010;
const int MAXM = 100010;
vector<int> poses[MAXN];
int N, M;
inline long double random01 () {
    return (long double)(rand()&65535)/65535.0;
}
inline int rand65() {
    return rand()&65535;
}
namespace Particles {
    long double getValue (long double p) {
        long double ret = 0;
        for(int i = 1; i<=N; i++) {
            vector<int>::iterator it = lower_bound(poses[i].begin(), poses[i].end(), p);
            int pos;
            if(it == poses[i].end()) pos = *(it-1);
            else if(it == poses[i].begin()) pos = *it;
            else {
                if((p-(*it))*(p-(*it)) > (p-(*(it-1)))*(p-(*(it-1)))) pos = *(it-1);
                else pos = *it;
            }
            ret += (p-pos)*(p-pos);
        }
        return ret;
    }
    const long double PER_TICK = 1.0;
    struct Unit {
        long double self_awareness;
        long double family_arareness;
        long double pos, vec, mass, bes;
        long double bval;
    };
    vector<Unit> units;
    long double bespos;
    long double besval;
    void runTick() {
        for(vector<Unit>::iterator it = units.begin(); it != units.end(); it++) {
            Unit u = (*it);
            (*it).vec = u.vec*u.mass +
            (u.self_awareness*(u.bes-u.pos)*random01()
             +u.family_arareness*(bespos-u.pos)*random01()*(rand65()>65000 ? -1 : 1));
            (*it).pos += (*it).vec*PER_TICK;
            long double now = getValue((*it).pos);
            if(u.bval >= now) (*it).bes = (*it).pos, (*it).bval = now;
            if(besval >= now) bespos = (*it).pos, besval = now;
        }
    }
    void generateUnit (int range) {
        Unit u;
        memset(&u, 0, sizeof u);
        u.self_awareness = random01();
        u.family_arareness = random01();
        u.mass = random01()*(long double)2.5;
        u.pos = (rand()%range)-(range>>1);
        u.bval = 1999999999999999.0;
        units.push_back(u);
    }
}

int main () {
    srand(20010627);
    scanf("%d%d", &N, &M);
    for(int i = 1; i<=M; i++) {
        int x, k;
        scanf("%d%d", &x, &k);
        poses[k].push_back(x);
    }
    Particles :: besval = 1999999999999999.0;
    for(int i = 1; i<=65; i++)
        Particles :: generateUnit(40000);
    int rrr = 54;
    while(rrr--) {
        Particles :: runTick();
    }
    printf("%.4lfn", (double)Particles :: bespos);
}