赛后心得

第一题:用二进制转换,然后记录,直接输出。

第二题:其实懂得有手就行,但是看到题目几乎都是第一时间想到快排,不然可AC的。

第三题:不懂就是不懂,骗到了5分。

第四题:不懂就是不懂,通过爆搜和骗分,骗到了25分。

【学习笔记】数据结构

启发式合并:

考虑一个问题:把n个总元素个数为m的数据结构合并起来(假设是线性的)。

每次合并复杂度最坏O(m),总复杂度On)?显然无法接受。

每次把个数少的合并到个数多的?复杂度O(min(m1,m2))。好像没啥用?

可是我们注意到,每次合并后个数为合并前少的部分的个数的两倍以上,每个元素最多合并logm次,总复杂度Olog)

继续阅读【学习笔记】数据结构

CSP2020分析

1.J组一套好题,一点都不水,有一定难度,而且考场了编程的基本算法和数据结构,二进制 排序 后缀表达式和中缀表达式(一直觉得不会考,然后没讲),dfs 记忆化 dp(经典问题)

2.S组。T1考察基本功 大模拟

T2 由于T1耗费太多时间,心态失衡,以至于大部分人都打小数据

T3 阅读理解很重要,由于没时间,小数据

T4 没时间,偷点

一套成功的题目,短短4道题,区分出高手 300+,优秀选手 200+,一般选手100+

2020年CSP第二轮比赛心得

T1 julian

非常搞心态,考试时调了起码2个半小时,最后一分也没有,失策了!

T2 zoo

因为T1花了太多时间,导致T2和T4都没认真看,0分。

T3 call

考试时只打了暴力,20分。。。

T4 snakes

同T2。20%的数据可以直接特判,可惜可惜。

总而言之,我个人的考试时间分配是有问题的,死磕T1,结果后面一塌糊涂。

 

 

2020 CSP-S2 游记

T1 儒略日

嗯...考场上看到这题直接跳过。

别问,问就是被坑惨过。

然后大概在五点左右才写完后面三题开始写这题。最后在考试结束前一分钟写完。

然后在洛谷一测,0分。

然后才发现一个细节没处理好(1582年只有355天,但是我把r减去355的时候忘了判年份了)

T2 动物园

其实挺水的,洛谷自测90,竟然没A!

表示超出我的预料。

其实思路很简单。把所有已知动物的编号按位或一遍,然后用cnt统计所有可用的位,最后答案就是2^cnt-n。

可用的位的意思是:这个位出现在已知动物的编号中(即某个编号中这个位为1),或者这个位没有出现在已知动物的编号中且如果这个位为1则购买清单会变化。

T3 函数

暴力。用vector存操作,洛谷上开个O3能有40,不开0分。

T4 贪吃蛇

据说是博弈论?反正我知道我这题肯定炸了。

赛后。

比赛

T1 先把数据60分拿到,剩下40分随缘打,如果没记错是这样打的

T2 排序呗就,好像是这样

T3 输入就不会了(字符串为什么会有空格啊???)

其他的可能还会比较容易

T4 深度优先搜索(不会)

把01背包代码改了一下就交了


总结:

第一次比赛还是有点慌的。。。不出意外这次第二题能A,第一题保底60,三四题能骗多少是多少了呗就。

反思:

好好学搜索!!!

最后,张老师能不能不停训啊!!!!!!

CCF CSP-2020赛后感想

话说今天的CSP-J2组是真的恶心,这第三题是典型的没马蹄;

第一题:(话说我是差不多骗分的),60分肯定稳了,剩下的靠造化;

第二题:我就打到sort就莫得做了(到10000就炸了),直接磕第三题;

第三题:原本一看,诶,好像做过,想都没想就开始打,打一半发现,我丢,我特么连输入都是错的。。。。

————————(上个厕所)——————————

第四题我一看,貌似挺简单诶,过大样例不有手就行,但是我心里始终十分忐忑不安,万一WA爆零怎么办。。。

今年的题目的确比去年难,现在只能希望CCF的测试数据水一点了

(老天保我不爆零)

2020.11.5

T1 friend   (n+1)*n/2。

T2 energy 结构体排序

T3 master

众所周知,位运算有与,或,异或三种。
与:相同位的两个数字都为 1,则为1 ;若有一个不为 1,则为0 。
或:相同位只要一个为1 即为 1。
异或:相同位不同则为 1,相同则为 0
给出l,r 以及运算符 ,询问[l,r] 区间内的每一个数通过 运算符运算后的值。

与运算

我们可以想到最后的结果一定与区间中0最多的(数)(2)有关,

eg:

r = 164(10) = 1010 0100 (2)
l = 132(10) = 1000 0100 (2)

我们引入一个中间变量 x = 160(10) = 1010 0000 (2),而 x & (x-1) = 1000 0000,可以发现 1000 0000 和区间(l,r)任意数的与运算结果都是 1000 0000,也就说区间(l,r)的连续与运算的结果为 1000 0000,

为什么x & (x-1) = 1000 0000?,

如:因为    x=160(10) = 1010 0000 (2),x -1 = 159(10)= 1001 1111 (2)
所以     (x - 1) & x =1000 0000 (2)
(x - 1) & x 可以把标记位往右的全部数位清零
因此可以寻找区间中间的 x ,来实现清零效果。

或运算

或运算的特点是,相同位只要一个为 1 即为 1。我们类比与运算,我们找到出现 1 最多的那个数就OK了。
还用刚刚的例子:

r = 164(10) = 1010 0100 (2)
l = 132(10) = 1000 0100 (2)

我们再次引入中间变量 x = 160(10) = 1010 0000 (2),而 x | (x-1) = 1011 1111,可以发现 1011 1111 和区间(l,r)任意数的与运算结果都是 1011 1111,也就说区间(l,r)的连续与运算的结果为 1011 1111。

异或

异或运算的特点是相同位不同则为 1,相同则为 0 。这里就很麻烦了,区间(l,r)中所有的数都对答案有贡献,我们要计算每一位上 0 和 1出现的次数。显然,直接统计区间(l,r)中所有数字的每一位上 0 和 1出现的次数是困难的。
异或运算两个很重要的性质:

  • 两个相同的数异或的结果为 0,即 x ^ x = 0。
  • 任何数 x 和 0 异或的结果为 x,即 x ^ 0 = x。

可以运用这两个性质对问题进行转化,我们定义 f(l,r) 为区间(l,r)的连续异或,则有 f(l,r) = f( 0 , l - 1 ) ^ f( 0 , r ) 。现在我们需要找到一个o(1)的方法计算出 f(0, x) 就OK。

  • 当 x % 4 = 0 时 f(0, x) = x
  • 当 x % 4 = 1 时 f(0, x) = 1
  • 当 x % 4 = 2 时 f(0, x) = x + 1
  • 当 x % 4 = 3 时 f(0, x) = 0

具体的证明过程,这里附上大佬的帖子,传送门
由 f(l,r) = f( 0 , l - 1 ) ^ f( 0 , r ) 和我们上边得出的结论,这个子问题也就解决了。

T4 circusee

题意:n个玩家在玩一个类似狼人杀的游戏,w个人是狼,剩下的是村民。m次发言,每次发言可以攻击或保护一个玩家。已知两匹狼不会互相攻击,狼保护的玩家一定是狼。没有一个玩家会被攻击或者保护超过一次,对于任何一次发言,a<b(输入中A a b 表示 a 攻击 b,D a b 表示 a 保护 b)。已知m次发言的情况,求场上的角色分配共有多少种可能的情况。

所有的发言会形成一个树形图(可能是森林),设立状态f[i][j][0/1]表示到第i个点的时候,有j匹狼,第i个人是狼或村民(0表示狼,1表示村民)的方案数。如果当前位的人是村民,那么他发言的对象有两种情况,可能是村民也可能是狼。而对于狼的发言只有一种情况。可做一个树上背包,将每颗子树里的方案数统计出来。(题解)

 

继续阅读2020.11.5