首页 > 其他分享 >CSP模拟49

CSP模拟49

时间:2023-10-06 09:03:38浏览次数:32  
标签:20 49 cdot dfrac 可以 位置 枚举 CSP 模拟

模板题、THUSC、8ady、白子说话

模板题

看似是多项式乘法模板题,实际发现最多只有 \(25\) 次询问。

那么就可以 \(O(n)\) 处理每次询问,维护一个前缀和直接处理即可,注意考虑 std::min(n,r - j) + j < l 的情况,这种情况不能计算贡献。

还有就是开 long long

THUSC

考虑什么时候两个值相等,

\[a_i \cdot x + b_i \cdot y=a_j \cdot x + b_j \cdot y \]

那么有

\[\dfrac{x}{y}=\dfrac{b_j - b_i}{a_i - a_j} \]

显然 \(\dfrac{x}{y}\) 的值相等的值是可以互换位置的,但是 \(\dfrac{x}{y}\) 的值相等不意味最终的权值相等。

权值和 \(\dfrac{x}{y}\) 均相等的一部分我们视为一个块,这些块内部可以互换位置,\(\dfrac{x}{y}\) 相同但权值不同的块之间不能互换位置,但块之间的相对位置可以换。

所以这部分的方案数就是各个块的方案数乘起来。

数据范围是 \(10^3\),可以直接 \(O(n^2)\) 枚举。(赛时以为数据范围 \(10^5\),恼了)

8ady

枚举要记得剪枝,搜到第 \(k\) 个就停,不然就 TLE 挂 \(20 \ \text{pts}\) 。

正解先考虑 \(O(n^3)\) 的暴力,考虑放置每一个数得到数列 \(a\)。

首先考虑一些值的位置是确定的,考虑第 \(i\) 位小于 \(1 \sim i - 1\) 位的前缀最大值。

那么显然这个数要放在第 \(i - 1\) 个数后,第 \(i-1\) 个数最靠后会放在第 \(i-1+m-1\) 个位置,那么第 \(i\) 个数要放在第 \(i+m-1\) 个位置上。

不能再往后放,因为再向后放它就不能到达第 \(i\) 个位置了。

把确定的部分记录后,剩下的部分考虑用一种类似康托展开的方式做。

先回忆康托展开:

例如要求第 \(k\) 小的排列(无特殊限制),设排列长度为 \(n\)。

假设第 \(1\) 个位置放 \(1\),那么共有 \((n-1)!\) 种方案。

若 \(k \leq (n-1)!\),那么第一个位置就确定了,去枚举第二个位置;

若 \(k > (n-1)!\),那么第一个位置不应放 \(1\),继续枚举这个位置的下一个数。

以此类推,最终填完所有位置。

这题同样是类似这种方式,但不同的是,对每个数可以放的位置有限制。

一个数最靠前可以放在哪里?它可以由第一个位置不断向后排序到达现在的位置。

最靠后这个数可以放在 \(i + m - 1\) 位上,所以一个数有 \(\min(i+m-1,n)\) 个可以放的位置。

然后依次枚举每一位填入不同数的方案数,每填入一个数,后面的数就少了一个可以放的位置。

考虑正解,由于 \(20!>10^{18}\),那么除了后 \(20\) 位外,其他位只需要按照字典序最小的方式排列,实际对字典序排名产生影响的只有最后 \(20\) 位,我们就对这最后 \(20\) 位跑 \(O(n^3)\) 的暴力就可以。

白子说话

咕咕咕。

标签:20,49,cdot,dfrac,可以,位置,枚举,CSP,模拟
From: https://www.cnblogs.com/baijian0212/p/csp-49.html

相关文章

  • CSP 2023
    以下是我的CSP2023时间线2023.9.1522:10比赛前一天,有点紧张2023.9.168:50到达普及组考场2023.9.1611:30考试结束我的CSP-J答案:BDAACBCADDABBADTTTABTFTCBDTTTBDCBACBDABABB2023.9.1613:32CSP-J:估分为90分使用https://oj.youdao.com/csp......
  • 10 月 5 日模拟赛总结
    #Before[本文章在博客园同步发布]()[Contest-Link](https://www.luogu.com.cn/contest/137474)预期$100+100+5+0=205$。实际$0+100(0)+5+0=105(5)$。(括号是重测前)挂分$200$。rk21,直接垫底。~~菜死了~~为什么会挂$200$呢?且听下文分解。#T1##Description......
  • 牛客网 $CSP-S$ 模拟赛 $T1$
    给定正整数\(n\),计算\(n\)个元素的集合\(\{1,2,3,...,n\}\),所有非空子集和的乘积取模\(998244353\)后的结果\(n\leq200\)我的第一思路是考虑能不能通过\(i-1\)个元素的情况推出\(i\)个元素的情况,然后寄掉了,遂看题解\(dp\)问题不只是线性递推,这题的思路是用\(......
  • 74th 2023/10/5 模拟赛总结56
    T1看完题目,看到n<=9的限制,心头一紧一个词汇浮现于心:BruceForces暴力+记忆化,\(O(能过)\)但赛时并没有这样打,而是选择了往DP方面思考因为真的没想到能过然后DP呢,又不清楚该如何存一列的状态就匆匆暴力后离去考虑状压DP保留有用状态关键点:\(k=\min(k,n-k)\)可以参考\(C^k......
  • 73rd 2023/10/4 模拟赛总结55&广义串并联图
    这次的比赛成绩并不令人失望,因为早有准备很用心去打的一场比赛,T1T2一开始在看题目时感觉可以很容易切掉T1感觉太简单了,就再看了一遍又一遍T2动手打的时候,感觉T1没那么简单,就在想了一下,想出来了正解,但给的第三个大数据总过不了然后就先放了一下T1,去打T2,因为感觉T2很简单,而且思......
  • 23/10/05 模拟赛总结
    时间安排7:40-7:50读题,毫无思路。7:50-8:10尝试写A题暴力,发现写不出来。8:10-8:30写了B题爆搜。8:30-9:30罚坐,想了一会D题,毫无思路。9:30-10:00读懂了C题,会了链的部分分,写的时候会了“正解”(随机图复杂度\(O(n\logn)\),菊花图复杂度\(O(n^2)\))。10......
  • 10.05模拟赛总结
    比赛传送门总结\(100+60+0+0=160\),Rank16,寄寄寄寄寄。T1优秀\(\texttt{/}\)\(\texttt{Good}\)题意求\(l\)和\(r\)之间的\(2\)的整数次幂。分析解法1由于\(l\)和\(r\)非常小,所以可以直接模拟,没啥好说的。时间复杂度\(O(r)\)。解法2充分发扬人类智慧,发......
  • CF1249(Div. 3) 题解(A to D)
    \(\texttt{EF}\)忘(不)记(会)写了。AYetAnotherDividingintoTeams题解题目大意有一个长度为\(n\)的序列\(a_1,a_2,\cdots,a_n\),将他们分为若干组,使得每一组没有两个数的差为\(1\),使分的组数尽可能少。解题思路排完序后对于任意\(1\lei<n\)均有\(a_i\)与\(a_{i......
  • 专题3——模拟退火
    P1337模拟退火是一门玄学,我发现全看手气,因此,为了避免消耗手气,赛前我只练四道。本题精度要求较高,因此选取较低温度,较高delta,温度下限取到1e-14。P2503这道题目中,随机化才是神。连续分段问题可以dp,这道题目,我们选择random_shuffle后再dp,正确率是很高的,因为最终的答案中,每......
  • CSP 2023 & HNCPC2023 游记
    2023-9-3开学前一天,文化课心态爆炸。下午刷了一套S组初赛润了。2023-9-4学校要求\(7:10\)到校。然后白天全都是入学教育,就是在会议厅听讲座。精神状态被老师折磨死了。然后晚上考试,大寄。基础爆搜分没拿。辛亏没作业,\(22:30\)睡觉。2023-9-5常规\(7:25\)到校。......