当前位置: 首页 > news >正文

2025国庆Day3

模拟赛

T1

对每个ai开个桶分别算答案即可

注意long long

T2

维护m个指针

倒着枚举l

p1~pm维护第i个字符已匹配的下标

每次匹配修改一个前缀

复杂度O(n)

另外可考虑:

image

T3

设dpi,j表示i子树内钦定返祖j次的方案数

将相邻向北的点对连边,形成若干条链

合并子树时方案数image

然后新加一个点,这个点相当于加入到任意一条链中,或者新增一条链

最后把钦定变成恰好,容斥一下

T4

牛逼的题

先考虑k=2

image

挖掘性质

image

image

image

image

image

DP

CF392B

fi,x,y表示前i个盘,从x到y的代价

容易转移

P2331

dpi,j,0~4表示第i行,选了j个矩阵

这一行的两个数{

  1. 没有元素被选择

  2. 第一列的元素在子矩阵中

  3. 第二列的元素在子矩阵中

  4. 两列元素在同一个子矩阵中

  5. 两列元素在不同子矩阵中
    }

分别转移即可

CF607B

fi,j表示消除[i,j]的最小代价

经典区间DP

CF571B

相当于要求选择k条链

求出k条链最大值减最小值最小能是多少

容易看出每条链不交

CF703E

b为k的倍数当且仅当gcd(b,k)=k

fi,j表示前i个数gcd=j的最小元素和

而gcd(Bb,k)=gcd(b,k)gcd(b,k/gcd(B,k))

P1169

对(i+j)奇数的点取反

变成颜色全相同的最大子矩阵/正方形

子矩阵就对每个点求出往上最大延伸长度

据此算出往左往右第一个比他小的位置

计算答案

正方形就设fi,j表示以i,j左上角最大边长

若si,j=i-1,j=i,j-1=i-1,j-1

则fi,j=max(f+1)

QOJ8933

fi,j表示i个事件,剩j个1分,最多0分的数量

此时2分数量=si-j

简单转移

QOJ9312

期望DP

image

QOJ8528

环上的线相交相当于区间相交

数据随机

答案不会太大(<900)

gi,j表示i,j最大匹配

满足单调性

fi,j表示满足gi,k=j的最小的k

转移考虑i是否匹配

若匹配,那么更新就是从 ri 继承过来加上 gi,ri 的答案

否则就是从 i + 1 继承

计数

GYM105336

容易发现如果一个 ai 和 bj 匹配了,那么 ai 后的元素与 bj 前的元素匹配对答案就不会产生改变了

考虑 答案 k 被确定时,方案可以简单算出

令 fi,j 表示前 i 个 a 匹配了 j 个 b 的方案数

每次枚举选不选即可转移

不难发现对于一个权值为 w 的方案,恰好在 k = 1~w 都被计算了一次

直接对所有 k 的答案求和即可得到所有匹配的权值和。

P2592

转化成网格计数

要求y-x极差<=k

image

(对称计算答案就是用类似卡特兰数的方法

卡特兰数公式:C(2n,n)-C(2n,n-2)

这个公式就是通过对称得来的)

复杂度O(n+m+k)

http://www.hskmm.com/?act=detail&tid=24329

相关文章:

  • 量子迁移计划启动:应对未来密码学挑战
  • HPE SPP 2025.09.00.00 - HPE 服务器固件、驱动程序和系统软件包
  • 详细介绍:Linux字符设备驱动开发全攻略
  • sql注入和xss漏洞
  • 数学 trick
  • 完整教程:精读C++20设计模式——行为型设计模式:解释器模式
  • js疑惑
  • 关于我
  • 20251004国庆模拟4
  • 珂朵莉树 ODT
  • 2025多校CSP模拟赛2
  • 详细介绍:深入了解linux网络—— 基于UDP实现翻译和聊天功能
  • Rewind: Codeforces Round 1055 (Div.1+Div.2)
  • 10.4模拟赛总结
  • 01.linux基础
  • 英语完形填空
  • 2025整体橱柜厂家TOP企业品牌推荐排行榜,云南昆明整体橱柜全瓷砖,开放式厨房,经济型,一站式无烟柴火灶,嵌入式,智能,多功能,全屋无烟柴火灶整体橱柜公司推荐
  • Centos7安装mysql8
  • vite-vue3脚手架(参考帝莎编程-后台管理系统开发)
  • 上传文件的后端程序handleFileUpload()、getOriginalFilename()、UUID
  • 从模拟入侵到渗透测试:我摸清了黑客的套路,也懂了企业的软肋 - 详解
  • 同样的Python代码,在Windows上运行没有错误,在Linux Centos上运行出行错误。
  • FreeBSD 14发布后的技术问题解析
  • handleFileUpload()
  • 实用指南:Typescript高级类型详解
  • 集合幂级数,FMT 与 FWT 学习笔记
  • 2025多校CSP模拟赛1
  • 上传文件前端需要注意的三个点:
  • AT_arc189_b [ARC189B] Minimize Sum
  • Jenkins安装与配备