小琢卷不动

分类

未归档(10) 题解(72)

/ 注册

全部文章（共80篇）

题解 | #盾与战锤#

首先选择的是子序列，考虑对原序列排序没有影响。理由是选择子序列相当于可以任意选数，所以排序之后从大到小取可以双向规约。另外考虑对于不同的 kkk，首先对排序后的攻击序列做一遍前缀和，便于查询它们的区间和。如果我们直接枚举不同的 kkk，然后考虑每一个长度为 kkk 的区间：实际上这个区间的直...

C++

2021-11-03

1 341

题解 | #寒冬信使#

首先扔一个结论：原序列奇数位置上的 1 有 1 个单位贡献，最后贡献为奇数则 T 否则 X。考虑证明，首先任意一个偶数位置上的 1 没有意义，因为你对这个位置 iii 操作完了之后，对手继续操作位置 i−1i-1i−1，就相当于：翻转 iii、翻转 i−1i-1i−1 翻转 i−1i-1...

C++

2021-11-03

2 428

简介

这里给出一些琢喵博客上的小提示。一、公开题目题解资源 (solution) 这部分一般会直接公开，直接通过「搜索」功能找到对应题目的题解即可。二、游记或算法总结等 (note) 这部分一般会设置密码，直接私信琢喵申请访问密码即可，注意要告诉琢喵是哪篇博文哦 \(\sim\) 三、非公开...

2021-10-27

0 330

【题解】P7238「DCOI」迷失森林

\(1~\text{树的直径}\) Subtask5 满足 \(n\le10^3\)，因此可以 \(O(n^2)\) 模拟建树。以 \(u\) 为根的子树中，\(u\) 必选时树的直径为 \(d_1+d_2-1\)。其中 \(d_1,d_2\) 分别表示以 \(u\) 为根最大、次大深度。...

2021-10-27

0 462

【题解】P7806 「DCOI2021」A 冰魄吐息

首先二分 \(d\)，对每一个点 \(i\)，考虑找到一个区间 \([L_i,R_i]\) 满足：当且仅当 \(k\in[L_i,R_i]\)，直线 \(y=kx\) 能够覆盖点 \(i\)。原问题转化为一个经典问题：\(N\) 条线段，最少点数覆盖它们。考虑直接贪心解决，按照结束时间从...

2021-10-27

0 351

【题解】P7807 「DCOI2021」C 魔力滋生

\[\rm C~\text{魔力滋生} \] 部分分提示正解：前两个 Subtask 一个满足 \(x=0\) 另一个满足 \(x=1\)，提示了分类讨论。 \(n\) 个点的树，每个点的度不超过 \(2\)，也就是说这是一条链。首先考虑 \(x=0\)：显然此时给出的树 \(T'\) ...

2021-10-27

0 320

【题解】P7813 「DCOI」谜

证明这里出题人补充一种较为理性的证法。证明：考虑设我们以此种方式遍历到的数依次为 \[a_1,a_2,\dots,a_K \] 我们将序列 \(a\) 进行分类，分为位于倒数第二行的序列 \(b_{K/2}\) 和位于倒数第一行的序列 \(c_{K-K/2}\)。其中： ...

2021-10-27

0 371

【题解】P7905 「DCOI」黄牛の争

出题人题解。 E 黄牛の争数学模型考虑优化 Special Judge 中 win 函数部分的暴力，首先记 \(\alpha=\left\lceil\dfrac{B}{a}\right\rceil\) 表示 \(\tt A\) 击败 \(\tt B\) 所需回合数； \(...

2021-10-27

0 417

【题解】P7904 「DCOI」火烧の云

出题人题解。 D 火烧の云 Sol 考虑最短路，设一个三元组 \(dis(i,j,k)\) 表示到达位置 \((i,j)\) 且方向状态为 \(k\) 时所需最少步数。初始化：所有点位置字符导致的连边、权值更新；\(dis(S_i,S_j,\{0,1,2,3\})=0\)，最终答案：\(\...

2021-10-27

0 554

【题解】P7903 「DCOI」兜心の顶

出题人题解。 C 兜心の顶按道理边做这题边点开 P7238、P7807，应该通过率 100% 吧。下文中「唯一性」代指直径、重心、直径重心三个「唯一」，「不等性」代指树的重心不等于直径重心。一、直径的长度讨论首先直径不会是偶数。否则设直径的长度是 \(2k\)，由 \(1\c...

2021-10-27

0 375