csp-j模拟赛2
A 公式求值
加入前缀和思想的高精度加法。
B 最长的Y
我永远喜欢 IOI 赛制。
考场写了两份代码，调了两个小时，结果到最后 10 分钟发现第一个代码能够 subtask 1，第二个能过 subtask 2，于是结合起来喜提 \(60\) 分。
我们先找到每一个 \(Y\) 块，然后循环找到左右两边离他最近的 \(Y\)，更新块长度和答案，直到耗尽 \(k\)，对于每个块更新答案即可。
C 交换序列
四维 dp？？
D 最长路径
三维 dp？？
csp-j模拟赛3
A 分糖果
气死人了，没仔细检查结果全 WAAAAAA
要把两种情况分类讨论，同时计算取最大值。
B 乒乓球
这是一个很巧妙的找规律，考虑到超过 \(11\) 分的比分性质相同，可以直接把类似于 \(114:115\) 当成 \(10:11\)，这样规律就比原始的比分更好找了。
C 与或
直接状压暴力。
简单来说，观察到 \(%30\) 数据的 \(n,k \le 20\)，而且 \(2^{20}=1048576\) 我们便可以想到把 \(\&\) 和 \(|\) 的状态压缩成一个数。
因题目要求 \(|\) 的字典序小于 \(\&\)，那么可以令这一位的 \(|\) 表示 \(0\)，\(\&\) 表示 \(1\)，那么序列 \(\& \& |\& \& \& \& \& \& |\& |\& ||\&|=11011111101010010=114514\)
在新的位置添加一个 \(|\) 就是 \(S<<1\)，添加一个 \(\&\) 就是 \(S<<1|1\)
最后在更新答案的时候可以直接比较数字的大小而不是遍历全部数组。
这样能让暴力更快一点（指快一两毫秒）
D 跳舞
要预处理每两个数的 \(\gcd\)，时间复杂度 \(O(n^2 \log n)\)，然后就是类似与区间 dp 的东西了。
E 音乐播放器
概率 dp。
csp-j模拟赛4
A 超市抢购
这就是小孩题，但因为随机数生成器的问题卡了 \(\text{long long}\)。
首先题目给出的随机数生成器是这样的：
int randseed;
unsigned int rnd()
{
unsigned int r;
r = randseed = randseed * 1103515245 + 12345;
return (r << 16) | ((r >> 16) & 0xFFFF);
}
- 首先观察到这个子函数的类型的 \(\text{unsigned int}\)，\(32\) 位无符号整型，即最高一位代表数字而非符号。
这样是为了防止溢出成负数，也是方便设置生成数字的位数为恰好 \(32\)。
但是我们观察到一个细节，就是 \(randseed\) 这个变量是 \(\text{int}\) 类型而非 \(\text{unsigned}\)，并且循环中输出的 \(randseed\) 也大多是负数。
原因很简单，\(\text{int}\) 和 \(\text{unsigned int}\) 存储的形式是相同的，没开 \(\text{unsigned int}\) 可能单纯是不想，但是我们 \(r\) 考虑的就要多了，所以必须得是 \(\text{unsigned}\)。
- 然后，观察到这个式子：
r = randseed = randseed * 1103515245 + 12345;
这是很古老的一种随机数生成算法，一种最简单的单状态 LCG（线性同余生成器），至于是啥，咱也不知道。
其中用到了 \(1103515245\) 和 \(12345\) 这两个数，我在网上找到的解释是
事实证明，rand() 的每个连续输出的低位将交替(例如，0,1,0,1,0,1，...)。
你明白为什么吗？ x * 1103515245 的低位与x的低位相同，然后加 12345 只会翻转低位。因此，低位交替
- 最后看到
return
\(0xFFFF=65535=2^{16}-1\)，并且 \((r << 16) | ((r >> 16) \& 0xFFFF)\) 使得或运算左边的表达式的低 \(16\) 位都为 \(0\)，或运算右边的表达式只有最低的 \(16\) 位。
这样与起来的长度必定大于等于 \(32\) 位，关键来了。
如果返回值是 \(\text{unsigned long long}\)，那么 r<<16 是会超过 \(\text{int}\) 的，因为不能保证 \(r\) 的值必定小于 \(65536\)。
如果返回值是 \(\text{unsigned int}\)，那么会自动溢出，直接将高位舍弃，保留低位。
这样就是不能用 \(\text{long long}\) 的原因了。
但事实上，那个 &0xFFFF 的运算是无意义的，因为你的 \(r\) 最大也是 \(32\) 个 \(1\)，右移 \(16\) 位必定小于 \(65535\) 了。
但事实上，如果把 &0xFFFF 放在或运算的左边，也就是这样写，可以使得返回值严格在 \(\text{unsigend int}\) 中：
(r & 0xFFFF) << 16 | (r >> 16)
这样会先使 \(r\) 只有最多 \(16\) 位，再右移 \(16\) 位那肯定小于 \(\text{unsigned int}\) 的最大值而不会溢出了。
但事实上，这样修改随机数生成器，还是保留 #define int long long 也是不行的，
原因很简单，\(r\) 在和随机数种子生成随机数的时候就可能已经溢出了，要想完美解决，这样写就好了：
B 核酸检测
考场上推出 \(O(NM)\) 的 dp 了，可惜死活没想到要把区间按左端点排个序，没想到和玮的思路一模一样，稍稍优化一下就 A 了、
首先，考虑状态 \(dp[i][j]\) 表示把前 \(i\) 个人都喊下来且最后一次喊在 \(k\) 时刻的最小次数，\(g[i][j]\) 表示其方案数。
容易得到：
- 当前扫描到第 \(i\) 个人，在第 \(j\) 时刻时，如果 \(dp[i-1][j]\) 有值，那么相当于和上一个人情况相同。
- 否则，可以把从 \(1\) 到 \(i\) 所有人的区间看成两个部分：前 \(i-1\) 和第 \(i\)，容易得到：
对于 \(g[i][j]\)，和上面类似：
- 当前扫描到第 \(i\) 个人，在第 \(j\) 时刻时，如果 \(dp[i-1][j]\) 有值，那么相当于和上一个人情况相同。
- 否则，可以把从 \(1\) 到 \(i\) 所有人的区间看成两个部分：前 \(i-1\) 和第 \(i\)，每一种都能从可转移的位置得到，容易得到：
优化一
有这样一张图：
可以看到 \(dp[i][j]\) 的值无非就是那两种，所以我们可以在处理上一行的同时直接处理出 \(\min(dp[i-1][j])\)
这样，查询最小方案的时间复杂度就来到了 \(O(NM)\)。
优化二
和上一优化一样，\(g[i][j]\) 的值也只有两种，因为，如果 \(g[i-1][j]\) 有值，那么 \(dp[i-1][j]\) 也必有值，也就是图中左边的情况。
否则，\(g[i-1][j]\) 没有值，\(dp[i-1][j]\) 也必定没有值，对应图中右边情况，这时的 \(dp[i][j]=\min(dp[i-1])\)，我们可以发现一个关键：
如果 \(g[i-1][j]\) 无值，那么\(g[i][j]\) 所对应的所有 \(dp[i-1]\) 都一样 \(=\min(dp[i-1])\)。
我们可以 \(O(M)\) 地在每次计算完后处理出所有满足 \(dp[i-1][j]=\min(dp[i-1])\) 的 \(g[i-1][j]\) 之和。
因为这种情况一定在上一个区间的右端外并且不重合，所以这种情况的 \(g[i][j]\) 一定相等，等于我们预处理出的 \(sum\)。
这样，我们也实现了 \(O(NM)\) 的查询方案组数，总体时间复杂度来到了可喜的 \(O(NM)\)。
优化三
虽然但是，时间复杂度刚好能过，但空间复杂度开始爆炸。
观察我上面写的所有式子，对于第 \(i\) 个人，他的所有答案、贡献只和 \(i-1\) 个人有关，那还怕啥，直接滚！
滚完之后就 ok 了
实际得分是 \(100\) 分，研究了一下，发现汇总答案确实需要第 \(n+1\) 个人，然后 第一个输出 \(ans-1\)。
C 七龙珠
不太会啊，看了题解也没思路。
考场推 \(k=1\) 情况的部分分，结果寄了。。
D 龙珠游戏
dfs 写假了，急急急。
csp-j模拟赛5
A 算术求值
妈呀，想复杂了，但是时间复杂度很优秀啊 hhhhhhh
考场上因为取模一直卡在 \(90\) 分，硬控半个小时。写到 T2 突然回光返照想起来补了取模就过了。。
考虑这样一个事情：这样的一个算式其实等同于一个线性的周期函数，周期为 \(T=998244353\)，定义域为 \((-\infin,+\infin)\)，值域为 \([0,998244352]\)。
但实际上的定义域，是 \([1,n]\)。我们需要在闭区间 \([1,n]\) 上找到 \(f(x)=kx+b\) 的极大值，这里的函数 \(f(x)\) 可以直接通过题目输入转化出来，很容易实现。
我们会遇到两种情况：
- 定义域横跨两个周期
- 定义域在一个周期内
第一种就是题目样例 \(x-6\) 的情况，在 \(f(5)\) 处能取到原函数的极大值。
我们可以这样判断：
首先令 \(f(x)_{\max}=m\)
注意这个 \(m\) 是一个取值的集合，我们这样表示：\(m=998244352+k998244353,k\in \Z\)。
回到刚才的函数，我们循环 \(m\) 的取值，并令
\(kx+b=m\)
\(x=\frac{m-b}{k}\)
每得到一个 \(x\) 就和定义域 \([1,n]\) 比较，如果在定义域内就更新最大值，准确来说是 \(f([\frac{m-b}{k}])\)
如果当前的 \(x\) 已经超出定义域，那么我们可以断定：定义域内不存在 \(f(x)\) 的最大值。
这就是定义域被包含在一个区间内的情况，因为 \(f(x)\) 在每个区间单调递增，所以这个情况的最大值就是在 \(f(n)\) 处取得。
这样就把所有情况讨论尽了。
找 \(k\) 和 \(b\) 的时间复杂度是近似 \(O(s)\)，找答案是时间复杂度基本上 \(O(1)\)，不会跑几次。
B 括号序列
直接栈+贪心 \(O(n)\) 战神一遍过。
C Count Multiset
神秘 dp，我不会，考场上还是普普通通的暴力 \(10\) 分。
D 选数
据说标程的时间复杂度已证伪，太吓人了，我选择 \(O(n^2 \log n)\) 暴力+二分答案。
E 划分序列
dp+二分答案区间，老套路看来得好好回顾一下。
csp-s模拟赛1
A 最短路 (path)
正解是 floyd，稍稍修改一下就能过，考场上没看出来，硬是打了一个 \(dfs\) 加树剖过了 \(30\)……
B 方格取数(matrix)
所有暴力终将会被绳之以法！
\(n^2\) 过百万，暴力碾标算
正解是单调栈/悬线法复杂度 \(O(n^2)\)，但是昨天晚上也是把 \(O(n^4)\) 代码卡过去了。
晚上回去想了一下，最后一个大点怎么会是 \(-1\)，而且 \(-1\) 的情况有哪些，昨天考场上想出来的都是能预处理的，现在我总结一下：
- 矩阵所有元素都大于 \(2k\)
可以预处理提前计算。
- 矩阵所有元素之和小于 \(k\)
同样前缀和一下就能判断。
- \(k=2\) 且矩阵中所有 \(1\) 的上下左右没有 \(1\)（是在矩阵没有单另的 \(2,3,4\) 前提下）
输入的时候可以预处理
- 其他情况
这里主要说的就是这个其他情况，因为前面说的 \(4\) 种 \(-1\) 都可预处理，只有这个不行。
考虑这样一件事：如果矩阵中的元素有 \(n^2-1\) 个都是 \(>2k\)，只有一个 \(<k\)，那么它肯定不符合，并且要得出答案必然要遍历全部矩阵，跑满 \(O(n^4)\)
或者这种情况，\(2k+1\) 和 \(k-1\) 交替出现，也是上述情况。
5 3
2 7 2 7 2
7 2 7 2 7
2 7 2 7 2
7 2 7 2 7
2 7 2 7 2
可以通过数据生成器来做出这种数据的完全体：
#include<bits/stdc++.h>
using namespace std;
int n,k;
int main()
{
freopen("in.txt","w",stdout);
srand(time(NULL));
n=2000,k=10000000;
cout<<n<<" "<<k<<endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if((i%2==1&&j%2==1)||(i%2==0&&j%2==0)) cout<<k-1<<" ";
else cout<<2*k+1<<" ";
}
cout<<endl;
}
}
但是又会想到，遍历全部矩阵的过程是一个严谨的逼近答案的过程，当循环次数趋近于无穷大而没有合适的子矩阵时，答案是 \(-1\) 的概率也会趋近于 \(1\)，所以我们在循环中加入卡时代码是不无道理的 ，嘿嘿
那么能完全 hack 的数据应该把答案分布在最右下角，并且有唯一答案，这样也是会跑满的。
C 数组(array)
拿两个线段树分别维护区间乘和区间取模，统计每个数的质因数分布，用 \(\text{long long}\) 状压维护一下。
考场上一直没想到用欧拉函数定义式去算，一直想着线性筛。。。
D 树(tree)
服了，勾式细节，考场上都把 \(40\) 代码码出来了，结果细节不到位，每个点都差一点，细节啊细节。。
正解是长链剖分+根号分治，比较神秘，我看一个人写的序列分块+树剖的代码还挺好。
标签：总结,int,text,复杂度,unsigned,long,模拟,暑假,dp From： https://www.cnblogs.com/ccjjxx/p/18297550