2019-2020 ICPC Asia Hong Kong Regional

*A - Axis of Symmetry

给若干面积无交的矩形，求整个图案的所有对称轴。

把线段该连的都连起来，图形内部的线段都删掉。然后判断每个线段是否对称。写了个屎山代码非常垃圾。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

typedef double T;
#define let const auto
#define lett const T
#define letp const P // P for point
#define letl const L // L for line
const T eps = 1e-5;
#define z(x) (abs((x)) <= eps) // is zero
 
inline int roundint(double x) {
	int y = ceil(x);
	for (int i = y - 2; i <= y + 2; ++i) if (z(x - i)) return i;
	return 2e9;
}
 
struct P {
    T x, y;
    P (T x = 0, T y = 0) : x(x), y(y) {}
    P operator + (letp &p) const {return {x + p.x, y + p.y};} 
    P operator - (letp &p) const {return {x - p.x, y - p.y};} 
    P operator * (lett &d) const {return {x * d, y * d};}
    P operator / (lett &d) const {return {x / d, y / d};}
    P operator - () const {return {-x, -y};}
 
    T operator | (letp &p) const {return x * p.x + y * p.y;} // dot
    T operator ^ (letp &p) const {return x * p.y - y * p.x;} // cross

    T norm() const {return x * x + y * y;}
    P proj (letp &p) const {return (*this) * (((*this) | p) / norm());}
    P refl (letp &p) const {return proj(p) * 2 - p;}
} zero;

double abs(letp &p) {return sqrt(p.norm());}
P perp(letp &p) {return {-p.y, p.x};} // turn pi / 2 left(counterclockwise)
 
struct L {
    P p, v;
    L shiftl(double d) const {return {p + perp(v) * d / abs(v), v};}
    P proj(letp &a) const {return p + v.proj(a - p);}
    P refl(letp &a) const {return p + v.refl(a - p);} 
    double dis(letp &a) const {return (v ^ (a - p)) / abs(v);} 
};

#define N 100007

vector<P> Pt;

map<int, multiset<pii>> H, V;

bool check1(L l) {
	for (auto [x, S] : V) {
		for (auto [y1, y2] : S) {
			P p1 = l.refl(P{1.0 * x, 1.0 * y1}), p2 = l.refl(P{1.0 * x, 1.0 * y2});
			int tx = roundint(p1.x), ty1 = roundint(p1.y), ty2 = roundint(p2.y);
			if (ty1 > ty2) swap(ty1, ty2);
			if (V[tx].count(make_pair(ty1, ty2)) == 0) return false;
		}
	}
	for (auto [y, S] : H) {
		for (auto [x1, x2] : S) {
			P p1 = l.refl(P{1.0 * x1, 1.0 * y}), p2 = l.refl(P{1.0 * x2, 1.0 * y});
			int ty = roundint(p1.y), tx1 = roundint(p1.x), tx2 = roundint(p2.x);
			if (tx1 > tx2) swap(tx1, tx2);
			if (H[ty].count(make_pair(tx1, tx2)) == 0) return false;
		}
	}
	return true;
}

bool check2(L l) {
	for (auto [x, S] : V) {
		for (auto [y1, y2] : S) {
			P p1 = l.refl(P{1.0 * x, 1.0 * y1}), p2 = l.refl(P{1.0 * x, 1.0 * y2});
			int ty = roundint(p1.y), tx1 = roundint(p1.x), tx2 = roundint(p2.x);
			if (tx1 > tx2) swap(tx1, tx2);
			if (H[ty].count(make_pair(tx1, tx2)) == 0) return false;
		}
	}
	for (auto [y, S] : H) {
		for (auto [x1, x2] : S) {
			P p1 = l.refl(P{1.0 * x1, 1.0 * y}), p2 = l.refl(P{1.0 * x2, 1.0 * y});
			int tx = roundint(p1.x), ty1 = roundint(p1.y), ty2 = roundint(p2.y);
			if (ty1 > ty2) swap(ty1, ty2);
			if (V[tx].count(make_pair(ty1, ty2)) == 0) return false;
		}
	}
	return true;
}

inline void work() {
	H.clear(); V.clear(); Pt.clear();
	int n = rd();
	int mxx = -1e9, mxy = -1e9, mnx = 1e9, mny = 1e9;
	for (int i = 1; i <= n; ++i) {
		int x1 = rd(), y1 = rd(), x2 = rd(), y2 = rd();
		Pt.push_back(P{1.0 * x1, 1.0 * y1}); Pt.push_back(P{1.0 * x1, 1.0 * y2}); 
		Pt.push_back(P{1.0 * x2, 1.0 * y1}); Pt.push_back(P{1.0 * x2, 1.0 * y2});
		mxx = max(mxx, x2); mnx = min(mnx, x1);
		mxy = max(mxy, y2); mny = min(mny, y1);
		V[x1].insert(make_pair(y1, y2)); V[x2].insert(make_pair(y1, y2));
		H[y1].insert(make_pair(x1, x2)); H[y2].insert(make_pair(x1, x2));
	}
	// connect segments
	multiset<pii> tmp; tmp.clear();
	for (auto &[x, S] : V) {
		int R = -1e9;
		for (auto [l, r] : S) {
			if (tmp.empty() || l > R) tmp.insert(make_pair(l, r));
			else {
				auto [l1, r1] = *--tmp.end(); tmp.erase(--tmp.end()); int l2 = l, r2 = r;
				if (r1 == l2) tmp.insert(make_pair(l1, r2));
				else {
					if (l1 != l2) tmp.insert(make_pair(min(l1, l2), max(l1, l2)));
					if (r1 != r2) tmp.insert(make_pair(min(r1, r2), max(r1, r2)));
				}
			}
			R = max(R, r);
		}
		swap(S, tmp); tmp.clear();
	}
	for (auto &[y, S] : H) {
		int R = -1e9;
		for (auto [l, r] : S) {
			if (tmp.empty() || l > R) tmp.insert(make_pair(l, r));
			else {
				auto [l1, r1] = *--tmp.end(); tmp.erase(--tmp.end()); int l2 = l, r2 = r;
				if (r1 == l2) tmp.insert(make_pair(l1, r2));
				else {
					if (l1 != l2) tmp.insert(make_pair(min(l1, l2), max(l1, l2)));
					if (r1 != r2) tmp.insert(make_pair(min(r1, r2), max(r1, r2)));
				}
			}
			R = max(R, r);
		}
		swap(S, tmp); tmp.clear();
	}

	vector<tii> ans; ans.clear();
	// y = midy
	if (check1(L{{0, (mxy + mny) / 2.0},{1, 0}})) {
		int a = 0, b = 2, c = mny + mxy;
		int g = gcd(gcd(abs(a), abs(b)), abs(c));
		a /= g; b /= g; c /= g;
		tii res = max(make_tuple(a, b, c), make_tuple(-a, -b, -c));
		ans.push_back(res);
	}
	
	// x = midx
	if (check1(L{{(mxx + mnx) / 2.0, 0},{0, 1}})) {
		int a = 2, b = 0, c = mnx + mxx;
		int g = gcd(gcd(abs(a), abs(b)), abs(c));
		a /= g; b /= g; c /= g;
		tii res = max(make_tuple(a, b, c), make_tuple(-a, -b, -c));
		ans.push_back(res); 
	}
 
	// "/"
	L l1{{0, 0}, {1, 1}};
	double mxd = -1e18, mnd = 1e18;
	for (auto p : Pt) {
		double d = l1.dis(p);
		mxd = max(mxd, d); mnd = min(mnd, d);
	}
	l1 = l1.shiftl((mxd + mnd) / 2.0);
	if (check2(l1)) {
		int a = roundint(2 * l1.v.y);
		int b = roundint(-2 * l1.v.x);
		int c = roundint(2 * (l1.p.x * l1.v.y - l1.p.y * l1.v.x));
		int g = gcd(gcd(abs(a), abs(b)), abs(c));
		a /= g; b /= g; c /= g;
		tii res = max(make_tuple(a, b, c), make_tuple(-a, -b, -c));
		ans.push_back(res); 
	}
 
	// "\"
	l1 = L{{0, 0}, {1, -1}};
	mxd = -1e18, mnd = 1e18;
	for (auto p : Pt) {
		double d = l1.dis(p);
		mxd = max(mxd, d); mnd = min(mnd, d);
	}
	l1 = l1.shiftl((mxd + mnd) / 2.0); // 平移到最远点对中间
	if (check2(l1)) {
		int a = roundint(2 * l1.v.y);
		int b = roundint(-2 * l1.v.x);
		int c = roundint(2 * (l1.p.x * l1.v.y - l1.p.y * l1.v.x));
		int g = gcd(gcd(abs(a), abs(b)), abs(c));
		a /= g; b /= g; c /= g;
		tii res = max(make_tuple(a, b, c), make_tuple(-a, -b, -c));
		ans.push_back(res);
	}

	printf("%d\n", (int)ans.size());
	sort(ans.begin(), ans.end());
	reverse(ans.begin(), ans.end());
	for (auto [a, b, c] : ans) printf("%d %d %d ", a, b, c);
	puts("");
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

针对这个题，因为都是边界平行于对称轴的图形之间的对称，所以对称轴必过 \((\frac{mnx+mxx}{2},\frac{mny+mxy}{2})\) ，找直线好找很多。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tii;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

typedef double T;
#define let const auto
#define lett const T
#define letp const P // P for point
#define letl const L // L for line
const T eps = 1e-5;
#define z(x) (abs((x)) <= eps) // is zero
 
inline int roundint(double x) {
    int y = ceil(x);
    if (z(y - 1 - x)) return y - 1;
    return (z(y - x) ? y : y + 1);
}
 
struct P {
    T x, y;
    P (T x = 0, T y = 0) : x(x), y(y) {}
    P operator + (letp &p) const {return {x + p.x, y + p.y};} 
    P operator - (letp &p) const {return {x - p.x, y - p.y};} 
    P operator * (lett &d) const {return {x * d, y * d};}
    P operator / (lett &d) const {return {x / d, y / d};}
    P operator - () const {return {-x, -y};}
 
    T operator | (letp &p) const {return x * p.x + y * p.y;} // dot
    T operator ^ (letp &p) const {return x * p.y - y * p.x;} // cross

    T norm() const {return x * x + y * y;}
    P proj (letp &p) const {return (*this) * (((*this) | p) / norm());}
    P refl (letp &p) const {return proj(p) * 2 - p;}
} zero;

struct L {
    P p, v;
    P proj(letp &a) const {return p + v.proj(a - p);}
    P refl(letp &a) const {return p + v.refl(a - p);} 
};

map<int, multiset<pii>> H, V;

bool check1(L l) { // H <-> H, V <-> V
    for (auto [x, S] : V) {
        for (auto [y1, y2] : S) {
            P p1 = l.refl(P{1.0 * x, 1.0 * y1}), p2 = l.refl(P{1.0 * x, 1.0 * y2});
            int tx = roundint(p1.x), ty1 = roundint(p1.y), ty2 = roundint(p2.y);
            if (ty1 > ty2) swap(ty1, ty2);
            if (V[tx].count(make_pair(ty1, ty2)) == 0) return false;
        }
    }
    for (auto [y, S] : H) {
        for (auto [x1, x2] : S) {
            P p1 = l.refl(P{1.0 * x1, 1.0 * y}), p2 = l.refl(P{1.0 * x2, 1.0 * y});
            int ty = roundint(p1.y), tx1 = roundint(p1.x), tx2 = roundint(p2.x);
            if (tx1 > tx2) swap(tx1, tx2);
            if (H[ty].count(make_pair(tx1, tx2)) == 0) return false;
        }
    }
    return true;
}

bool check2(L l) { // H <-> V
    for (auto [x, S] : V) {
        for (auto [y1, y2] : S) {
            P p1 = l.refl(P{1.0 * x, 1.0 * y1}), p2 = l.refl(P{1.0 * x, 1.0 * y2});
            int ty = roundint(p1.y), tx1 = roundint(p1.x), tx2 = roundint(p2.x);
            if (tx1 > tx2) swap(tx1, tx2);
            if (H[ty].count(make_pair(tx1, tx2)) == 0) return false;
        }
    }
    for (auto [y, S] : H) {
        for (auto [x1, x2] : S) {
            P p1 = l.refl(P{1.0 * x1, 1.0 * y}), p2 = l.refl(P{1.0 * x2, 1.0 * y});
            int tx = roundint(p1.x), ty1 = roundint(p1.y), ty2 = roundint(p2.y);
            if (ty1 > ty2) swap(ty1, ty2);
            if (V[tx].count(make_pair(ty1, ty2)) == 0) return false;
        }
    }
    return true;
}

inline void work() {
    H.clear(); V.clear();
    int n = rd();
    int mxx = -1e9, mxy = -1e9, mnx = 1e9, mny = 1e9;
    for (int i = 1; i <= n; ++i) {
        int x1 = rd(), y1 = rd(), x2 = rd(), y2 = rd();
        mxx = max(mxx, x2); mnx = min(mnx, x1);
        mxy = max(mxy, y2); mny = min(mny, y1);
        V[x1].insert(make_pair(y1, y2)); V[x2].insert(make_pair(y1, y2));
        H[y1].insert(make_pair(x1, x2)); H[y2].insert(make_pair(x1, x2));
    }

    multiset<pii> tmp; tmp.clear();
    for (auto &[x, S] : V) {
        int R = -1e9;
        for (auto [l, r] : S) {
            if (tmp.empty() || l > R) tmp.insert(make_pair(l, r));
            else {
                auto [l1, r1] = *--tmp.end(); tmp.erase(--tmp.end()); int l2 = l, r2 = r;
                if (r1 == l2) tmp.insert(make_pair(l1, r2)); // connect segments
                else { // remove the intersection
                    if (l1 != l2) tmp.insert(make_pair(min(l1, l2), max(l1, l2)));
                    if (r1 != r2) tmp.insert(make_pair(min(r1, r2), max(r1, r2)));
                }
            }
            R = max(R, r);
        }
        swap(S, tmp); tmp.clear();
    }
    for (auto &[y, S] : H) {
        int R = -1e9;
        for (auto [l, r] : S) {
            if (tmp.empty() || l > R) tmp.insert(make_pair(l, r));
            else {
                auto [l1, r1] = *--tmp.end(); tmp.erase(--tmp.end()); int l2 = l, r2 = r;
                if (r1 == l2) tmp.insert(make_pair(l1, r2)); // connect segments
                else { // remove the intersection
                    if (l1 != l2) tmp.insert(make_pair(min(l1, l2), max(l1, l2)));
                    if (r1 != r2) tmp.insert(make_pair(min(r1, r2), max(r1, r2)));
                }
            }
            R = max(R, r);
        }
        swap(S, tmp); tmp.clear();
    }

    vector<tii> ans; ans.clear();
    // y = midy
    if (check1(L{{0, (mxy + mny) / 2.0},{1, 0}})) {
        int a = 0, b = 2, c = mny + mxy;
        int g = gcd(gcd(abs(a), abs(b)), abs(c));
        a /= g; b /= g; c /= g;
        tii res = max(make_tuple(a, b, c), make_tuple(-a, -b, -c));
        ans.push_back(res);
    }
    // x = midx
    if (check1(L{{(mxx + mnx) / 2.0, 0},{0, 1}})) {
        int a = 2, b = 0, c = mnx + mxx;
        int g = gcd(gcd(abs(a), abs(b)), abs(c));
        a /= g; b /= g; c /= g;
        tii res = max(make_tuple(a, b, c), make_tuple(-a, -b, -c));
        ans.push_back(res); 
    }
    // "/"
    L l1{{(mxx + mnx) / 2.0, (mxy + mny) / 2.0}, {1, 1}};
    if (check2(l1)) {
        int a = roundint(2 * l1.v.y);
        int b = roundint(-2 * l1.v.x);
        int c = roundint(2 * (l1.p.x * l1.v.y - l1.p.y * l1.v.x));
        int g = gcd(gcd(abs(a), abs(b)), abs(c));
        a /= g; b /= g; c /= g;
        tii res = max(make_tuple(a, b, c), make_tuple(-a, -b, -c));
        ans.push_back(res); 
    }
    // "\"
    l1 = L{{(mxx + mnx) / 2.0, (mxy + mny) / 2.0}, {1, -1}};
    if (check2(l1)) {
        int a = roundint(2 * l1.v.y);
        int b = roundint(-2 * l1.v.x);
        int c = roundint(2 * (l1.p.x * l1.v.y - l1.p.y * l1.v.x));
        int g = gcd(gcd(abs(a), abs(b)), abs(c));
        a /= g; b /= g; c /= g;
        tii res = max(make_tuple(a, b, c), make_tuple(-a, -b, -c));
        ans.push_back(res);
    }
    printf("%d\n", (int)ans.size());
    sort(ans.begin(), ans.end());
    reverse(ans.begin(), ans.end());
    for (auto [a, b, c] : ans) printf("%d %d %d ", a, b, c);
    puts("");
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

看了下比较短的代码，发现都是用边界上所有拐点的对称性来判断的。边界上拐点就是只出现过一次的矩形顶点 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tii;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

typedef double T;
#define let const auto
#define lett const T
#define letp const P // P for point
#define letl const L // L for line
const T eps = 1e-5;
#define z(x) (abs((x)) <= eps) // is zero
 
inline int roundint(double x) {
    int y = ceil(x);
    for (int i = y - 1; i <= y + 1; ++i) if (z(x - i)) return i;
    return 2e9;
}
 
struct P {
    T x, y;
    P (T x = 0, T y = 0) : x(x), y(y) {}
    P operator + (letp &p) const {return {x + p.x, y + p.y};} 
    P operator - (letp &p) const {return {x - p.x, y - p.y};} 
    P operator * (lett &d) const {return {x * d, y * d};}
    P operator / (lett &d) const {return {x / d, y / d};}
    P operator - () const {return {-x, -y};}
 
    T operator | (letp &p) const {return x * p.x + y * p.y;} // dot
    T operator ^ (letp &p) const {return x * p.y - y * p.x;} // cross

    bool operator == (letp &p) const {return z(x - p.x) && z(y - p.y);}
    bool operator != (letp &p) const {return ! operator == (p);}
    bool operator < (letp &p) const {return z(x - p.x) ? y < p.y : x < p.x;}
    bool operator > (letp &p) const {return !(*this < p || *this == p);}

    T norm() const {return x * x + y * y;}
    P proj (letp &p) const {return (*this) * (((*this) | p) / norm());}
    P refl (letp &p) const {return proj(p) * 2 - p;}
} zero;

struct L {
    P p, v;
    P proj(letp &a) const {return p + v.proj(a - p);}
    P refl(letp &a) const {return p + v.refl(a - p);} 
};

set<P> s;

vector<tii> ans; 

inline void work() {
    s.clear(); ans.clear();
    int n = rd(), mxx = -1e9, mxy = -1e9, mnx = 1e9, mny = 1e9;
    auto add = [&](int x, int y) {
        P nw = P{1.0 * x, 1.0 * y};
        if (s.count(nw)) s.erase(nw); else s.insert(nw);
    };
    for (int i = 1; i <= n; ++i) {
        int x1 = rd(), y1 = rd(), x2 = rd(), y2 = rd();
        add(x1, y1); add(x1, y2); 
        add(x2, y1); add(x2, y2);
        mxx = max(mxx, x2); mnx = min(mnx, x1);
        mxy = max(mxy, y2); mny = min(mny, y1);
    }
    auto check = [&](L l) {
        for (auto p : s) if (s.count(l.refl(p)) == 0) return false;
        return true;
    };
    auto addans = [&](int a, int b, int c) {
        int g = gcd(gcd(abs(a), abs(b)), abs(c));
        a /= g; b /= g; c /= g;
        tii res = max(make_tuple(a, b, c), make_tuple(-a, -b, -c));
        ans.push_back(res);
    };
    // y = midy
    if (check(L{{0, (mxy + mny) / 2.0},{1, 0}})) addans(0, 2, mny + mxy);
    // x = midx
    if (check(L{{(mxx + mnx) / 2.0, 0},{0, 1}})) addans(2, 0, mnx + mxx);
    // "/"
    L l1{{(mxx + mnx) / 2.0, (mxy + mny) / 2.0}, {1, 1}};
    if (check(l1)) addans(roundint(2 * l1.v.y), roundint(-2 * l1.v.x), roundint(2 * (l1.p.x * l1.v.y - l1.p.y * l1.v.x)));
    // "\"
    l1 = L{{(mxx + mnx) / 2.0, (mxy + mny) / 2.0}, {1, -1}};
    if (check(l1)) addans(roundint(2 * l1.v.y), roundint(-2 * l1.v.x), roundint(2 * (l1.p.x * l1.v.y - l1.p.y * l1.v.x)));

    printf("%d\n", (int)ans.size());
    sort(ans.begin(), ans.end());
    reverse(ans.begin(), ans.end());
    for (auto [a, b, c] : ans) printf("%d %d %d ", a, b, c);
    puts("");
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

B - Binary Tree

给定一棵树，轮流删掉一个满二叉子树，问谁赢。

注意到满二叉树的点数总是奇数，所以答案只和总节点数的奇偶性有关。

#include<bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

inline void work() {
	int x = rd();
	puts((x & 1) ? "Alice" : "Bob");
	for (int i = 1; i < x; ++i) {rd(); rd();}
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

C - Constructing Ranches

胖胖说是点分治板子题。

#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=maxn<<1,LOG=17;

int te,n,a[maxn+5];LL sum[maxn+5],dis[maxn+5],ans;
int E,lnk[maxn+5],nxt[(maxn<<1)+5],to[(maxn<<1)+5];
int fa[maxn+5],dep[maxn+5],SH[maxn+5],top[maxn+5];
int lt[maxn+5],ST[LOG+1][maxn+5],lg[maxn+5];
int gr,S,si[maxn+5],ms[maxn+5];bool vis[maxn+5];
int m;pair<int,LL> p[maxn+5];
LL c[maxt+5];int tr[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
	static char buf[1<<16],*l=buf,*r=buf;
	return l==r && (r=(l=buf)+fread(buf,1,1<<16,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
	T tot=0;char ch=readc(),lst='+';
	while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
	while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
	lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
inline void Add(int x,int y) {to[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
void DFS(int x,int pre=0){
	si[x]=1;SH[x]=0;fa[x]=pre;dep[x]=dep[pre]+1;
	for (int j=lnk[x];j;j=nxt[j])
		if (to[j]!=pre){
			DFS(to[j],x);si[x]+=si[to[j]];
			if (si[to[j]]>si[SH[x]]) SH[x]=to[j];
		}
}
void HLD(int x,int lst,int pre=0){
	lt[x]=++lt[0];ST[0][lt[0]]=a[x];top[x]=lst;
	if (SH[x]) HLD(SH[x],lst,x);
	for (int j=lnk[x];j;j=nxt[j])
		if (to[j]!=pre && to[j]!=SH[x])
			HLD(to[j],to[j],x);
}
int Max(int L,int R) {int k=lg[R-L+1];return max(ST[k][L],ST[k][R-(1<<k)+1]);}
void getgr(int x,int pre=0){
	si[x]=1;ms[x]=0;
	for (int j=lnk[x],u;j;j=nxt[j])
		if ((u=to[j])!=pre && !vis[u]){
			getgr(u,x);si[x]+=si[u];
			ms[x]=max(ms[x],si[u]);
		}
	ms[x]=max(ms[x],S-si[x]);
	if (!gr || ms[x]<ms[gr]) gr=x;
}
pair<int,LL> Ask(int x,int y){
	int MAX=0;LL S=0;
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		MAX=max(MAX,Max(lt[top[x]],lt[x]));
		S+=sum[lt[x]]-sum[lt[top[x]]-1];
		x=fa[top[x]];
	}
	if (lt[x]>lt[y]) swap(x,y);
	MAX=max(MAX,Max(lt[x],lt[y]));
	S+=sum[lt[y]]-sum[lt[x]-1];
	return mp(MAX,S);
}
void getpair(int x,int fa,int pre=0){
	p[++m]=Ask(x,fa);
	for (int j=lnk[x],u;j;j=nxt[j])
		if ((u=to[j])!=pre && !vis[u]) getpair(to[j],fa,x);
}
int Find(LL x){
	int L=1,R=c[0];
	for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
		x<=c[mid]?R=mid-1:L=mid+1;
	return L;
}
void Insert(int x,int y) {for (;x<=c[0];x+=x&-x) tr[x]+=y;}
int Sum(int x) {int sum=0;for (;x;x-=x&-x) sum+=tr[x];return sum;}
void Count(int x,int fa,int f){
	m=0;getpair(x,fa);
	sort(p+1,p+1+m);c[0]=0;
	for (int i=1;i<=m;i++) c[++c[0]]=(p[i].fr<<1)-p[i].sc,c[++c[0]]=p[i].sc-a[fa];
	sort(c+1,c+1+c[0]);c[0]=unique(c+1,c+1+c[0])-(c+1);
	for (int i=1;i<=c[0];i++) tr[i]=0;
	for (int i=1;i<=m;i++){
		LL A=c[0]-Find((p[i].fr<<1)-p[i].sc)+1,B=c[0]-Find(p[i].sc-a[fa])+1;
		ans+=f*Sum(A-1);Insert(B,1);
	}
}
void Divide(int x){
	vis[x]=true;Count(x,x,1);
	for (int j=lnk[x],u;j;j=nxt[j])
		if (!vis[u=to[j]]){
			Count(u,x,-1);
			gr=0;S=si[u];getgr(u);Divide(gr);
		}
}
int main(){
	for (int i=2;i<=maxn;i++) lg[i]=lg[i>>1]+1;
	for (readi(te);te;te--){
		readi(n);for (int i=1;i<=n;i++) readi(a[i]);
		E=0;for (int i=1;i<=n;i++) lnk[i]=0;
		for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);
		DFS(1);lt[0]=0;HLD(1,1);
		for (int j=1;(1<<j)<=n;j++)
			for (int i=1;i+(1<<j)-1<=n;i++)
				ST[j][i]=max(ST[j-1][i],ST[j-1][i+(1<<j-1)]);
		for (int i=1;i<=n;i++) sum[i]=sum[i-1]+ST[0][i];
		for (int i=1;i<=n;i++) vis[i]=false;
		ans=0;gr=0;S=n;getgr(1);Divide(gr);
		printf("%lld\n",ans);
	}
	return 0;
}

D - Defining Labels

找 \(k\) 进制下的第 \(X\) 小数。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxl=100000;

int te,K,n,a[maxl+5];

int main(){
	for (scanf("%d",&te);te;te--){
		scanf("%d%d",&K,&n);
		LL pw=K,len=1;
		while (n>pw) n-=pw,pw*=K,len++;
		n--;
		for (int i=0;i<len;i++) a[i]=n%K,n/=K;
		for (int i=len-1;~i;i--) putchar(a[i]+10-K+48);puts("");
	}
	return 0;
}

*E - Erasing Numbers

给定长度为 \(n\) 的数列 \(a_1,a_2,\dots,a_n\) ，保证 \(n\) 是奇数，\(a_i\) 两两不同，每次操作选择相邻的三个数，保留中位数。

最后一定只会剩下一个数字。对于每个 \(a_i\) ，询问是否存在一种操作顺序，使得最后剩下的数字是他。

又是奇怪的贪心题。首先如果一个数是中位数，那么它肯定能被留下来。

比如当前考虑的是 \(x\) ，令比 \(x\) 大的为 \(1\) ，比 \(x\) 小的为 \(0\) ，那么肯定有某一类会多出来。

以 \(x\) 为断点将序列分成两段，每一段尽可能消除多的那一类即可（连续 \(3\) 个即可少 \(2\) 个）。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

inline bool getmin(int &a, int b) {return (a > b ? (a = b, true) : false);}
inline bool getmax(int &a, int b) {return (a < b ? (a = b, true) : false);}

#define N 5007

int a[N], b[N];

inline int getmax(int l, int r, int tar) {
    int cnt = 0, sum = 0;
    for (int i = l; i <= r; ++i) {
        if (b[i] == tar) {
            if (cnt) --cnt;
            else sum += tar;
        } else {
            ++cnt;
            if (cnt >= 3) cnt -= 2;
        }
    }
    return -tar * cnt + sum;
}

inline void work() {
    int n = rd();
    for (int i = 1; i <= n; ++i) a[i] = rd();
    for (int i = 1; i <= n; ++i) {
        int sum = 0;
        for (int j = 1; j <= n; ++j) 
            if (j != i) {
                b[j] = (a[j] > a[i] ? 1 : -1);
                sum += b[j];
            }
        if (sum == 0) {putchar('1'); continue;}
        else {
            if (sum > 0 && getmax(1, i - 1, -1) + getmax(i + 1, n, -1) <= 0) {putchar('1'); continue;}
            if (sum < 0 && getmax(1, i - 1, 1) + getmax(i + 1, n, 1) >= 0) {putchar('1'); continue;}
        }   
        putchar('0');
    }
    puts("");
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

F - Falling Objects

三维计算几何大模拟。

G - Game Design

小清新构造，满足叶子权值 \(=1\) ，父节点权值 \(=\prod\) 儿子权值 \(+1\) ，根节点给定。

每次分奇偶讨论即可，偶数一个儿子，奇数两个儿子 \(2\) 和 \(x/2\) ，这样只有 \(\log n\) 个点。

#include<bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 200007

int tot, fa[N], son[N];

int build(int k, int faa) {
	int u = ++tot;
	fa[u] = faa;
	--k;
	if (k == 0) {son[u] = 1; return u;}
	if (k & 1) son[u] = son[build(k, u)];
	else {
		son[u] += son[build(2, u)];
		son[u] += son[build(k / 2, u)];
	}	
	return u;
}

int main() {
	int k = rd();
	if (k == 1) {puts("2\n1\n1 2"); return 0;}
	build(k, 0);
	printf("%d\n", tot);
	for (int i = 2; i <= tot; ++i) printf("%d ", fa[i]); 
	puts("");
	for (int i = 1; i <= tot; ++i) printf("%d ", son[i]);
	return 0;
}

H - Hold the Line

胖胖补的，貌似是把大常数双 log 改小常数双 log。链接

**I - Incoming Asteroids

有 \(n\) 个集合，强制在线，支持 \(m\) 个操作：

申请一个新的 ID，初始权值是 \(0\) ，目标值是 \(y_i\) ，将 ID 加入给出的 \(k\ (k\le 3)\) 个集合。

对某个集合中的 ID，令他们的权值增加 \(w_i\) 。报告第一次达到目标的人数。

神奇的暴力。考虑一个需求被分成了 \(k\) 份，如果要被达到，总有一份要达到总量\(/k\) 。

因此在每个插入的集合里都放上一个提醒，如果增量达到了需求，就把所有集合的提醒都撤销，然后重新分 \(k\) 份塞进去。

每次提醒当前剩余的需求最多剩下原来的 \(\frac{k-1}{k}\) ，所以复杂度是 \(\mathcal{O}(m\log_{\frac{k}{k+1}} y_i)\) ，当 \(k=3\) 时可以接受。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define fr     first
#define sc     second
#define mp     make_pair
#define mt     make_tuple
#define pb     push_back
#define pii    pair<int, int>
#define tii    tuple<int, int, int>
#define all(s) (s).begin(), (s).end()

#define N 200007

set<pii> s[N];

vector<pii> a[N];

vector<int> ans, pos;

ll need[N], val[N];

inline void reset(int id) {
	pos.clear();
	for (auto [w, p] : a[id]) {s[p].erase(mp(w, id)); pos.pb(p);}
	a[id].clear(); 

	ll nw = 0;
	for (auto p : pos) nw += val[p];
	if (nw >= need[id]) {ans.pb(id); return;}
	ll w = max(1ull, (need[id] - nw) / pos.size());
	for (auto p : pos) {
		s[p].insert(mp(val[p] + w, id));
		a[id].pb(mp(val[p] + w, p));
	}
}	

int main() {
	int n = rd(), m = rd();
	int id = 0, lst = 0;
	for (int i = 1; i <= m; ++i) {
		int op = rd();
		if (op == 1) {
			need[++id] = rd() ^ lst;
			int k = rd();
			ll w = max(1ll, need[id] / k);
			for (int p; k; --k) {
				need[id] += val[p = rd() ^ lst];
				s[p].insert(mp(val[p] + w, id));
				a[id].pb(mp(val[p] + w, p));
			}
		} else {
			int x = rd() ^ lst;
			val[x] += rd() ^ lst; ans.clear();
			while (!s[x].empty() && val[x] >= s[x].begin() -> fr) reset(s[x].begin() -> sc);
			printf("%d", lst = ans.size());
			sort(all(ans));
			for (auto i : ans) printf(" %d", i);
			puts("");
		}
	}
	return 0;
}

J - Junior Mathematician

胖胖说是数位dp板子题。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=5000,maxk=60,MOD=1e9+7;

int te,K,pw[maxn+5];char L[maxn+5],R[maxn+5];
int n,a[maxn+5],f[maxn+5][maxk+5][maxk+5][2],ans;

inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
void DP(int tp){
	for (int i=0;i<=n;i++)
		for (int j=0;j<K;j++)
			for (int k=0;k<K;k++)
				f[i][j][k][0]=f[i][j][k][1]=0;
	f[0][a[0]%K][(K-a[0]*pw[n]%K)%K][1]++;
	for (int i=0;i<a[0];i++) f[0][i%K][(K-i*pw[n]%K)%K][0]++;
	for (int i=1;i<=n;i++)
		for (int j=0;j<K;j++)
			for (int k=0,F;k<K;k++){
				if (F=f[i-1][j][k][0])
					for (int t=0;t<10;t++){
						int A=(j+t)%K,B=(k+j*t+K-t*pw[n-i]%K)%K;
						f[i][A][B][0]=ADD(f[i][A][B][0],F);
					}
				if (F=f[i-1][j][k][1]){
					for (int t=0;t<a[i];t++){
						int A=(j+t)%K,B=(k+j*t+K-t*pw[n-i]%K)%K;
						f[i][A][B][0]=ADD(f[i][A][B][0],F);
					}
					int A=(j+a[i])%K,B=(k+j*a[i]+K-a[i]*pw[n-i]%K)%K;
					f[i][A][B][1]=ADD(f[i][A][B][1],F);
				}
			}
	for (int i=0;i<K;i++) ans=ADD(ans,MUL(tp,ADD(f[n][i][0][0],f[n][i][0][1])));
}
int main(){
	for (scanf("%d",&te);te;te--){
		scanf("%s%s%d",L,R,&K);n=strlen(R);
		pw[0]=1;for (int i=1;i<=n;i++) pw[i]=(pw[i-1]*10)%K;
		n=strlen(L)-1;for (int i=0;i<=n;i++) a[i]=L[i]-'0';
		reverse(a,a+n+1);a[0]--;
		for (int i=0;i<=n && a[i]<0;i++) a[i]+=10,a[i+1]--;
		while (n>0 && !a[n]) n--;
		reverse(a,a+n+1);
		ans=0;
		DP(MOD-1);
		n=strlen(R)-1;for (int i=0;i<=n;i++) a[i]=R[i]-'0';
		DP(1);
		printf("%d\n",ans);
	}
	return 0;
}

*K - Key Project

有 \(n\ (n\le 800)\) 栋楼排成一列，给出相邻两个楼的距离。

有 \(m\ (m\le 50000)\) 个 A 类人，\(m\) 个 B 类人，每个人有两个参数 \(x,c\) ，代表位于第 \(x\) 栋楼中，聘请的代价是 \(c\) 。

称一对人包括一个 A 类人一个 B 类人，代价是聘请他们的代价和 + 他们之间的距离。

现在要聘请 \(k\) 对人，代价是聘请每一对的代价之和，求最小代价。对 \(k=1\dots m\) 。

对 \(k=1\dots m\) 即每次考虑新增一对，这提示我们考虑费用流。

为每个建筑建一个点，相邻建筑之间连容量无穷，代价为距离的边。

对于每个 A 类人，连 \(S\to x_i\) ，容量为 \(1\) ，代价为 \(c_i\) ；对于 B 类人就和 \(T\) 以同样的方式相连。

问题变成每次增广流量为 \(1\) 的流。直接做 EK 复杂度比较高。

考虑模拟费用流，单次增广复杂度降低到 \(O(n)\) 。

因为每次增广的流量只有 \(1\) ，所以：

每个点只需要考虑它拥有的最小代价的 A 类人和 B 类人。用堆维护。
每条边只需要考虑 \(1\) 流量时的最小代价，优先考虑退流的负代价边即可。

对每个方向求出来代价的前缀和，那么选择一对点的代价可以拆分成两个位置独立的贡献。

然后扫一遍就可以求出来答案了，注意答案有 A 左 B 右、B 左 A 右两种情况。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define rep(i, x, y) for(int i = (x); i <= (y); ++i)
#define per(i, x, y) for(int i = (x); i >= (y); --i)

template<typename T>
inline bool getmin(T &a, T b) {return a > b ? (a = b, true) : false;}
template<typename T>
inline bool getmax(T &a, T b) {return a < b ? (a = b, true) : false;}

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 807
#define inf 1e18

/*
1. lr[i] : the number of backflow unit from i - 1 to i 
   cost for [(i - 1) -> i] = (lr[i] > 0 ? -d[i] : d[i]);
2. rl[i] : the number of backflow unit from i to i - 1
   cost for [i -> (i - 1)] = (rl[i] > 0 ? -d[i] : d[i]);
*/
int d[N], lr[N], rl[N], mnA[N], mnB[N];

ll cstlr[N], cstrl[N];

priority_queue<int, vector<int>, greater<int>> A[N], B[N];

int main() {
    int n = rd(), m = rd();
    rep(i, 2, n) d[i] = rd();
    rep(i, 1, m) {int p = rd(); A[p].push(rd());}
    rep(i, 1, m) {int p = rd(); B[p].push(rd());}
    /*
    cost from l to r : (mnA[L] - cstlr[L]) + (mnB[R] + cstlr[R])
    cost from r to l : (mnB[L] - cstrl[L]) + (mnA[R] + cstrl[R])
    */
    ll ans = 0;
    rep(t, 1, m) {
        rep(i, 1, n) {
            // [mnx[i] = 0] : person of type x dosen't exist
            mnA[i] = (A[i].empty() ? 0 : A[i].top());
            mnB[i] = (B[i].empty() ? 0 : B[i].top());
        } 
        rep(i, 2, n) {
            cstlr[i] = cstlr[i - 1] + (lr[i] ? -d[i] : d[i]);
            cstrl[i] = cstrl[i - 1] + (rl[i] ? -d[i] : d[i]);
        }
        ll cst = inf;
        int pA = 0, pB = 0, Al = 0, Bl = 0;
        rep(i, 1, n) {
            if (mnA[i] && (!Al || mnA[Al] - cstlr[Al] > mnA[i] - cstlr[i])) Al = i;
            if (mnB[i] && (!Bl || mnB[Bl] - cstrl[Bl] > mnB[i] - cstrl[i])) Bl = i;
            if (Al && mnB[i] && getmin(cst, mnA[Al] - cstlr[Al] + mnB[i] + cstlr[i])) {pA = Al; pB = i;}
            if (Bl && mnA[i] && getmin(cst, mnB[Bl] - cstrl[Bl] + mnA[i] + cstrl[i])) {pA = i; pB = Bl;}
        }
        ans += cst; printf("%lld\n", ans);
        A[pA].pop(); B[pB].pop();
        if (pA < pB) rep(i, pA + 1, pB) lr[i] > 0 ? --lr[i] : ++rl[i];
        else rep(i, pB + 1, pA) rl[i] > 0 ? --rl[i] : ++lr[i];
    }
    return 0;
}

Official Contests

Greedy Segment Tree Geometry Tricks Flows Divide and Conquer

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！