文章

1. 题目 传送门=￣ω￣= 题目大意： 给你一个长度为 $n$的序列，还有 $m$个操作，每次操作给出区间 $[l,r]$，表示将该区间内的数字反转（比如 123 变成 321），求所有操作后的序列。 $n,m<=100000$ 2. 题解 裸的 splay 区间操作（反转），拿来练手，毕竟 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 这个题是一个很经典的问题：最大点权问题 二分图最大点权独立集问题，就是找出图中一些点，使得这些点之间没有边相连，这些点的权值之和最大。 独立集与覆盖集是互补的，求最大点权独立集可以转化为求最小点权覆盖集（最小点权支配集）。最小点权覆盖集问题可以转化为最小割问 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 感觉没啥好说的，比较水。 从源点到每个类型连一条边，容量为该类型需要的题目数。 从每个类型到该类型对应的每个题目连一条边，容量为 1。 从每个题目到汇点连一条边，容量为 1. 跑最大流。跑完看从源点出发的边如果有没满流的则说明无解。否则对于每个类型来说，它所 阅读更多…

//其实应该是因为常数小所以跑得比较快吧 //但是其实比优化后的 Dinic 还是慢的，所以 dalao 可以不用看这篇文章了 //其实写这篇文章主要是因为蒟蒻 XZY 被骗了所以 “作文以记之”。 0. 引言 Binic 算法，即：“比你快” 算法。 在蒟蒻 XZY 被骗了（可能是 Ta 自己看教程 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 建模真奇妙。（同时这是我打的第一个真·Dinic，以前被骗了一直在打 BFS 版的增广路算法。。。）第一问用 dp 解决就行了。 第二问就得网络流。 首先我们把 $1,2,3,…,n$这些位置每个位置拆成两个点，我们设它们为 $(1,a),( 阅读更多…

考虑到我组选择的 “研究性学习” 课题内容需要简单的图形化界面，故决定在 Ubuntu 上用 OpenGL 实现。 1. 安装 sudo apt-get install build-essential sudo apt-get install libgl1-mesa-dev sudo apt-get 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 前面发了这题的贪心解法，但是毕竟题目没给出总人数限制，所以不严谨。 这里再给出网络流解法吧。 建图的话就是从源点连一条容量为 $r_i$的边到第 $i$个单位，再从第 $i$个桌子连一条容量为 $c_i$的边到汇点，最后从每个单位连一条容量为 1 的边到每个 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 一开始打了个网络流判断是否有解，然后打个贪心算方案。。。 我是不是傻逼啊，直接贪心算答案，发现算不出不就没解么。 只要一个一个地把人放到桌子上，每次取出空位子最多的桌子就行了。 主要是题目没给出总人数，所以可能会 GG。 但是实际是过了的，速度还可以。 代码 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 额。。。 要是我 NOIP2017 有这运气就好了。 代码： #include <bits/stdc++.h> using namespace std; int n,ans; stack<int> st[60]; bool ispow 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 DAG 的最小不相交路径覆盖问题 算法：把原图的每个点V拆成Vx和Vy两个点，如果有一条有向边A->B，那么就加边Ax−>By。这样就得到了一个二分图。那么最小路径覆盖=原图的结点数-新图的最大匹配数。 证明：一开始每个点都是独立的为一条路径，总共有 n 条 阅读更多…