Tweetuzki

分类

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

/ 注册

全部文章（共20篇）

当 C++ 遇上音乐

前几天在洛谷日报征文中看到了这样一篇文章：C++不止能做题。作为原来校管弦乐队的一名成员，而后因为信息完全放弃了管弦乐队，我看完是又激动又怀念。于是我自行去研究了一下：C++ 如何让蜂鸣器叫出乐曲。由于本人乐理只有五线谱D2-2级，数学成绩中游，信息也只有普及组水平。如果有哪里写错了，望大家指正...

音乐

2018-08-31

0 567

题解 CF934A 【A Compatible Pair】 ——贪心

题意：给定两个数列 \(A\) 、 \(B\) ，元素个数分别为 \(n\) ， \(m\) \((2 \le n,m \le 50)\) 。数列中所有元素大小均在 \(-10^{9}\) 到 \(10^{9}\) 之间。现要求在 \(A\) 数列中删掉一个元素，使得 \(A\) 中任一...

贪心

2018-06-18

0 667

洛谷 P3381 【【模板】最小费用最大流】

题目描述如题，给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。输入第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。接下来M行每行包含四个正整数ui、vi、wi、fi，表示...

网络流

2018-02-06

0 569

洛谷 P3376 【【模板】网络最大流】

题目描述如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。输入第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）...

网络流

2018-02-04

0 486

洛谷 P1027 【Car的旅行路线】

题目描述又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第i个城市中高速铁路的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。图例...

广搜最短路

2018-01-26

0 717

洛谷 P1273 【有线电视网】

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

动规树

2018-01-12

0 578

洛谷 P1856 【Picture】

题目描述 N(N<5000) 张矩形的海报，照片和其他同样形状的图片贴在墙上。它们的边都是垂直的或水平的。每个矩形可以部分或者全部覆盖其他矩形。所有的矩形组成的集合的轮廓称为周长。写一个程序计算周长。图 1 是一个有 7 个矩形的例子：图 1.一个 7 个矩形的集合对应的...

排序

2018-01-09

0 636

FZOJ P2109 【卡德加的兔子】

题目描述卡德加喜欢养兔子。他在达拉然的下水道里放了 $N$ 个兔笼（编号从 $1$ 到 $N$），里面养着他从德拉诺带来的兔子。它们的繁殖遵循斐波那契数列的规律：刚开始时，笼子里有一对刚出生的兔子。每对兔子在出生第二个月后，每个月都生一对兔子。（第一个月结束后有 $1$ 对兔子。第二个月结束后...

线段树矩阵快速幂

2018-01-06

0 560

洛谷 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

矩阵快速幂

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

矩阵快速幂动规

2017-11-28

1 594