10.9 guz模拟题题解
感谢@guz
顾z的题题解
考试共三道题,其中
第一题help共10个测试点,时间限制为 1000ms,空间限制为 256MB.
第二题escape共20个测试点,时间限制为1000ms2000ms,空间限制1MB16MB。
第三题cure共20个测试点,时间限制为 1000ms,空间限制为 256MB.
PS：题目背景与题目本身无关,可跳过
help
题目背景
在梦中,王 小 呆 到了一个神秘的地方.这里是昆虫王国!国王见王 小 呆 好生俊俏,便给了他一杯昆虫国的老白干.王 小 呆一口下肚,突然出现了问题!”这酒有毒!”突然,王 小 呆在梦中又睡着了.
题目描述
梦中的王 小 呆饿了!他竟然想吃蚂蚁!我们要救他!王 小 呆发现了有n 只 蚂蚁排成一队,每只蚂蚁身上有一个编号\(a_i\) 他想吃掉他们。但是这些蚂蚁部分是有毒的,我们为了救他,只能帮他挑选出zmj蚁.吃了zmj 蚁,王 小 呆才能恢复正常.
某一段区间中 zmj蚁的数量是该段区间中不能被这个区间的区间gcd整除的蚂蚁的个数。该段区间中不等于区间gcd的蚂蚁个数
输入输出格式
输入格式
第一行给出一个整数n ，代表有n 只蚂蚁.
第二行给出n 个整数\(a_i,a_2,\dots,a_n\)
第三行给出一个整数 \(m\),代表有 \(m\)次询问.
接下来\(m\) 行,每一行给定 \(l,r\),询问 \([l,r]\)里的zmj 蚁的数量。
PS:找出 蚁之后,王 小 呆 并不会直接吃掉他们.即原序列中 蚁数量不变.
输出格式 共 m行,每一行对应一个询问.
输入输出样例
输入样例 #1：
5
1 3 2 4 2
4
1 5
2 5
3 5
4 5
输出样例 #1：
4
4
1
1
数据规模
对于 30％ 的随机数据 ，\(1\le n\le5000,1\le m\le500,1\le a_i\le10^4\) ，
对于 100％ 的随机数据 , \(1\le n\le10^5,1\le m\le2\times10^4,1\le a_i\le10^9\)，
题解
这题有好几种xjb算法，机房里面AC的基本上一个人一个算法，那么我就说说我的算法把。
倍增+树状数组。
首先我们可以通过倍增预处理gcd，令f[i][j]表示第i个点向右跳\(2^j\)步路上所有数的gcd。f[i][j]求法很简单：
f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]。
然后我们就可以在log的时间内求出一个区间的gcd了。所以我们求出所有区间的gcd，然后树状数组单点修改，区间查询。将所有区间按照gcd排序，所有数字也排个序，按照数字大小往树状数组里面塞值就行了。
escape
题目背景
终于王 小 呆被拯救了出来,他再也不想看见 zmj蚁了,可是这时 zmj国的蚁后:zmj 出现了!王 小 呆又被抓入了 zmj国忍受#@￥&!*~的酷刑,当王 小 呆 气息奄奄的时候, 皇后的一个仆人找到了王 小 呆 ,他要拯救王 小 呆 ,但是在救王 小 呆 之前他要考一考王 小 呆 ,并宣称如果王 小 呆 答对就会帮助他逃脱.但王 小 呆只剩一口气了,你能帮助他逃脱吗?
题目描述
仆人给出了n 个数字,这 n个不超过 n的正整数中, 其中有一个数出现了两次, 其余的数都只出现了一次, 他想让王 小 呆求这个出现两次的数.你能办到么?
输入输出格式
输入格式
共两行.第一行为一个整数 n,代表有\(n\) 个数字.第二行为 n个数字,每两个整数之间以一个空格间隔.
输出格式
一个整数,即出现两次的数.
输入输出样例
输入样例 #1：
3
2 3 3
输出样例 #1：
3
数据规模
对于 5％的随机数据, n<=5000
对于 15%的随机数据,n<=\(10^5\)
对于 50％ 的随机数据,n<=10\(^6\)
对于 100％ 的随机数据\(2\le n\le10^7\),
题解
空间一开始是1MB，std超空间了，后来guz改成了16MB，导致bitset能轻松水过。
我们来算一下bitset的空间：10的7比8Bytes，即1.25MB（那些说应该是1.1920928955078125MB的注意应该是1.1920928955078125MiB而非MB，这是Windows的锅，//初赛题CCF莫名背锅）不多扯了
反正我觉得要是内存限制正解能过但是bitset过不了，很不好设置，甚至无法设置。那就说说正解吧。
由于题目里是小于等于N的正整数，那么既然有一个数出现了两次（设为x），那么恰好有另一个数没有出现（设为y）。设输入为a，那么\(x-y=\sum{a_i}-\sum{i}\)，并且\(\displaystyle\frac x y=\frac{\sum{a_i}}{\sum{i}}\)。解这个方程组即可。std在模意义下解的，但是也可以直接开double。
cure
题目背景
从 zmj国逃出来的王 小 呆 遇到了正在驾车的顾z,王 小 呆匆匆忙忙上了顾z的车.(随随便便上别人的车真的好嘛?)
伟大的无私的善良的不要脸的顾z看到王 小 呆奄奄一息的样子,很是心痛,便决定带他去海边的沝(zi)吅(xuan)山找那里的山女芽 佟 雪要千年冰宩来救命.但是上山之前,他们遇到了问题.想要找到山上的山女 芽 佟 雪 ,必须知道她家的温度.
题目描述
沝(zi)吅(xuan)山永远刮着风。风从地点 依次吹到地点 1，地点2 直到地点N ，共 N+1个地点。住在地点N。地点 的海拔 ，地点 0的海拔为 0。 风的温度随海拔升降而变化。地点 0在海边，温度为 0度；对于任一地点 ，从地点i 吹到地点i+1 的风的温差仅取决于两地的海拔差。具体来说：
如果 \(A_i=A_{i+1}\)，风的温度不变；
如果 \(A_i<A_{i+1}\)风每爬升1米，温度就会下降S度；
如果 \(A_i>A_{i+1}\)风每爬升1米，温度就会升高T度；
沝(zi)吅(xuan)山的地壳运动很强烈。他们得到了Q天来地壳运动的数据。在第j日1<=j<=Q，地点\(L_j,L_{j+1},…,R_j(1\le L_j\le R_j\le N)\)的海拔升高了\(X_j\)。
注意\(x_j\)可能是负数。
他们的任务是，计算每天地壳运动后芽 佟 雪住所的温度。
输入输出格式
输入格式
第一行有四个整数\(N,Q,S,T\)，用空格分隔。 在接下来的N+1行中，第i行(\(1\le i\le N+1\))有一个整数\(A_{i-1}\)。在接下来的Q行中，第j行\((1\le j\le Q)\)有三个整数\(L_j,R_j,X_j\),,用空格分隔。 输入的所有数的含义见题目描述
输出格式
共 \(Q\)行，第\(j\) 行\((1\le j\le Q)\) 有一个整数，表示第\(j\) 日地壳运动后 芽 佟 雪住所的温度。
输入样例
2 2 5 5
0
6
-1
1 1 4
1 2 8
输出样例
5
-35
数据规模
对于 30％ 的数据N,Q<=2000 ,
对于另外20%的数据S=T, , 对于 100％的数据
\(1\le N\le2\times10^5,1\le S,T\le10^6\)
\(A_0=0,|A_i|\le10^6(1\le i\le N)\)
题解
据说这题是裸的差分！！？！？！？不用树状数组！？！？？！
嗯好像是真的不用。
然而我用了
long long没开好
数组越界
骗了5分
mdzz
其实树状数组只是多一个log，而且常数贼他妈小一定是能AC的。
箰榤煁山。。。
差分就是每次修改去修改两个端点出温差相对值，同时直接维护答案。。。
懒得说了