复旦集训-Test1
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
---------------------------------------------------
手速场...
对我们这样的不会打字的残疾人不利啊...
（这篇文章是加密的嘿嘿嘿）
---------------------------------------------------
概述：
---------------------------------------------------
赛中通过11题，赛后通过1题，共通过12题。
---------------------------------------------------
比赛记录：
---------------------------------------------------
一开始因为下chrome的关系卡了一会儿，我进去的时候已经有人把B，C A了，然后我就跟着把B，C A了，然后发现D好像很多人A了，我就去把DA了，然后又发现很多人把AA了，于是我就去把AA了，做A的时候卡了一会儿，主要是推公式，然后后面水题一路做着走，反正基本上哪道过的人多我就做哪到，最后就只剩E，F，L了，然后我看了一下E，手玩了几种情况，感觉不是很会（而且还看错题了...我一直以为P任何时候都可以等于1），再看一看L一个A的都没有，于是就跑去做F，然后想出了一个错误的算法，但是考场上我没反应过来他是错的，就写了，然后就A了。
后面一直在想E，但是没想出来（看错题了也是没办法...）,临考试结束之前抱着侥幸心理交了一个xjb找出来的规律上去，没A。嗯...然后就没有了。
---------------------------------------------------
比赛题解：
---------------------------------------------------
A（题目状态：赛中通过）
给你一个01串，长度≤200000，问你有多少组(i,j,k)使得i<j<k并且[i,j]和[j,k]内1的个数相等
送分题。首先处理出连续的0（两端如果是1的话，要在他外面添加0个0，中间如果有连续的1，也要认为中间有0个0），然后把他们的个数+1，设这样得到了一个数组a
然后yy一下，答案就是(a[1]-1)*(a[2]-1)+(a[2]-1)*(a[3]-1)+...+a[1]*(a[4]+a[6]+a[8]+...)+a[2]*(a[5]+a[7]+a[9]+...)+a[3]*(a[6]+a[8]+a[10]+...)+...，随便搞一搞把左边这个式子O(n)算出来就行了
---------------------------------------------------
B（题目状态：赛中通过）
题意就是说投票选队名，哪个票数高就选哪个
送分题
---------------------------------------------------
C（题目状态：赛中通过）
说是N个长颈鹿去吃饭，每个人要吃一定的食物，然后食物是按盘卖的，每个盘子的大小都是一样的。每盘的价格和食物的量都等于这个盘子的大小，然后如果一个人没有吃完某个盘子里的食物，这些食物就浪费掉了，问每个盘子多大，才能使总花费最小，并求出总花费。
送分题。盘子的大小就是所有人食物总量的gcd，总花费就是食物总量
---------------------------------------------------
D（题目状态：赛中通过）
说是有一堆竹子，给出每个的初始高度，每次你可以选择某一个把他砍短1的长度，然后其他竹子都会长高1的长度，问是否能把所有竹子砍的一样长
送分题。砍短1然后其他的长高1就相当于砍短2，所以只需要判断所有竹子是否同奇偶。
---------------------------------------------------
E（题目状态：赛后通过）
说是有两个海鸥玩游戏，一开始有一排N个白色的格子，每次可以选择连续P个白色的格子把他们染黑，满足P≤ceil(L/2)且P是素数，其中L是当前最长的连续的白色格子的个数，如果不存在合法的P，那么P=1，不能操作的人输，问最后谁胜
首先可以手玩出来N=1，2，3的情况。当N≥4时，如果N是奇数，就拿掉中间3个，这样左右两边就都是一样的了，然后只需要模仿对方的走法即可，如果N是偶数，就拿掉中间两个，这样左右两边也是一样的。因此N≥4的时候是先手必胜的。
---------------------------------------------------
F（题目状态：赛中通过）
说是有一群n个猴子，一开始排成一排坐在椅子上，然后他们一共讲了m个笑话，第i次讲笑话的猴子是xi，讲的是第li个笑话，然后跟他距离不超过ki的猴子都能听到。
设定是这样的：如果一个猴子听到了一个没听过的笑话，他们他就会笑翻在地上，如果他已经在地上了，那么就依然在地上，如果他听到了一个听过的笑话，那么他就会回到椅子上，如果他本来就在椅子上，那么他依然在椅子上
然后问所有笑话讲完之后有多少猴子在椅子上。n,m≤1e5 , 1≤li≤1e5
易知每个猴子最后的状态只和他最后一个听的笑话是不是听过有关，所以我们可以先求出每个猴子最后听的笑话，然后再看一下他听这个笑话听了多少次
首先是求出每个猴子最后听的笑话，因为每个笑话的区间是连续的，所以用线段树打一打标记就好了。因为这道题是离线的，所以也可以倒过来搞然后用并查集优化一下，把连续的已经听过笑话的猴子连起来，以后就跳过他们。
然后这样就有n个询问，每个询问是第ai个猴子听第bi个笑话听了多少次，只需要把这些询问关于bi储存，然后模拟讲笑话的过程，每个笑话去回答他的询问，因为可以听到的猴子是连续的，所以可以用线段树来处理每个猴子听到笑话的次数。
（话说我突然发现我考试的时候写的代码是错的，我考试的时候上面那个过程是暴力处理的，然后理论上来说应该是会T的...）
---------------------------------------------------
G（题目状态：赛中通过）
说是你有一个矩形N * M的土地，然后有些格子有炸弹，问你有多少种方法框一个没有炸弹的子矩阵出来。
N,M≤10000，炸弹数≤20
送分题，考虑容斥，就是 至少有0个炸弹的方案数-至少有1个炸弹的方案数+至少有2个炸弹的方案数...这样
---------------------------------------------------
H（题目状态：赛中通过）
给你一个串，判断他是否是镜面串（回文且每一个字母都是和自己镜面对称的）。长度≤1000
送分题，暴力即可。
---------------------------------------------------
I（题目状态：赛中通过）
给你一个串，判断他有多少个子串是镜面串。长度≤1000
送分题。暴力即可（从每个点作为中心出发往两边暴力扩展）。
---------------------------------------------------
J（题目状态：赛中通过）
有一个圆，然后有一个三角形，两个顶点在圆周，一个顶点是圆心，知道半径r和圆心角a，求三角形的非半径边和圆周围成的不包含三角形的扇形的面积。
送分题。s = PI * r * r * (a / 2PI) - r * r * sin(a) / 2
---------------------------------------------------
K（题目状态：赛中通过）
有一个N，给出一个等式y=a*x*x+b*x，然后问你由这个等式生成的不超过N的y（x是正整数）组成的胜利数字是多少，有多个输出最小的，没有（集合为空集）就输出-1。胜利数字就是得分最高的数字，一个数字的得分就是，如果他是这个集合中某个数中出现次数最大的数字，那么他的得分就+1。1≤a，b，N≤100000
送分题。枚举x，按照规则暴力算出答案就好。
---------------------------------------------------
L（题目状态：未通过）
题意是有n堆连续放置的砖头，然后可以忘里面装水，现在两种操作，一种是询问一共可以装多少水，第二种是把某一堆砖头增加一定正数个。操作数和初始高度≤100000，每次增加量≤10000
⊙w⊙
---------------------------------------------------
M（题目状态：赛中通过）
题意就是给你C种货币和N次收益，每种货币告诉你名称和他和第纳尔的汇率，然后每次收益告诉你收获了多少某种货币，然后问你这些加起来一共收获了多少第纳尔。N,C≤100000，货币名称长度≤10。
送分题。按照题目上说的暴力就好了。
货币的名称可以用字典树来转换为数字。
---------------------------------------------------
比赛总结
---------------------------------------------------
这一场挺水的...其实没什么好说的，拼手速吧...
要注意的是读错题的问题，英文题面读了一遍就不想读第二遍了，所以读的时候最好是认真一点，读错题的话就很亏了
另外基本上感受了一下ACM的节奏，13道题一个人做如果不是这么水的话应该压力是很大的，还是要有队友的配合...
而且对一次AC率要求很高，一方面是有罚时，另一方面是时间太紧了,没什么用来调试的时间,如果考完之后有能A的题没有A的话那就很亏了...
---------------------------------------------------
---------------------------------------------------
---------------------------------------------------
评论 (0)
