NOI2024省选训练赛01
时间：2023.9.16
目录A.t3
Time Limit: 4 sec / Memory Limit: 512 MB
Description
维护一个长度为 \(n\) 的数列 \(a_i\)，支持如下几种操作，操作有 \(m\) 次。
\(1 \, l \, r \, x\) ，把区间 \([l,r]\) 的数字全部加 \(x\)
\(2 \, l \, r \, x\) ，把区间 \([l,r]\) 的数字全部设置为 \(x\)
\(3 \, l \, r\, x\) ，询问 \(\sum_{i=l}^r a_i^x\) ，答案对 \(10^9+7\) 取模
Constraints
\(k\) 表示操作 3 对应的 \(x\) 。
对于 \(20 \%\) 的数据，满足 \(n,m \le 1000\)
对于另外 \(20\%\) 的数据，满足 \(k\le 1\)
对于另外 \(20\%\) 的数据，满足 \(k\le 2\)
对于另外 \(20\%\) 的数据，满足 \(n,m\le 50000\)
对于 \(100\%\) 的数据，满足 \(n,m\le 100000,0\le k \le 10\)
操作 1，2 对应的 \(x<10^9+7\)
Solution
做法是对的，然后实现得有点问题，最后调了两天QwQ
想法很简单，先考虑一个区间 \([l,r]\) ，假设我们已经算出了所有的 \(sum_x=\sum_{i=l}^r a_i^x (0\le x\le 10)\) 的值，然后，我们考虑给这个区间的每一个数加上 \(d\)。
那么新的区间和就会变成：
\[\begin{eqnarray} \sum_{i=l}^r (a_i+d)^x &=& \sum_{i=l}^r \sum_{j=0}^x { x \choose j } a_i^j d^{x-j} \\ &=& \sum_{j=0}^x {x \choose j} d^{x-j} \sum_{i=l}^r a_i^j \\ &=& \sum_{j=0}^x {x \choose j} d^{x-j} sum_j \end{eqnarray} \]这个东西可以很方便地用线段树维护，于是就做完了。
当然，注意要仔细地实现懒标记，我就是这里写烂了QwQ
B.Life
Time Limit: 3 sec / Memory Limit: 1024 MB
Description
给定正整数 \(L\)，然后给出 \(q\) 组问询，每组问询给出一个正整数 \(x\)，找出一组整数三元组 \((a,b,c)\) ，满足 \(-L \le a,b,c \le L\) 且 \(a^3+b^3+c^3=x\) .
如果没有这样的三元组，那么输出用空格隔开的三个 \(L+1\) .
Constraints
对于 \(30\%\) 的数据满足 \(L\le 100,q\le 10\)
对于 \(60\%\) 的数据满足 \(L\le 100\)
对于 \(100\%\) 的数据满足 \(L\le 1000,q,x\le 10^4\)
Solution
无脑题。考虑通过数据点分治启发正解。
Subtask1：无脑暴力。 \(O(8qL^3)\)
Subtask2：预处理每一个三元组，存在 map 里面，然后 \(O(1)\) 回答问询。 \(O(8L^3+q)\)
Subtask3：如果我们仍然枚举全部的三个变量的话，会 T 飞，考虑少枚举一点，只枚举其中两个变量，存到 map 里面。查询的时候枚举一个变量，然后到 map 里面查询。 \(O(4L^2+2Lq)\)
小优化：直接使用 map 会 T，需要使用 unordered_map。还有，别开 long long。