分类:题解

大半年打一次cf结果因为评测机出锅unrated了,非常不爽。这次比赛是和@Duanyll大佬合作打的,但因为我很弱出了很多锅坑了他,不过幸好是unrated。好歹还是A了四道题的,还是总结一下吧。A. Lunar New Year and Cross Counting题意给你一个矩阵,只要满足 $M(i,j)=M(i-1,j-1)=M(i-1,j+1)=M(i+1,j-1)=M(i+1,j...
题解 比赛-Codeforces
卧槽竟然一遍就A了,可把身为蒟蒻的我nb坏了刚开始让我做这道题,我是拒绝的,然后看完题发现,这就是道裸的最短路,连边搞就是了。然后发现它只给三个点,看了题解才知道第四个点可以用向量点乘判断垂直来求,路燕我对不起你。思路就是把一个城市分成四个点,同一个城市坐车,不同城市坐飞机,得到所有点的坐标和所在城市以后跑一遍最短路就行了。因为我很菜只会dijkstra,所以我就写的dijkstra。#de...
题解 图论-最短/最长路
提高+/省选-
这是一道由ljq大佬出的绝世好题,虽然看似容易,实则考察了诸位OIer对于C++语言的熟悉程度。同时,该题目又以我校物竞第一大佬PS作为题目背景,充满大佬之气,值得各位前来吸收RP。而原标程又由wzx大佬亲笔书写,可以相信几乎没有疏忽之处。所以,此题也配得上黑题这一难度评分。以下仅代表个人拙见,已AC,但不代表是最终正确程序。我们先来梳理下编译错误有哪些情况:#define和#undef后面...
题解 算法-模拟 字符串
尚无评定
显然用dp,用 $f[i]$ 表示前 $i$ 辆车过桥的最短时间,枚举上一个分组的最后一辆车 $j$ 进行转移,方程式为:$$f[i]=min \begin{cases} f[i] \\ f[j-1]+len\div s[i] \times 60 & j<=i, \sum ^{i}_{k=j}w[k]<=wmax \end{cases}$$其中 $tmax$ 是这一组中最...
题解 动态规划
普及+/提高
这道题应该是迄今为止我做的时间跨度最久的题,在2018.5.17第一次提交,直到今天(2019.1.26)才终于AC。题意就是给你一棵树,起初所有节点上的数是 $0$ ,对于每次操作 $(a,b,c)$ ,把 $a$ 和 $b$ 及之间的节点全部加上 $c$ ,最后输出每个节点上的数。其实题本身很简单,就是一道裸的树剖,但是有多组数据,所以一定要记得清空数组!!!需要被清空的数组:前向星的边...
题解 数据结构-树链剖分
省选/NOI-
就是一道区间dp+高精,最开始还想拿int_128来水水的,结果算算还是不太够,就老老实实写了高精。$f[st][ed][cnt]$ 表示在区间 $st..ed$ 放 $cnt$ 个乘号的最大值,转移方程式为:$$f[st][ed][cnt]=\max \{ f[st][mid][x]\times f[mid+1][ed][cnt-x-1] \}$$每次转移时枚举放乘号的位置 $(mid)$...
题解 算法-高精度 动态规划
普及+/提高
看到是蓝题我就知道不可能是那道黄题的做法了,不过还是打了个暴力,无氧60,吸氧70bool mp[16][16],vis[16],vis2[32],vis3[32]; //x-y+14;x+y int n,m,a,b,c,ans; void dfs(int x) { if (x==n+1) { ans++; return; } ...
题解 算法-搜索 算法-位运算
提高+/省选-
重题,双倍经验。https://llf0703.com/p/uva-1292.html而且uva的题还有多组输出,删掉就行了。struct Edge{ int next,to; } edge[3005]; int head[1505],n,m,a,b,c,cnt,f[1505][2],out[1505]; inline void add(int u,int v) { edg...
题解 动态规划-树形DP
提高+/省选-
要不是徐妈让我做,我这辈子都不可能碰这道题的。这是我做过的代码最长的非数据结构题,模拟题最长也就一百来行,这道题第一次原生态(包括注释和调试)交上去有214行,删掉调试输出和合并一些if后也有174行。况且我一点优化都没加,纯种裸暴搜,加了优化不知道有多复杂。不过这题暴力能过就是了,吸氧前最大点1618ms,吸氧后774ms。思路整个过程可以分为 移动 --> 移动后的掉落 -->...
题解 算法-搜索
提高+/省选-
跟舞会那道题差不多,如果父节点没有取那么所有子节点都必须取;如果父节点取了,子节点取或不取皆可。$$\begin{cases} f[i][1]=\sum \min(f[j][0],f[j][1]) \\ f[i][0]=\sum f[j][1] \end{cases}$$需要注意的是题目中已经把子树说明了,这就意味着只能有一个点作为根节点,所以应该连单向边,并且事先找到那个点作为根节点。st...
题解 动态规划-树形DP
提高+/省选-
大水题,题意就跟题目名一样,决策就是对于节点 $x$ 是否取当前搜到的儿子 $y$ ,显然要当前子树和要大于0我们才会取,然后dfs即可。方程式:$$f[x]+=max(f[y],0)$$struct Edge{ int next,to; } edge[32005]; int s[16005],n,m,a,b,c,cnt,head[16005],w[16005],ans; inli...
题解 动态规划-树形DP
普及+/提高
题意要从 $N$ 门课中选出 $M$ 门,有的课有价值和先决条件,求价值总和最大值。其中 $N,M\le 300$ 。题解1.多叉转二叉我们用 $f[x][cnt]$ 表示当前x节点,在以 $x$ 为根的子树中选 $cnt$ 个节点。对于每一个节点,可以有选和不选两个选项,如果不选就把 $cnt$ 全都给兄弟节点,也就是右节点;如果要选就把 $cnt$ 分别分配给 $x$ 的兄弟和以 $x$...
题解 算法-多叉树转二叉树 动态规划-树形DP
提高+/省选-
我在做某题的时候看到有个多叉树转二叉树,就去学了下,看的这篇文章: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...
题解 算法-二分/三分
普及/提高-