hard
Passable Paths (hard version)
先写正常写法: 我的评价是,后面的分讨我直接树剖拿下。 我觉得这样分讨方便一点。 lca(u,v)=v(或者u,反证就是一条链的形状),那么 lca(u,i)==i,保证i在链上。 然后还有Y字形路径,lca(u,v)=t,则lca(u,i)=i且d[i]>=d[t]。 统一起来就是 \(lca(u ......
CF1450C2 Errich-Tac-Toe (Hard Version)
思路 实际上,如果你会简单版本,那么困难版本也没有那么难了。 同样考虑构造一种通解,如下, 红色的格子改为 X,绿色的格子改为 O,就是一种通解,同样的,这样改可能会超过棋子总数的 \(\frac 1 3\)。 将方案整体向上挪一格和两格可以得到一共三种通解,这三种通解需要改的棋子总数就是棋盘上的棋 ......
Fight Hard for Ecological Protection and Governance of the Yellow River to Address the Water Contamination
1.Effective measure aimed at addressing the water contamination: We will fight hard for ecological protection and governance of the Yellow River. We w ......
cf1856E2. PermuTree (hard version)(bitset+二进制优化背包+开不同大小bitset)
https://codeforces.com/contest/1856/problem/E2 结论是显然的,关键是有一些科技在里面 bitset+二进制优化 具体分析可以参考https://codeforces.com/blog/entry/98663 简而言之就是可以通过\(O(\frac{C\s ......
cf1582F2. Korney Korneevich and XOR (hard version)(暴力优化)
cf1582F2 对于每种数可以维护一个列表v[x],表示到当前位置,最后一个数小于等于x,能够取到的值,对于当前的数ai,我们可以用v[ai]中的值x与ai异或,来更新v[ai+1],v[ai+2]后面的值。 然后就是有两个优化,每次我们更新完后,都对v[a[i]]清空,因为只有两个相同数之间的数 ......
CF1868B2 Candy Party (Hard Version) 题解
Problem - 1868B2 - Codeforces Candy Party (Hard Version) - 洛谷 相信大家已经看过 Simple Version ,这题和上题不同之处就在于如果 \(b_i = 2^x\) ,他可以被分解成 \(2^x\) 或 \(2^{x+1}-2^x\) ......
《CF1889C2 Doremy's Drying Plan (Hard Version)》 解题报告
考场上不会做。 如果考虑删掉哪些区间实际上不太可做。正难则反,转化贡献,考虑哪些点可以有贡献。 显然一个点如果可能有贡献,那么当且仅当覆盖它的区间 \(\le K\) 个。 于是我们记一个状态 \(f_{i,j}\) 表示前 \(i\) 个点中, \(i\) 是最后一个贡献的点,已经删除了 \(j\ ......
CF1889C2 Doremy's Drying Plan (Hard Version) 题解
Description 有 \(n\) 个点和 \(m\) 条线段,你可以选择 \(k\) 条线段删除,最大化未被线段覆盖的点的数量,输出最大值,\(n, m \le 2 \times 10^5, k \le \min(m, 10)\) Solution 一道比较好玩的 dp 题。建议评级紫。 单独 ......
CF1889C2. Doremy's Drying Plan (Hard Version)
容易想到 dp:设 \(dp_{i,p}\) 表示前 \(i\) 天,强制第 \(i\) 天 dry,并且一共消除了 \(p\) 个区间的答案。 转移时可以考虑枚举前面的决策 \(j\),此时有转移方程: \[dp_{i,p}=\max(dp_{j,p-w})+1 \]其中 \(w\) 为满足 \( ......
D2. Dances (Hard Version)
D2. Dances (Hard Version) This is the hard version of the problem. The only difference is that in this version $m \leq 10^9$. You are given two arrays ......
CF1883G2 Dances (Hard Version)
思路 大体上的思路应该和简单版本一致,建议先看本人关于简单版本的题解。 与简单版本不同的是,困难版本的 \(m\) 可以不为 \(1\),而是取遍 \([1,m]\) 中的整数,所以答案的总值会变大很多倍。 如果直接枚举 \(m\) 次,时间复杂度将会达到 \(O(mn\log n)\) 显然过不了 ......
洛谷 P9432 [NAPC-#1] rStage5 - Hard Conveyors
这道题我看大家都用 dijkstra 啊,惊恐,这里提供一种换根 dp 的写法。 两点间最短路径,那一定是 LCA 没错了。用一遍 dfs 求出根节点到每个点的距离,记为 \(dist\)。那么 \(u,v\) 间最短路径长度就是 \(dist_u+dist_v-dist_{\operatornam ......
CF1542E2 Abnormal Permutation Pairs (hard version) 题解
Abnormal Permutation Pairs (hard version) 两个限制:字典序小、逆序对大,一个显然的想法就是确保一对关系,统计另一对关系。 确保哪一对呢?我们想了想,决定确保字典序小,因为字典序是可以贪心的。 具体而言,我们考虑两个排列自第 \(i\) 位开始出现了不同。这样 ......
【前缀和优化 dp】CF1542E2 Abnormal Permutation Pairs (hard version) 题解
CF1542E2 首先时间复杂度肯定是 \(\mathcal{O}(n^3)\) 的。 容易想到先枚举最长公共前缀,然后枚举 \(p_{len+1}\) 和 \(q_{len+1}\),再枚举逆序对数进行统计。 令 \(f_{i,j}\) 表示有 \(j\) 个逆序对的 \(i\) 阶排列的个数。 ......
AtCoder Regular Contest 066 F Contest with Drinks Hard
洛谷传送门 AtCoder 传送门 下文令 \(a\) 为原题中的 \(T\)。 考虑若没有饮料,可以设 \(f_i\) 表示,考虑了前 \(i\) 道题,第 \(i\) 道题没做的最大得分。转移就枚举上一道没做的题 \(j\),那么 \([j + 1, i - 1]\) 形成一个连续段。设 \(b ......
CF1204D2 Kirk and a Binary String (hard version) 题解
CF1204D2 Kirk and a Binary String (hard version) 题解 分析 先来分析 \(01\) 串的最长不下降子序列。全是 \(0\) 显然是不下降的,如果中间出现一个 \(1\),为了维护不下降的性质,后面就只能全是 \(1\)。一句话概括一下,\(0\) 后 ......
[AGC001E] BBQ Hard 题解
一道十分有趣的题。 一眼推式子,发现自己不会。 看了题解,发现是有趣思维题。但是由于我的朋友学习了有趣的思维题做法,因此我决定学习更有趣的生成函数做法!!! 考虑把原式拆开, \[\frac{1}{2}\times \left( \sum_{i=1}^{n}\sum_{j=1}^{n} \binom ......
CodeForces 1882E2 Two Permutations (Hard Version)
洛谷传送门 CF 传送门 如何评价,模拟赛搬了一道,前一天晚上代码写了一半的题。 考虑如何让操作次数最小。发现直接做太困难了。根本原因是,一次操作对序列的影响太大了。考虑做一些转化,减少一次操作对序列的影响。 仍然先考虑一个排列怎么做。 不知道为什么可以想到在排列前面添加特殊字符 \(0\) 变成 ......
[LeetCode] 1944. Number of Visible People in a Queue_Hard tag: stack
There are n people standing in a queue, and they numbered from 0 to n - 1 in left to right order. You are given an array heights of distinct integers ......
Zero-One (Hard Version) (删除多余信息,区间dp)
题目补充: 使得 a=b, 思路: 在 y<=x 好处理 在 y>x 时 利用区间dp处理 a==b 0, a!=b 1, 1要变 先预处理 把 0的 位置删了 删除多余信息 方便后面处理 然后 对于 取2个点 为 y ,另外一种操作就是 选2个连续的点直接 (他们位置差)*x 以此区间dp即可 或 ......
【主席树】P8201 [传智杯 #4 决赛] [yLOI2021] 生活在树上(hard version)题解
P8201 简单题。 题中求的是 \(dis_{a, t} \oplus dis_{t, b} = k\) 是否存在,显然不好直接维护,考虑转化。 令 \(dist = dis_{a, t} \oplus dis_{t, b}\),\(val = \bigoplus\limits_{x\in \te ......
Learning Hard C# 学习笔记: 8.C#中的特性 - 委托
介绍了委托的调用和它引入的原因,之后从IL的角度揭秘了委托的本质。最后介绍了委托链的概念:我们可以使用“+”运算符把一个委托添加到委托链实例中,也可以使用“-”运算符把委托实例从委托链中移除。 ......
Learning Hard C# 学习笔记: 6.C#中的接口
本章主要介绍了接口的定义、实现以及对其方法的调用;分析了隐式接口实现与显式接口实现间的区别,总结了两种实现使用的一般场景;最后分析了抽象类与接口之间的差异,给出了它们在面向对象编程中的应用。 ......
Learning Hard C# 学习笔记: 5.C#中的面向对象编程
本章详细介绍了C#中面向对象的3个特性——封装、继承和多态。通过这些内容,我们了解了将字段定义为私有的原因,学习了如何去继承一个类,以及如何去覆写和隐藏基类成员。最后,本章还简单地介绍了.NET中所有类的父类——System.Object 。 ......
Learning Hard C# 学习笔记: 4.C#中的类
类是面向对象语言都有的一种数据类型, 它的存在在于将现实中的概念抽象概括为代码中的数据类型. 4.1 什么是类? 以人类这个概念为例, 人类就可以作为一个类, 人类是一个种群, 这个种群中包包含许多个体, 这些个体可以当作一个对象. 比如说小明就是人类中的一个个体, 他是人类这个概念具体化之后推导而 ......
Learning Hard C# 学习笔记: 3.C#语言基础
前言 由于最近工作开始重新使用了C#, 框架也是.Net4.5, 看了下, 这本书是比较合适的, 所以就重新学习了下, 由于之前本人已有C#相关基础, 所以不会所有内容都做笔记, 只会对不熟悉或者比较重要的内容做笔记. 3.2 基础数据类型 3.2.4 枚举类型 枚举类型属于值类型, 用于定义一组命 ......
[LeetCode] 2334. Subarray With Elements Greater Than Varying Threshold_Hard tag: dp, stack
You are given an integer array nums and an integer threshold. Find any subarray of nums of length k such that every element in the subarray is greater ......
P9432 [NAPC-#1] rStage5 - Hard Conveyors
P9432 [NAPC-#1] rStage5 - Hard Conveyors 感谢此题让我知道了 Dijkstra 的一种新用法。 题意: 给定一棵 \(n\) 个节点的无根树以及树上的 \(k\) 个关键节点,给定边的长度。有 \(q\) 次询问,每次给出 \(s,t\),问从 \(s\) 到 ......
CF1791G2 Teleporters (Hard Version) 题解
CF1791G2 Teleporters (Hard Version) 题解 题目大意 题意挺清楚的,给个传送门吧。 分析 比较简单的贪心题,很容易就能看出来是贪心,也很容易就能看出来贪什么。 我没做简单版(Teleporters (Easy Version)),但是我去看了一眼。那个也非常简单,不 ......