线段树、扫描线、最大流最小割
前言
这个专题像是在复习，不过真的很多题目加深了我对原来学习的数据结构的理解
- 相遇碰撞模型 POJ 3684
https://www.cnblogs.com/SoniciSika/p/9034202.html - 从一道题目的解法试谈网络流的构造与算法 江鹏
https://wenku.baidu.com/view/a55eb5af84254b35eefd34ca.html - 扫描线 POJ 2932
http://www.cppblog.com/Wangzhihao/articles/109348.html
Crane - POJ - 2991
题意
有N条线段，标号为1到N，初始时所有线段都竖直向上，在每条线段的最上方有一个可以旋转的关节点。当一个关节点旋转时，它上面所有的线段都会跟着旋转。现在有多次旋转，每次旋转时将第i条线段和第i+1条线段的夹角变为rad（从第i条到第i+1条逆时针为正），问每次旋转后最上面一个关节点的坐标。
思路 —— 线段树区间修改
首先建线段树的时候先维护每条线段的坐标（向量）和绝对角度，对于每次旋转则首先从第i条线段和第i+1条线段的相对角度（原夹角）和输入给定夹角推算出旋转角度，再修改区间[i + 1, n]的绝对角度和坐标，最后输出根节点的x和y就是答案（因为最后一个关节点的坐标等于整段区间向量之和）
太久没打线段树了，WA了好几发 QAQ
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e4 + 15;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
double a[N];
double x[N << 2], y[N << 2], angle[N << 2];
double lzy[N << 2];
void rotAngle(int rt, double ang){
double prex = x[rt], prey = y[rt];
x[rt] = prex*cos(ang) - prey*sin(ang); //向量旋转公式
y[rt] = prex*sin(ang) + prey*cos(ang);
angle[rt] += ang;
}
void pushDown(int rt){
if(lzy[rt]){
lzy[rt << 1] += lzy[rt];
lzy[rt << 1 | 1] += lzy[rt];
rotAngle(rt << 1, lzy[rt]);
rotAngle(rt << 1 | 1, lzy[rt]);
lzy[rt] = 0;
}
}
void pushUp(int rt){
x[rt] = x[rt << 1] + x[rt << 1 | 1];
y[rt] = y[rt << 1] + y[rt << 1 | 1];
}
void build(int l, int r, int rt){
lzy[rt] = 0;
if(l == r){
x[rt] = 0;
y[rt] = a[l];
angle[rt] = PI/2;
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushUp(rt);
}
void update(int ql, int qr, double ang, int l, int r, int rt){
if(ql <= l && r <= qr){
rotAngle(rt, ang);
lzy[rt] += ang;
return;
}
pushDown(rt);
int m = (l + r) >> 1;
if(ql <= m) update(ql, qr, ang, lson);
if(m < qr) update(ql, qr, ang, rson);
pushUp(rt);
}
double query(int idx, int l, int r, int rt){
if(l == r) return angle[rt];
pushDown(rt);
int m = (l + r) >> 1;
if(idx <= m) return query(idx, lson);
else return query(idx, rson);
}
void change(int idx, double toang, int n){
double a1 = query(idx, 1, n, 1);
double a2 = query(idx + 1, 1, n, 1);
double ang = a1 - a2 + toang - PI; //旋转相对角度
update(idx + 1, n, ang, 1, n, 1);
}
int main() {
int n, q;
bool first = true;
while(~scanf("%d%d", &n, &q)){
if(first) first = false;
else puts("");
for(int i = 1; i <= n; i++){
scanf("%lf", &a[i]);
}
build(1, n, 1);
while(q--){
int idx;
double ang;
scanf("%d%lf", &idx, &ang);
change(idx, ang*PI/180, n);
printf("%.2f %.2f\n", x[1], y[1]);
}
}
return 0;
}
Minimizing maximizer - POJ - 1769
题意
给定一些区间，要求在给定的区间序列固定的情况下，从左到右选择最少的区间覆盖一整个区间[1, n]（允许重叠）
思路 —— 线段树优化DP
首先定义DP状态dp[i]代表以i为右端点的区间最少覆盖的区间个数，则对于区间[l, r]，dp[r] = min(dp[r], min(dp[l], dp[l + 1], ..., dp[r]) + 1)，因此可以用线段树维护DP的结果最小值
注意初始时dp[1] = 0, dp[2] = dp[3] = … = inf
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 50000 + 15;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
int a[N];
int minn[N << 2];
void init(){
memset(minn, 0x3f, sizeof(minn));
}
int pushUp(int rt){ return minn[rt] = min(minn[rt << 1], minn[rt << 1 | 1]); }
void update(int idx, int val, int l, int r, int rt){
if(l == r){
minn[rt] = min(minn[rt], val);
return;
}
int m = (l + r) >> 1;
if(idx <= m) update(idx, val, lson);
else update(idx, val, rson);
pushUp(rt);
}
int query(int ql, int qr, int l, int r, int rt){
if(ql <= l && r <= qr) return minn[rt];
int ret = inf;
int m = (l + r) >> 1;
if(ql <= m) ret = min(ret, query(ql, qr, lson));
if(qr > m) ret = min(ret, query(ql, qr, rson));
return ret;
}
int main() {
int n, m;
while(~scanf("%d%d", &n, &m)){
init();
update(1, 0, 1, n, 1);
while(m--){
int l, r;
scanf("%d%d", &l, &r);
int dpr = query(r, r, 1, n, 1);
int tmp = query(l, r, 1, n, 1);
if(dpr > tmp + 1){
update(r, tmp + 1, 1, n, 1);
}
}
printf("%d\n", query(n, n, 1, n, 1));
}
return 0;
}
Blocks POJ - 3734
题意
用红蓝绿黄四种颜色涂n个方格，求其中绿色和红色都是偶数的方案数有多少种
思路 —— 矩阵优化DP
看了dalao题解 orz
定义a[i]为红色绿色都是偶数的方案数，b[i]为红色和绿色有且只有一种是奇数的方案数，c[i]为都是奇数的方案数
a[i + 1] = 2*a[i] + b[i]，在a[i]后面涂蓝黄，或者在b[i]后面涂绿或红
b[i + 1] = 2*a[i] + 2*b[i] + 2*c[i]，在a[i]后面涂红绿，在b[i]后面涂蓝黄，在c[i]后面涂红绿
c[i + 1] = b[i] + 2*c[i]，在b[i]后面涂绿或红，在c[i]后面涂蓝黄
然后用矩阵优化DP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 50000 + 15;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int MOD = 1e4 + 7;
struct Matrix{
int met[3][3];
};
Matrix multiply(Matrix a, Matrix b){
Matrix ans;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
ans.met[i][j] = 0;
for(int k = 0; k < 3; k++){
ans.met[i][j] += (a.met[i][k] * b.met[k][j])%MOD;
}
ans.met[i][j] %= MOD;
}
}
return ans;
}
Matrix quickPow(Matrix met, int b){
Matrix ans, base = met;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
ans.met[i][j] = (i == j ? 1 : 0);
}
}
while(b){
if(b&1) ans = multiply(ans, base);
base = multiply(base, base);
b >>= 1;
}
return ans;
}
int main() {
int t;
scanf("%d", &t);
while(t--){
Matrix initmet;
memset(initmet.met, 0, sizeof(initmet.met));
initmet.met[0][0] = 1;
Matrix fac;
memset(fac.met, 0, sizeof(fac.met));
fac.met[0][0] = fac.met[1][0] = fac.met[1][1] = fac.met[1][2] = fac.met[2][2] = 2;
fac.met[0][1] = fac.met[2][1] = 1;
int n;
scanf("%d", &n);
Matrix ans = multiply(initmet, quickPow(fac, n));
printf("%d\n", ans.met[0][0]);
}
return 0;
}
Dual Core CPU - POJ - 3469
题意
给定n个任务，对于任务i，用A核心跑需要花费ai,用B核心少需要花费bi，而给定任务u,v，如果他们不在同一核心跑需要额外花费ci，求花费最小值
思路 —— 最小割
没想到是最小割，长见识了 orz
建一个源点s和汇点t，对于每一个任务i，从s连接到i一条ai的边，从i连接到t一条bi的边，如果两个节点有额外花费，再他们之间连接一条ci的边（双向），那么这道题就变成了求这幅图的最小割，因为使得s不能流向t刚好就是能符合题目要求的切割方法
根据最大流最小割定理，跑最大流就可以了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 15;
const int inf = 0x3f3f3f3f;
struct edge{
int v, nxt, val;
edge(int pv, int pnxt, int pval): v(pv), nxt(pnxt), val(pval) {}
edge() {}
};
edge e[N << 3];
int head[N], cur[N], gap[N], pre[N], d[N];
int tot;
inline void init(){
memset(head, -1, sizeof(head));
memset(d, 0, sizeof(d));
memset(gap, 0, sizeof(gap));
tot = 0;
}
inline void addEdge(int u, int v, int val){
e[tot] = edge(v, head[u], val);
head[u] = tot++;
e[tot] = edge(u, head[v], 0);
head[v] = tot++;
}
int ISAP(int src, int des, int n){
memcpy(cur, head, sizeof(head));
gap[0] = n;
int u = pre[src] = src;
int ans = 0;
while(d[src] < n){
if(u == des){
int aug = inf, v;
for(u = pre[des], v = des; v != src; v = u, u = pre[u]) aug = min(aug, e[cur[u]].val);
for(u = pre[des], v = des; v != src; v = u, u = pre[u]){
e[cur[u]].val -= aug;
e[cur[u]^1].val += aug;
}
ans += aug;
continue;
}
bool flag = false;
for(int& i = cur[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(d[u] == d[v] + 1 && e[i].val){
pre[v] = u;
u = v;
flag = true;
break;
}
}
if(!flag){
int mind = n;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(e[i].val && d[v] < mind){
mind = d[v];
cur[u] = i;
}
}
if((--gap[d[u]]) == 0) break;
d[u] = mind + 1;
gap[d[u]]++;
u = pre[u];
}
}
return ans;
}
int main() {
int n, m;
while(~scanf("%d%d", &n, &m)){
init();
int src = 0, des = n + 1;
for(int i = 1; i <= n; i++){
int a, b;
scanf("%d%d", &a, &b);
addEdge(src, i, a);
addEdge(i, des, b);
}
while(m--){
int u, v, val;
scanf("%d%d%d", &u, &v, &val);
addEdge(u, v, val);
addEdge(v, u, val);
}
printf("%d\n", ISAP(src, des, n + 2));
}
return 0;
}
Coneology - POJ - 2932
题意
给定n个圆的圆心坐标和半径，求其中未被其他圆包含的点的数量
思路 —— 扫描线
这题看到题解真是跪了 orz
用扫描线维护未被其他圆包含圆
具体来说就是，用set维护未被其他圆包含的圆，首先圆按左右端点排序（即一个圆要复制两个，端点相同半径大的在先），以便我们扫描（该扫描线是垂直于y轴的）
当我们扫描到一个圆的左端点时，检查其是否被其他圆包含，这一步只需要检查set中离其圆心y坐标最近的圆，即比它y坐标大的一个圆和小的一个圆，如果未被包含则入set
当我们扫描到一个圆的右端点时，如果其存在于set中，就删除这个圆，因为它不会对后续扫描产生影响
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int N = 4e4 + 15;
const int inf = 0x3f3f3f3f;
typedef pair<double, int> pdi;
double x[N], y[N], r[N];
struct Node{
int idx;
double cy, lrpoint;
bool is_left;
bool operator < (const Node& b) const{
if(lrpoint != b.lrpoint) return lrpoint < b.lrpoint;
else return r[idx] > r[b.idx];
}
};
bool inSide(int i, int j){
double dx = x[i] - x[j], dy = y[i] - y[j], dr = r[i] - r[j];
return dx*dx + dy*dy <= dr*dr;
}
set<pdi> st;
vector<Node> vec;
vector<int> ans;
int main() {
int n;
while(~scanf("%d", &n)){
st.clear();
vec.clear();
ans.clear();
set<pdi>::iterator it;
for(int i = 1; i <= n; i++){
scanf("%lf%lf%lf", &r[i], &x[i], &y[i]);
vec.push_back(Node{i, y[i], x[i] - r[i], 1});
vec.push_back(Node{i, y[i], x[i] + r[i], 0});
}
sort(vec.begin(), vec.end());
for(int i = 0; i < vec.size(); i++){
Node& u = vec[i];
if(u.is_left){
it = st.lower_bound(make_pair(y[u.idx], u.idx));
if(it != st.end() && inSide(u.idx, it->second)) continue;
if(it != st.begin() && inSide(u.idx, (--it)->second)) continue;
ans.push_back(u.idx);
st.insert(make_pair(y[u.idx], u.idx));
}else{
st.erase(make_pair(y[u.idx], u.idx));
}
}
printf("%d\n", ans.size());
sort(ans.begin(), ans.end());
for(int i = 0; i < ans.size(); i++){
printf("%d", ans[i]);
if(i < ans.size() - 1) putchar(' ');
}
puts("");
}
return 0;
}
