2019年1月

卧槽竟然一遍就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$ 是这一组中最...
题解 动态规划
普及+/提高
项目地址:https://github.com/Llf0703/Luogu-Difficulty-Tag(有时间给分类为项目的文章加个button用自定义字段指向项目地址)下面把README.md复制了一遍Luogu-Difficulty-Tag 洛谷难度标签 for typecho项目结构. ├── luogu.php ├── README.md ├── LICENSE ├── css ...
项目
这道题应该是迄今为止我做的时间跨度最久的题,在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; } ...
题解 算法-搜索 算法-位运算
提高+/省选-
rt.已知bug已经全部修复完毕。已知bug:代码高亮、目录和公式的js尚未回调,如果确实需要请手动刷新查看。archives页面出现未知错误。(感谢Duanyll大佬)评论区在pjax加载后无法使用。欢迎在评论区反馈bug。启用pjax参考资料:https://www.ihewro.com/archives/354/先引入jQuery和pjax的js文件。注意:jq2.x配pjax1.x,...
博客 其它-pjax
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划52 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP16 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP3 图论4 图论-LCA4 图论-Tarjan11 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束4 图论-强连通分量2 图论-最小环1 图论-最小生成树6 图论-最短/最长路19 图论-树上差分2 图论-树的直径4 图论-桥1 图论-缩点5 图论-负环4 字符串3 字符串-kmp2 思维题3 数学26 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-并查集2 数据结构-栈1 数据结构-树状数组6 数据结构-树链剖分10 数据结构-线段树5 数据结构-队列1 比赛-Codeforces21 比赛-JX Round1 比赛-NOIp/CSP5 算法-KM算法1 算法-二分/三分12 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希2 算法-多叉树转二叉树2 算法-差分4 算法-悬线法1 算法-拓扑排序2 算法-排序3 算法-搜索21 算法-模拟5 算法-状态压缩4 算法-贪心10 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2