Tweetuzki

分类

一些算法(4) 未归档(2) 题解(14)

/ 注册

全部文章（共5篇）

矩阵快速幂

这周学习了矩阵快速幂，就在这里记录下我的一下理解吧。要学习矩阵快速幂，首先得先知道“矩阵”和“快速幂”的写法。先说快速幂顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为O(log₂N)，与朴素的O(N)相比效率有了极大的提高。 ——百度百科以NOI...

矩阵快速幂动规

2017-11-28

1 594

洛谷 P2915 【[USACO08NOV]奶牛混合起来Mixed Up Cows】

类似于n皇后的思想，只要把dfs表示放置情况的数字压缩成一个整数，就能实现记忆化搜索了。一些有关集合的操作： {i}在集合S内：S&(1<<i)==1；将{i}加入集合S：S=S|(1<<i)；集合S内包含了{0,1,2,...,n-2,n-1}：S==...

动规状态压缩

2018-01-01

0 380

洛谷 P1273 【有线电视网】

题目描述某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总...

动规树

2018-01-12

0 579

动态 DP 学习笔记

不得不承认，去年提高组 D2T3 对动态 DP 起到了良好的普及效果。动态 DP 主要用于解决一类问题。这类问题一般原本都是较为简单的树上 DP 问题，但是被套上了丧心病狂的修改点权的操作。举个例子，我们来看一道例题。【模板】动态 DP 给定一棵 \(n\) 个点的树。\(i\) 号...

动态 DP 树动规树链剖分

2019-01-15

0 569

牛客OI周赛9-提高组题目记录

牛客OI周赛9-提高组题目记录昨天晚上做了这一套比赛，觉得题目质量挺高，而且有一些非常有趣而且非常清奇的脑回路在里边，于是记录在此。 T1: 扫雷题目链接设 \(f_i\) 表示扫到第 \(i\) 个雷的期望用时，那么我们要求的答案就是 \(f_n\)。我们不难写出一个递推式：...

线段树树动规

2019-04-27

0 652