『模拟赛』多校A层冲刺NOIP2024模拟赛05

news/2024/10/11 21:10:13
Rank

烂。

image

A. 好数（number）

签，唐，没签上。

考虑之前几次类似的题方法都是选 \(k-1\) 的方案存起来以使总复杂度除以一个 \(n\)，故考虑记共 \(n^2\) 个两两组合之和，枚举当前点 \(i\) 前面的点，找是否有值为它们的差的组合，复杂度 \(\mathcal{O(n^2)}\)，用 map 记再挂个 \(\log n\)。

赛时唐氏枚举反了，使复杂度成为 \(\mathcal{O(n^3\log n)}\)，然后被 hack 10pts。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second
const int Ratio = 0;
const int N = 2e4 + 5, M = 3e7 + 5;
int n, ans;
int a[N], nc[M], tot;
unordered_map<int,int> st;
namespace Wisadel
{short main(){// freopen(".in", "r", stdin) , freopen(".out", "w", stdout);// freopen(".err", "w", stderr);freopen("number.in", "r", stdin) , freopen("number.out", "w", stdout);n = qr;fo(i, 1, n) a[i] = qr;st[2 * a[1]] = 1;fo(i, 2, n){fo(j, 1, i - 1)if(st[a[i] - a[j]]){ans++; break;}fo(j, 1, i) st[a[i] + a[j]] = 1;}printf("%d\n", ans);return Ratio;}
}
int main(){return Wisadel::main();}

B. SOS字符串（sos）

不难想的分讨型 dp，但赛时脑子被卡住了一点没想 dp。

发现转移只用到后串的最后几个字符，且只用到两种状态：

  1. \(S\rightarrow SO\)
  2. \(SO\rightarrow SOS\)

故 dp 数组设为 \(f_{i,0/1/2}\)，0/1 对应上面两种，2 表示除上述两种以外的状态，SOS 也计入状态 2。题目要求 SOS 出现三次及以上数量，我们再开一维 0/1/2/3 表示目前已经出现了几次 SOS，超过 3 次计入 3 状态内。然后就可以开始分讨状态转移方程了。

  • 对于 \(f_{i,0,j}\)，\(i-1\) 为 S，第 \(i\) 位仍为 S；\(i-1\) 为状态 2，第 \(i\) 位也可放 S，故有：

\[f_{i,0,j}=f_{i-1,0,j}+f_{i-1,2,j} \]

  • 对于 \(f_{i,1,j}\)，\(i-1\) 为 S，\(i\) 位放 O，故有：

\[f_{i,1,j}=f_{i-1,0,j} \]

  • 对于 \(f_{i,2,j}\)，\(i-1\) 为 S，\(i\) 位放除 S、O 以外的 24 种字母；\(i-1\) 为 SO，\(i\) 位放除 S 以外的 25 种字母；\(i-1\) 为状态 2，\(i\) 位放除 S 以外的 25 种字母，故有：

\[f_{i,2,j}=f_{i-1,0,j}\times 24+f_{i-1,1,j}\times 24+f_{i-1,2,j}\times 25 \]

  • 考虑当 \(j\gt 0\) 时，SOS 可由 SO 加 S 转移而来，故有：

\[f_{i,2,j}=f_{i-1,1,j-1} \]

  • 考虑当 \(j= 3\) 时，由于 3 次及以上都计入 3 内，SOS 可由 SO 加 S 转移而来，故有：

\[f_{i,2,j}=f_{i-1,1,j} \]

最终答案为 \(\sum_{i=0}^2\ f_{n,i,3}\)。复杂度线性，有 4 的常数。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second
const int Ratio = 0;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int n;
ll f[N][3][4];
namespace Wisadel
{short main(){// freopen(".in", "r", stdin) , freopen(".out", "w", stdout);// freopen(".err", "w", stderr);freopen("sos.in", "r", stdin) , freopen("sos.out", "w", stdout);n = qr;f[0][2][0] = 1;fo(i, 1, n){fo(j, 0, 3){f[i][0][j] = (f[i][0][j] + f[i - 1][2][j] + f[i - 1][0][j]) % mod;f[i][1][j] = (f[i][1][j] + f[i - 1][0][j]) % mod;f[i][2][j] = (f[i][2][j] + f[i - 1][0][j] * 24 + f[i - 1][1][j] * 25 + f[i - 1][2][j] * 25) % mod;if(j > 0) f[i][2][j] = (f[i][2][j] + f[i - 1][1][j - 1]) % mod;if(j == 3) f[i][2][j] = (f[i][2][j] + f[i - 1][1][j]) % mod;}}printf("%lld\n", (f[n][0][3] + f[n][1][3] + f[n][2][3]) % mod);return Ratio;}
}
int main(){return Wisadel::main();}

C. 集训营的气球（balloon）

很好的 trick：退背包。

先考虑部分分，发现存在修改与查询，故考虑线段树。发现 \(c\le 20\)，我们可以求出每一个子段内不同 \(c\) 的方案数，超过 \(c\) 计入 \(c\) 内。

证明

证：\(f_{rt,k}=\sum_{i+j=k}f_{ls,i}\times f_{rs,j} (k\lt c)\)，\(f_{rt,c}=\sum_{i+j\ge c} f_{ls,i}\times f_{rs,j}\)。

对于前一个式子是比较显然的：左选 \(i\) 个，右选 \(j\) 个得出共选 \(i+j\) 个的方案数。主要考虑第二个式子。

已知 \(i+j\ge c\)，即左中所有子方案都选 \(i\) 个，右中所有子方案都选 \(j\) 个，依据乘法原理，得出左右子方案两两相乘得到总方案的所有子方案，每个子方案都选 \(i+j\ge c\) 个，显然计入 \(c\) 中不重不漏。

这样做时间复杂度是 \(\mathcal{O(nc^2\log n+q)}\) 的，空间复杂度按四倍空间算是 \(\mathcal{O(4nc^2)}\) 的，无论时间还是空间都过不去 \(n=10^6\) 的点。这样算上前三个 Subtask 的背包得分，最高可获得 80pts。

考虑正解。正解需要由前三个 Subtask 所推的 01 背包做法优化得来，考虑怎么背包。将题目视为容量为 \(c\)，每个人体积为 1 并将 \(a_i\)，\(b_i\) 看作权重计入，发现需要算大于 \(c\) 的所有容量的方案数，复杂度是 \(\mathcal{O(n^2)}\) 的，显然不可行。

发现容量不超过 \(c\) 的情况很小，故正难则反考虑容斥，用总方案数减去容量小于 \(c\) 的方案数求解。这样在不带修的情况下，我们的复杂度就降到 \(\mathcal{O(nc)}\) 了。

考虑带修改怎么做。我们将修改操作视为删除与添加，删除时直接在 dp 数组中删去该需求的全部贡献，其实就是反着做 01 背包，然后在插入一个新需求，即给它单独做一个 01 背包。这就是退背包。这样我们的总复杂度就是 \(\mathcal{O(nc+qc)}\) 了。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second
const int Ratio = 0;
const int N = 1e6 + 1, M = 1e6;
const int mod = 1e9 + 7;
int n, c, m;
ll a[N], b[N];
ll f[21], tot;
namespace Wisadel
{ll Wqp(ll x, int y){ll res = 1;while(y){if(y & 1) res = res * x % mod; x = x * x % mod; y >>= 1;}return res;}void Wjin(int x){fu(i, c - 1, 1) f[i] = (f[i - 1] * a[x] % mod + f[i] * b[x] % mod) % mod;f[0] = f[0] * b[x] % mod;tot = tot * (a[x] + b[x]) % mod;}void Wtui(int x){ll ny = Wqp(b[x], mod - 2);f[0] = f[0] * ny % mod;fo(i, 1, c - 1) f[i] = (f[i] - f[i - 1] * a[x] % mod + mod) % mod * ny % mod;tot = tot * Wqp(a[x] + b[x], mod - 2) % mod;}short main(){// freopen(".in", "r", stdin) , freopen("a.out", "w", stdout);// freopen(".err", "w", stderr);freopen("balloon.in", "r", stdin) , freopen("balloon.out", "w", stdout);n = qr, c = qr;fo(i, 1, n) a[i] = qr;fo(i, 1, n) b[i] = qr;f[0] = tot = 1;fo(i, 1, n) Wjin(i);m = qr;fo(i, 1, m){int x = qr, aa = qr, bb = qr;Wtui(x);a[x] = aa, b[x] = bb;Wjin(x);ll ans = tot;fo(j, 0, c - 1) ans = (ans - f[j] + mod) % mod;printf("%lld\n", ans);}return Ratio;}
}
int main(){return Wisadel::main();}

D. 连通子树与树的重心（tree）

原[FJOI2014] 树的重心

树的重心具有如下性质：

  • 如果重心为两个 \(a\)，\(b\)，那么 \(a\)，\(b\) 必定是一条边上的两个端点，且把这条边断开后，以 \(a\)，\(b\) 为根的子树大小相同。

  • 如果重心为 1 个，若这棵树的大小为 \(S\)，以重心为根时其最大的子树大小为 \(m\)，则有 \(S-m\gt m\)。

证明摘自洛谷。

image

那么和 T3 很像，我们设 \(f_{u,i}\) 为 \(u\) 节点所在连通块大小为 \(i\) 的方案数，那么显然有：

\[f_{u,k}=\sum_{i+j=k}\ f_{v,i}\times f_{u,j}(u\rightarrow v) \]

这样两个重心的情况就可以在 \(\mathcal{O(n^2)}\) 内解决了。

考虑一个重心的情况，依旧从暴力开始想，最暴力的方法就是枚举重心的儿子，然后背包做，复杂度是 \(\mathcal{O(n^3)}\) 的，原题是多测范围小可通过，模拟赛中则不行，需要另行优化。

考虑 T3 怎么做的？容斥和退背包！我们算不合法的情况，即 \(S-m\le m\)。比较显然根节点最多只有一个子节点满足这个情况，因此我们直接枚举它的子节点，重心所在连通块大小和子节点的节点数，这样复杂度就到了 \(\mathcal{O(n^2)}\)。然后再容斥，因为此时 \(f_{u,S-i}\times f_{v,i}\) 会算重 \(v\) 子树的贡献，因此我们做一个退背包将它删掉就好了。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second
const int Ratio = 0;
const int N = 5000 + 5;
const int mod = 10007;
int n, c1, c2, W = 1e9, ans;
int siz[N], w[N];
int hh[N], to[N << 1], ne[N << 1], cnt;
int f[N][N];
namespace Wtask2
{void Wdfs(int u, int fa){siz[u] = 1, f[u][1] = 1;for(int i = hh[u]; i != -1; i = ne[i]){int v = to[i];if(v == fa) continue;Wdfs(v, u);fu(j, siz[u], 1) fu(k, siz[v], 1)f[u][j + k] = (f[u][j + k] + f[u][j] * f[v][k] % mod) % mod;siz[u] += siz[v];}}short main(){fill(siz + 1, siz + 1 + n, 0);Wdfs(c1, c2), Wdfs(c2, c1);fo(i, 1, n) ans = (ans + f[c1][i] * f[c2][i] % mod) % mod;printf("%d\n", ans);return Ratio;}
}
namespace Wtask1
{int zc[N][N];void Wdfs(int u, int fa){siz[u] = 1;f[u][1] = 1;for(int i = hh[u]; i != -1; i = ne[i]){int v = to[i];if(v == fa) continue;Wdfs(v, u);fu(j, siz[u], 1) fu(k, siz[v], 1)f[u][j + k] = (f[u][j + k] + f[u][j] * f[v][k] % mod) % mod;siz[u] += siz[v];}}short main(){Wdfs(c1, 0);for(int i = hh[c1]; i != -1; i = ne[i]){int v = to[i];fo(j, 1, n){zc[v][j] = f[c1][j];fo(k, 1, min(j, siz[v]))zc[v][j] = (zc[v][j] - zc[v][j - k] * f[v][k] % mod + mod) % mod;}}fo(i, 1, n){ans = (ans + f[c1][i]) % mod;for(int j = hh[c1]; j != -1; j = ne[j]){int v = to[j];fo(k, (i + 1) / 2, min(i, siz[v]))ans = (ans - f[v][k] * zc[v][i - k] % mod + mod) % mod;}}printf("%d\n", ans);return Ratio;}
}
namespace Wisadel
{void Wadd(int u, int v){to[++cnt] = v;ne[cnt] = hh[u];hh[u] = cnt;}void Wfc(int u, int fa){siz[u] = 1;for(int i = hh[u]; i != -1; i = ne[i]){int v = to[i];if(v == fa) continue;Wfc(v, u);siz[u] += siz[v];w[u] = max(w[u], siz[v]);}w[u] = max(w[u], n - siz[u]);W = min(W, w[u]);}short main(){// freopen(".in", "r", stdin) , freopen(".out", "w", stdout);// freopen(".err", "w", stderr);freopen("tree.in", "r", stdin) , freopen("tree.out", "w", stdout);memset(hh, -1, sizeof hh);n = qr;fo(i, 1, n - 1){int a = qr, b = qr;Wadd(a, b), Wadd(b, a);}Wfc(1, 0);fo(i, 1, n) if(w[i] == W)if(!c1) c1 = i;else c2 = i;if(!c2) return Wtask1::main();else return Wtask2::main();return Ratio;}
}
int main(){return Wisadel::main();}

末

签到题没签上属实有点唐，好在赛时不知道没影响心态，T3 暴力打出来了。

还是，没思路想 dp！今天四道题一眼三个取模，结果三个 dp，两个都用到了退背包，就当加训 dp 了，学到新 trick 不亏。

晚上开小会了，挺燃的，以后要开始专注模式了。

完结撒花~

最后一张！

Aqr 钦定的又一张

image

image

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.ryyt.cn/news/70390.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！

相关文章

vscode 搭建 python 开发环境

vscode 搭建 python 开发环境

1、安装 python 插件 2、按 Ctrl + Shift + P，在打开的输入框中输入 Python: Select Interpreter 搜索，选择 Python 解析器3、运行：ctrl + F5，调试：F5 4、查看安装包列表pip list5、安装外部库pip install xxx
阅读更多...
idea - properties文件unicode中文显示

idea - properties文件unicode中文显示

💖简介 idea中properties文件中文默认展示为unicode码unicode 中文展示为 \u开头的ASCII🌟调整中文显示 idea -> settings -> Editor -> File EncodingsGlobal Encoding 选择 UTF-8 Project Encoding 选择 UTF-8 Default encoding for properties files 选择 UTF-…
阅读更多...
基于MPPT的太阳能光伏电池simulink性能仿真,对比扰动观察法,增量电导法,恒定电压法

基于MPPT的太阳能光伏电池simulink性能仿真,对比扰动观察法,增量电导法,恒定电压法

1.课题概述在simulink中，实现基于MPPT的太阳能光伏电池，对比对比扰动观察法,增量电导法,恒定电压法三种MPPT方法。2.系统仿真结果局部放大可以看到三个算法的对比结果如下：3.核心程序与模型 版本：MATLAB2022a 4.系统原理简介太阳能光伏（PV）系统是一种将太阳能转换为电能的…
阅读更多...
Nacos服务注册与发现的原理和如何配置

Nacos服务注册与发现的原理和如何配置

由于在大型为微服务项目中存在很多服务提供者，甚至相同的服务会使用不同的路径去调用，为了更好的管理并调用这些服务，我们需要使用注册中心来帮助我们管理这些服务以nacos为例， 1.当使用nacos来管理服务的时候，服务启动时会将自己的注册信息，例如服务名，Ip，端口注册到注…
阅读更多...
多校 A 层冲刺 NOIP2024 模拟赛 05

多校 A 层冲刺 NOIP2024 模拟赛 05

难度 ★★★☆☆多校A层冲刺NOIP2024模拟赛05 T1 好数（number） 签到题 首先 \(O(nV)\) 的背包暴力是显然的，注意到本题只需要合法性，状态只有 \(0/1\)，上 \(bitset\) 优化转移即可。 时间复杂度 \(O(\frac{nV}{w})\)。 T2 SOS字符串（sos） 签到题 计数题难点在不重不漏，…
阅读更多...
VS2019/2022配置C++ OpenCV4.10.0环境

VS2019/2022配置C++ OpenCV4.10.0环境

一、下载opencv4.10.0 官网链接：https://opencv.org/ 安装的时候记住安装路径，本人安装到E盘 二、新建C++项目 1、本人新建C++/CLR .Netframework项目 2、右击打开C++项目属性 2.1、添加包含目录 此处本人配置的是绝对地址，拷贝build文件夹到程序目录，然后配置相对地址方…
阅读更多...
搜狗输入法ng版导入细胞词库过程的简要分析

搜狗输入法ng版导入细胞词库过程的简要分析

今天有点时间，对deepin/uos上的搜狗输入法ng版导入细胞词库的行为做了一下分析。今天有点时间，对deepin/uos上的搜狗输入法ng版导入细胞词库的行为做了一下分析，过程如下： 1.在属性设置界面，用户选择.scel细胞词库文件，输入法对.scel的文件头进行验证，如果是 40 15 00 0…
阅读更多...
花指令与anti-debug

花指令与anti-debug

花指令 anti-Debugptrace反调试 (1) ptrace系统调从名字上看是用于进程跟踪的,它提供了父进程可以观察和控制其子进程执行的能力,并允许父进程检查和替换子进程的内核镜像(包括寄存器)的值。其基本原理是: 当使用了ptrace跟踪后,所有发送给被跟踪的子进程的信号(除了SIGKILL),都…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 尧图建网站 广利置业