复旦集训-Test1

---------------------------------------------------
手速场...
对我们这样的不会打字的残疾人不利啊...
(这篇文章是加密的嘿嘿嘿)
---------------------------------------------------
 

概述:
---------------------------------------------------
赛中通过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的话那就很亏了...
---------------------------------------------------

 

---------------------------------------------------

---------------------------------------------------