[10.11]CSP-S模拟赛

news/2024/10/11 20:21:49

宝贵经验:

写题的时候想出时间正确的方法后千万注意计算空间,否则可能会像我一样:

\(35\to 15\to 0\)

赛前

小 L 说比上次简单。

赛时

T1 一开始没有思路,但是注意到了两个关键条件:

询问数 \(\le 300\)

\(n,m\le 10^9\)

然后想到正解绝对不是去直接修改。

注意到询问是单点,容易想到只考虑这个点的移动情况。想到这儿其实已经结束了,所以开始写代码。

写完以后发现挂了,然后意识到有很多细节错误。开始调代码,终于在 2h 左右过掉了大样例。

T2 最开始发现条件很奇怪,如果设 \(dp_{i,j}\) 表示从 \((1,1)\)\((i,j)\) 的答案,稍微转化一下发现 \(dp_{i,j}\) 可以从 \(dp_{i-1,j},~dp_{i,j-1},~dp_{i-1,j-1}\) 转移过来,得到一个类似二位前缀和的 DP。

然后写完以后轻松过掉样例。发现 \(n,m\le 10^4\) 的点也可以跑,于是就写了个 long long dp[10000][1000] 上去。

改完以后有了 35pts(

T3 大部分人的分数都一样,枚举全排列以后暴力 \(mn\) 找答案,小 H 神奇做法得到 20pts%%%。

赛时我时间复杂度计算错误,一位全排列是 \(\mathcal{O}(2^n)\) 的,并且猜出了测试点算法(bushi。

猜完以后我先写了暴力,然后去想我猜的那个做法的实现(竟然还发现了很多类似无后效性的性质),想了半天想不出来,就弃了去搞 T2。

其实看到这个 \(n,m\le 80\) 的数据范围就应该意识到正解大概是一个 \(\mathcal{O}(n^4\sim n^5)\) 的 DP,讲题的时候发现果然是,但是状态很神奇,于是想起来 取代_ 之前说过小 L AK了 JOI 的 DP 场,所以就联系起来了%%%

T4 赛时感觉题面太长了就没看,赛后的讲解比较有思维难度,需要再去好好看看。

赛后

T2 赛后意识到空间会炸。问了 HDS 发现果然会炸。心存侥幸问了小 L 评测方式,希望是按照控件使用计算空间,但是回应是按照开的大小,然后没希望了。

改成 vector 以后有了 15pts,然后突然意识到我最后只需要求 \(dp_{n,m}\),所以根本不需要数组,直接用一个变量统计答案就可以了。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ryyt.cn/news/70368.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

相关文章

南沙C++信奥赛陈老师解一本通题 1950:【10NOIP普及组】接水问题

​ 【题目描述】学校里有一个水房,水房里一共装有m个龙头可供同学们打开水,每个龙头每秒钟的供水量相等,均为1。 现在有n 名同学准备接水,他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n 编号,i号同学的接水量为w。接水开始时,1 到m 号同学各占一个水龙头,并同…

如何快速上手一个新项目?

前言 最近知识星球中有小伙伴问我:如何快速上手一个新项目? 这个问题是一个公共问题,估计很多换了公司的小伙都想问这个问题。 我在工作的这些年当中,换过几次工作,接手过同事的一些项目,需要经常上手一些不同类型的新项目。 今天这篇文章跟大家一起聊聊我的一些总结和思…

Nacos服务相关

nacos是阿里开源的一款用于微服务的多服务管理工具,通过服务注册进入内部服务器可以看到注册的服务; 服务注册原理: 在微服务远程调用的过程中,包括两个角色: 服务调用者,调用其他服务的接口,服务提供者,提供接口给其他服务调用 在大型微服务项目中,服务提供者的数量会…

熵权法

熵是热力学的一个物理概念,是体系混乱度或无序度的度量,熵越大表示系统越乱(即携带的信息越少),熵越小表示系统越有序(即携带的信息越多)。 信息熵借鉴了热力学中熵的概念,香农把信源所含有的信息量称为信息熵,用于描述平均而言事件信息量的大小,所以在数学上,信息熵…

MacOS在VS code上运行Python失败,通过更改pythonPath解决

问题描述安装完成python后,默认的运行python命令是python3,而VSCode上默认命令是python 解决办法在file\preference\settings下(或使用快捷键Ctrl + ,),搜索python.pythonPath然后点击Add Item,加入 "python.pythonPath" = "python3"再修改一下调试结…

插值方法

插值是什么 在工程中,我们经常要用一条曲线将一些点依次连接起来,称为插值。 插值的可行性证明 插值法定理:对n+1个不同的节点有唯一多项式\(\phi (x)=a_0+a_1x+\cdots+a_nx^n\),使得\(\phi_n(x_j)=y_j(j=0,1,2,\cdots,n)\) 证明:将\(x_0\)到\(x_n\)带入多项式能得到一个线性…

5.4求解非凸非线性规划

import numpy as np from scipy.optimize import minimize# 定义目标函数 def objective(x):return -np.sum(np.sqrt(x)) # 注意:scipy的minimize默认是最小化问题,所以这里取负号# 定义约束条件 constraints = [{type: ineq, fun: lambda x: 10 - x[0]}, # x[0] <= 10{…

CentOS系统安全配置

一、账户安全及权限 禁用root以外的超级用户禁用root以外的超级用户 1.检测方法:点击查看代码 cat /etc/passwd 查看口令文件,文件格式如下 login_name:password:user_ID:group_ID:comment:home_dir:command 若user_ID=0,则该用户拥有超级用户的权限。查看此处是否有多…