首页 > 其他分享 >多校A层冲刺NOIP2024模拟赛17

多校A层冲刺NOIP2024模拟赛17

时间:2024-11-02 16:57:27浏览次数:1  
标签:那么 二元 17 多校 冲刺 NOIP2024

多校A层冲刺NOIP2024模拟赛17

T1、 网格

首先看上去很麻烦,但是最终所有的式子都可以写成 几个数的积相加的形式,那么我们只要处理 数(拼接起来)、 数的积 以及 积的和。

那么我们维护三个变量,第一个是 $ x $ ,表示最后一个积前面所有的数和 ,第二个是 $ y $ ,表示目前的积,第三个是 z ,表示前面的数的积乘上当前的数的积。

那么 $ f_{i,j,x/y/z} $ 表示 走到 $ (i,j) $ 这个位置所有情况的 x/y/z 的和。

那么对于每一种情况:

当他遇到一个 $ + $ 时: $ x = x + y , y = 1 , z = 0 $ 。

当他遇到一个 $ * $ 时: $ y = z , z = 0 $ 。

当他遇到一个 数字 $ k $ 时: $ z = z*10 + y * k $ 。

那么实际转移时,我们只要把 $ f_{i-1,j} 和 f_{i,j-1} $ 的情况转移到 $ (i,j) $ 上加起来就行了。

但是有一个细节,当遇到 $ + $ 时,会把 $ y $ 赋值为 1 ,但是实际转移时 $ f_{i,j} $ 考虑了走到 $ (i,j) $ 的所有情况,所以 $ y $ 应该赋值为 走到 $ (i,j) $ 的情况数。

T2、 矩形

赛时水过去了,后来把自己卡了。

说正解。

首先之前打过一个一样的题,但是那个数据范围很小,直接 $ O(x^2) $ 就能做,x是一共有多少列,但是这个的 $ n $ 是 2e5。

怎么优化呢,在 $ n^2 $ 暴力里,我们是对于每一列去和别的列求交,对于所有的列求交的时间复杂度 是 $ O(n) $ 的,那么想要卡满 $ n^2 $ 就得出一些 每列的点都很少,但是列比较多,比如一条直线,然后就死了。

我们想一下暴力的本质是什么,其实对于每两列求交就是再找他们有多少个共同的二元组 $ (x,y) $ ,每一个二元组都可以有 1 的 贡献。所以对于上面点很少的列,我们可以暴力求出他们的二元组,然后记下来,直接扫过去就行。

那就是把每列分为点多的和点少的。多少算多呢,自然想到根号分治,然后就做完了。

一些细节就是在匹配二元组的时候数组存不下,所以得开 map ,unordered_map很慢,用pbds的哈希表就行。还有一种方法,我们匹配二元组时可以枚举一维,然后直接开数组记另外一维,这样就快了。

T3、 集合

不会,run了

T4、 倒水

我要推博客了: G-数据结构-G

写这道题真的会豁然开朗好几次,我昨天豁然开朗了一晚上。

标签:那么,二元,17,多校,冲刺,NOIP2024
From: https://www.cnblogs.com/GGrun-sum/p/18522022

相关文章

  • H7-TOOL的LUA小程序教程第17期:扩展驱动AD7606, ADS1256,MCP3421, 8路继电器和5路DS18B2
    LUA脚本的好处是用户可以根据自己注册的一批API(当前TOOL已经提供了几百个函数供大家使用),实现各种小程序,不再限制Flash里面已经下载的程序,就跟手机安装APP差不多,所以在H7-TOOL里面被广泛使用,支持在线调试运行,支持离线运行。TOOL的LUA教程争取做到大家可以无痛调用各种功能函数,不需......
  • 自由学习记录(17)
    unity核心实践设置Panel时,用背景图来遮挡后面的组件被点击字典是存了每个要展示出来的面板的类型引用地址,如果对象本身删了,字典里面的那个匹配数据还会留在那里,字典中的引用仍然会保留,但它们将变得无效。如果你尝试访问被删除对象的方法或属性,将会抛出异常(通常是MissingR......
  • 2024 暑假多校 做题记录
    代码链接HDU7445鸡爪可以发现容易构造出\(\lfloor\frac{n}{3}\rfloor\)的上界。对于字典序,只要考虑\(n\)是\(3\)的倍数的情形(对于\(n\)不是\(3\)的倍数的情形,只要将余出边的左端点设为\(1\)即可)。因为要求字典序最小,自然考虑节点\(1\)最多能连多少条边,而\(n\)......
  • C++17 折叠表达式
    折叠表达式C++17之前处理参数包C++17折叠表达式的出现让我们不必再用递归实例化模板的方式来处理参数包。在C++17之前,实现必须分成两个部分:终止条件递归条件这样的实现不仅写起来麻烦,对C++编译器来说也很难处理。C++17折叠表达式能显著的减少程序员和编译器的工作量......
  • 多校 A 层冲刺 NOIP2024 模拟赛 17
    多校A层冲刺NOIP2024模拟赛17T1网格签到题注意到\(+\)与\(\times\)由于优先级其实是分开的,所以可以考虑每到达一个\(+\)计算一次贡献(乘上一个组合数),然后将前置贡献重新赋值为方案数,DP只需考虑连续\(\times\)段即可。时间复杂度\(O(nm)\)。T2矩形根号分治发现不......
  • E74 树形DP P4657 [CEOI2017] Chase
    视频链接:E74树形DPP4657[CEOI2017]Chase_哔哩哔哩_bilibili  P4657[CEOI2017]Chase-洛谷|计算机科学教育新生态(luogu.com.cn)//树形DPO(n*m)#include<bits/stdc++.h>#defineLLlonglongusingnamespacestd;constintN=100010,M=110;intidx,he......
  • CF2026 (Educational round 171) vp记录
    EducationalCodeforcesRound171vp记录A.PerpendicularSegments4min+0唐题。一眼限制紧的边必然连对角线,因为最小长度的限制是相同的所以另一条边也连对角线即可。B.BlackCells9min+0唐题。显然最优策略是相邻的点匹配,$n$为奇数的情况有一个孤立点随便连,为......
  • 【考试题解】多校A层冲刺NOIP2024模拟赛17
    A.网格(grid)题目内容给你一个\(n\timesm\)的字符网格\(s\),\(s_{i,j}\in[1,9]\cup\{+,*\}\),从\((1,1)\)开始,仅向下或向右走并最终到达\((n,m)\)的路径被称为合法路径,求所有合法路径对应的表达式的运算结果之和,答案对\(998244353\)取模。部分分44pts爆搜,枚举路径,......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛17
    Rank一般A.网络签不上的签到题。首先考虑枚举路径的做法,如果先枚举再计算的话复杂度会是\(\mathcal{O(\binom{n+m-2}{n-1}(n+m))}\)的,稍微优化一点的过程中可以去掉后面的\((n+m)\)。考虑此时我们要记什么,首先遇到加号其前面的值\(z\)就确定了,若上个符号为乘号那么......
  • NOIP2024 模拟赛 #12
    学长出的模拟赛,风格挺好。赛时8:00T1会了一个\(O(n^2\logn)\)的做法,先写一下,看看能不能过样例。8:20过了小样例,大样例跑得慢但是是对的。8:40发现一个好的做法,可以枚举\(c_i\)最小的那一天选了哪个,再枚举\(k\)天,这样纯枚举复杂度是\(O(k)\)的。但是有些细节不太......