23/10/28 NOIP模拟赛总结
时间安排
7:40-8:00
看题
8:00-8:30
看到T1题面的第一眼：寄。
看到提示，发现做法已经给出来了，直接写过。
8:30-8:50
开T2，没啥思路，先打了30的暴力。
8:50-9:30
T3写了个 \(O(n^2)\) 的做法，当时以为是 \(O(2^n)\)，后来发现能拿40，但是调了很长时间。
9:30-10:15
回去想T2，想到了T2 50的DP，开写开写。
10:15-10:30
写了T3菊花图的分，手搓了几个样例后，想起来会出现重边，改后样例都过了，结果数组开小了。
10:30-11:20
想了想T4，没想到暴力怎么写，只写了个链的10分。
又想了一会T4，以为可以贪心，赛后发现贪心是错的。
11:20-11:45
发现T2的优化思路，最后10分钟调出来了，拼包，对拍。
11:45-11:50
写freopen，编译运行，交题。
反思总结
1.应该加强心理暗示，将模拟赛当成NOIP来打。
2.数组不要开小/ll，写完代码后应该仔细检查一遍。
简要题解：
T1:
\(tp==1\) 的情况直接按提示的方法做，\(tp==2\) 倒着做一遍。
（赛时还害怕会TLE）
T2:
设 \(f_{i,j}\) 表示前 \(i\) 个位置中奇数字有 \(j\) 个出现偶数次，\(g_{i,j}\) 表示前 \(i\) 个位置中偶数字有 \(j\) 个出现奇数次。
转移：
\[f_{i,j}= f_{i-1,j-1}\ \times\ (a-j+1) \]\[f_{i,j}= f_{i-1,j+1}\ \times\ (j+1) \]g的转移类似，答案：
\[ans=\sum_{i=0}^n f_{i,0}\ \times\ g_{i,0}\ \times \ C(n,i) \]T3:
先考虑不强制在线的情况：
- 性质：对于一个 \(y\)，若 \(x\) 为 \(i\) 时合法，则 \(x\) 可以取 \([1,i]\) 中的任意值。
因此我们对于每个点维护一个 \(g_p\) 使得 \((p,g_p,y)\) 是合法的，而 \((p,g_p+1,y)\) 不合法，每个询问只需check \(x\le g_p\) 。
强制在线只需要将 \(g_p\) 用主席树记录历史版本即可。
T4:
待补。
标签：11,10,30,T2,50,20231028,times From： https://www.cnblogs.com/Kai-benefit/p/17794333.html