7.1总结

7.1总结

比赛链接

得分情况

比赛的时候和zsh讲话被xc抓了，罚站30min，zsh换了位置

估分：100+100+30=230

实际：100+92+98=290

Rank 4

？？？

第三题$n^2$50000有98分？？

第二题少了8分？

又是一套欺诈题

T1

一眼逆序对，没了。

差点忘开long long

T2

被c++的奇妙函数坑了。

错误的上取整方法：

x=ceil(x)

double up(double s)
{
	if (floor(s)==s) return s;
	else return (floor(s)+1);
}

正确的上取整方法：

double up(double s)
{
	long long ss=(long long)(s*1000000);
	if (ss%1000000==0) return s;
	else return (floor(s)+1);
}

T3

奇妙数据

(n^2)dp做法显然，水了98分

正解

正解在比赛的时候没想到

居然是二分答案之后再dp。

比赛的时候觉得二分之后不能贪心，就以为二分是错的，结果被打脸了。

先二分出一个mid表示最长空格的长度小于等于mid

设f[i]=0/1表示以i结尾可不可行

这样我们只用找可行解，不用找最优解，大大降低了难度。

f[i]由f[j]转移过来的条件有：

1. sum[i]-sum[j]+i-j-1<=w

2. sum[i]-sum[j]+mid(i-j-1)>=w

那我们就可以用队列来做，队列里存能更新i的决策点，记录队列里的决策点有多少个1就好了。

T4

比完赛新加的题目，刚开始没人切，标程都TLE了，然后xzb一遍过，切掉了它。

把人赶回家之后，那人似乎会有很大进步——XC

xzbtql%%%

你被困在一个密室里。经过一轮摸索，你在密室里有所发现：1.密室是一个呈m×n网格的长方形，地面有六个格子被上了色；2.密室地面部分格子可能有障碍物；3.密室的某一格有一个六面都没上色的立方体；4.当立方体滚动到相邻无障碍物的格子，如果立方体接触地面的一面没有颜色而地面有颜色，则该颜色会从地面转移到立方体上；如果立方体接触地面的一面有颜色而地面没有颜色，则该颜色会从立方体转移到地面上；如果立方体接触地面的一面和地面都有颜色，则两者的颜色都不会转移。5.当立方体滚动到密室的指定地点，如果立方体六面都被涂上了颜色，则传送门就会开启，让你逃离这个密室。由于时间紧迫，你必须借助计算机的力量，算出立方体最少滚动几次就可以让你逃离这个密室。

…

整个密室保证正好有6个格子是‘P’，1个格子是‘C’，1个格子是‘G’，‘.’的格子不超过12个。

…

2<=m<=20，2<=n<=20

一开始以为是一道神仙题，后来注意到了“‘.’的格子不超过12个。”的条件。

所有方案只有(C_{26}^6*20)个，可以爆搜解决。

小结：

1. long long！！
2. 上取整函数不要打ceil,下取整不要打floor,转成long long来判断。
3. 最大（小）的最小（大）值想到二分转判定性问题。
4. 水法真神奇，暴力出奇迹！！