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