清北省选模拟考试

杂记

day1

T1: 点分治，没写过，只写了暴力。想到了只有1的不会写。。正解：点权是2^15，拆成15个0/1.
T2：暴力
T3：
想到了dp转移方程，但是有后效性，推式子，变换一下，然后只会只有一个h相等的。
临近考完时最后发现一个bug，改了过来。然后在最后一遍检查是否过样例时，发现，过不了样例，慌乱的调了一下，还是不过，由于时间到了，就交上了。交上后一分钟调了出来。
先交上的10分，调出的20.

最后：找到bug后，测试一下以前的样例，不要拆了西墙补东墙，改了旧bug，有了新bug。

day2

T1 枚举操作顺序的全排列，取最小值，不知道哪里挂了。
T2 打表到10，数据是20。。。
T3 一个细节，要不是大1就是小1，与答案相差很小。

zz的我
1、T1 中Li有全是0的，即截止时间都是0，想到按T排序，从小的往大的取，然后对这个贪心不确定，于是证明了一下：
对于每个任务，假设都在0时刻完成。那么收益就是0。对于第一次要做两个任务a,b，Ta < Tb，如果先做b，那么后面所有的任务的工作完成时刻要加Tb，即0-Tb*(n-1),先做a，那么后面所有的任务完成时刻都加Ta,0-Ta*（n-1），显然先做a，代价是-Ta*(n-1) < -Tb*(n-1)，
所以先做a更优。
然后按T排序后，可以求出第一天的，往后每天修改一次却不会写了。

其实这个贪心对于所有的数据是可以的。。。按照此贪心，可以暴力小于等于1000的。

2、T3中有20分，m=1，即要求[l,r]中，是否有>=x的数，有就是0，否则就是1。
当时的思路：

• 判断是否有大于等于x的，那么可以求x在这个区间的排名就好了。可以先把x排序，然后找大于等于x的，有没有在区间[l,r]的。但是不行。
• 求出x在区间[l,r]的排名,还可以用主席树，做，但是只写过一次主席树，于是就艰难的默写了。调试了好久，终于调出，然后试了几个样例，发现有个老是过不了，调试，发现，主席树是用权值，而这个题权值是1e9，，，不行。
• 然后求最大值，又想到可以用splay做，取出，[L,R]，这段区间，然后把这段区间放到根节点的右儿子的左子树，找到最右边的点即最大值，然后写出。，，之后发现若用下标建树，那么最右边就是R这个点，用权值建，无法取出一段区间。。。
• 最后没写出。。。。。

其实求一个最大值，线段树就行了。。。。。用splay按坐标建树，维护个最大值也可以。。。

最后：集中注意力写代码，调代码，想问题，扩展思路

day3

T1 输出格式居然有误，，，如果输出-1，是printf("-1\n");然后下面还有一个puts("");
T2 50分matrix-tree 定理，高斯消元卡精度。。k=1的测试点也错了。。
T3 25分的，没过样例，莫名其妙得了25分。

zz的我
1、T1思路：
对于k<=100暴力（加了记忆化）

对于a=1，c=0，即$f(x) *b = x -- （1）$，转化一下即$f(x)=\frac{x}{b}$，那么满足（1）式的前提是，x是b的倍数。所以枚举b的倍数即可。然后判断是否等于x，然后发现如果b太小，那么复杂度也不行的。又想了会，发现，f(x)最大是72，（算错了其实是81，考场上我直接用的100），然后由（1）式，x最大是100*b，所以枚举b的倍数即可，最大到100*b。

对于b=1，c=0，
$f(x)^a = x$，还是转化一下，$f(x)=\sqrt[a]{x}$
那么x是开出后是整数，所以$x=i^a,i=1,2...$
那么a<=5，x<=1e9,所以a=2是，i最大枚举到1e5不到，a=3的话，才1e3。但是等于1的时候就很大了，于是又想了一会，求$f(x) = x$，又想到了前面的性质，f(x)最大100，所以枚举f(x)，到100好了。

全部的数据，和上面一样，开根，枚举b的倍数。

zz的发现了f(x)<=100，其实对于所有数据枚举f(x)都可以的，与正解擦肩而过。。。。。

2、虽然上面很zz，但是居然写错了输出格式

int sz = ans.size();
printf("%d\n",sz);
if (sz==0) printf("-1");
else for (int i=0; i<sz; ++i) printf("%d ",ans[i]);
puts("");

所以输出-1后两个换行符。
对拍也没有发现任何问题。

3、

差不多是下面的样子。

int n,k;
cin >> n >> k;
if ( nn <= 100 ) {work1(); return 0;}
if ( k == 1 ) {puts("1"); return 0;}

n是int型的，然后读入的是long long ，所以n变成了一个小于等于100的数，然后进入了高斯消元。。

最后：低级错误一堆的一天

day4

T1：暴力30，后面的用set超时，按权值和坐标分别为第一关键字和第二关键字排序，每次查找1v,2v...kv，然后除掉，线段数维护。v很小的话就不行了，所以在区间查一个最大值，枚举到大于最大值。复杂度不对，但是时限改为了3s，试一下吧，还是不对。
T2：暴力。看着像数位dp（数据范围），但不会写。。。
T3：凸包，不会写，考场上最后把上面的写完了，上网学了一下。没交。。。

zz的我

没有比这更智障的了

这是T1的数据范围，但是读完30%，然后想到是可以暴力的。
读第二行，和第三行，心里默默地说了一句“一定有？又不是全都有，有什么用？？？”
。。。

最后：最zz的一天，还有要学会各种算法，写完板子还有暴力分！！！

day 5

T1：一看就是原题，以前做过，博客里还有题解代码呢。然后发现这道题70分是那个（还是需要离散化的，博客里的没有离散化的），30分强制在线。想了很长时间，忍不住看了博客，然后想起了思路，很不想写，因为不是想出来的。所以写了莫队，转移时发现复杂度很大，但是算错了数据范围，于是想即使优化了这里，复杂度也是不对的，所以也没管。不过中途写了博客里的解法，调出后，与莫队对拍，发现莫队根本就不过，于是开始优化那个地方，最后的思路是用set优化，复杂度是$n\sqrt {n}(logn)$差不多这个复杂度，然后当时对拍时已经很晚了，最后优化也没有调出。

T2：暴力，预处理，简单的几何知识，算一个斜率，加模拟。

T3：对于前30%，只有一个字符串，
结论：若答案是INF:字符串接起来时，一个字符串完整的出现在回文串中，所以一个字符串复制一份，合起来，求回文串，然后判断一个字符串是否完整的出现一次即可。
否则，把一个字符串复制一份，合起来，求回文串，就是答案。回文串在接起来的中间。

第一种情况：caba--- cabacaba —— caba完整的出现了一次
第二种情况：

然后manacher板子不会写了。去博客看了下，回忆了一下，最后没写。没有交。

没有交是最大的错误，输出INF也好啊。（以为有多组数据，没看好题面。。。）

最后：Don't give up

day6

T1：数位dp，先写了dfs版的，发现最大到20000左右，于是改成了递推版，复杂度O(n)，过了60%
T2：第一眼看上去，感觉很难，于是打了一个暴力。
T3：Q=1，O(n)的做即可，k=1求mex，主席树。但是0分，读入优化写错了。。。

zz的我
1、开始5分钟，写完板子（包括读入优化），T1,T2输入数据小（还有long long），用的cin，T3时发现数据很大，用的读入优化（心想：终于用上读入优化了，没有白敲），后来0分，发现读入优化写错了（当时的样例都过了，对拍了也没有问题（两个程序有了一个读入优化。。。读的数据一样））。

inline char nc() {
static char buf[100000],*p1 = buf,*p2 = buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
    }
inline int read() {
    int x = 0,f = 1;char ch = getchar();
    for (; ch<'0'||ch>'9'; ch=nc()) if(ch=='-')f=-1;
    for (; ch>='0'&&ch<='9'; ch=nc()) x=x*10+ch-'0';
    return x * f;
}

read函数第一行。。。

2、T2后来讲完了发现也是可以做的，别看到题面就跑。

3、即使读入优化没错，也只有10分（询问为1）。
对于k=1，求mex，当时想到了昨天T1的思路，发现略有不同，之后想到了主席树。查询区间的最小的没有出现的数，写完了，对拍了一下，没有问题，然后把程序最后写完可以交了。
临近交的时候，突然发现没有判-1的情况，于是就赶紧再调，终于可以出-1了，对拍了一下。然后最后还是因为-1的问题。（这个不判应该没分，判了错了也是没分。。。）

4、11:00，距离考试结束还有一个小时，想出了k=1的部分，也想出了感觉挺对的针对100%数据的解法（没试，改天写写）。于是纠结，写什么好，对于100%的是k=1的加强，处理的就复杂了，所以写了k=1的，想：写完k=1的，然后稍微改改在写100%的，于是11:40差不多调出。当时想写100%的，但是为了求稳着点，于是写了对拍，50好了，还有10分钟，放弃100%的思路。。。。。不知道时间安排有没有问题。

100%的思路：有k=1和k=2过渡而来。k=1：构造主席树，然后查询区间的最小的没有出现的数。k=2：查询的是最小的没有出现的连续的两个数，于是可以每个数记录它自己和它后面一个数的转态，如果这两个数都没有出现，这个值为0即可，表示从这个数开始往后一个数都没有出现，查询即可。所以100%的，k<=10，每个点保存往后10个数的状态即可。

最后：别被题面吓到跑路，合理安排时间，加快写代码速度，集中注意力写，以此减少调试找bug

day7

T1：60分dp
T2：概率dp和期望dp。
写了一个可以过有小龙强化，没有大龙强化，的概率dp
一个既没有小龙强化也没有大龙强化的期望dp
莫名其妙10分。
T3：10:58开始写的，手玩了一个小时，除了第二个点10分，其他的不是满分。

1、时间没有分配好。第一二题花的时间太长，导致第三题的时间很短。
2、以为T3只有前1或者2个点可以手算，没想到后三个点行列也是56。（本来算完12就完成了，打开后面的测试点发现居然是56。在11点时，当时已经想T3只算完12就好了，于是时间花费的也比较长。在11:30左右，才打开看了一下后面的测试点。。。）
3、最后时间太紧，看到第34567个点时，只是感觉nm有点大，就没有写，实际上并不是很难写。由于每个点都是在纸上画的，根本就不知道34567的图什么样子，应该写一个程序帮助手玩，例如：地图生成器，模拟操作后显示的地图什么样子等等，由于最后时间太急。没想到写，最后太急，导致脑子混乱，东西居然写反了，还是最后马一凌告诉我，方向开始写shang,xia,zuo,you，最后替换掉就行。

最后：冷静些，不要太混乱导致写错，“脑子短路”等，分配好时间。