NOIp才考了（好吧是我把它做成了）分治，再加上我分治也不太熟悉，就先做下分治。虽然是一道普及-，但细节还是廷考验人的，再加上很久没打题了所以搞了很久。思路就是找到原数所能分出的最大的2的整数幂次方，然后将幂次数和剩下的分治处理即可。细节就是2(2(0))应该直接写成2int n;
void work(int x)
{
if (x==0)
{
printf(...
NOIp2018情况$$ 100+40+10+64+15+4=233 $$感觉分数就像个玩笑一样，不过今年NOIp确实给我开了一个玩笑，D1T2人人都会的傻逼题我只有40，D2T2推出了部分规律又把快速幂打爆了（开了bits而且函数名用的小写pow），D2T1也写爆了。我个人感觉D1T2的爆炸是主要原因，导致D2整个心态都是崩的 （心态崩了我要妹子）。而D1T2我觉得可能有点心态的原因，考前...
只是发个板子。虽说似乎NOIp近几年一般都是取膜而不是高精了，但我还是担心会考，所以就复习了一下。定义用struct储存整个数和位数。整个数全部倒序方便计算。struct bigint{
int s[5005],len;
bigint(){memset(s,0,sizeof(s));len=0;}
};加法inline bigint add(bigint x,bigint y...
晚上做了洛谷TG试炼场的DP lv1 模块，还是大致总结一下。洛谷P1005 矩阵取数游戏区间DP。对于每行，我们可以单独处理。用 $ f[l][r] $ 表示已经取了 $ l..r $ 这个区间后的得分最大值。然后记忆化搜索即可。$ $ 肯定是爆long long了，按理来说应该要写高精的，但是我发现这玩意写高精如果没有运算符重载版的是真的恶心，然后__int128水过去了。#includ...
这篇文章不全且含有错误，建议查看 初赛知识点选讲排序希尔排序作者： dreamcatcher-cx 出处： https://www.cnblogs.com/chengxiao/本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在页面明显位置给出原文链接。我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这...
我前段时期刷紫书才发现我搜索实在是菜的一匹，近期就在做这方面的题。今天突然有觉得自己该发一篇文章了，于是就有了这个。洛谷P1379 八数码难题这道题其实并不是太难，说到这我想起了一位已经AFO搞物竞的同学花了三个月改了九个版本真正纯种暴搜最后拿了15的故事，主要难点集中在判重。这里我用的是康托展开。康托展开是用来求在n个数的 所有排列组合中 某种排列组合的编号(就是从小到大的第几个)。公式是...
很久没写过总结了。紫书做了那么多道题，但是我的动规并没有找到什么感觉，也就只有普及难度的可以不看题解写，剩下的都是看着题解写完的，我还是太弱了。这里还是来总结一下吧。例题9-1 UVa1025-A Spy in the Metro$f[i][j]$表示在车站i，时刻是j，还剩多少时间（根紫书略有不同）决策有三个，上左边的车，上右边的车，如果都不开往幼儿园就等一时刻的车。注意还要判断某一时刻是...
第一次写树剖没看题解A题，发现题解洛谷题解区大佬里竟然没有一个做法一样的，实在是太激动了树剖学习：https://llf0703.com/p/shu-lian-pou-fen.html方法裸树剖，直接用线段树维护每一段区间中被标记的最深的节点就行了。先全部赋值为-1，然后向上传递时直接取两段中的最大值即可（因为越深的点dfs序越大）还有需要注意的是查询中在链上往上跳时只要找到了有标记的节点就...
作为一个上个月刚学完线段树的蒟蒻，看Splay又看不懂，便直接跳着来学树剖了。又在一个博客上看到说学树剖之前最好还要把LCA给学了，便去花了一天学了一个Tarjan求LCA（然而后来发现并不怎么需要），然后是几乎照着别人的代码把树剖抄懂的。在这里我就讲一下我理解的树剖。准备工作链表/链式前向星线段树/树状数组/Splay等可以维护一段数据的数据结构LCA （其实只涉及到一些思想，而且几乎用不...
概念最小生成树即为无向图中结点构成的树中各边权值之和最小的树，可以有多种情况。一般用Kruskal（克鲁斯卡尔）算法或Prim（普里姆）算法求出。Kruskal算法方法可以将Kruskal算法理解成对边的贪心算法。1.将路径用邻接表存储，存储的值为起点、终点和权值；2.将邻接表按照权值为关键字排序；3.从最小权值的边开始循环，每连接起两个结点就把它们并到同一个集合（并查集实现），连接之前判断...
Day -N去年只参加PJ，凑巧拿了个一。今年第一次参加TG，还有在徐妈的逼迫下又参加了PJ，还想拿个高分（事实上死的很惨）Day 0就复习了点简单的东西（毕竟考前三天才学会c++的文件，P转C的痛苦），中午大半时间在颓2048，感觉什么都没干Day 1上午TG。妈的我第一题找了大半个小时都没找出规律就打了个暴力了事；第二题纯种模拟，二十多个变量，样例都过了，当时感觉应该没有问题；第三题直接...