div2A
题意：
有$n$幢楼排成一排，每幢楼的高度都是$h$，楼房之间在$[a,b]$层有通道相连，在楼内垂直走1层和通过通道走到相邻的楼房所需时间都是1，给出$k$个询问，问从$t_a$楼的$f_a$层走到$t_b$楼$f_b$层最短时间。
题解：
没什么好讲的。
代码：
#include <bits/stdc++.h>
using namespace std;
int n, h, a, b, k;
int main()
{
scanf("%d%d%d%d%d", &n, &h, &a, &b, &k);
for (int i = 0; i < k; i++)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
if (x1 == x2) printf("%d\n", abs(y1 - y2));
else if (y1 < a) printf("%d\n", a - y1 + abs(x1 - x2) + abs(a - y2));
else if (y1 >= a && y1 <= b) printf("%d\n", abs(x1 - x2) + abs(y1 - y2));
else printf("%d\n", y1 - b + abs(x1 - x2) + abs(b - y2));
}
}
div2B
题意：
给出一个$n$个节点的有向图，每个节点的出度为1。问从每个点开始往后走，第一个访问两次的点是什么。
题解：
写的时候没看清数据范围写了个$O(n)$的还wa了一发。。
因为$n \leq 1000$，所以之间$O(n^2)$模拟就好了。
代码：
#include <bits/stdc++.h>
using namespace std;
int n, p[1010], num = 0, fst[1010], ans[1010];
bool oncir[1010], v[1010], tf[1010];
stack<int> sta;
struct edge
{
int x, y, n;
} e[1010];
void dfs(int x)
{
if (v[x])
{
while (!sta.empty() && sta.top() != x)
{
oncir[sta.top()] = 1;
sta.pop();
}
oncir[x] = 1;
return;
}
if (tf[x]) return;
v[x] = tf[x] = 1;
sta.push(x);
dfs(p[x]);
v[x] = 0;
}
void dfs2(int x, int st)
{
ans[x] = st;
for (int i = fst[x]; i; i = e[i].n)
{
int y = e[i].y;
if (!oncir[y]) dfs2(y, st);
}
}
void ins(int x, int y)
{
e[++num] = {x, y, fst[x]};
fst[x] = num;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &p[i]);
ins(p[i], i);
}
for (int i = 1; i <= n; i++)
if (!v[i])
{
while (!sta.empty()) sta.pop();
dfs(i);
}/*
for (int i = 1; i <= n; i++)
printf("%d ", oncir[i]);
puts("");*/
for (int i = 1; i <= n; i++)
if (oncir[i])
dfs2(i, i);
for (int i = 1; i <= n; i++)
printf("%d ",ans[i]);
puts("");
}
div2C/div1A
题意：
有$m$个政党和$n$个选民，每个选民有个偏爱的党派和收买他所需的花费，问你最少支付多少钱收买选民使得1号政党的选票严格大于其他政党。
题解：
把所有选民按花费排个序，每个政党的选民也分别排序。枚举最终1号党的选票数，然后对于每个选民多于当前枚举的票数的政党，把他们最便宜的那些选民收买使得这个政党的选票少于当前枚举的票数。做完后如果1号政党的票数还不够枚举的就在所有选民里（不包括投1号的）找最便宜的补齐。记录一下答案就好了。
代码：
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long ans = 1LL << 62, sum[3010][3010];
vector<int> a[3010];
struct th
{
int x, i, j;
} b[3010];
int cmp(th x, th y)
{
return x.x < y.x;
}
int main()
{
scanf("%d%d", &m, &n);
for (int i = 0; i < m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
a[x].push_back(y);
}
for (int i = 1; i <= n; i++)
sort(a[i].begin(), a[i].end());
int hh = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j < a[i].size(); j++)
b[hh++] = {a[i][j], i, j};
sort(b, b + m, cmp);
for (int i = 1; i <= n; i++)
for (int j = 0; j < a[i].size(); j++)
sum[i][j] = (j == 0 ? 0 : sum[i][j - 1]) + a[i][j];
for (int i = max(1u, a[1].size()); i <= m; i++)
{
long long s = 0;
int cnt = a[1].size();
for (int j = 2; j <= n; j++)
{
if (a[j].size() >= i) s += sum[j][a[j].size() - i], cnt += a[j].size() - i + 1;
}
for (int j = 0; j < m && cnt < i; j++)
if (b[j].i != 1 && (a[b[j].i].size() < i || a[b[j].i].size() >= i && b[j].j > a[b[j].i].size() - i))
{
s += b[j].x;
cnt++;
}
// printf("%lld\n", s);
ans = min(ans, s);
}
printf("%lld\n", ans);
}
div2D/div1B
题意：
交互题。有一个长度为$n$（$n$为偶数）的环，每个位置有一个整数，并且相邻两个数的差的绝对值严格$=1$。每次你可以询问某个位置的数是几。你的任务是求出一个位置满足他和他对面的数相等。$2 \leq n \leq 100000$，询问数不能超过60个。
题解：
%爆beginend
设$f_i$表示$a_i - a_{i + \frac n 2}$，那么$f_i - f_{i - 1}$的值只可能是-2，0或2。我们可以把$f_x$看成一个连续函数，而$f_1=-f_{1 + \frac n 2}$，我们就可以在$2\log n$的询问内二分出零点。零点就是我们要求的位置。
代码：
#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
scanf("%d", &n);
int l = 1, r = 1 + n / 2;
int ll, rr, hh;
printf("? %d\n", l);
fflush(stdout);
scanf("%d", &ll);
printf("? %d\n", r);
fflush(stdout);
scanf("%d", &rr);
if (ll == rr)
{
puts("! 1");
fflush(stdout);
return 0;
}
ll -= rr;
rr = -ll;
while (l + 1 < r)
{
int md = l + r >> 1;
printf("? %d\n", md);
fflush(stdout);
int hh;
scanf("%d", &hh);
int oo = md + n / 2;
if (oo > n) oo -= n;
printf("? %d\n", oo);
fflush(stdout);
scanf("%d", &oo);
hh -= oo;
if (hh == 0)
{
printf("! %d\n", md);
fflush(stdout);
return 0;
}
else if (hh * ll > 0)
{
l = md;
ll = hh;
}
else
{
r = md;
rr = hh;
}
}
puts("! -1");
fflush(stdout);
}
div2E/div2C
题意：
给出一个$n$个节点$m$条边的有向图，求一个点集$Q$，满足没有一对点$x, y \in Q$直接相连，并且对于集合外的点$z \notin Q$可以从$Q$中的点出发在两步内到达他。
题解：
SAM队都不会做的大难题
考虑如果把一个点及其一步能到的点从原图中删去，假如我们已经知道了新图的点集，那么假如点击内的点与删去的这个点直接相连，那么这个点集也是原图的答案；否则就把那个点加入到点集中。我们可以模拟这个过程，从1到n删点，然后反过来做就好了。
代码：
#include <bits/stdc++.h>
using namespace std;
int n, m, num = 0, fst[1000010];
bool del[1000010], reachable[1000010];
struct edge
{
int x, y, n;
} e[1000010];
stack<int> sta;
vector<int> ans;
void ins(int x, int y)
{
e[++num] = {x, y, fst[x]};
fst[x] = num;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
ins(x, y);
}
for (int i = 1; i <= n; i++)
if (!del[i])
{
sta.push(i);
for (int j = fst[i]; j; j = e[j].n)
{
int y = e[j].y;
del[y] = 1;
}
}
while (!sta.empty())
{
int x = sta.top();
sta.pop();
if (!reachable[x])
{
for (int i = fst[x]; i; i = e[i].n)
{
int y = e[i].y;
reachable[y] = 1;
}
ans.push_back(x);
}
}
printf("%d\n", ans.size());
for (int x : ans) printf("%d ", x);
}
div1D
题意：
平面上有$n$个点，问是否存在三个点使得它们组成的三角形的面积$=S$。保证任意三个点不在一条直线上。
题解：
考虑一条直线平滑地转一圈，一对点到它的距离的大小的相对顺序当且仅当它们两个的角度和直线的角度相等时才会改变。所以我们可以把每对点连成的线段按极角$[0, \pi)$排序，并且把点按纵坐标排序。对于每条线段，我们可以在点集中二分两次，看看能不能构成答案。二分两次的原因是为了处理面积为负的情况。处理完后，交换两个端点在点集中的位置以保证处理后面的线段时点还是有序的。
代码：
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-7;
int n, pos[2010]; // i号节点的位置
long long s;
struct pnt
{
long long x, y;
int id;
pnt(long long x = 0, long long y = 0) : x(x), y(y) {}
} a[2010];
pnt operator-(pnt x, pnt y) {return pnt(x.x - y.x, x.y - y.y);}
long long operator*(pnt x, pnt y) {return x.x * y.y - x.y * y.x;}
struct seg
{
int x, y;
double angle;
} b[4000010];
int cmp1(pnt x, pnt y)
{
return x.y == y.y ? x.x < y.x : x.y < y.y;
}
int cmp2(seg x, seg y)
{
return x.angle < y.angle;
}
int main()
{
scanf("%d%lld", &n, &s);
s *= 2;
for (int i = 0; i < n; i++)
scanf("%lld%lld", &a[i].x, &a[i].y);
sort(a, a + n, cmp1);
int nn = 0;
for (int i = 0; i < n; i++) pos[i] = a[i].id = i;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
b[nn++] = {i, j, atan2(a[j].y - a[i].y, a[j].x - a[i].x)};
}
sort(b, b + nn, cmp2);
for (int i = 0; i < nn; i++)
{
int l = 0, len = n;
pnt x = a[pos[b[i].x]], y = a[pos[b[i].y]];
while (len)
{
int md = l + (len >> 1);
if ((y - x) * (a[md] - x) < s)
{
l = md + 1;
len = len - (len >> 1) - 1;
}
else len >>= 1;
}
if (l < n && (y - x) * (a[l] - x) == s)
{
printf("Yes\n%lld %lld\n%lld %lld\n%lld %lld\n", x.x, x.y, y.x, y.y, a[l].x, a[l].y);
return 0;
}
l = 0, len = n;
while (len)
{
int md = l + (len >> 1);
if ((y - x) * (a[md] - x) < -s)
{
l = md + 1;
len = len - (len >> 1) - 1;
}
else len >>= 1;
}
if (l < n && (y - x) * (a[l] - x) == -s)
{
printf("Yes\n%lld %lld\n%lld %lld\n%lld %lld\n", x.x, x.y, y.x, y.y, a[l].x, a[l].y);
return 0;
}
swap(a[pos[b[i].x]], a[pos[b[i].y]]);
swap(pos[b[i].x], pos[b[i].y]);
}
puts("No");
}
div1E
题意：
给你一颗$n$个节点的树，$i$号边的边权为$a_i \times t + b_i$，问对于每个$t \in [0, m]$，树的直径是多少。
题解：
首先要知道，所有构成答案的点$(a, b)$构成了一个上凸包，而且相邻两个点的连线的斜率$<0$。简单证明一下：首先显然左下角的点一定是劣于右上角的点的，前者的起始位置和增长速率都不及后者；然后考虑三个点$(a_i, b_i),="" (a_j,="" b_j),="" (a_k,="" b_k)$满足$a_i="" <="" a_k="" a_j,="" b_j="" b_k="" b_i,="" \frac{b_k="" -="" b_i}{a_k="" a_i}="" \frac{b_j="" b_i}{a_j="" a_i}$（即$k$在$i$的右下角，$j$在$k$的右下角，$i,k$的斜率小于$j,k$的斜率）。右下角的点之所以能成为答案，是因为它的增长率$a$高于左边的点，在某个时刻可以超过前面的点。而$k$超过$i$的时刻为$x_k="\frac{b_k" b_i}{a_i="" a_k}$，$j$超过$i$的时刻为$x_j="\frac{b_j" b_i}="" {a_i="" a_j}$，由假设可知$x_k=""> x_j$，也就是说$j$比$k$更早超过$i$，而又因为$a_k < a_j$，$k$永远都追不上$j$了，所以$k$是没用的。
知道这个结论后，我们就可以用边分治做了。从当前边往两边深搜，分别维护凸包，然后合并起来，加上这条边的权值。怎么合并呢？我们要求的相当是点集$S = \{ (x, y) | (x,y)=(x_1,y_1) + (x_2, y_2), (x_1, y_1) \in S_1, (x_2, y_2) \in S_2\}$的凸包。这个就是大名鼎鼎的闵可夫斯基和。我们可以把两个集合最左边相加放进新点集中，然后归并地把两个点集中的点按极角放入新点集中。递归下去用求得的子问题答案之间更新凸包就好了。
代码：
#include <bits/stdc++.h>
using namespace std;
int n, m;
struct pnt
{
long long a, b;
pnt() {}
pnt(long long x, long long y) : a(x), b(y) {}
};
pnt operator+(pnt x, pnt y) { return pnt(x.a + y.a, x.b + y.b); }
bool operator<(pnt x, pnt y) { return x.a == y.a ? x.b < y.b : x.a < y.a; }
bool operator==(pnt x, pnt y) { return x.a == y.a && x.b == y.b; }
pnt operator-(pnt x, pnt y) { return pnt(x.a - y.a, x.b - y.b); }
long long operator*(pnt x, pnt y) { return x.a * y.b - x.b * y.a; }
class edges
{
public:
int num = 0, fst[200010];
struct edge
{
int x, y, n;
pnt c;
} e[400010];
void ins(int x, int y, pnt c)
{
e[++num] = {x, y, fst[x], c};
fst[x] = num;
}
} ori;
class graph : public edges
{
int sz[200010];
bool v[200010];
void get_sz(int x, int fa)
{
sz[x] = 1;
for (int i = fst[x]; i; i = e[i].n)
{
int y = e[i].y;
if (v[y] || y == fa) continue;
get_sz(y, x);
sz[x] += sz[y];
}
}
int get_rt(int x, int full, int fa, int from)
{
for (int i = fst[x]; i; i = e[i].n)
{
int y = e[i].y;
if (y != fa && !v[y] && sz[y] >= full / 2) return get_rt(y, full, x, i);
}
return from;
}
void dfs(int x, pnt now, vector<pnt> &s, int fa)
{
bool tf = 0;
for (int i = fst[x]; i; i = e[i].n)
{
int y = e[i].y;
if (!v[y] && y != fa) dfs(y, now + e[i].c, s, x), tf = 1;
}
if (!tf) s.push_back(now);
}
public:
void wk(int x, vector<pnt> &ans)
{
get_sz(x, 0);
if (sz[x] == 1) return;
int hh = get_rt(x, sz[x], 0, 0);
int a = e[hh].x, b = e[hh].y;
// printf("#%d %d\n", a, b);
vector<pnt> s1, s2, h;
dfs(a, pnt(0, 0), h, b);
sort(h.begin(), h.end());/*
for (pnt x : h)
printf("%lld %lld\n", x.a, x.b);
puts("");*/
for (pnt x : h)
{
while (!s1.empty() && s1.back().b <= x.b || s1.size() > 1 && (s1.back() - s1.end()[-2]) * (x - s1.end()[-2]) >= 0)
s1.pop_back();
s1.push_back(x);
}
h.clear();
dfs(b, pnt(0, 0), h, a);
sort(h.begin(), h.end());/*
for (pnt x : h)
printf("%lld %lld\n", x.a, x.b);
puts("");*/
for (pnt x : h)
{
while (!s2.empty() && s2.back().b <= x.b || s2.size() > 1 && (s2.back() - s2.end()[-2]) * (x - s2.end()[-2]) >= 0)
s2.pop_back();
s2.push_back(x);
}
h.clear();
h.push_back(s1[0] + s2[0]);
int i = 1, j = 1;
while (i < s1.size() && j < s2.size())
{
if ((s1[i] - s1[i - 1]) * (s2[j] - s2[j - 1]) <= 0)
h.push_back(h.back() + s1[i] - s1[i - 1]), i++;
else
h.push_back(h.back() + s2[j] - s2[j - 1]), j++;
}
while (i < s1.size()) h.push_back(h.back() + s1[i] - s1[i - 1]), i++;
while (j < s2.size()) h.push_back(h.back() + s2[j] - s2[j - 1]), j++;
for (pnt &x : h)
x = x + e[hh].c;
vector<pnt> ans1, ans2;
v[b] = 1;
wk(a, ans1);
v[b] = 0;
v[a] = 1;
wk(b, ans2);
v[a] = v[b] = 1;/*
printf("#%d %d\n", a, b);
for (pnt x : h)
printf("%lld %lld\n", x.a, x.b);
puts("");
for (pnt x : ans1)
printf("%lld %lld\n", x.a, x.b);
puts("");
for (pnt x : ans2)
printf("%lld %lld\n", x.a, x.b);
puts("");*/
i = 0, j = 0;
int k = 0;
while (i < ans1.size() || j < ans2.size() || k < h.size())
{
pnt x(1LL << 62, 1LL << 62);
if (i < ans1.size() && ans1[i] < x) x = ans1[i];
if (j < ans2.size() && ans2[j] < x) x = ans2[j];
if (k < h.size() && h[k] < x) x = h[k];
if (i < ans1.size() && x == ans1[i]) i++;
else if (j < ans2.size() && x == ans2[j]) j++;
else k++;
while (!ans.empty() && ans.back().b <= x.b || ans.size() > 1 && (ans.back() - ans.end()[-2]) * (x - ans.end()[-2]) >= 0)
ans.pop_back();
ans.push_back(x);
}
}
} bin;
void build_bin(int x, int fa)
{
int last = x;
for (int i = ori.fst[x]; i; i = ori.e[i].n)
{
int y = ori.e[i].y;
if (y == fa) continue;
build_bin(y, x);
bin.ins(last, ++n, pnt(0, 0));
bin.ins(n, last, pnt(0, 0));
last = n;
bin.ins(n, y, ori.e[i].c);
bin.ins(y, n, ori.e[i].c);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i < n; i++)
{
int x, y, a, b;
scanf("%d%d%d%d", &x, &y, &a, &b);
ori.ins(x, y, pnt(a, b));
ori.ins(y, x, pnt(a, b));
}
build_bin(1, 0);/*
puts("");
for (int i = 1; i <= bin.num; i += 2)
printf("%d %d %lld %lld\n", bin.e[i].x, bin.e[i].y, bin.e[i].c.a, bin.e[i].c.b);*/
vector<pnt> ans;
bin.wk(1, ans);
long long now = 0;/*
puts("======");
for (pnt x : ans)
printf("%lld %lld\n", x.a, x.b);*/
if (ans.empty())
{
for (int i = 0; i < m; i++) printf("0 ");
puts("");
return 0;
}
for (int i = 0, j = 1; i < m; i++)
{
now = ans[j - 1].a * i + ans[j - 1].b;
while (j < ans.size() && i * ans[j].a + ans[j].b > now) now = i * ans[j].a + ans[j].b, j++;
printf("%lld ", now);
}
puts("");
}