Praying_cqf

分类

训练总结(1) 题解(1)

/ 注册

全部文章（共14篇）

回家问题题解

【前言】比较难的题目。【暴力】每次搜索最佳路径。复杂度很大。【正解】正难则反。把问题变成，牛牛要按顺序出村子，尽量不经过有其他牛牛的位置。考虑一个优美一点的暴力，假设我们知道当前每个点出发离开网格时的最小内疚值，一个牛牛出村子可能会影响一些牛牛的答案，我们就暴力地更新，这样做最坏情况看起来是O(n^...

2020-07-10

0 684

树与异或问题题解

【前言】此题比较简单。【暴力】枚举一条简单路径，枚举另一条简单路径，暴力判断是否有公共边。复杂度O(n^4)或更高。【正解】根据异或的性质，x^y^y=x，所以说，两条简单路径的公共边在异或的过程中被抵消了，相当于没有选这些边，两条简单路径删除公共边的结果还会是两条简单路径，因此，有公共边这个条件可...

2020-07-10

0 598

树与序列问题题解

【前言】这是一道思维题，本质是贪心，没什么代码量。偶尔抖机灵抖出来的题目。【暴力】O(n!)枚举，我的数据最小的n是100.很遗憾。当然可能有稍微优秀一点点的暴力做法。【正解】目标是最大化答案，答案最大的情况就是每条边被选正好一次，因为无论如何改变排列p[],p[i]和p[i+1]的路径的并集都...

2020-03-09

0 703

线段树编号问题题解

在很早之前研究线段树的时候发现，以常规方法构造出的线段树编号可能并不连续。因此便有了这一题。结论1：手写若干个线段树可以发现，若给线段树分层，设区间[1,n]代表的点为第1层，下面是第2层第3层以此类推，我们可以发现，第i+1层的编号永远大于第i层的编号。证明：首先同层的情况下，左边节点编号小于右...

2020-02-14

0 1049