hk_cnyali's Blog

靡不有初,鲜克有终


  • Home

  • Tags

  • Archives

  • About-Me

  • Friendly-Links

  • ToDoList

  • Debug

  • 搜索

虚树学习笔记

发表于 2019-02-19 19:11 | 更新于: 2019-02-19 21:40 | 分类于 Algorithm | | 阅读次数:

又是一个全机房只有我不会的知识点

同样,这篇文章也不适用于对这个知识点一无所知,且需要大量严谨证明的同学阅读

阅读全文 »

「UR #6」智商锁 - 随机 + Matrix-Tree

发表于 2019-02-17 20:29 | 更新于: 2019-02-17 21:17 | 分类于 Problem | | 阅读次数:

给出kkk,请你构造一个结点数不超过 100100100 的无向图,使得这个无向图中生成树的个数对998244353998244353998244353取模后恰好等于kkk

k∈[0,998244353)k\in [0, 998244353)k∈[0,998244353)

阅读全文 »

「UR #9」App管理器 - 贪心 + dfs

发表于 2019-02-17 20:24 | 更新于: 2019-02-17 20:38 | 分类于 Problem | | 阅读次数:

给你一个nnn个点mmm条边的混合图(既有有向边也有无向边)

你需要给所有无向边定向,使得新图中任意点两两可达

输出任意一种方案,数据保证有解

n,m≤5000n, m\le 5000n,m≤5000

阅读全文 »

Matrix-Tree定理

发表于 2019-02-16 14:48 | 更新于: 2019-02-18 21:28 | 分类于 Algorithm | | 阅读次数:

请注意,此文章内不含任何证明,因为我懒的写也不会,就先记着个结论好了

比较详细但易懂的证明可见这里

阅读全文 »

「清澄A1482」登顶计划 - 单调栈 + 计算几何

发表于 2019-02-16 10:53 | 更新于: 2019-02-16 16:08 | 分类于 Problem | | 阅读次数:

你在一座由nnn个点构成的山脉中爬山,第iii个点坐标为(xi,yi)(x_i, y_i)(x​i​​,y​i​​)

你的爬山策略是:

  • 一直往当前可见的最高点的方向走,也就是说你的策略是不断动态变化的

求从每个顶点出发,到达所能到达的最高点的路程分别是多少

加强版:

阅读全文 »

「CF578F」Mirror Box - 神仙题 + Matrix-Tree

发表于 2019-02-16 10:50 | 更新于: 2019-02-16 15:59 | 分类于 Problem | | 阅读次数:

题意太长,就放里面了

阅读全文 »

「CF814E」An unavoidable detour for home - 动态规划

发表于 2019-02-16 10:46 | 更新于: 2019-02-16 14:46 | 分类于 Problem | | 阅读次数:

给出nnn个点,和每个点的度让你构造出一张无向图满足以下两条性质:

  1. 点111到点iii仅有唯一一条最短路

  2. 点111到点iii的最短路长度大于等于点111到点i−1i-1i−1的最短路长度

求能构成满足条件的无重边无自环的无向图的个数

原题:n≤50n\le 50n≤50

加强版:n≤400n \le 400n≤400

阅读全文 »

线性基小结

发表于 2019-02-11 20:29 | 更新于: 2019-02-11 22:17 | 分类于 Algorithm | | 阅读次数:

线性基是常用来解决子集异或/线性空间中一些题目的算法

阅读全文 »

「CF1100F」Ivan and Burgers - 线性基 - 分治

发表于 2019-02-11 20:14 | 更新于: 2019-02-11 20:23 | 分类于 Problem | | 阅读次数:

给定长度为nnn的序列aia_ia​i​​,有次qqq询问(l,r)(l,r)(l,r),求在中选取任意个,使得它们的异或和最大

n≤500000,ai≤106n\le 500000, a_i\le 10^6n≤500000,a​i​​≤10​6​​

阅读全文 »

「CF1101G」(Zero XOR Subset)-less - 线性基

发表于 2019-02-11 19:08 | 更新于: 2019-02-11 19:17 | 分类于 Problem | | 阅读次数:

给出一个长度为nnn的序列{ai}\{a_i\}{a​i​​},试将其划分为尽可能多的非空子段,满足每一个元素出现且仅出现在其中一个子段中,且在这些子段中任取若干子段,它们包含的所有数的异或和不能为000.

n≤105,ai≤109n\le10^5, a_i\le 10^9n≤10​5​​,a​i​​≤10​9​​

阅读全文 »
12…29
hk_cnyali

hk_cnyali

287 日志
5 分类
154 标签
RSS
GitHub 知乎 Codeforces Luogu
Useful Website
  • graph_editor
  • geometry_widget
  • math
  • GeoGebra
0%
© 2019 hk_cnyali