主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
JOI 2021 final 做题记录
最后更新于 2025-08-27 21:02:50
作者
Nerovix
分类
个人记录
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
**~~口胡警告~~** ### T1 求个差分，那么最终的差分数列应该是在某个分界点前全是正的，之后全是负数的。考虑区间+1的含义：差分数列的某个位置+1，其后的某个位置-1。于是枚举最终的那个分界点，求它之前的差分不合法位置之和和他之后的差分不合法位置之和取个max，再全局取min就行 ### T2 可以一个log，但是太懒了，写的俩log 就是在x[i]和x[i+1]之间二分分界点，然后预处理两个前缀和的前缀min/max数组，在上面lower_bound就行 ### T3 keyobservation：最后的排列方式一定是3，2，1，7，6，5，4，9，8这样的倒着接起来的连续段。 然后结合常识（？）最小交换次数等于逆序对数, 于是求一个where[H[i]]=i,再结合树状数组（用于动态维护逆序对数）做一个$O(n^2\log n)$的dp。 ### T4 直接一边跑最短路一边考虑怎么改边（因为你不会经过同一条边两次） 考虑重新建图：对于每个点x，以及每个与x相连的边的颜色c，建立一个新点(x,c)。原来的x称为(x,0) 则对于原来的一条从x到y，颜色为c，修改代价为p的边，建立新边： - (x,0)->(y,0),边权$\min(p,\sum_{e\in E,e!=(x,y,c,p),e\ is\ connected\ with\ x}e.p)$ - (x,0)->(y,c),边权$0$ - (x,c)->(y,0),边权$\sum_{e\in E,e!=(x,y,c,p),e\ is\ connected\ with\ x}e.p$ 从(1,0)到(n,0)的最短路就是答案，若为inf则输出-1 ### T5 勉强看懂了kczno1dalao的代码，然后写了一下。。 这个题要具体想清楚的细节蛮多的 读代码看谷歌翻译的题解看了一个晚自习才懂 先放个大佬博客占坑[link](https://www.cnblogs.com/chasedeath/p/14435913.html)
正在渲染内容...
点赞
0
收藏
0
