首页 > 其他分享 >2024.11.4 test

2024.11.4 test

时间:2024-11-04 14:30:35浏览次数:1  
标签: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

相关文章

  • The 2024 ICPC Asia Chengdu Regional Contest
    目录写在前面L签到,构造J签到,模拟G构造,结论,二进制A构造,括号匹配I思维,枚举,gcdB枚举,DPK结论,费用流E换根DP,树上差分D枚举,构造写在最后写在前面比赛地址:。以下按个人难度向排序。混进赛站群偷取了补题链接。看着原榜打的,题开得很顺但是写得很烂,反思!同时因为在赛站群所以......
  • AtCoder Beginner Contest 378 考试总结
    发挥还行,就是罚时吃饱了,B题卡精度卡成78了。赛时得分:ABCDEFG√√√√√××[ABC378A]Pairing先对序列排个序,然后从小往大扫,如果和之后匹配了就贡献加一,然后跳过一个位置继续匹配。时间复杂度\(O(4)\)。#include<bits/stdc++.h>#definelllon......
  • FontDialogTest自定义字体对话框的使用
    packagecom.shrimpking.t1;importjavax.swing.*;importjava.awt.*;importjava.awt.event.ActionEvent;importjava.awt.event.ActionListener;/***CreatedbyIntelliJIDEA.**@Author:Shrimpking*@create2024/11/310:44*/publicclassFontDial......
  • 2024.11.1(周五)
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="utf-8"><metahttp-equiv="X-UA-Compatible"content="IE=edge"><metaname="viewport"content="width=......
  • 《人件集》阅读笔记2(2024.11.1)
    一、章节内容梳理(一)第五章:环境与协作的交织这一章让我深刻认识到办公环境对软件开发人员的重要性。无论是物理空间的布局,还是设施的配备,都如同隐形的手影响着工作效率和团队沟通。从开发人员的角色定位角度看,合适的环境能让他们更清晰地明确自己在团队中的位置,更好地发挥专长。......
  • The 2023 ICPC Asia Xi'an Regional Contest
    Preface久违地组队训练一场,不知道打什么就挑了场最近才上QOJ的23年西安Regional作为“声名远扬”的凹包场,还有\(O(\frac{n^3}{\omega})\)过\(n=5000\)的神秘数据,导致这场的downvote率奇高但上QOJ的时候数据应该是修复了的,凹包好像fix了,bitset大力出奇迹的题我......
  • 2024.11 训练记录
    训练记录11.1补题,怒学LCT。没学会。theend。只会splay。辅助树太难了。11.2无。休息日就摸了一整天鱼,都干了啥我一点也记不清了。11.3noip10连估分100+0+20+30=150实际60+0+20+45=125T11e5二分答案\(nlog^2n\)卡完了。咋这样。赛后换了一个快......
  • 2024.11.3训练记录
    杂题选讲CF1392FOmkarandLandslide手玩会发现,最后的序列必定要么全都差\(1\)上升,要么有一个位置与上一个相同,其他位置仍然差\(1\)上升。那么在\([1,i-1]\)合法的情况下:当\([1,i-1]\)中没有相同项,会增加一个相同项。当\([1,i-1]\)中存在相同项,会减少一......
  • 2024.11.03 2000版
    起于《海奥华预言》的思考◆地球管理结构和参考持续更新中...... 英文地址:https://github.com/zhuyongzhe/Earth/tags中文地址:https://www.cnblogs.com/zhuyongzhe85作者:朱永哲 ---------------------------------------------------------------------------------......
  • 2024.11.3 test
    BP6563[SBCOI2020]一直在你身旁,\(n\le10^5\),\(c_i\le9\)。考虑利用\(c_i\le9\)的性质,那么最后答案很小。我们原本是计算每个区间的答案,同时区间答案具有单调性,那么考虑把答案放进状态里即可。即维护\(f_{l,ans}\)表示花费\(ans\)的代价能确定的最远的\(r\)。C请......