（不定期更新，一般心情好的时候会咕）

2019-04-15

Merge的函数题，没有保存变量就直接elem[i] = elem[j++]，导致数据丢失。从22：06：04到23：26：41，提交共十次。

2019-04-16

大数阶乘，压位做法。在j从0到len遍历的前提下把res[j] *= i和res[j+1] += res[j] / MOD混在一起写，这样的运算顺序是有误的。从1：36到1：52。

最近点对问题。将Points_x与Points_y混淆以致造成了难以发觉的错误。疯狂对拍但几无成效，在四个点的情况下还是直接调试更能发现问题。一开始在Merge中使用了n导致超时。从18：30到20：00再到22：00。

文件名的问题倒是一下就能发现。

2019-04-17

有序序列中位数问题，一直纠结于二分，没想到顺序一下就成。思路没打开。

2019-05-06

凸包旋转卡壳的算法中，用$>$出现了问题，换成$\geq$则没事了。凸函数不一定严格单调啊。

调试时候把数组改小了记得做标记……不然看到RE很惭愧。

括号很多的时候记得检查，否则调试起来心情差。

2019-05-10

这一个标题下尽是，愚蠢的问题和糟心的状态……

5月8日期中考，旁边的人键盘敲得很响，想起了校赛时候的不适应，我的心境仿佛又回到了高中时代……偏执、疑虑、焦躁……今早的离散考试时状态亦复如是。

得冷静下来。这不仅是关于programming的问题了，它关系我的学习观，关系我对自己与他人的看法。Just admit it, scorn it, surplus it.

最后，“Cheers to the goddamn life, society, and everything.”

①他妈的”由裁判实现细节不表“！Sample都跑不起来的代码就交上去，这是计算机学院的学生做的事情吗？但不光是这一项，对dev的不熟悉，对于win7环境的不熟练还有内心世界的混乱都给解题的过程添了不少堵。一项一项的，都给我去死吧！

猪头临沂大学的漂亮代码是这样得：

1
2
3
4
5
6
typedef  int  KeyType;
typedef  struct {
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/
  int Length;
}SqList;
void  CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/

那这个CreatSqList怎么实现呢？从Sample可以看出是要先读长度，然后一项一项读进来。因为参数是(SqList *L)，所以下面都要用->，直接L.Length就报错。但是实践之后发现只能读Length，读elem就会报错，为何？因为没有分配地址。所以这笔函数要这么写：

1
2
3
4
5
6
7
8
void  CreatSqList(SqList *L)
{
	int i;
	L->elem = (int *)malloc(sizeof(int *));
	scanf("%d", &L->Length);
	for(i = 1;i <= L->Length;i++)
		scanf("%d", &L->elem[i]);
}

但是我一万年没有用malloc了，写这个函数的时候就慌得一批，之后想着要分配元素嘛，就写L->elem = 1000(int )…，但是这样是不行的。因为它elem啊，只是一个指针而已。

我不喜欢指针所以平时也不怎么用指针，自己写写代码基本不会有这方面的问题，但一到考试就凉透了！5月7日晚”复习“的指针完全没用。

这些几把考试不让查资料，所以把语法搞清楚很重要。血的教训！

②快排在5月7日晚上有“复习”，但是考试的时候还是一团乱麻。要理解快排，先要用例子建立直观的概念模型，从简单的例子到复杂的例子。简单的例子不包括重复项如“3 2 4 1 9 0 7”，还有不直观但容易调试的例子如“1 2”“2 1”等，乱七八糟的例子如“1 1 1”。理解之后是处理细节，考虑重复项他喵的该怎么搞，这样这样，基本就没问题了。

③有理数均值，特判！0/10这样的。要么在输出分母的时候加上去，要么把euclid写得更鲁棒一点，而不要少怀疑sscanf的有效性，虽然我之前的写法也很漂亮。

④整数分解，又是傻逼题一道……复习还是有一丁点用处的，因为当时也没有用心对待这题。本质就是个dfs，参数里设m——本次要分解的数，last——上次传下来的最大值，d——当前层数。对于;和\n搞个全局变量mark还有其函数专门处理。就这样，然后细节瞎搞。有的地方?:之类能让代码更简洁。

综上，关键词如下。高效复习、语法、模拟（从易到难、细节）、代码风格（优雅、鲁棒）、心态……

层层深入。

2019-06-10

今天补CF的状态……实在……一言难尽。题目是这个，看着很像密码题，它勾起了我关于ACTF的一些回忆……

一开始先是把题目看错了，不知怎地就把$p_{a_i}$理解成了$p_i$，导致处理$a_i$为质数和$a_i$为合数的方法产生了很大的分离，代码很冗长，而且写完后才发现有细节没想到，要处理非常麻烦。重新看题才发现是自己理解有误，只得把代码推倒重来。

之后是采用贪心的思路，分别用last_prime与last_composite维护$a_i$为质数/合数时$b_i$的index。但是在处理$a_i$为质数时，没有真正搞清楚变量的真实含义，以致屡出问题。在认识到所谓last_prime本质上是一个index后才对代码的正确性有了更深入的感受。

但这样还是碰到了一个很诡谲的error……本地测试没有问题，但是提交到服务器上便出错，此记录如下：

1
2
3
// origin
while(primes[nodes[last_prime].num] > nodes[i].num)
	last_prime--;
1
2
3
4
5
// polished
while(nodes[last_prime].num >= 200000) // caution
	last_prime--;
while(primes[nodes[last_prime].num] > nodes[i].num)
	last_prime--;

隐蔽的数组越界。以后在手工模拟是要尤为注意，越界与否，这样的问题。

在越界的问题上，还碰到了RE的问题。RE是因为题目中给定的n最大规模为2e5，但是输入的是2n，故而该规模需×2。在校赛时也碰到了类似的问题，还需要多加注意。

之后在跑一个点时出现错误。debug的思路为：判断output和answer中不一样的数，发现answer中一个位置为质数而output中对应的位置为合数。猜想nodes[last_composite].used = 0出现问题。调试发现last_composite对应的位置存在问题！last_prime确实可用贪心维护，但是last_composite并不能用贪心维护！于是手写了一个lower_bound，才得以通过此测试点。

然而这样还是碰到了TLE的问题。观察测试点发现它有相当多的重复数据。于是此时，lower_bound的复杂度会由二分退化为线性。需要添加记忆化的操作。至此，此题成功AC。

有何启示？明天再说……

2019-11-08

ds的bonus 2，再次在这些睿智课上感到了自己的睿智。

题目要求MST，我们的老师只给C，所以sort啊priority_queue呀用不了了。要么prim，要么kruskal。简单回忆了一下，前者要手打堆，后者要手写归并。因为不想手写归并，就手打堆了。把自己之前写的prim粘了出来，然后修修改改调了老半天，代码又臭又长，整整130行，交上去，一半点没过。

把手打的堆换成priority_queue试试看，然后还是有1WA2T。理论上不该T啊，prim不是适用于稠密图的么，那个WA又是什么情况。浪费时间猜想猜了半天啥也不懂。

assert半天，测了一下PTA速度，发现读3e5的数据就要个70ms，离谱。prim里面也没有死循环，应该就是复杂度炸了。（但是为什么呢，不懂不懂不懂啊）

搜题解，发现别人的prim里没堆，就直接搜。咱也不懂为啥这样能对……反正能对就能对吧，默写一遍……

还是有两个点过不去，memset啊assert啊又调了老半天，最后发现prim的松弛和dijkstra是不一样的……wsdsb。

心态得调整好啊还是。

2020-01-25

码个左偏树能wa两回，我是傻逼。

不是merge的问题，是pop的时候路径压缩的问题——不能把删掉的结点直接连到0，因为子孙可能连向了它（至于为什么，我就不清楚了，wtcl），而要把这个结点标记一下并放到图里。