好像是历年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);
}
Join the discussion