记录
2026-10-02 08:26:30
发布于:山东
一.复习
P2879
注意点回想:根据输入完成操作的题目需要注意若输入是否有可能重复。
思路点拨:实质性的批量区间同质操作,也应该要向异或的方面去想/
P2420
注意点回想:异或的优先级比较低,所以异或运算需要加括号。
思路点拨:异或很容易需要用到前缀和,看到异或可以直接往这个方面去想。
卡点补充:树的边输入n-1条而非n条
P1083
注意点回想:?
思路点拨:确定一个点且n=1e5/1e6 时间复杂度支持O(nlogn)的且有符合要求的单调性的,可以使用二分。
二.昨日遗留补全
昨天本来应该有一道绿题精做的,没做。今天补。
区间修改单点查询。
我想我需要把区间修改单点查询的模板复习一下
哦。就是维护差分是吗。懂了。
感觉不会。遂看题解。
这道题目需要用到一个没见过的技巧:二阶差分。
二阶差分/前缀和的唯一作用就是快速处理等差数列差分
一阶只能处理去建立的每个数加上同一个值
如果题目要求区间每个数加上一个等差数列,一阶差分就不够用了。
对于区间[l,r]加上首项为X,公差为K的等差数列,也就是:
a[l]+=X
a[l]+=X+K
a[l]+=X+2*k
a[l]+=X+(r-l)*k
对二阶差分数组dd做如下操作:
dd[l]+=X
dd[l+1]+=K-X
dd[r+1]-=x+(r-l+1)*k
dd[r+2]+=x+(r-l)*k
配套操作:二阶前缀和
a[k]=sigma(i = 1~k) dd[i]*(k-i+1)
=(k+1)*sigma(i = 1~k)dd[i] - sigma(i = 1~k)dd[i]*i
那么实际上我们需要做的事情是:维护dd[i]*i的前缀和还有dd[i]*i的前缀和。
这个题调的我头秃。
来做一个总结吧。
这道题目首先需要的前置知识是二阶差分+二阶前缀和。不会就没办法写。
但是我确实不会。
然后,为了把二阶前缀和与差分顺利地运用上去,我们需要重新推出一个a[k]的公式。
这就是绿题的两层转换。
其实还有隐藏的一阶就是从O(nlogn)+区间修改单点查询推出需要使用树状数组或者线段树。
挺难的,肯定还需要重新去练习。
另外能够看出有点浮躁,代码实现有很大块大块的问题。
三.限时黄题
瑟瑟发抖。今天怎么是小模拟专题。
/*
有m台机器加工n个工件。
每个工件有m道工序。每道工序都在不同的指定机器上完成。
每个工件的每个工序称为一个操作(用记号j-k表示)。
给定各操作安排顺序。
操作安排满足以下约束:
1.对同一个工件,每到工序必须在它前面的工序完成后才能开始(1在2前,2在3前)
2.同一时刻每一台机器只能加工一个工件
由于统一工件都是按工序的顺序拍的,因此只按照原顺序给出工件号仍可得到同样安排顺序
所以将输入数据简化成工件号而非工件号-工序号
需要注意:“安排顺序”只要求按给定的顺序安排(加粗)每个操作。不一定是各机器上的实际操作顺序
约定:在保证约束条件的情况下,如果当前任务有多个空挡可以插入,就插到最前面的空当。
询问完成所有任务所需要的总时间。
预想代码框架:
1.输入:
m(机器数) n(工件数)
m*n个数(给定排序)
接下来2n行,每行用空格隔开m个正整数
(前n行一次表示每个工件的每个工序所使用的机器号,后n行一次表示每个工件的每个工序的加工时间)
2.模拟
按照给定排序开始排每个工件的所在机器和花费时间
对于当前工序,遍历同工件前面的那些工序,找到最早可以开始时间
然后在当前机器里知道开始时间,一个一个点标记。
*/
这个还没写完,仅仅只是把
初步观察发现z[i]<=16,结合本科课题:从问题的过程走向可计算的结果。
本题要求构造一个符合题目最大公约数限制的数列。
并且a[i]是在int范围之内的正整数
n=10^5,那么时间复杂度大概率是O(nlogn)
可以使用ST表在O(nlogn)
这里空空如也















有帮助,赞一个