首页 > 其他分享 >AT_utpc2012_07 k番目の文字列 题解

AT_utpc2012_07 k番目の文字列 题解

时间:2024-11-01 21:59:14浏览次数:3  
标签:utpc2012 填入 题解 len 番目 num DP op

模拟赛搬了这个题,来写个题解。

\(n\) 这么小,不是状压就是很多很多维 DP(暴论)。状压我没想出来,那就正常 DP。

考虑依次填入字符串的每个位置,记 \(f(i,j,num,op)\) 表示填了前 \(i\) 个位置,其中比 \(s_0\) 小的有 \(j\) 个,目前字典序比 \(s\) 小的子串有 \(num\) 个的方案数,\(op\) 表示是否已经把 \(s\) 填入。那转移分三种:

\[f(i,j,num,op) \rightarrow \begin{cases} f(i+1,j+1,num+j+1,op) \\ f(i+1,j,num+j,op) \\ f(i+len_s,j+cnt,num+j*len_s+tot,1) & op=0 \And i+len_s \le n \end{cases} \]

其中 \(cnt\) 表示 \(s\) 内部比 \(s_0\) 小的位置的个数,\(tot\) 表示 \(s\) 内部对 \(num\) 的贡献,这两个量都可以在 \(s\) 串中预处理得到。

应该比较好理解,三种转移分别表示在 \(i+1\) 处填入比 \(s_0\) 小的、比 \(s_0\) 大的、直接填入 \(s\)。

记搜比较好写,我写的记搜。

code

标签:utpc2012,填入,题解,len,番目,num,DP,op
From: https://www.cnblogs.com/tai-chi/p/18521374

相关文章

  • 天津大学2024华为杯I.个大的大个 题解
    原题链接https://acm.tju.edu.cn/problem/P2040学校oj好像挂了,题解发不出去,又没有草稿功能,所以先存在这里了。前言华为杯时候对字符串不太熟,加上看错题了导致没做出这题,很可惜,苦练几个月,现在已经成为串串大师,回过头来秒一下这题发个题解泄恨。题意给定一个长为\(n\)的字符......
  • 2024御网线上Pwn方向题解
    ASMChecksec检查保护基本上保护都关闭了64位ida逆向程序只有一段,并且返回地址就是输入的数据,看起来就是srop了,找一下可以用的gadget通过异或清空rax值,然后通过异或ecx和1,异或rax和rcx即可增加rax的值,同理左移一位同样可以增加rax的值,将rax增加到0xf然后打srop,程序还给出了......
  • CodeForces Dora and C++ (2007C) 题解
    CodeForcesDoraandC++(2007C)题解题意给一个数组\(c_{1...n}\),定义数组的\(range\)是最大值减最小值,即极差。给出两个值\(a\)和\(b\),每步操作中,可给数组中任一一个数增大\(a\)或增大\(b\)。问任意步操作后(可以是\(0\)步),极差的最小值。思路(要直接看答案可以跳......
  • 第八届御网杯线下赛Pwn方向题解
    由于最近比赛有点多,而且赶上招新,导致原本应该及时总结的比赛搁置了,总结来说还是得多练,因为时间很短像这种线下赛,一般只有几个小时,所以思路一定要清晰,我还是经验太少了,导致比赛力不从心,先鸽了~Skillchecksec检查保护(没有开PIE和Canary)ida逆向分析一下不同的选项对应不同的功......
  • 【考试题解】多校A层冲刺NOIP2024模拟赛17
    A.网格(grid)题目内容给你一个\(n\timesm\)的字符网格\(s\),\(s_{i,j}\in[1,9]\cup\{+,*\}\),从\((1,1)\)开始,仅向下或向右走并最终到达\((n,m)\)的路径被称为合法路径,求所有合法路径对应的表达式的运算结果之和,答案对\(998244353\)取模。部分分44pts爆搜,枚举路径,......
  • 2024 -- 国庆集训 -- 临沂四中 -- 10月01 日 -- S/N模拟赛#1 题解
    A.2025--[炼石计划--NOIP模拟三]--T1--矩形赛时草了个\(O(n^4\log(n))\)竟然能过70分虽然本来就是这么分配的,发现正解只需将二分改为双指针就可以了,最气的是上面计算的时候用到还是尺取下面就用的二分(唐诗)。其实这题就是暴力,然后在低级的暴力上加一些操作变得稍微高级一......
  • abc318_g Typical Path Problem 题解 圆方树
    题目链接:https://atcoder.jp/contests/abc318/tasks/abc318_g题目大意:给出一个有\(n\)个顶点和\(m\)条边的无向连通图\(G\),没有重边和自环。顶点的编号为\(1\simn\),边的编号为\(1\simm\),第\(i\)条边连接顶点\(u_i\)和\(v_i\)。给出图上三个不同的顶点\(A,B,C......
  • 《上海市计算机学会竞赛平台2024年8月月赛丙组题目T1 统计得分 T2 等差数列的素性 T3
    T1统计得分内存限制: 256 Mb时间限制: 1000 ms题目描述在一场知识竞赛中,选手答对一题得 11 分,答错不得分且要倒扣 11 分,但扣分不能让分数小于 00。给定一个由 Y 及 N 构成的字符序列,答对记为 Y,答错记为 N。选手一开始从 00 分开始,请输出选手最后的得分......
  • 思维题配套题解
    配套题单:CodeForces思维题目CF79DPassword你有\(n\)个灯泡,一开始都未点亮。同时你有\(l\)个长度,分别为\(a_1\sima_l\)。每次你可以选择一段连续的子序列,且长度为某个\(a_i\),并将这些灯泡的明灭状态取反。求最少的操作次数,使得最后有且仅有\(k\)个位置是亮的,......
  • 题解 洛谷 Luogu P1308 [NOIP2011 普及组] 统计单词数 C++
    题目传送门:P1308[NOIP2011普及组]统计单词数-洛谷|计算机科学教育新生态https://www.luogu.com.cn/problem/P1308getline() 会清除使当次getline() 终止的换行,而cin 不会因此cin 以换行终止,之后还需要getline()的话,需要用getchar() 吞换行Linux的一些相......