2022 CSP-J 游记
Day
−
∞
-\infty
−∞
在家里跟父母约定
“只要csp-j一等奖，手机随你挑！”
对于一个没有手机的初中生废物，这个约定显然勾引了我
刷题！
刷题！
再刷！
刷废……
Day
−
∞
+
?
-\infty + ?
−∞+?
发现每次刷初赛，分数都是
60
60
60多，玄！（我爱初赛）
算了，不刷了（似乎不太好）,看小说吧
但是
U
n
l
u
c
k
Unluck
Unluck,被发现了……（挺痛的）
刷题！
刷题！
再刷！
刷飞~~
Day 9.17
初赛前一天，肯定是留在学校的啦（我的作业……）
因为每次模拟测试基本都是
80
+
80+
80+的我,一点都不慌（虽然我对着我们学校的大佬考试的桌子拜了10多分钟）
好好地
s
l
e
e
p
sleep
sleep，准备明天的比赛
Day 9.18
初赛当天，我们回了机房，拿了东西，顺便打了会
g
a
m
e
game
game
这是，国豪跑进来，把我们赶了出来
于是，我和同学来到了考场，第一次见到金属探测的我感觉高级
一会休整，比赛就开始了（老师带小学生去厕所了，晚发了卷……）
前面做的很顺，来到第一道程序题（被卡住了），老样子不管它，坐后面的
发现宝藏！，最后程序填空题，第一道质因数分解，第二道，
B
f
s
Bfs
Bfs模板？
不管这么多，直接火速填完去检查
考完之后感觉分数线会很高，但是不管这么多，开网的电脑诱惑比这个大多了
Day 9.?
分数出来前一天，我还在吊着个心
不过总算好了点：
78
78
78！ 分数线才
68.5
68.5
68.5？,有点小水
嘚瑟了几天的我，重新回到了复赛的备赛
刷了
N
O
I
P
NOIP
NOIP普及的题,有蓝题？（自闭）
模拟赛也不是很理想（虽然没认真做）
感觉我要
d
i
e
die
die
但是我转念一想，不就是绿题和黄题嘛，有什么难得
于是我就保持着这样的心态到考试那一天
Day 10.?
2010
C
S
P
−
J
CSP-J
CSP−J第三题表达式的值
A
C
AC
AC
Day 0
好消息，封校了，该开心还是伤心呢？
前一天，国豪开了网
我拼命复习
R
M
Q
RMQ
RMQ,
L
C
A
LCA
LCA,
状压
d
p
状压dp
状压dp,
树状数组和线段树
树状数组和线段树
树状数组和线段树
事实证明这些普及都不会考……
“6:20到学校门口集合”，有病吧，8:30考试，7:00到？留着看风景吗？
不管他了，睡觉先！
Day 1
于是我跟我们宿友说：“
6
:
00
6:00
6:00钟叫我”
于是我
6
:
18
6:18
6:18起……
“我以为你们开玩笑·，我就没叫你们”
好家伙，你宿友有考试了你不知道？
算了，我粗糙的整理一番，直接跑下楼，眼睛在冷风中半睁半闭，难受
到了那里，成为最后一名的感觉不错
但是
7
:
00
7:00
7:00才走的大巴让我很无语
在车上,平分了零食
我吃了4根绿肠，祝我考高点
在考场门前，和大家聊了会，就进入了考场（我旁边的认识！）
T1：乘方
真的水，开个
l
o
n
g
l
o
n
g
long\ long
long long
如果超过了1e9,那就输出-1，否则输出就行(没想到有个点竟然是
1
1
0
9
1^{10^9}
1109,把我卡了一个点)
T2:解密
应该是我想的最久的一道题了
首先又题意得，可以得出一个方程组
{
n
i
=
p
i
∗
q
i
1
式
e
i
∗
d
i
=
(
p
i
−
1
)
(
q
i
−
1
)
+
1
2
式
\left\{\begin{aligned} n_i &= p_i*q_i &&1式\\ e_i*d_i&=(p_i-1)(q_i-1)+1&&2式 \end{aligned}\right.
{niei∗di=pi∗qi=(pi−1)(qi−1)+11式2式
我们将二式拆一下
e
i
∗
d
i
=
p
i
∗
q
i
−
p
i
−
q
i
+
2
3
式
\begin{aligned} e_i*d_i=p_i*q_i-p_i-q_i+2&&3式 \end{aligned}
ei∗di=pi∗qi−pi−qi+23式
发现一式和三式都有而二次项的
p
i
∗
q
i
p_i*q_i
pi∗qi,我们不希望有二次项，于是我们用一式减三式
得
n
−
e
i
∗
d
i
=
p
−
i
+
q
i
−
2
n
−
e
i
∗
d
−
i
+
2
=
p
i
+
q
i
p
i
+
q
i
=
m
\begin{aligned} n-e_i*d_i&=p-i+q_i-2\\ n-e_i*d-i+2&=p_i+q_i\\ p_i+q_i&=m \end{aligned}
n−ei∗din−ei∗d−i+2pi+qi=p−i+qi−2=pi+qi=m
于是我们就可以得到一个方程组
{
p
i
+
q
i
=
m
p
i
∗
q
i
=
n
\left\{\begin{aligned} p_i+q_i = m\\ p_i*q_i=n \end{aligned}\right.
{pi+qi=mpi∗qi=n
于是我们就可以枚举了，枚举加法会好一点
需要枚举
m
2
\frac{m}{2}
2m次，总共时间复杂度是
O
(
Q
m
2
)
O(Q\frac{m}{2})
O(Q2m),显然时间复杂度承受不住
m
2
\frac{m}{2}
2m次的枚举次数显然太多，我们要优化下
很容易想到二分，于是我们就要证单调性
设有两个数
a
,
b
a,b
a,b,显然我们要证明
a
∗
b
<
(
a
+
1
)
∗
(
b
−
1
)
a*b<(a+1)*(b-1)
a∗b<(a+1)∗(b−1)什么时候成立
我们拆一下右边
(
a
+
1
)
∗
(
b
−
1
)
=
a
∗
b
−
a
+
b
−
1
=
a
∗
b
−
(
a
−
b
+
1
)
\begin{aligned} &(a+1)*(b-1)\\ &=a*b-a+b-1\\ &=a*b-(a-b+1) \end{aligned}
(a+1)∗(b−1)=a∗b−a+b−1=a∗b−(a−b+1)
于是只要
a
−
b
+
1
<
=
0
a
+
1
<
=
b
\begin{aligned} a-b+1<=0\\ a+1<=b \end{aligned}
a−b+1<=0a+1<=b
单调性成立
于是我们只要将
a
a
a的枚举范围限制在
m
2
\frac{m}{2}
2m二分即可
总时间复杂度是
O
(
Q
l
o
g
m
2
)
O(Qlog\frac{m}{2})
O(Qlog2m)，可以
A
C
AC
AC这题
T3:逻辑表达式
考场上看到这题开心的不得了，从而看错了几次题目
为什么？
这不是和
C
S
P
2020
T
3
CSP2020T3
CSP2020T3差不多一样吗？
于是我就将他转后缀，建树，然后一通乱过了大样例（我考试前一周才做过……)
T4:上升点列
考场上过了第三题，高兴过度，导致没有看对题
直接打了个暴搜（还搜错了），就去检查了（睡梦中检查的？）
这里说下正解吧（我考场想出来了，没时间写了，第三题看错题耽误好久）
显然是
d
p
dp
dp
我们定义
d
p
dp
dp数组含义为
d
p
i
j
:
前
i
个点用了
j
个点的最大点数（排了序）
dp_{ij}:前i个点用了j个点的最大点数（排了序）
dpij:前i个点用了j个点的最大点数（排了序）
状态转移方程为
d
p
i
j
=
max
d
p
k
m
+
m
+
1
,
d
p
i
j
(
m
=
d
i
s
(
i
,
j
)
−
1
)
dp{ij}=\max{dp_{km}+m+1,dp_{ij}}(m=dis(i,j)-1)
dpij=maxdpkm+m+1,dpij(m=dis(i,j)−1)
最后统计答案的时候加上
k
−
j
k-j
k−j就可
期望得分
100
+
100
+
100
+
0
=
300
\mathcal{100+100+100+0=300}
100+100+100+0=300
各大平台估分
100
+
70
+
100
+
5
=
275
\mathcal{100+70+100+5=275}
100+70+100+5=275基本是稳的了
D
a
y
?
Day\ ?
Day ?
数据出来了，教练说有个同学
270
270
270分的变成了
200
200
200分，我从那个时候心就跳了，说那个同学第二题
0
0
0分
我等不及了，直接找了台开网的电脑，测了我第二题
0
0
0分？
f
a
c
k
fack
fack!!!
我对比了一下我满分的代码，将二分边界的
m
/
2
−
1
m/2-1
m/2−1改成
m
/
2
+
1
m/2+1
m/2+1
100
100
100分？
f
a
c
k
fack
fack!!!
毫无疑问，一等奖没了
我哭了好几天
我爱死这二分，爱死
C
S
P
CSP
CSP出的数据（每个数据都有
p
=
q
p=q
p=q的点？一分都不给？）
真实成绩：
100
+
0
+
100
+
10
=
210
\mathcal{100+0+100+10=210}
100+0+100+10=210
反思
换个角度想，这次出的问题明显是心态问题，不应该高兴过度，我应该想够用就行
因为你不知道你前几题到底是不是全对
第一次
C
S
P
CSP
CSP之旅，没了
不管他了，争取明年
J
组满分
J组满分
J组满分！
S
进复赛！
S进复赛！
S进复赛！
D
a
y
Day
Day
+
∞
+\infty
+∞
不去想了，奋力战斗！
惜哉!
最新文章
- [Keras] Install and environment setting
- Android 6.0 权限管理最佳实践
- windows上配置git
- POJ 2001
- Ehcache(2.9.x) - API Developer Guide, Transaction Support
- NameNode元数据的管理机制(三)
- [Angular 2] Using a Value from the Store in a Reducer
- hadoop的thriftserver配置
- vector cin
- Navicat查询结果不能修改的原因
- 7.4 electirc.c -- 计算电费
- Docker: 创建带数据的MySql container
- IntelliJ IDEA生成live template（代码模板）
- C++虚表详解
- 在centos使用redis几个坑
- 洛谷 P1070 道路游戏 解题报告
- python垃圾回收三之标记清除
- Python3基础 if elif 示例 判断一个数在哪个区间内
- python打包到pypi小结
- Spring Boot中使用EhCache实现缓存支持