关于THUSC2021，一些思维碎屑

THUSC2021题意复盘(5.16) -- 2yh_Z77&zqyyy
Day1
T1:给定n个数，每次取若干个数总和小于一个给定数，首先要求取的数的个数尽量多，其次再要求取的数的编号从小到大组成的串字典序尽量大，求取的次数。\(n\leq 5\times 10^4，1\leq a_i\leq m\leq 10^9\)。
T2:给定一棵树，每个点有一个权值，寻找一条路径，使得其上的最长上升子序列的长度在此树上最长，输出此长度。\(2\leq n\leq 10^5\)。
T3:给定一个二维数组，若第i行j列的数为-1，则第i个人讨厌j食物，否则为第i个人吃到第j个食物将留下的钱，选一些食物，一个值为都不讨厌这些食物的人留下的线总和，求此值的最大值。\(n\leq 20，m\leq 10^6\)。
T4:(通信)加密一棵树成一个无符号128位整数，再把此整数解密为与原树同构的树。\(1\leq n\leq 70\)。
Day2
难以描述，关于光线追踪，一道交互七道提答。


CSP2021前的一些思考(10.15) -- 2yh_Z77&zhuyifan
Day1
T1:首先排序，显然的可以求出取数的总个数以及此时取的数，考虑对取出数的序列进行调整。
对于一个没确定位置的数，显然希望尽量往后选，考虑二分这个位置最后可以定位在哪个位置。
判断合法时，我们可以先预处理出后缀选出K个元素和的min。
设当前二分边界\([l,r]\)，判断位置为\(mid=x\)，当前还需要选择\(y\)个元素：
若当前以\(x\)为剩余选择元素中最靠前的序列选出\(y\)个元素的最小值\(>=m-\)已选元素的和，则说明无法做到选择\(y\)个满足和小于m，二分边界\([l,mid-1]\)。
否则说明当前位置可以满足条件，二分边界\([mid,r]\)。
现在考虑如何维护以一个下标为开头，选出若干个元素的和的最小值，要求支持删除元素，可以用树状数组+主席树维护，具体做法看Luogu P2617 Dynamic Rankings。
由于每个元素只会被二分判断一次，被删除一次，每一次判断为 \(O(log_2^2 n)\)，一个元素会被判断\(log_2 n\)次，一共\(n\)个元素，所以总的复杂度为 \(O(n\times log_2^3 n)\)。
T2:原题啊...CF490F Treeland Tour。也不知道该怎么说，模板吧，长剖或者线段树合并啊...
T3:根据数据范围，显然我们要枚举会带来贡献的人的集合S，设其贡献为\(f(S)\)，则答案是\(\max f(S)\)。
直接计算答案复杂度为 \(O(2^n\times m)\)，显然不行，考虑容斥，构造函数\(g(S)\)，使得\(f(S)=\sum_{S\subset T}g(T)\)。
则当S中某位为1时，T只能为1，显然要加贡献。
而当S为0时，T可以为1或0，为1加贡献时同时需要为0减掉贡献，就可以达到容斥计算答案的目的。
同时简化计算过程，设菜品j有无权值的01序列为\(w_j\)，可以得到以下式子：当\(a_{i,j}\ne -1\)时，\(g(w_j)\leftarrow g(w_j)+a_{i,j}\)；\(g(w_j-\{i\})\leftarrow g(w_j-\{i\})-a_{i,j}\)。
最终复杂度为\(O(n\times m+n\times 2^n)\)。
T4:/yiw/yiw/yiw当时就看不懂题，但是据说做法好像是卡特兰数。
Day2
爆零选手2yh_Z77不适合思考Day2/kel/kk