首页 > 其他分享 >2023.07.16 高质量 NOIP 模拟赛题解

2023.07.16 高质量 NOIP 模拟赛题解

时间:2023-07-16 16:35:36浏览次数:57  
标签:le NOIP 16 cdot 题解 sum text 2n 2k

HDU5719 Arrange

【模拟】

给定数列 \(B_n,C_n\),求出满足

\[B_i=\min_{j=1}^i\{A_j\},\quad C_i=\max_{j=1}^i\{A_j\} \]

排列 \(A\) 的数量。

维护每个位置可能的数字数量,然后乘法原理即可。

代码:http://acm.hdu.edu.cn/viewcode.php?rid=38654445

HDU5807 Keep In Touch

【分段 dp】

有 \(n\) 个城市,编号依次为 \(1\) 到 \(n\),同时有 \(m\) 条单向道路连接着这些城市,其中第 \(i\) 条道路的起点为 \(u_i\)​​,终点为 \(v_i\)(\(u_i<v_i\))。

一共有 \(3\) 名成员将要执行 \(q\) 次任务。

在每次任务中,三人可能会处于三个不同的城市,他们互相之间通过对讲机保持联络。编号为 \(i\) 的城市的无线电频为 \(w_i\)​​,如果两个城市的无线电频差值的绝对值不超过 \(K\),那么无线电就可以接通。三名成员每个时刻必须要选择一条道路,走到下一个城市,每条道路都只需要花费 \(1\) 个单位时间。

他们可以选择在任意城市终止任务,甚至可以在起点就终止任务,但不允许在道路上终止任务。现在他们想知道,对于每次任务,给定三个人的起始位置,有多少种可能的合法行动方案,使得行动过程中任意在城市的时刻,他们都可以两两联络?

两个方案被视作不同当且仅当至少存在一个人在某一时刻所在的城市不同。

注意:\(3\) 名成员必须同时结束任务。

对于所有数据,保证:\(1\le T\le10\),\(1\le n\le50\),\(1\le m\le \dfrac{n\cdot(n-1)}2\),\(0\le k\le10^9\),\(1\le q\le 125000\),\(1 \le w_i\le10^9\),\(1\le u_i<v_i\le n\),\(1\le x,y,z\le n\)。

令 \(f[i][j][k][p]\) 表示三个人分别在 \(i,j,k\) 且此时的启动状态为 \(p\) 时的方案数。直接 dp 即可。复杂度 \(O(n^4)\)。

代码:http://acm.hdu.edu.cn/viewcode.php?rid=38654447

HDU5597 GTW likes function

【数论】

已知 \(f_0(x)=\sum\limits_{k=0}^x(-1)^k\cdot 2^{2x-2k}\cdot\text C_{2x-k+1}^k\),且对于 \(n\ge1\),有 \(f_n(x)=f_0(f_{n-1}(x))\)。

给定 \(n,x\ (1\le n,x\le 10^{12})\),求 \(\varphi(f_n(x))\)。

建议改为:【模板】求 \(\varphi(x)\)。

先证 \(f(x)=x+1\)(这里 \(f\) 默认指 \(f_0\)):

【证明】 首先,

\[\begin{aligned} f(n)&=\sum\limits_{k=0}^n(-1)^k\cdot 2^{2n-2k}\cdot\text C_{2n-k+1}^k\\&=\sum\limits_{k=0}^n(-1)^k\cdot 2^{2n-2k}\cdot\left(\text C_{2n-k}^k+\text C_{2n-k}^{k-1}\right)\\&=\sum\limits_{k=0}^n(-1)^k\cdot 2^{2n-2k}\cdot\text C_{2n-k}^k-\sum\limits_{k=0}^{n-1}(-1)^k\cdot 2^{2(n-1)-2k}\cdot\text C_{2(n-1)-k+1}^{k}\\&=\sum\limits_{k=0}^n(-1)^k\cdot 2^{2n-2k}\cdot\text C_{2n-k}^k-f(n-1)\\&=g(n)-f(n-1) \end{aligned} \]

另外,下面的关键问题是研究 \(g(n)\),即

\[\begin{aligned} g(n)&=2^{2n}+\sum\limits_{k=1}^{n-1}(-1)^k\cdot 2^{2n-2k}\cdot\left(\text C_{2n-k-1}^k+\text C_{2n-k-1}^{k-1}\right)+(-1)^n\\&=\sum_{k=0}^{n-1}(-1)^k\cdot 2^{2n-2k}\cdot\text C_{2n-k-1}^k+\sum_{k=1}^n(-1)^k\cdot 2^{2n-2k}\cdot\text C_{2n-k-1}^{k-1}\\&=4\sum_{k=0}^{n-1}(-1)^k\cdot 2^{2(n-1)-2k}\cdot\text C_{2n-k-1}^k-\sum_{k=0}^{n-1}(-1)^k\cdot 2^{2(n-1)-2k}\cdot\text C_{2(n-1)-k}^{k}\\&=4f(n-1)-g(n-1) \end{aligned} \]

联立上述两式,易得 \(f(x)-f(x-1)=C\)(常数)。

考虑到 \(f(0)=1,f(1)=2\),所以 \(f(x)=x+1\),证毕。

所以 \(f_n(x)=x+n+1\)。

HDU5669 Road

有 \(n\) 个顶点,有 \(m\) 个五元组 \((a,b,c,d,w)\),每个五元组表示编号在区间 \([a,b]\) 之中的每一个顶点和编号在区间 \([c,d]\) 之中的每一个顶点,都有一条长度为 \(w\) 的边。现在,可以选择 \(k\) 条边,将其边长置为 \(0\),求 \(1\) 到 \(n\) 的最短路。

对于所有数据,保证:\(1\le T\le10\),\(1\le n\le5\times10^4\),\(1\le m\le10^4\),\(0\le k\le10\),\(1\le w\le10^3\)。

暴力显然直接每次 \(O(n^2)\) ​的连边,最后跑一次分层图最短路即可。

然后我们考虑优化一下这个连边的过程,利用线段树来维护整个图,连边时候找到对应区间,把线段树的节点之间连边,然后再跑分层图最短路。

为解决边的规模,开两棵线段树,连边时候新建一个中间节点,在对应区间的节点和中间节点之间连边。最后跑一下分层图最短路,复杂度 \(O(m\log^2n)\)。

标签:le,NOIP,16,cdot,题解,sum,text,2n,2k
From: https://www.cnblogs.com/plenilunesept/p/noip-2023-07-16.html

相关文章

  • 2023/7/16
    今天主要学习了字符串操作1.首先是获取字符串sbustring(int)和substring(int,int)前者是从索引开始一直到字符串的结尾,后者是从前索引位置到后索引位置,不包括后索引位置package字符串操作;publicclass获取子字符串{publicstaticvoidmain(String[]args){......
  • 【雕爷学编程】Arduino动手做(163)---大尺寸8x8LED方格屏模块
    37款传感器与模块的提法,在网络上广泛流传,其实Arduino能够兼容的传感器模块肯定是不止37种的。鉴于本人手头积累了一些传感器和执行器模块,依照实践出真知(一定要动手做)的理念,以学习和交流为目的,这里准备逐一动手试试多做实验,不管成功与否,都会记录下来——小小的进步或是搞不掂的问题......
  • HHHOJ #1247. 「NOIP 2023 模拟赛 20230715 A」1 题解--zhengjun
    法老找来的题,说是找了三道其他模拟赛的T4拼成T1~T3,另外搞了道T4。思维好题,但是放在T1有点搞心态,但是还好大样例够强,400没挂。然而T3大样例输出错了,浪费了我0.5h,差评。首先发现向左走之后向右走是一定不优的,所以最短路的情况只能先向右再向左。考虑枚举起点\(s......
  • 7.16 动态规划
    线性DP[USACO20DEC]SleepingCowsP先不考虑极大,将奶牛和牛棚放在一起排序并离散化,设\(F_{i,j}\)为处理到第i个元素(奶牛/牛棚),有j头奶牛还没有进入牛棚的方案数。对于牛棚:\[F_{i,j}\rightarrowF_{i+1,j}\]\[j*F_{i,j}\rightarrowF_{i+1,j-1}\]对于奶牛:\[F_{i,j}......
  • 题解 P2839【[国家集训队] middle】
    Problem一个长度为\(n\)的序列\(a\),设其排过序之后为\(b\),其中位数定义为\(b_{n/2}\),其中\(a,b\)从\(0\)开始标号,除法下取整。给你一个长度为\(n\)的序列\(s\)。回答\(Q\)个这样的询问:\(s\)的左端点在\([a,b]\)之间,右端点在\([c,d]\)之间的子区间中,最大的中......
  • [ARC162D] Smallest Vertices
    [ARC162D]SmallestVerticesAtcoder:[ARC162D]SmallestVertices洛谷:[ARC162D]SmallestVerticesProblem在本问题中,当我们提到有根有向树时,我们指的是所有边都指向从根到叶子的有根树。给定一个使得其总和为\(N-1\)的非负整数序列\(d=(d_1,d_2,\ldots,d_N)\)。对于带编......
  • 20090316_為什麼輪迴很苦
    因果輪迴是一種工具、是公正無私的,而人是活生生的生命有長智慧的。人會對輪的害怕是來自對死亡的恐懼,不知道死後會去哪?會是怎樣的世界?死亡意味著剝奪你生前的所有。但是,佛法也要人們不思過去跟未來,遠離死後該去哪的煩惱。會害怕輪迴是因為人們認為那是要受苦的,也因為人們體會的......
  • 你省(福建)省队集训 Day5 T1 题解
    简要题意有两个正整数\(a<b\le10^9\),给出\(\dfrac{a}{b}\)的小数点后\(19\)位,要求还原\(a,b\),保证有解。solution一个科技:\(\texttt{Stern-Brocottree}(SBT)\),可以参考这个博客学习。先给出\(O(n)\)找的代码:......
  • 云斗杯 T2 派蒙是最好的伙伴! 题解
    云斗杯T2题解赛时脑抽了只打了60pts暴力xwx。题目描述给定两个长度为\(n\)的\(01\)序列\({a_n}\)和\({b_n}\),与另一个矩阵\({c_{n,n}}\)。矩阵\({c_{n,n}}\)的生成规则如下:\[c_{i,j}=a_i\timesb_j\]现给定一个数\(k\),求在矩阵\(c_{n,n}\)内,有多少个......
  • vue-day16---模拟一个数据监测
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"/><title>模拟一个数据监测你</title></head><body><scripttype="text/javascript">letdata={......