首页 > 其他分享 >20241013 洛谷SCP模拟

20241013 洛谷SCP模拟

时间:2024-11-08 15:22:39浏览次数:5  
标签:lfloor cyq 洛谷 20241013 大神 rfloor 转移 frac SCP

20241013 洛谷SCP模拟

J1. 带余除法

急眼了,J 组 T1 做不出来。经 cyq 大神指点。

考虑将题中给出的带余除法转化:\(n=kq+r\),移项得到 \(r=n-kq\)。

这里 \(n,k\) 都是定值,于是对于每一个 \(q\),都有唯一的一个 \(r\) 与之对应。考虑余数的性质:

\[0\le r=n-kq<q \]

解不等式得到 \(\lfloor\frac n{k+1} \rfloor < q\le\lfloor \frac n k\rfloor\)。容易发现这个范围内的所有整数都可以取到,于是答案为 \(\lfloor \frac n k\rfloor-\lfloor\frac n{k+1} \rfloor\)。

J2. 奖牌排序

急眼了,J 组 T2 做不出来。经 cyq 大神指点。

对于每个人,有三种排序方式取最优。

那么对某种方式考虑,我们先对这一维排序,接着对每个人更新答案。考虑每个人在这种方式下的最高排名怎么算,发现其实就是这一维比他小的人的个数加一,于是可以二分求解。

J4. 配对序列

cyq 大神说这题代码很简单并且是 \(O(n)\) 的,可是我只会无脑数据结构,破防。

考虑一个朴素的 dp。设 \(f_{i,0/1}\) 表示选第 \(i\) 个位置,且这个位置是相邻数对中的第 \(1/2\) 个数,最长序列的长度。转移枚举上一个选的位置 \(j\),那么若 \(a_j=a_i\),则 \(f_{j,0}\) 可以转移到 \(f_{i,1}\);否则 \(f_{j,1}\) 可以转移到 \(f_{i,0}\)。

对于第一种转移,我们记录 \(g_i\) 表示所有满足 \(a_j=i\) 的 \(j\) 中,\(f_{j,0}\) 的最大值,这样就能 \(O(1)\) 转移了。对于第二种转移,我们开一颗权值线段树,记录 \(f_{j,1}\) 的最大值,转移时只要查询区间 \([1,a_i)\) 和 \((a_i,V]\) 即可。\(O(n\log V)\)。

这题 \(n,V\) 同阶,\(V\) 开大时加个离散化就行了。所以时间复杂度是 \(O(n\log n)\) 的。

S1. 商店砍价

这题绝对比 J 组 T1T2 都简单。

注意到 \(v\) 只有 \(10^5\),那么容易看出,第二种操作进行时,剩余数的位数一定不超过 \(5\)。于是容易想到枚举进行第二种操作时的 \(n\) 并计算贡献,注意这里枚举的数一定是原数的子序列,子序列自动机判一下即可。

cyq 大神说我绝对是非正解。又被 D 了。

标签:lfloor,cyq,洛谷,20241013,大神,rfloor,转移,frac,SCP
From: https://www.cnblogs.com/luyuyang/p/18535172

相关文章

  • 洛谷P1157 组合的输出(Python)
    伤痕,是男子汉的勋章。——圣斗士星矢一、题目P1157组合的输出https://www.luogu.com.cn/problem/P1157二、代码defpri(L):foriinrange(len(L)):ifL[i]==True:print("{:3d}".format(i),end='')defdfs(n,r,cur,count):#n,r为题......
  • 洛谷题单指南-二叉堆与树状数组-P2827 [NOIP2016 提高组] 蚯蚓
    原题链接:https://www.luogu.com.cn/problem/P2827题意解读:初始n个数,每次取最大值x,根据u/v分成两部分:x*u/v,x-x*u/v,然后其余数都增加q,整个过程重复m次。输出有两类数据:第t,2t,3t...次取出的最大值;最后剩余的数第t,2t,3t...个,从大到小输出。解题思路:直观上,通过模拟法可以实......
  • 洛谷P3870[TJOI20009]-开关
    时间复杂度越高的算法能模拟的结构就越多...题目大意:给定一串长度为n,元素只能为0或1的序列,默认该序列元素全为0.接下来需要进行m次操作,操作分为两种:1.把区间\([a,b]\)中的所有元素值取反.2.求区间\([a,b]\)中元素值为1的元素数量.每一次调用操作1时,每次一行输出一个......
  • 洛谷 P2113 看球泡妹子(DP)
    传送门https://www.luogu.com.cn/problem/P2113解题思路可以设  表示前  场比赛看了  场,小红的满足度为  的最大精彩度。然后可以枚举前面的一个比赛 ,可以得到转移方程:但是,我们发现数组空间有一点小大,可以优化一下。发现每一次转移都是 ,于是可以滚动数组优化空......
  • 洛谷P3516 [POI2011] PRZ-Shift
    题意Link有一个排列\(a\),你可以执行两种操作:A:将最后一个数移到最前面B:将第三个数移到最前面构造一组操作序列将其变为递增排列,输出形如5a2b...表示执行\(5\)次A操作再执行\(2\)次B操作。思路很有意思的构造。仔细思考,操作A使我们能将原排列变为它的任何一......
  • 洛谷P5741
    P5741【深基7.例10】旗鼓相当的对手-加强版-洛谷|计算机科学教育新生态【深基7.例10】旗鼓相当的对手-加强版题目描述现有N(N<=1000)名同学参加了期末考试,并且获得了每名同学的信息:姓名(不超过8个字符的字符串,没有空格)、语文、数学、英语成绩(均为不超过150的自然......
  • 洛谷 P1638 逛画展
     此题运用滑动窗口和左右指针1.用identifiers储存画师的编号2.用count储存画师的画的数量3.将左右指针初始化为0,先右移右指针,当恰好找到第一个解时(即左右指针范围内画师数量恰好等于m),进入下一个while,如果此时窗口长度小于前一个解的窗口长度,相等则取左指针较靠前的。4.移......
  • 洛谷题单指南-二叉堆与树状数组-P1801 黑匣子
    原题链接:https://www.luogu.com.cn/problem/P1801题意解读:动态维护一组序列,并随时可以求第k小的值,每次求第k小的顺序是递增的,比如第一次取第1小,然后是第2小,以此类推。解题思路:对于求第k小的问题,已经介绍过几种方案:1、快选算法,每次查询时间复杂度logn,传送门:https://www.cnblogs......
  • 【洛谷 P3695 CYaRon!语】从一道大模拟入坑自制编程语言
    原题传送门本来是想投题解的,但是仔细阅读了一下主题库题解规范,发现这篇文章更加适合单独作为一篇blog阅读而非挂在题解区里污染环境,所以就这样了。0xff开始之前这道题我很早以前就开始看了,那时还只有星野梦美大佬的一篇题解。而到现在,我终于是有了时间和能力来切掉这道题,......
  • 洛谷题单指南-二叉堆与树状数组-P3378 【模板】堆
    原题链接:https://www.luogu.com.cn/problem/P3378题意解读:实现二叉堆。解题思路:二叉堆本质上一棵完全二叉树,根节点称为堆顶,根据特性不同分为有两种:大根堆:所有父节点的值大于子节点,根节点最大小根堆:所有父节点的值小于子节点,根节点最小主要作用:动态维护序列,并快速找到最大/最......