首页 > 其他分享 >2024.9.13训练记录

2024.9.13训练记录

时间:2024-09-13 21:45:56浏览次数:14  
标签:满足条件 13 训练 2024.9 可以 元素 枚举 区间 dp

下午ARC104模拟短时赛

T1、T2:

T1签到题。

T2签到题, \(O(n^2)\) 乱做。但是实际上可以空间换时间开桶到 \(O(n)\)。也非常简单。

T3:

考场没有做出。
思考的关键在于想到可以对于区间单独判断是否满足条件。
知道了如何判断区间是否满足条件后,可以做一次 \(O(n)\) 的 \(dp\)。每次枚举最后一个段来判断前 \(i\) 个位置能否满足条件。
现在来想如何判断区间是否合法:
对于一个完整的满足条件的区间,一定是端点重叠的形式。
比如判断 \([1, 6]\) 这个区间。如果它合法,可能的填写形式就只有 \([1,4], [2,5], [3,6]\) 这三个区间。
简而言之也就是:区间的前一半全都是进电梯,后一半是这些人按进的顺序出。
这样就可以 \(O(n)\) 判断区间是否合法。
总时间复杂度:\(O(n^3)\)。

T4:

考场没有做出。
感觉是订正后提升最大的一道题。
题面非常阴间。
英译中后大意为求对于每个 \(x\exist[1,n]\),求出集合元素在 \([1, n]\) 中任选,可以选的次数在 \([0,k]\) 间的操作组成的,满足元素平均数为 \(x\) 的多重集个数。
首先有一个经典(/jk)trick,因为需要求平均数为 \(x\) ,所以在做背包之前将每个数 \(i\) 变为 \(i-x\),这样背包只需要维护和为 \(0\),不用多维护一个元素个数求平均数。
这里赛场上就没想到。考虑了维护元素个数,空间会炸,遂放弃D死磕C。遗憾的。
感觉很多考试不能发挥好都是思维题开头的一个经典小trick导致的问题转化没有想到,输输输。
非常思维的点是,因为要对于每一个 \(x\) 求值。首先确定下来要枚举 \(x\),然后便可以考虑从 \(x-1\) 到 \(x\) 的过程中有哪些变化。
原本可选的元素是 \([1, n]\),在上一次做 \(x-1\) 的答案时被考虑成了 \([1-(x-1), n-(x-1)]\)。
而现在则是 \([1-x,n-x]\)。
注意到就是在数轴上向左移了一位。
在考虑和为 \(0\) 时,可以看做被选择元素的负数部分和正数部分绝对值之和相等
所以可以将负数部分和正数部分看做同一个问题。
即:预处理 \(f[i][j]\) 表示可选值域在 \([1,i]\),每个数最多选 \(k\) 次,最终和为 \(j\) 的方案数。
最终对于每一个 \(x\) 的答案就是\(k + (k + 1) * ∑_{1 \leq j \leq lim}f[-(1-x)][j] * f[n-x][j]\)。
即枚举正负部分的绝对值 \(j\) 来统计方案。
这里注意到 \(dp\) 状态中的值域是从 \(1\) 开始的,实际上拍到数轴上还可以随意选 \(0\)。
对于每一个方案,可选 \(0\) 的个数是 \([0,k]\) 共 \(k+1\) 种,所以sigma外面乘上一个 \(k+1\)。而绝对值同样可以是 \(0\),此时的方案有 \(k\) 种,所以再加上 \(k\)。
即可通过此题。

感觉对我来说,写多重背包的预处理也是一个难点。因为枚举每个数选几次会T。
这里用到神秘前缀和优化。
注意到枚举选的次数的写法中,\(f[i - 1][j - p * i]\) 会加到 \(f[i][j]\) 上,即 \(f[i][j]\) 是上一层的所有 \(j'\) 与 \(j\) 关于 \(i\) 同余,且 \(j'>=j-k*i\) 的状态的和
所以可以写出这样的代码:

    for(int i = 1; i <= n; i ++) {
        for(int l = 0; l <= 505000; l ++) {
            f[i][l] += f[i - 1][l];
            if(l - i >= 0) f[i][l] += f[i][l - i], f[i][l] %= mod;
        }
        for(int l = 505000; l >= 0; l --) {
            if(l - (k + 1) * i >= 0) f[i][l] -= f[i][l - (k + 1) * i];
            f[i][l] = (f[i][l] + mod) % mod;
        }
    }

注意到在第一次 \(l\) 的循环中,没有考虑 \(j'>=j-k*i\),所以在第二次循环把 \(j-k*i\) 之前的减掉。
很难不发现,在订正代码时,其他同学都早就理解了这个优化写法,只有我傻乎乎看了半个晚上再写(/kk)。
这道题就到这里了。

T5,T6

T5讲评时没有完全听懂,听懂了ywz的dp方法,但是忘记了其他部分/yiw?
T6讲评听了个开头,寄了。

订正情况

标签:满足条件,13,训练,2024.9,可以,元素,枚举,区间,dp
From: https://www.cnblogs.com/docxjun/p/18412874

相关文章

  • 学习笔记 韩顺平 零基础30天学会Java(2024.9.13)
    P545TreeMap源码解读     TreeSet的k-v其中的v是一个静态的对象,但是TreeMap的v是可以变化的     TreeMap使用默认构造器取出的顺序和添加的顺序是不一样的,但是有构造器实现了Comparator接口的匿名内部类,可以按顺序排序P546Collections工具类1P547Collect......
  • 8200-1312 蒸汽轮机数字调速器控制
    特性和功能集成图形前面板HMI屏幕多语言屏幕(包括中文),便于操作员使用、诊断和控制大屏幕允许轻松导航和图标查看参数和性能操作员和工程师可在本地查看实时趋势带有当前操作点视图的图形蒸汽图,用于提取和进入可配置的标签名称,可轻松识别连接内部“涡轮机模拟器”,用于在系统......
  • 基于SpringBoot的学生网上选课系统(11355)
     有需要的同学,源代码和配套文档领取,加文章最下方的名片哦一、项目演示项目演示视频二、资料介绍完整源代码(前后端源代码+SQL脚本)配套文档(LW+PPT+开题报告)远程调试控屏包运行三、技术介绍Java语言SSM框架SpringBoot框架Vue框架JSP页面Mysql数据库IDEA/Eclipse开发四、项......
  • 9.13 模拟赛(炼石计划 11 月 04日 CSP-S 十连测 #7)
    炼石计划11月04日CSP-S十连测#7【补题】-比赛-梦熊联盟(mna.wang)复盘基本上一眼秒了T1,先写这题。在8:30写完了对拍。用了将近一个小时。然后放到桌面2就没管,一直拍到了比赛结束。T2什么牛魔题面???出题人学过语文吗???T3把题读懂了,但是一直不能正确模拟出样例1,......
  • 南沙csp-j/s一对一家教陈老师解题:1334:【例2-3】围圈报数
    ​【题目描述】有n个人依次围成一圈,从第1个人开始报数,数到第m个人出列,然后从出列的下一个人开始报数,数到第m个人又出列,…,如此反复到所有的人全部出列为止。设n个人的编号分别为1,2,…,n,打印出列的顺序。【输入】nn和mm。【输出】出列的顺序。【输入样例】417【输出样例】......
  • 南沙csp-j/s一对一家教陈老师解题:1317:【例5.2】组合的输出
    ​ 【题目描述】排列与组合是常用的数学方法,其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n),我们可以简单地将n个元素理解为自然数1,2,…,n,从中任取r个数。现要求你用递归的方法输出所有组合。例如n=5,r=3,所有组合为:123 124 125 134 135 14......
  • java学习9.13
    将java测试卷重新完成,测试完后基本完成需求,无明显BUG结合课堂上去写这个java测试卷,总的来说,之前没有独立写过类似项目+限时是比较大的问题。如果之前没有经历类似的情况,很多功能都是第一次用,那么就会导致出现bug而不知道如何去改,并且加上时间限制,如果时间全花在改bug上,又无法完......
  • 0913
    亲爱的出租车大人你好让我嘎掉的方式有很多种但绝不是像是要开出80公里一样猛踩油门后又在车轮区区位移80厘米后猛踩刹车我承认你的双脚很灵活可以自如的做到刹车和油门但是我宁可你把这种灵活用在用你的双脚控制方向盘上也不愿意你用在花式踩在我前后移动的胃上当然你的......
  • NFLS 2024.9.13 T4
    题意给出一棵以\(1\)为根的树\((n\le10^4)\)和\(k(k\le10^{14})\)。要求给每个点一个\(a_i\)使得\(a_i\mida_{fa_i}\),且\(\proda_i\lek\)。思路这题有一个很妙的思路,但不是前面。设最终的\(\proda_i=S\),可以对\(S\)的每个质因子单独考虑。设\(g(s)\)......
  • 20240913_155935 mysql 触发器
    建表需求创建一个日志表记录teacher表的操作日志情况增删改的相关信息要保存起来方便定期查看明确字段表名:log_info列信息idactioninfotime创建表格CREATETABLElog_info( idINTPRIMARYKEYAUTO_INCREMENT, action_nameVARCHAR(11), infoVARCHAR(111), act_......