关于THUSC2021，一些思维碎屑

THUSC2021题意复盘(2021.5.16) – 2yh_Z77&zqyyy

Day1

T1:给定n个数，每次取若干个数总和小于一个给定数，首先要求取的数的个数尽量多，其次再要求取的数的编号从小到大组成的串字典序尽量大，求取的次数。 $，$ 。
T2:给定一棵树，每个点有一个权值，寻找一条路径，使得其上的最长上升子序列的长度在此树上最长，输出此长度。。
T3:给定一个二维数组，若第i行j列的数为-1，则第i个人讨厌j食物，否则为第i个人吃到第j个食物将留下的钱，选一些食物，一个值为都不讨厌这些食物的人留下的线总和，求此值的最大值。 $，$ 。
T4:(通信)加密一棵树成一个无符号128位整数，再把此整数解密为与原树同构的树。。

Day2

难以描述，关于光线追踪，一道交互七道提答。

CSP2021前的一些思考(2021.10.15) – 2yh_Z77&zhuyifan

Day1

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

Day2

爆零选手2yh_Z77不适合思考Day2/kel/kk