我在做某题的时候看到有个多叉树转二叉树,就去学了下,看的这篇文章:https://blog.csdn.net/c20190102/article/details/69946551然后就去找了这道题做,最开始想法是建了树以后转成二叉树然后再dfs得到深度,然后发现有点问题,因为链式前向星是逆序存边的,于是就改用临接表,然后t了很多发,不知道有多少组数据啊。去看题解发现转成二叉树以后每个树的深度...
我一看到wxh大佬题单里一道斜率优化一道cdq就果断跳过,然后终于找到一道可做的了。我一开始没看到相同面积,心想搜索时间复杂度怕是要爆炸,但也没想出其它方法,然后看了题解才发现是相同面积,那直接搜索就完事了。因为面积相同,所以每次切的长宽一定是 $x\div cnt$的倍数(cnt是当前这块能分成几份),所以直接枚举在哪里切即可。#include<bits/stdc++.h>
...
最开始我zz的想法是直接把整个区间二分,但后来才发现只能找到一个。然后看了下题解,因为每个长度为1的区间只可能有一个解,所以直接枚举每一个长度为1的区间来二分即可。只需要注意区间不能重复,所以可以把右端点减一个很小的数即可。我犯的最智障的错误莫过于用快读来读了double。。。而且改了半天今早才想起,感觉白学OI了。#define eps 1e-2
double a,b,c,d,ans[5...
昨天做了,为了抢夜宵就没写自己做了半天,感觉及其恶心,就去看了题解,发现了一种及其巧妙的写法。这种写法的原理就是按照2的整数幂次将一共 $2^{n}$ 行分成 $n$ 组来操作,操作就是把之前的图形左右各复制一个即可,只是要注意要在前后加上空格。int n,m;
string ans[1100];
inline void work(int x)
{
int mx=x*2;
...
NOIp才考了(好吧是我把它做成了)分治,再加上我分治也不太熟悉,就先做下分治。虽然是一道普及-,但细节还是廷考验人的,再加上很久没打题了所以搞了很久。思路就是找到原数所能分出的最大的2的整数幂次方,然后将幂次数和剩下的分治处理即可。细节就是2(2(0))应该直接写成2int n;
void work(int x)
{
if (x==0)
{
printf(...
晚上做了洛谷TG试炼场的DP lv1 模块,还是大致总结一下。洛谷P1005 矩阵取数游戏区间DP。对于每行,我们可以单独处理。用 $ f[l][r] $ 表示已经取了 $ l..r $ 这个区间后的得分最大值。然后记忆化搜索即可。$ $ 肯定是爆long long了,按理来说应该要写高精的,但是我发现这玩意写高精如果没有运算符重载版的是真的恶心,然后__int128水过去了。#includ...
我前段时期刷紫书才发现我搜索实在是菜的一匹,近期就在做这方面的题。今天突然有觉得自己该发一篇文章了,于是就有了这个。洛谷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序越大)还有需要注意的是查询中在链上往上跳时只要找到了有标记的节点就...