题解 联盟noip

Day -4 17 号我们就要出发。 好快啊。 写了博客，并不是很全，打算回来继续完善。 想起之前有个 dfs 序求 lca 的坑还没填完。 呃等我以后直接重构吧。 看了辰星凌的DP优化，打算板刷一下题。 UVA 的题在 \(4\) 发 UKE 后终于 AC。 给老师批了卷子。 NOIP 很快就到了 ......

「GLR-R3」惊蛰 题目背景 「微雨众卉新，一雷惊蛰始」 中午，休息室，阿绫肩膀上。 “我有一个愿望，参加全国音乐祭，获奖，和阿绫一起，摆脱这训练的苦海。” “为热爱而到来，为抽身而努力……吗”。 正午的阳光渗过窗帘，抚上困倦的人儿的脸颊。天依的左手悄悄搭上阿绫怀里的吉他， “铮——” 蛰虫被雷声 ......

闲话 调了好一会，甚至还重构了一次代码才对，但是还是很喜欢并查集，并查集可爱捏。 题意省流 $n$ 个学生分成 $3$ 人一组，要满足 $m$ 个条件，每个条件给出两个数 $x,y$，要求 $x$ 和 $y$ 必须在一个组里。 正文 要使学生三人一组，一眼使用并查集。 首先考虑无解（输出 $-1$ ......

NOJ题解 30-40 素数 埃氏筛，欧拉筛都可 可变参数累加/平均 用给出的库函数即可 基思数 根据题意模拟 #include<stdio.h> #define ll long long ll num[102]; inline bool IsKeith(ll n) { int tot = 0, t ......

InfOJ NOIP2023 模拟赛 T1 给定长度为 \(n\) 的数列 \(a\)，每次操作需要选择 \([l, r]\)，满足 \(a_l, a_{l + 1}, \cdots, a_r\) 按位与的结果为 \(0\)，然后删去 \([l, r]\)，删去后左边和右边合并起来。 问最多能合并多 ......

P6569 [NOI Online #3 提高组] 魔法值 不放简要题意了，题面写的很简要。 看到数据范围自然可以想到矩阵快速幂优化。但乘法对异或没有分配律。所以直接拆位，把异或变成加法对二取模就有分配律了。 还有一个优化就是提前预处理出矩阵的 2 的幂次方，然后询问时直接二进制分解乘起来就行。 时 ......

前言 ARC119F 好厉害，是没见过的自动机 DP。 正文 [1] 分析 主要分析一下为什么这么写。 [2] 状态设计 [3] 自动机状态转移 感觉状态设计中最难的就是如何处理带 \(O\) 的。 见参考资料。 [4] 代码 还没写。写ing 这是自动机的初始化（有点麻烦）。 int to[Kin ......

P6772 [NOI2020] 美食家 给你一张 \(n\) 个点 \(m\) 条边的有向图，经过每条边需要 \(w_i\) 的时间，每个点有价值 \(c_i\)。每次经过一个点时可以获得它的价值（可重复获得）。 还有 \(k\) 个附加价值 \((t, x, y)\) 表示如果你在 \(t\) 时 ......

P9836 种树 题目链接 前言废话：不怎么打洛谷的比赛，昨天心血来潮，结果只看了 T1 且分配指数假了，或者说根本没深入思考，这下掉大分了。但个人感觉是很不错的题。 题意：给你一个序列 \(a\)，并给你一个数 \(k\)。可以将其分解因数后乘到任意 \(a_i\) 上。求最大化的 \(a_i\) ......

义乌二中OJ网址（点击跳转） 网址首页有Python IDLE和Thonny的下载链接，点击即可下载 摘要 本题解按照题目难度进行分类，分为：入门、青铜、白银、黄金 优先更新青铜难度试题，入门难度试题会挑部分更新，白银和黄金难度试题后置 题解文章发布于本人的CSDN博客账号，点击文章链接即可跳转（如 ......

[NOIP2022] 比赛 0.问题转化 首先需要转化为区间历史和问题。 具体上来讲，就是将询问离线后，扫描线维护对于 \(r\) 来说，每一个 \(l\) 的 \(\sum_{i=l}^{r}(\max_{j=l}^{i}a_j\ \cdot\ \max_{j=l}^{i}b_j)\) 那么答案就 ......

洛谷 NOIP 2023 模拟赛 P9836 种树 目录洛谷 NOIP 2023 模拟赛 P9836 种树题目大意思路code 题目大意 路边有 \(n\) 棵树，每棵树的 高度 均为正整数，记作 \(p_1, p_2 \dots p_n\)。 定义一棵树的 宽度 为它高度的正因数个数，这些树能覆盖 ......

洛谷 NOIP 2023 模拟赛 P9837 汪了个汪 目录洛谷 NOIP 2023 模拟赛 P9837 汪了个汪题目大意思路code 题目大意 构造一个高为 \(n\) 的棋盘，第 \(i\) 行有 \(i\) 个格子。 每个格子里的数是 \([1 , n]\) 并且每一行中的每个数各不相同，所有 ......

原题链接 洛谷题面 提交记录 闲话 赛场就做了这道和 A，喜提 \(625\) 大分。 带权并查集练手题，有点像银河英雄传说。 题目大意 存在一个长度为 \(N\) 的数列 \(X\)，给定 \(Q\) 个三元组 \((a_i,b_i,d_i)\)，定义一个好集合为集合 \(S\subseteq\{ ......

1. 问题H:【C语言训练】排序问题<1> 1.1. 解题思路 题目已经告诉你了，用排序 1.2. 解题方法 1.2.1. 冒泡排序 #include <stdio.h> #define N 10 void bubberSort(int *a, int size);//冒泡排序，升序，即按从小到大的 ......

洛谷 NOIP 2023 模拟赛 T2 汪了个汪 考试建出正解图不知道怎么处理，题解区樱雪喵博客薄纱。 樱雪喵题解链接 Ps:笔者语文爆炸，不建议阅读本文 思路 首先你会发现，一共有 \(\frac{n(n-1)}{2}\) 个二元组，有 \(\frac{n(n-1)}{2}\) 个横向相邻数对。 ......

题解：[春季测试 2023] 幂次 给定 \(n,k\) ，求有多少个整数 \(i \in [1,n]\) ,满足 \(i=a^b (a,b \in N^+,b \geq k)\) 算法一 \(k \ge 3:\) 发现只需要筛到1e6就没有贡献了，加上 \(set\) 暴力判重即可。 \(k=2: ......

设 \(m\) 次选的位置分别为 \(b_{1\sim m}\)。 于是答案为 \(\mathbb E(\prod\limits_{i = 1}^{n}(a_i + \sum\limits_{j = 1}^{m}[b_j \le i]\cdot v)) = \frac{S}{n^m}\)。 首先考虑 ......

注意事项与提醒（请选手务必仔细阅读） 件文例样有带 立建已 1.选手提交的源程序必须存放在 ...好的，且 ...... 件文发下和 ..... 的文件 较比文 理 的全 受 后 予 车 不 回 诉 末 申 文 关相 空 影 行末 为 的 略 制 成 忽 限 造 小 绩 大 成 件 对 文 则 码 ......

双倍经验 分析 这是一道求最长下降子序列的题目，且要统计方案，但是会有重复情况，例如以下的的数据， 4 4 2 2 3 我们可以选择 \(1, 2\), \(1, 2\), \(1, 4\) 这几天来购买，但是 \(1, 2\) 和 \(1, 3\) 本质上是一样的，所以只算一种。 根据上面的说明， ......

P9838 挑战 NPC IV 定义 \(f(x) = 1 + \log_2 \operatorname{lowbit}(x)\)。 定义一个 \(1 \sim n\) 的排列 \(p\) 的权值是 \(\sum_{l = 1}^n \sum_{r = l}^n \sum_{i \in [l, r] ......

学习重点 图论 最短路 树：树基础、树直径、LCA、树重心 最小生成树 拓扑排序 差分约束 强连通分量 双连通分量 割点与桥 字符串 trie树 字符串哈希 字符串匹配（kmp） 动态规划 记忆化搜索 背包dp 线性dp 区间dp 树形dp 数据结构 分块 ST表 线段树 数学 筛法 gcd 素数 ......

这篇 blog 在我的博客后台躺了好几天了，只不过今天才记起来发。 种树 (plant) 首先看到因数个数，想到在质因数分解后的序列上考虑问题。进一步观察，每个不同质因子的贡献是独立的。 也就是说，我们单独考虑某一个质因子对答案的贡献，是这样的问题： 给长度为 \(n\) 的序列 \(a\) 和一个 ......

题目难度 \(B<D<E=C<A\) Candy war Question 有 \(N\) 个盒子摆成环形，第 \(i\) 和盒子里面有 \(a_i\) 个糖果，他们开始在 \(1\) 好盒子，然后每个人取一次，可以取\(1\)， 或者小于当前盒子内糖果数的一个质数 \(p\), 两个人都取了之后就 ......

anti-game 没有用，能取到 \(n-1\) 的必胜，不能取到 \(n-1\) 的必败，所以现在考虑取走最后石子获胜的情况。 对于一个 \(n\) 来说合法的 \(k\) 一定是一个前缀，并且一定是贪心取最小的（留给对方的机会更小），所以启发将每个 \(n\) 最小的合法的 \(k=a_n\) ......

A 直接模拟即可。 cin>>n>>m; for(int i=1;i<=n;++i){ int x; cin>>x; if(x<=m)sum+=x; } cout<<sum; B 直接模拟即可。 int n,ans; bool chk(int x,int y){ int dig=x%10; x/=1 ......

blog。提供一个普通并查集 + 启发式合并做法。 考虑直接维护 \(X_i\)。对于 \(X_u-X_v=w\)，分四种情况。 \(X_u,X_v\) 都没被维护过。直接钦定 \(X_u\gets w,X_v\gets0\)，以后再改。 \(X_u\) 没被维护过，\(X_v\) 被维护过。显然 ......

k-d-sequence 给你一个长为 \(n\) 的序列，求最长的子区间使得它加入至多 \(k\) 个数后，重排后是公差为 \(d\) 的等差数列。 \(n, k \le 2 \times 10^5\)，\(0 \le d \le 10^9\)。 公差是 \(d\) 的等差数列模 \(p\) 的值 ......

blog。剩下几分钟的时候胡出来了，但是时间不够，痛失 AK /dk。 \(N\le22\)，显然状压 DP。\(dp_s\) 表示确定 \(s\) 集合的元素所需的代价（这些元素都放在最前面）。 确定了 \(s\) 后，发现会有 \(\operatorname{popcount}(s)\) 个元素 ......

Mr. Kitayuta vs. Bamboos 给定 \(n\) 个数 \(h_{1 \dots n}\)。 你需要进行 \(m\) 轮操作，每轮操作为 \(k\) 次修改，每次修改可以选择一个数 \(h_i\) 修改为 \(\max(h_i - p, 0)\)。 每轮操作后每个 \(h_i\) ......