首页 > 其他分享 >2024.11.4 test

2024.11.4 test

时间:2024-11-04 14:30:35浏览次数:4  
标签:2024.11 最大值 个数 等价 字符串 回路 test 欧拉

B

你可以进行以下的操作:选择一个点染白色;此后每次染有白色点相邻的,且 \(a_i\) 最小的点。
\(q\) 次询问每次给出 \(p,k\),问有多少种选择点的方案,使得 \(p\) 是第 \(k\) 个选到的。
\(a_i\) 是排列。\(n,q\le 1e5\)。

设 \(l=p-k+1,r=p+k-1\),若 \([l,p-1]\) 能取到且 \(a_p<a_{l-1}\),那么算上 \([l,p-1]\) 的答案。
若 \([p+1,r]\) 能取到且 \(a_p<a_{r+1}\),算上 \([p+1,r]\) 的答案。
考虑一个区间能否取到,考虑取出最大值的位置 \(x\)。
若 \(a_x<a_{l-1}\) 那么 \(x\) 左边的位置都可以作为开头,\(a_x<a_{r+1}\) 那么右边的也都能取到。
现在计算 \(x\) 能否取到,取左边右边分别的最大值,
那么最后的形式一定是左右边一个顶到最大值处,另一边到边界,只需要判断是否出边界即可。

C

我们称两个字符串 \(s\) 和 \(t\) 是等价的,如果对于任意长度为 \(2\) 的字符串在 \(s,t\) 中出现次数相同。
询问一个字符串其有多少个字符串与其等价。字符集大小为 \(3\)。

这是一个欧拉路径计数。
由于 best 定理是计算欧拉回路的,若算的是 \(s\to t\) 的欧拉路径,那么加一条 \(t\to s\) 的边。
由于最后算的是循环同构的回路方案数,考虑旋转使得加的那条边在最后,删掉即可。
即本质不同的欧拉回路个数与欧拉路径的个数是一一对应的关系。
如果算的是欧拉回路个数,要乘上 \(n-1\),因为从环路的任意位置开始都可以。
最后考虑所有边是等价的情况,那么乘上 \(\prod_{i,j}\frac{1}{E_{i,j}!}\)。

标签:2024.11,最大值,个数,等价,字符串,回路,test,欧拉
From: https://www.cnblogs.com/Simon-Gao/p/18525193

相关文章

  • FontDialogTest自定义字体对话框的使用
    packagecom.shrimpking.t1;importjavax.swing.*;importjava.awt.*;importjava.awt.event.ActionEvent;importjava.awt.event.ActionListener;/***CreatedbyIntelliJIDEA.**@Author:Shrimpking*@create2024/11/310:44*/publicclassFontDial......
  • 《人件集》阅读笔记2(2024.11.1)
    一、章节内容梳理(一)第五章:环境与协作的交织这一章让我深刻认识到办公环境对软件开发人员的重要性。无论是物理空间的布局,还是设施的配备,都如同隐形的手影响着工作效率和团队沟通。从开发人员的角色定位角度看,合适的环境能让他们更清晰地明确自己在团队中的位置,更好地发挥专长。......
  • 2024.11.3 test
    BP6563[SBCOI2020]一直在你身旁,\(n\le10^5\),\(c_i\le9\)。考虑利用\(c_i\le9\)的性质,那么最后答案很小。我们原本是计算每个区间的答案,同时区间答案具有单调性,那么考虑把答案放进状态里即可。即维护\(f_{l,ans}\)表示花费\(ans\)的代价能确定的最远的\(r\)。C请......