首页 > 其他分享 >[DMY]2024 CSP-S 模拟赛 Day 10

[DMY]2024 CSP-S 模拟赛 Day 10

时间:2024-10-05 14:21:59浏览次数:8  
标签:10 赛时 复杂度 T3 T1 2024 时间 Day 暴力

赛时

对于 T1,看懂题面以后感觉很可做。

首先明确正解复杂度应该是基于 \(N\) 额度线性做法。

把输入按照开始时间排序,然后依次处理。

赛时考虑到一个元素在覆盖过程中遇到其他元素时无法确定时间先后,确定后想要找到该元素的当前位置和重新覆盖有些困难,写了 1h 以后先放弃了。

舍远求近,基于时间写了一个 \(\mathcal{O}(nk)\) 的做法,发现时间很大,用 20min 对时间进行离散化,跑过了小样例。

先不管 T1,去看 T2。

T2 的话可以根据正负性列方程搜索求解,复杂度 \(\mathcal{O}(2^n)\)。

想了一会发现并不是太会低复杂度做法,先去看后面的题。

T3 和 T4 一开始的时候都不太会暴力做法,这时候我面临去改 T1 还是继续拿暴力分的选择。

上个厕所回来回了 T3 和 T4 的暴力做法。

T3 的话为了在遍历的时候复杂度低于 \(n^2\) 做到 \(nlogn\) 使用了 set,赛后发现 T 了导致爆蛋。

T4 的话使用 Floyd 硬搞,复杂度 \(n^5\),一遍就过掉了样例。

时间还剩下 1h,看别人都过掉了 T1,便回去改 T1。

想到了一个利用优先队列找时间节点的方法,代码很长,用 30min 写了一个将近 200 行的代码,剩下的时间都在挑,结果到最后也没有调出来。

赛后

班里的分数差距主要在于 T1。

如果当时没有去写暴力分并且 A 掉 T1 的话,我将以 110 分的成绩挤进首页。

但是 T3 暴力写挂了,T1 只拿了 50 分。

想想看来 T1 其实很简单,赛时没有考虑到按照时间排序以后其实可以直接大胆覆盖,不会出现占用状况。

正解其实很短,可以做一个多源 bfs 最短路。

T3 的话主要是 set 浪费了时间,赛时其实使用 vector 的话也可以做到低于 \(n^2\)。这个不难想,但是赛时没有想出来。

打的不太好,差距主要还是在 T1。

标签:10,赛时,复杂度,T3,T1,2024,时间,Day,暴力
From: https://www.cnblogs.com/Lydic/p/18447833

相关文章

  • 蓝桥杯2024年第十五届省赛A组-有奖问答
    题目描述小蓝正在参与一个现场问答的节目。活动中一共有30道题目,每题只有答对和答错两种情况,每答对一题得10分,答错一题分数归零。小蓝可以在任意时刻结束答题并获得目前分数对应的奖项,之后不能再答任何题目。最高奖项需要100分,所以到达100分时小蓝会直接停止答题。......
  • Leecode热题100-3.无重复字符最长子串
    给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串 的长度。示例 1:输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc",所以其长度为3。示例2:输入:s="bbbbb"输出:1解释:因为无重复字符的最长子串是"b",所以其长度为1。......
  • R3CTF2024 WP
    一、PWN1.Nullullullllu在直接给libc_base的情况下,一次任意地址写\x00。直接修改 IO_2_1_stdin 的_IO_buf_base末尾为\x00,那么_IO_buf_base就会指向 IO_2_1_stdin 的_IO_write_base,接下来就是利用getchar函数触发写操作修改 IO_buf_base 为 IO_2_1_stdout ,再......
  • [赛记] 多校A层冲刺NOIP2024模拟赛01【衡中】
    构造字符串50pts错解50pts;考虑正解,对于题目中的要求,我们可以转换成若干个相等与不等的操作,若相等则用并查集合并一下,不等则连边,若同块连边则无解,否则从前往后遍历赋值,每次找所连边其它块值的$\operatorname{mex}$即可;时间复杂度:$\Theta(nm\alpha(n))$;点击查看代码#i......
  • WMCTF 2024 wp
    WEBPasswdStealer前言本来题目叫PasswdStealer的:)考点就是CVE-2024-21733在SpringBoot场景下的利用。漏洞基本原理参考 https://mp.weixin.qq.com/s?__biz=Mzg2MDY2ODc5MA==&mid=2247484002&idx=1&sn=7936818b93f2d9a656d8ed48843272c0不再赘述。SpringBoot场景下的利用前文的分析......
  • Cornell cs3110 - Chapter7 Exercises
    (*Exercise:mutablefields*)typestudent={name:string;mutablegpa:float;}letstuA={name="Alice";gpa=3.7}let()=stuA.gpa<-4.0(*Exercise:intfun*)letinc=ref(funx->x+1)letnum=!inc3109(*Exercise:a......
  • Leetcode 1011. 在 D 天内送达包裹的能力
    1.题目基本信息1.1.题目描述传送带上的包裹必须在days天内从一个港口运送到另一个港口。传送带上的第i个包裹的重量为weights[i]。每一天,我们都会按给出重量(weights)的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。返回能在days天内将传送带上的所......
  • 2024.10.4(周五)
    <%@pagelanguage="java"contentType="text/html;charset=UTF-8"pageEncoding="UTF-8"%><!DOCTYPEhtml><html><head><title>工资核算信息</title><style>/*整体页面布局和样式*/......
  • 2024.10.7(周一)
    <%@pagelanguage="java"contentType="text/html;charset=UTF-8"pageEncoding="UTF-8"%><!DOCTYPEhtml><html><head><title>车间班组</title><style>/*整体页面布局和样式*/......
  • 《代码大全》阅读笔记1(2024.10.4)
    第一章:引言软件构建的艺术:介绍了软件开发的复杂性,以及编写高质量代码的重要性。强调了良好的编码习惯不仅能提高代码的可读性和可维护性,也能降低后期的开发成本。第二章:软件构建的哲学质量的重要性:讨论了软件质量的定义,强调高质量软件不仅包括功能的正确性,还包括可维护性、......