T1圆圈游戏
暴力DP有60分，设包含圆i的最小的圆是fa[i]，那没最终会的得到一棵树，对于一棵子树，选了根节点就不能选子树内其它点，f[i]=max(w[i],\(\sum f[son]\)).
瓶颈就在怎么建图，因为圆不相交相切，所以扫描线的时候相对位置不会发生改变，用set维护一下就好啦。

#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<cstdio>
#include<set>
using namespace std;
int n, ans, tmp, lx;
const int N = 200010;
int f[N], fa[N];
struct yuan 
{
	int x, y, r, w;
	double h(int dir) {return y + dir * sqrt(1.0 * r * r - (1.0 * lx - x) * (lx - x));}
} y[N];
struct hu 
{
	int dir, id;
	friend bool operator <(const hu &a, const hu &b)
	{return a.id == b.id ? a.dir < b.dir : (y[a.id].h(a.dir) < y[b.id].h(b.dir));}
} b[N];
inline int read() 
{
	int res = 0; char ch = getchar(); bool XX = false;
	for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
	for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
	return XX ? -res : res;
}
int my(hu a, hu b) {return y[a.id].x - a.dir * y[a.id].r < y[b.id].x - a.dir * y[b.id].r;}
set<hu>s;
set<hu>::iterator it;
signed main() 
{
	cin >> n;
	for (int i = 1; i <= n; ++i) 
	{
		y[i].x = read(); y[i].y = read(); y[i].r = read(); y[i].w = read();
		b[++tmp] = (hu) {1, i}, b[++tmp] = (hu) { -1, i};
	}
	sort(b + 1, b + 1 + tmp, my);
	for (int i = 1; i <= tmp; ++i) 
	{
		int id = b[i].id, dir = b[i].dir;
		lx = y[id].x - dir * y[id].r;
		if (dir == 1) 
		{
			if (!s.empty()) 
			{
				it = s.upper_bound(b[i]);
				if (it != s.end())
					fa[id] = (it->dir == 1) ? it->id : fa[it->id];
			}
			s.insert((hu) {1, id}); s.insert((hu) { -1, id});
		} else 
		{
			s.erase((hu) {1, id}); s.erase((hu) { -1, id});
			f[fa[id]] += max(f[id], y[id].w);
		}
	}
	cout << f[0];
	return 0;
}

T2划分序列
很明显的二分答案，关键就在于check。
设f1[i]表示在i处划分一下，在满足mid的条件下最少划分次数，f2[i]表示最多的划分次数，若\(f1[n] \le k \le f2[n]\)则mid合法。
暴力dp是\(O(n^2)\)的，发现更新f1,f2的是区间最大/最小值，用树状数组维护一下就可以了。

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
int n, k, ans, tot;
const int N = 100010, inf = 1 << 30;
int a[N], f1[N], f2[N], tr1[N], tr2[N], b[N], t1[N], t2[N];
inline int read() 
{
	int res = 0; char ch = getchar(); bool XX = false;
	for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
	for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
	return XX ? -res : res;
}
inline int lowbit(int x) {return x & (-x);}
void change1(int pos, int val) 
{
	for (; pos; pos -= lowbit(pos))tr1[pos] = min(tr1[pos], val);
}
int ask1(int pos) 
{
	int res = inf;
	for (; pos <= tot; pos += lowbit(pos))res = min(res, tr1[pos]);
	return res;
}
void change2(int pos, int val) 
{
	for (; pos; pos -= lowbit(pos))tr2[pos] = max(tr2[pos], val);
}
int ask2(int pos) 
{
	int res = -inf;
	for (; pos <= tot; pos += lowbit(pos))res = max(res, tr2[pos]);
	return res;
}
int check2(int mid) 
{
	tot = 0;
	for (int i = 0; i <= n; ++i) 
	{
		b[++tot] = a[i];
		b[++tot] = a[i] - mid;
	}
	sort(b + 1, b + 1 + tot);
	tot = unique(b + 1, b + 1 + tot) - b - 1;
	for (int i = 0; i <= n; ++i) 
	{
		t1[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;
		t2[i] = lower_bound(b + 1, b + 1 + tot, a[i] - mid) - b;
	}
	for (int i = 1; i <= tot; ++i)tr1[i] = inf, tr2[i] = -inf;
	change1(t1[0], 0); change2(t1[0], 0);
	for (int i = 1; i <= n; ++i) 
	{
		f1[i] = ask1(t2[i]) + 1; f2[i] = ask2(t2[i]) + 1;
		change1(t1[i], f1[i]); change2(t1[i], f2[i]);
	}
	return f1[n] <= k && k <= f2[n];
}
void solve2() 
{
	int l = 0, r = 0;
	for (int i = 1; i <= n; ++i)
		if (a[i] < 0)l += a[i];
		else r += a[i];
	for (int i = 1; i <= n; ++i)a[i] += a[i - 1];
	while (l <= r) 
	{
		int mid = (l + r) / 2;
		if (check2(mid))ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	cout << ans;
}
int main() 
{
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)a[i] = read();
	solve2();
	return 0;
}

T3生成树求和
由于加法不进位，所以每一位我们单独考虑。
用矩阵树定理求的是\(\sum\)所有生成树边权的积,而这里我们需要求的是边权和，所以三次单位根的乘法来完成加法。
最后还要求解一下三元一次方程，可以选择高斯消元，也可以像我一样手动消元。

#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
#define LL long long
using namespace std;
int n, m, ans;
const LL N = 105, mod = 1e9 + 7, inv2 = (mod + 1) >> 1, inv3 = (mod + 1) / 3, sqrt3 = 82062379;
int fr[N * N], to[N * N], val[N * N], bin[20];
inline int read() 
{
	int res = 0; char ch = getchar(); bool XX = false;
	for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
	for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
	return XX ? -res : res;
}
LL ksm(LL a, LL b, LL mod) 
{
	LL res = 1;
	for (; b; b >>= 1, a = a * a % mod)
		if (b & 1)res = res * a % mod;
	return res;
}
struct xu 
{
	LL a, b;
	xu(int _a = 0, int _b = 0) {a = _a, b = _b;}
	friend xu operator +(const xu &x, const xu &y)
	{return (xu) {(x.a + y.a) % mod, (x.b + y.b) % mod};}
	friend xu operator -(const xu &x, const xu &y)
	{return (xu) {(x.a - y.a + mod) % mod, (x.b - y.b + mod) % mod};}
	friend xu operator *(const xu &x, const xu &y)
	{return (xu) {(x.a * y.a % mod - x.b * y.b % mod + mod) % mod, (x.a * y.b + x.b * y.a) % mod};}
	friend xu operator *(const xu &x, const int &y)
	{return (xu) {(x.a * y) % mod, (x.b * y) % mod};}
	friend xu operator /(const xu &x, const int &y) 
	{
		int inv = ksm(y, mod - 2, mod);
		return (xu) {(x.a * inv) % mod, (x.b * inv) % mod};
	}
	friend xu operator /(const xu &x, const xu &y) 
	{
		return x * (xu) {y.a, mod - y.b} / ((y.a * y.a % mod + y.b * y.b % mod) % mod);
	}
} w[3], invw[3], a[N][N], coef[3], inv;
xu work() 
{
	xu res = xu(1, 0);
	for (int i = 1; i < n; ++i) 
	{
		for (int j = i; j < n; ++j)
			if (a[j][i].a || a[j][i].b) 
			{
				if (i == j)break;
				swap(a[i], a[j]); res = res * (mod - 1);
				break;
			}
		for (int j = i + 1; j < n; ++j) 
		{
			inv = a[j][i] / a[i][i];
			for (int k = i; k < n; ++k)a[j][k] = a[j][k] - inv * a[i][k];
		}
		res = res * a[i][i];
	}
	return res;
}
void solve(xu *p) 
{
	xu tmp[3];
	tmp[0] = p[0]; tmp[1] = p[1]; tmp[2] = p[2];
	p[0] = tmp[0] + tmp[1] + tmp[2];
	p[1] = tmp[0] + tmp[1] * invw[1] + tmp[2] * invw[2];
	p[2] = tmp[0] + tmp[1] * invw[2] + tmp[2] * invw[1];
	for (int i = 0; i <= 2; ++i)p[i] = p[i] * inv3;
}
LL suan(int p) 
{
	int k;
	xu w0, w1, w2, c;
	for (int i = 0; i <= 2; ++i) 
	{
		memset(a, 0, sizeof(a));
		w0 = xu(1, 0); w1 = w[i]; w2 = w[(i + i) % 3];
		for (int j = 1; j <= m; ++j) 
		{
			k = val[j] / bin[p] % 3;
			c = (k == 1 ? w1 : (k == 2 ? w2 : w0));
			a[fr[j]][fr[j]] = a[fr[j]][fr[j]] + c;
			a[to[j]][to[j]] = a[to[j]][to[j]] + c;
			a[fr[j]][to[j]] = a[fr[j]][to[j]] - c;
			a[to[j]][fr[j]] = a[to[j]][fr[j]] - c;
		}
		coef[i] = work();
	}
	solve(coef);
	return ((coef[1].a + coef[2].a + coef[2].a) % mod) * bin[p] % mod;
}
signed main() 
{
	freopen("sum.in", "r", stdin);
	freopen("sum.out", "w", stdout);
	cin >> n >> m;
	w[0] = xu(1, 0); w[1] = xu(mod - inv2, sqrt3 * inv2 % mod);
	w[2] = xu(mod - inv2, mod - sqrt3 * inv2 % mod);
	invw[0] = xu(1, 0) / w[0]; invw[1] = xu(1, 0) / w[1]; invw[2] = xu(1, 0) / w[2];
	for (int i = 1; i <= m; ++i)fr[i] = read(), to[i] = read(), val[i] = read();
	bin[0] = 1;
	for (int i = 1; i <= 10; ++i)bin[i] = bin[i - 1] * 3;
	for (int i = 0; i <= 10; ++i)(ans += suan(i)) %= mod;
	cout << ans;
	return 0;
}