数位DP学习心得

学数位DP还是要从搜索开始学才容易懂,一开始就丢DP的转移方程式90%的人都学不会。

B站上有一个视频讲得很好:https://www.bilibili.com/video/BV1gA411h7XC

他已经给出了模板,一个搜索的模板,代码精炼,只要把条件判断修改一下就可以套进去,非常好用,比DP好多了。

最后,所有讲解都在上面的视频里,请自行观看。

2021.2.6比赛心得

A - Vanishing Pitch:刚开始题目都没看懂......群中老师解释后才lijie了,第一题还真hand就行。

B - Remove It:尽管谷歌翻译不给力但是这题简直就是白送。输入如果与m相等就赋值为0,if(a[i]!=0)就输出。Attention:数据范围是10^9。

C - Digital Graffiti:这题题目都没看懂......谷歌吧输入的s全翻译成“小号”讲评时学长解释后才明白,不过学长那方法还真妙

D - Circle Lattice Points:ceil(x)是把x向上取整,floor(x)是把x向下取整

E - Come Back Quickly:用dijkstra。

F - GCD or MIN:

2020.2.6训练心得

熟悉的中文经过百度翻译我居然看不懂

A  青木君和他的好基友玩棒球

https://atcoder.jp/contests/abc191/tasks/abc191_a

有手就行


1
2
3
4
5
6
7
8
9
10
11
12
13
    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
       ios::sync_with_stdio(false);
       int v,t,s,d;
       cin>>v>>t>>s>>d;
       if(d<v*t||d>v*s)
           printf("Yes");
       else
           printf("No");
       return 0;
    }

B  不玩球了玩删数

有手就行


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    #include<bits/stdc++.h>
    using namespace std;
    const int MAXN=100000005;
    int main()
    {
       int n,x,a[MAXN],upset=0;
       cin>>n>>x;
       for(int i=0;i<n;i++)
       {
           cin>>a[i];
       }
       for(int i=0;i<n;i++)
       {
           if(a[i]!=x)
           {
               a[upset]=a[i];
               cout<<a[upset]<<" ";
               upset++;
           }
       }
    }

C 玩方块

AtCoder家的虾可以一半好吃一半放生吗

WA

D 玩圈

???

E 玩最短路

先试了试Floyd直接超时,然后Dijkstra依旧超时

听了讲解说要堆优化

F 共cd和比较小的那个

我寻思这看上去挺简单的,结果发现我太年轻了

100+200=300

???

2月6日比赛感想

这次yy不知道又从哪里搜到一个奇奇怪怪的网站,日本的,叫啥AtCoder,在这网站打题,首先,英语过了十级再说,或者日语十级也行,实在不行的话也要找个靠谱的翻译,不然会翻译出一些奇奇怪怪的东西,其次呢,要选对语言,(苦逼的我编译错误了N次才发现选成C++了),然后要学习前十名的大佬那打字速度,可能你刚把题目看完,别人就全A了

任务A

没什么好讲的

题目看得懂就能打出来(有手就行)

任务B

这也就是一个删除数组元素一题,也没什么好讲的,不过要注意它的范围1e9 数组的话会超时,所以直接读一个判断一下,然后输出

任务C

这题就有点小难了,思路不好想,代码实现很简单,我是7号早上学长讲完后才A的(妙,妙,妙啊!) 具体的看直播回放吧

任务D没懂

任务E

dijkstra打,但是我不会,堆优化都不会(出大问题)

任务F

没听,当时去改C了,所以亿脸懵

python教学笔记1_如何读入两个数,以空格分隔

https://blog.csdn.net/zmxSuperIT/article/details/103948498

使用map函数将上面代码整理为一行

读入a,b以空格隔开


1
2
a,b = map(int,input().split())#这样就很简明了
print(a,b)

1
2
3
4
5
6
a,b,c=input().split()  #输入三个整数
b=int(b)               #进行强制类型转换
c=int(c)
a=int(a)
ans=b*b-4*a*c          #计算方程结果
print(ans)             #输出

python 打印/输出元素,用 逗号/空格 分隔

如果有个列表list1=[a,b,c]

用print打印后:

a

b

c

如果不想换行:

print(list,end="")

如果想用逗号分隔:

print(list,end=",")

但输出:a,b,c,

多了一个逗号

这时可以用:print(",".join(str(i)for i in list1))

在每个元素之间加入一个逗号,可以换成空格


1
2
3
4
5
a=int(input())
b=int(input())
for i in range(a,b+1):
    print(i,end=" ")
 

一维数组:

arr = input("") #输入一个一维数组,每个数之间使空格隔开

num = [int(n) for n in arr.split()] # //将输入每个数以空格键隔开做成数组

print(num) #打印数组

二维数组:

(以n*n的二维数组为例)

n = int(input()) #输入二维数组的行数和列数

line = [[0]*n]*n #初始化二维数组

for i in range(n):

line[i] = input().split(" ") #输入二维数组,同行数字用空格分隔,不同行则用回车换行

print(line) #打印二维数组

https://www.php.cn/python-tutorials-427886.html

【NOIP2020】退役的总结

By Shy

高中生涯正式退役后的最后一篇blog。

时间仓促,只能简短的写写了。


这一次省一拿到了,应该也就不再继续了。

173这个成绩,对我来说,其实心中还是略微有点遗憾的,只能责怪当初年轻的自己,如果当初再努力一点点,我还能走的更远吧。

但是我想已经足够了,在这些努力过的岁月里我收获的东西太多了。

一个陕西的OI的朋友告诉我,他停了半年的课,现在文化课已经回不去了,踩线进了省一,他只能选择继续冲省队。

我想,我是幸运的,因为我还有选择,还有退路。


与信息学竞赛的这一场偶然的相遇,我从来没有后悔。

我踏上竞赛这条道路的时候,心中并不是想着名次,而是一种纯粹的热爱,对知识的渴求。

竞赛生涯中最让我难忘的,并不是真正走上赛场的那一刻。比赛前的十几个日日夜夜的奋斗,才是真正值得我永远铭记的东西。

走的越远,越发现,进步终究是要靠一点一滴的付出。我在竞赛中的最大的收获,就是学会了静下心,把自己全身心的投入到解决问题之中。我想学习也是如此,只有投入与付出,才能真正的学到知识。

信息学竞赛的学习,给了我一种不同的思考问题的方式。例如分析问题,转化模型,这些都是在理科的学习中重要的技能与方法。在不断的学习与思考中,我真正的得到了思维上的锻炼。


比赛的地点是在师大附中,

说到这个地方我就有点PTSD,因为我在这翻了两次车了,一次是省选爆0,一次是物竞的惨败。

机房的键盘感觉不像机械键盘,反而像软键盘,还是一样的难打。

交题的模式还和省选一样,就更PTSD了。

先看了半小时题吧。

第一题一眼就是裸的拓扑排序,好写,但是涉及到了分数处理,粗略估算一下可能会爆long long,不想写高精(高精除我也不会啊)于是用unsigned long long,优化了一下通分的顺序,折腾了将近一个小时吧,太久了其实,不过没办法的事。

第二题字符串,讲真这个是我失策,考前啥都复习了偏偏没复习字符串,就像省选时复习了字符串但是没复习tarjan一样。然后看这题以为字符串DP,就没想到哈希上去。

又看了第三题和第四题吧,第三题就是个构造方案题,有点像汉诺塔,口胡了一个方案发现步数会超820000,就先放着了。

第四题有点眼熟但是想不起来哪题,似乎纪中有类似题但又不太一样,只看出可以暴力整段循环节跳。

然后又过了一小时,第二题想了个n方根号n的预处理约数的暴力算法,可以拿48,感觉不错就写了。其实判断字符串相等可以用哈希多拿一点分的,就是慌了然后没想起来。

第四题本来还想写个倍增拿多一个点的分,但是时间不够只能放弃去写暴力,写完发现情况少判了,只能调了很久,结果无解的情况忘判-1了……

写完过了大样例只剩30分钟了,赶紧写t3。写完发现checker.cpp不会用,没法测样例,干瞪眼。

最后5分钟突然明白checker怎么用了,一测大样例挂了,好惨。

然后就结束了。

这个比赛写的挺狗屎的吧,其实还是太想赢了,偏偏考的又比较偏,和我预料的有差别,所以浪费太多时间了,应该多研究部分分才对的。

oitiku上测的时候t2挂了,以为自己凉了,省一都没了,悲伤至极痛定思痛下决心攻读文化课从此不碰竞赛。

然后正式成绩没几天出来后发现t2的48活了,t1经过几次csp的格雷码什么的经验教训有了先见之明开了unsigned long long结果90了,t4虽然忘判-1但影响不大,然后高中的OI生涯就完美的落下帷幕了。

据说t2卡了哈希导致朋友的哈希结果挂到连暴力分都没有,也许我的选择还是对的吧,有时成败也是有运气的啊。

愿我们都有一个光明的前途!

 

差35分省一

emmmm

省赛前一天的代码没背下来

如果背下来了,那么我就180了

第三题题目是真的没看懂

第二题的话

想法还是要改进一下

不能一直用快排,要换一种想法

桶排的话是可以做出来的

哎呀

还是要努力一点

下次希望能拿个省一

奥利给