思博题，没什么好讲的。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
ll n;
scanf("%lld", &n), printf("%lld %lld\n", -n + 1, n);
}
return 0;
}
Continue reading → 斜率优化其实不是很难，可以理解为在平面上的一些点作为决策点，而你现在有一条斜率为 \(k\) 的直线，你需要使其经过一个合适的点，使得这条线的截距最大/最小化。这个显然可以使这些点组成一个上/下凸包、然后二分找到斜率相近的那条线段进行转移。
Continue reading →啊，又是无根树 DP。首先讨论奇偶性，如果是奇数的话可以直接 DP；如果不是，则需要容斥一波。
设置状态 \(dp[scale][maxPart][degree]\)，意为大小为 \(scale\)、最大子树大小为 \(maxPart\) 且根度数为 \(degree\) 的方案树。转移其实很好想，看代码吧。
Continue reading →我操这个题是真的有意思（做完后索然无味）。
肯定这个题状压 DP 没跑的，所以可以先设 \(f[S]\) 为集合 \(S\) 双连通的最小代价。直接做有点困难，我们需要思考一个归纳的方式来构造一个双连通图。
Continue reading →思博题，考虑两端和奇偶性即可。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n, A, B, ans = 0x7fffffffffffffff;
scanf("%lld%lld%lld", &n, &A, &B);
ans = min(A - 1, n - B) + 1 + ((B - A - 1) >> 1);
if (!((A^B) & 1))
ans = min(ans, (B - A) >> 1);
printf("%lld\n", ans);
return 0;
}
Continue reading →