某岛

Original link: https://www.shuizilong.com/house/archives/luogu-p2053-scoi2007-%E4%BF%AE%E8%BD%A6/ https://www.luogu.com.cn/problem/P2053 It seems that dp is possible, but the cost of repairing each car is not the same for each person. So it can be modeled as a bipartite graph. #include <lastweapon/io> #include <lastweapon/mincostflow> using namespace lastweapon; int main() { #ifndef ONLINE_JUDGE freopen(“in.txt”, “r”, stdin); //freopen(“out.txt”, “w”, stdout); #endif int m, n; …

Luogu P2053. [SCOI2007] Car Repair Read More »

Original link: https://www.shuizilong.com/house/archives/luogu-p1973-noi2011-noi-%E5%98%89%E5%B9%B4%E5%8D%8E/ https://www.luogu.com.cn/problem/P1973 O(n4) Violence can be written well. . . . #include <lastweapon/io> using namespace lastweapon; const int N = 200 + 1, PN = N*2 + 1; VI P; int L[N], R[N], s[PN][PN]; int pre[PN][N], suf[PN][N]; // one side is j, the other side is at most int f[PN][PN]; int n, pn; …

Luogu P1973. [NOI2011] NOI Carnival Read More »

Original link: https://www.shuizilong.com/house/archives/luogu-p1971-noi2011-%E5%85%94%E5%85%94%E4%B8%8E%E8%9B%8B%E8% 9B%8B%E6%B8%B8%E6%88%8F/ https://www.luogu.com.cn/problem/P1971 https://vjudge.net/problem/HDU-3446 This article is reproduced from: https://www.shuizilong.com/house/archives/luogu-p1971-noi2011-%E5%85%94%E5%85%94%E4%B8%8E%E8%9B%8B%E8% 9B%8B%E6%B8%B8%E6%88%8F/ This site is only for collection, and the copyright belongs to the original author.

Original link: https://www.shuizilong.com/house/archives/luogu-p2048-noi2010-%E8%B6%85%E7%BA%A7%E9%92%A2%E7%90%B4/ https://darkbzoj.cc/problem/2006 https://www.luogu.com.cn/problem/P2048 You can first write a violent RMQ to solve the 10-point code of K=1, to ensure that you have not read the wrong question and understood it as a string problem. Then top K can use a method similar to the ugly number Humble Numbers in [USACO3.1] to open a …

Luogu P2048. [NOI2010] Super Piano Read More »

Original link: https://www.shuizilong.com/house/archives/luogu-p2046-noi2010-%E6%B5%B7%E6%8B%94/ https://www.luogu.com.cn/problem/P2046 Simple planar graph minimum cut, the difficulty is to prove that this is the minimum cut. The main focus of the code is one-handed symmetry. = = #include <lastweapon/io> #include <lastweapon/dijkstra> using namespace lastweapon; int n, s, t; int id(int x, int y) { if (x == -1 || y == …

Luogu P2046. [NOI2010] Altitude Read More »

Original link: https://www.shuizilong.com/house/archives/luogu-p3227-hnoi2013%E5%88%87%E7%B3%95/ https://www.luogu.com.cn/problem/P3227 Simple minimum cut~ #include <lastweapon/io> #include <lastweapon/maxflow> using namespace lastweapon; int P, Q, R, D, s, t; int id(int p, int q, int r) { return r*P*Q + p*Q + q; } bool inGrid(int p, int q) { return 0 <= p && p < P && 0 <= q && …

Luogu P3227. [HNOI2013] Cut Cake Read More »

Original link: https://www.shuizilong.com/house/archives/luogu-p8500-noi2022-%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F/ https://uoj.ac/problem/768 https://www.luogu.com.cn/problem/P8500 Intersections of intervals are of course troublesome. . A few days ago when I was in CF #875 C, I was able to use the hash method to get away with it. . It will definitely not work this time. . Let’s deal with this situation at the end first, …

Luogu P8500. [NOI2022] Bubble sort Read More »

Original link: https://www.shuizilong.com/house/archives/luogu-p3629-apio2010-%E5%B7%A1%E9%80%BB/ https://www.luogu.com.cn/problem/P3629 The advanced method of finding the diameter twice seems to be rotten. . Here is a more conventional dp replacement. . The method is that Two Paths can consider one more situation~~ #include <lastweapon/io> using namespace lastweapon; const int N = int(3e5) + 9; int dn[N], up[N]; // Inner diameter of …

Luogu P3629. [APIO2010] Patrol Read More »

Original link: https://www.shuizilong.com/house/archives/saco-2018-february-contest-gold-problem-2-directory-traversal/ Basically Tree Distances II, The transfer function is adjusted slightly. #include <lastweapon/io> using namespace lastweapon; const int N = int(2e5) + 9; int n, m, h[N], c[N], l[N]; LL f[N], g[N]; VVI v; void dfs1(int r, int p = -1) { for(int& a : v[r]) if (a != p) { dfs1(a, r); …

SACO 2018 February Contest, Gold Problem 2. Directory Traversal Read More »

Original link: https://www.shuizilong.com/house/archives/luogu-p3647-apio2014-%E8%BF%9E%E7%8F%A0%E7%BA%BF/ https://www.luogu.com.cn/problem/P3647 https://oj.uz/problem/view/APIO14_beads The unrooted tree is not in a good design state. Find a way to convert it into a rooted tree, and then replace Dafa with a subtree. Then run and change the root dp. I love macros forever. #include <lastweapon/io> using namespace lastweapon; const int N = int(2e5) + 9; …

Luogu P3647. [APIO2014] Lianzhuxian Read More »

Original link: https://www.shuizilong.com/house/archives/izho-2017-problem-f-hard-route/ https://oj.uz/problem/view/IZhO17_road It is very easy to write if the number of solutions is not considered. Similar to the previous question, we only need to maintain the downward top3 and upward top1. Then use the mean inequality to get the optimal solution must be a*(b+c) | a >= b >= c. #include <lastweapon/io> …

IZhO 2017. Problem F. Hard route Read More »

Original link: https://www.shuizilong.com/house/archives/spoj-twopaths-two-paths/ https://www.spoj.com/problems/TWOPATHS/ https://codeforces.com/problemset/problem/14/D Question: Find the maximum value of the product of two disjoint paths. Analysis: The dfs order maintains diameter has a very nice property. . . That is, you can find the diameter inside the subtree and the diameter outside the subtree. . So we only need to do dfs again, …

SPOJ TWOPATHS. Two Paths Read More »

Original link: https://www.shuizilong.com/house/archives/luogu-p5828-%E8%BE%B9%E5%8F%8C%E8%BF%9E%E9%80%9A%E5%9B% BE%E8%AE%A1%E6%95%B0/ https://www.luogu.com.cn/problem/P5828 Almost the same as the previous question , double experience! #include <lastweapon/poly> using namespace lastweapon; Poly H, HH; int n; LL C2(LL n) { return n*(n-1)/2; } int b(int n) { Poly A(n); REP(i, n) A[i] = H[i] * -n; Poly B = HH.mod(n) * A.exp(); return (B[n-1] * fac[n-1] …

Luogu P5828 edge biconnected graph counting Read More »