本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2020-07-19 16:49:15

该重载的运算符都重载了，赋值、强制类型转换都没问题。输入输出可以直接用 cin,cout。

自带压位优化。

唯一的区别是，没有取模运算，除法会返回 pair<结果,余数>。

class Int {
public:
	using ll = long long;
	Int() {};
	Int(const string& s);
	Int(ll a) :Int(to_string(a)) {}
	Int(const Int& bInt) :nums(bInt.nums), isPositive(bInt.isPositive), length(bInt.length) {}
	Int(Int&& bInt) noexcept :nums(move(bInt.nums)), isPositive(bInt.isPositive), length(bInt.length) {}
	Int(const vector<int>& vec, bool sign = true) :nums(vec), isPositive(sign) { cutLeadZero(); }
	friend istream& operator >>(istream& is, Int& bInt) {
		string s;
		is >> s;
		bInt = move(Int(s));
		return is;
	}
	friend ostream& operator <<(ostream& os, const Int& bInt);
	operator string() const;
	const Int& operator +() const { return *this; }
	Int operator -() const {
		Int tmp(*this);
		if (!tmp.isZero())
			tmp.isPositive = !isPositive;
		return tmp;
	}
	bool operator <(const Int& bInt) const;
	bool operator <=(const Int& bInt) const;
	bool operator ==(const Int& bInt) const;
	Int operator +(const Int& bInt) const;
	Int operator -(const Int& bInt) const;
	Int operator *(const Int& bInt) const;
	\/\/ 除法会返回 商和余数
	pair<Int, Int> operator \/(const Int& bInt) const;
	int operator[](int idx) const { return nums[idx]; }
	Int& operator =(const Int& bInt) {
		if (bInt == *this)
			return *this;
		nums = bInt.nums;
		isPositive = bInt.isPositive;
		length = bInt.length;
		return *this;
	}
	Int& operator =(Int&& bInt)noexcept {
		nums = move(bInt.nums);
		isPositive = bInt.isPositive;
		length = bInt.length;
		return *this;
	}
	size_t size() const { return nums.size(); }
	void cutLeadZero();
	bool isZero() const;
	Int absValue() const {
		return move(Int(nums));
	}
	static Int e(size_t n) {
		if (n <= 0)
			return move(Int(vector<int>(1, 1)));
		int m = n \/ digit;
		n -= m * digit;
		vector<int> ans(m);
		string s = "1";
		s += move(string(n, '0'));
		ans.push_back(stoi(s));
		return move(Int(ans));
	}
private:
	\/\/ 低位到高位
	vector<int> nums;
	bool isPositive = 1;
	int length = 0;
	static int digit;
	static int mod;
};
int Int::digit = 8;
int Int::mod = 100000000;
Int::Int(const string& s) {
	int n = s.size(), minIdx = 0;
	if(s[0]=='-')
		isPositive = false, minIdx = 1;
	else if(s[0]=='+')
		isPositive = true, minIdx = 1;
	for (int i = n - 1; i >= minIdx; i -= digit) {
		int beg = max(minIdx, i - digit + 1);
		nums.push_back(stoi(s.substr(beg, i - beg + 1)));
	}
	cutLeadZero();
}
ostream& operator <<(ostream& os, const Int& bInt) {
	os << (string)bInt;
	return os;
}
Int::operator string() const {
	string ans;
	if (!isPositive)
		ans += "-";
	int n = nums.size();
	for (int i = n - 1; i >= 0; i--) {
		string s = to_string(nums[i]);
		if (i != n - 1)
			ans += string(digit - s.size(), '0');
		ans += s;
	}
	return ans;
}
bool Int::operator<(const Int& bInt) const {
	if (isPositive && !bInt.isPositive)
		return false;
	if (!isPositive && bInt.isPositive)
		return true;
	bool flag = true;
	if (!isPositive)
		flag = false;
	if (length < bInt.length)
		return flag;
	else if (length > bInt.length)
		return !flag;
	int n = size();
	for (int i = n - 1; i >= 0; i--) {
		if (nums[i] < bInt[i])
			return flag;
		else if (nums[i] > bInt[i])
			return !flag;
	}
	return false;
}
bool Int::operator<=(const Int& bInt) const {
	if (isPositive && !bInt.isPositive)
		return false;
	if (!isPositive && bInt.isPositive)
		return true;
	bool flag = true;
	if (!isPositive)
		flag = false; \/\/ 都为负数
	if (length < bInt.length)
		return flag;
	else if (length > bInt.length)
		return !flag;
	int n = size();
	for (int i = n - 1; i >= 0; i--) {
		if (nums[i] < bInt[i])
			return flag;
		else if (nums[i] > bInt[i])
			return !flag;
	}
	return true;
}
bool Int::operator==(const Int& bInt) const {
	if (length != bInt.length)
		return false;
	int n = size();
	for (int i = 0; i < n; i++)
		if (nums[i] != bInt[i])
			return false;
	return true;
}
Int Int::operator+(const Int& bInt) const {
	if (!bInt.isPositive)
		return *this - (-bInt);
	if (!isPositive)
		return bInt - (-*this);
	vector<int> ans;
	int n = size(), m = bInt.size(), sum = 0, i = 0, j = 0;
	while (i < n || j < m || sum)
	{
		if (i < n)
			sum += nums[i++];
		if (j < m)
			sum += bInt[j++];
		ans.push_back(sum % mod);
		sum \/= mod;
	}
	return move(Int(ans, isPositive));
}
Int Int::operator-(const Int& bInt) const
{
	if (!bInt.isPositive)
		return *this + (-bInt);
	if (!isPositive)
		return -((-*this) + bInt);
	if (*this < bInt)
		return -(bInt - *this);
	vector<int> ans;
	int i = 0, j = 0, n = size(), m = bInt.size(), sum = 0;
	while (i < n || j < m || sum) {
		if (i < n)
			sum += nums[i++];
		if (j < m)
			sum -= bInt[j++];
		int flag = 0;
		if (sum < 0) {
			flag = -1;
			sum += mod;
		}
		ans.push_back(sum);
		sum = flag;
	}
	return move(Int(ans));
}
Int Int::operator*(const Int& bInt) const {
	int n = size(), m = bInt.size();
	vector<int> ans(n + m);
	using ll = long long;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			ll tmp = ans[i + j] + nums[i] * 1ll * bInt[j];
			ans[i + j] = tmp % mod;
			ans[i + j + 1] += tmp \/ mod;
		}
	}
	return move(Int(ans, isPositive == bInt.isPositive));
}
pair<Int, Int> Int::operator\/(const Int& bInt) const {
	Int a = absValue();
	Int b = bInt.absValue();
	if (b.isZero())
		return pair<Int, Int>(*this, move(b));
	if (a < b)
		return pair<Int, Int>(move(Int(0)), *this);
	int len = a.length - b.length + 1;
	string ans;
	if (isPositive != bInt.isPositive)
		ans = "-";
	for (int i = 0; i < len; i++) {
		Int tmp = e(len - i - 1) * b;
		int times = 0;
		while (tmp <= a) {
			a = a - tmp;
			++times;
		}
		ans += times + '0';
	}
	a.isPositive = isPositive;
	return pair<Int, Int>(move(Int(ans)), move(a));
}
void Int::cutLeadZero() {
	while(nums.size() > 1 && nums.back() == 0)
		nums.pop_back();
	if(nums.empty()) length = 0;
	else length = (nums.size() - 1) * digit + to_string(nums.back()).size();
}
bool Int::isZero() const {
	return nums.size() == 1 && nums.back() == 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-01-17 10:28:45

更好的阅读体验

心路历程

一开始看了看题面就自闭了很久（带权树的重心？）

后来惊奇地发现数据范围只有100?!!

那还想什么？暴力啊！！！

解法

对于每一个点，都有一个权值、父节点、左儿子和右儿子（没有的是0）

于是就有：

struct node
{
    int w,fa,l,r;
}a[110];

然后思路是：

对于每一个节点，跑一遍DFS，求出距离和，然后取最小值。

于是：

int main()
{
    \/\/输入
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].w>>a[i].l>>a[i].r;
        a[a[i].l].fa=i,a[a[i].r].fa=i;
    }
    \/\/求最小值
    \/\/dfs( now（当前节点）, last（上一个节点), dis（当前距离）)
    int minn=2147483647;
    for(int i=1;i<=n;i++)
        minn=min(minn,dfs(i,0,0));
    \/\/输出
    cout<<minn<<endl;
    \/\/完结撒花！！！
    return 0;
}

dfs:

int dfs(int now,int last,int dis)
{
    \/\/特判
    if(now==0)
        return 0;
    \/\/加入自身
    int ans=dis*a[now].w;
    \/\/if避免出现死循环
    if(a[now].fa!=last)
        ans+=dfs(a[now].fa,now,dis+1);
    if(a[now].l!=last)
        ans+=dfs(a[now].l,now,dis+1);
    if(a[now].r!=last)
        ans+=dfs(a[now].r,now,dis+1);
    \/\/返回
    return ans;
}

完整代码 （知道你们就是来看这个的）：

#include<iostream>
using namespace std;
struct node
{
    int w,fa,l,r;
}a[110];
int dfs(int now,int last,int dis)
{
    if(now==0)
        return 0;
    int ans=dis*a[now].w;
    if(a[now].fa!=last)
        ans+=dfs(a[now].fa,now,dis+1);
    if(a[now].l!=last)
        ans+=dfs(a[now].l,now,dis+1);
    if(a[now].r!=last)
        ans+=dfs(a[now].r,now,dis+1);
    return ans;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].w>>a[i].l>>a[i].r;
        a[a[i].l].fa=i,a[a[i].r].fa=i;
    }
    int minn=2147483647;
    for(int i=1;i<=n;i++)
        minn=min(minn,dfs(i,0,0));
    cout<<minn<<endl;
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-05-10 13:04:12

更好的阅读体验

温馨提示1：本文推式子比较多，建议跟着文章自己推一推。

温馨提示2：本文小字比较多，如果分辨率不够可以放大网页。

0. 扩展欧几里得是什么

扩展欧几里得（exgcd）是一个可以用来求$ax+by=c$（$c\mod \gcd(a,b)=0$，否则无解）的解的算法

怎么求$ax+by=c (c\mod \gcd(a,b)=0)$的解呢？

1. $ax+by=\gcd(a,b)$

怎么求$ax+by=\gcd(a,b)$的解呢？

首先，如果$b=0$的话，$\gcd(a,b)=a$，则解为$\begin{cases}x=1 \\ y=0\end{cases}$

设此方程的解为$\begin{cases}x=x_0 \\ y=y_0\end{cases}$

那么我们需要做的就是将$ax_0+by_0=\gcd(a,b)$转化为$b=0$的格式，这就要用到辗转相除法了。

设另一个方程：$bx_1+(a\mod b)y_1=\gcd(b,a\mod b)$

设$a_1=b,b_1=a\mod b$

则该方程转化为$a_1x_1+b_1y_1=\gcd(a_1,b_1)$

我们会发现它和原方程的格式是一样的，而且根据欧几里得原理，它可以一直递推到$a_nx_n+b_ny_n=\gcd(a_n,b_n)$使得$b_n=0$，就可以求得解$\begin{cases}x_n=1 \\ y_n=0\end{cases}$

那假设我们已经求得了该结果，那如何推导出$x_0$和$y_0$呢？

我们首先研究如何从$x_1$和$y_1$推导出$x_0$和$y_0$，其他的就同理了

因为

$\begin{cases}bx_1+(a\mod b)y_1=\gcd(b,a\mod b) \\ ax_0+by_0=\gcd(a,b)\end{cases}$

且根据欧几里得定理，$\gcd(a,b)=\gcd(b,a\mod b)$

所以

$ax_0+by_0=bx_1+(a\mod b)y_1$

且$a\mod b=a-\lfloor\frac{a}{b}\rfloor b$（好好体会一下）

所以

$ax_0+by_0=bx_1+(a-\lfloor\frac{a}{b}\rfloor b)y_1$

$ax_0+by_0=bx_1+ay_1-\lfloor\frac{a}{b}\rfloor b y_1$

$ax_0+by_0=b(x1-\lfloor\frac{a}{b}\rfloor y_1)+ay_1$

$ax_0+by_0=ay_1+b(x_1-\lfloor\frac{a}{b}\rfloor y_1)$

即$\begin{cases}x_0=y_1 \\ y_0=x_1-\lfloor\frac{a}{b}\rfloor y_1\end{cases}$

这样，我们就由$x_1$和$y_1$推导出了$x_0$和$y_0$，其他同理

于是乎：

struct node
{
	int x,y;
};
node exgcd(int a,int b)
{
	if(b==0)
	{
		node tmp;
		tmp.x=1,tmp.y=0;
		return tmp;
	}
	node tmp=exgcd(b,a%b);\/\/递归求出x_(k+1)和y_(k+1)
	node ans;
	ans.x=tmp.y,ans.y=(tmp.x)-a\/b*(tmp.y);\/\/推导出x_k和y_k
	return ans;
}

这样，我们就求出了$ax+by=\gcd(a,b)$的一组解

2. $ax+by=c$的一组解$\begin{cases}x=x_{tmp}\\y=y_{tmp}\end{cases}$

我们已经求出了$ax+by=\gcd(a,b)$的一组解$\begin{cases}x=x_0 \\ y=y_0\end{cases}$

那么我们就可以知道$akx_0+bky_0=k\gcd(a,b)$

又因为要求$c$是$\gcd(a,b)$的倍数（否则无解）

所以$k=\frac{c}{\gcd(a,b)}$

所以很简单：

$\begin{cases}x_{tmp}=kx_0=\frac{c}{\gcd(a,b)}x_0 \\ y_{tmp}=ky_0=\frac{c}{\gcd(a,b)}y_0\end{cases}$

3.$ax+by=c$的所有解$\begin{cases}x=x_{ans}\\y=y_{ans}\end{cases}$

我们已经求出了$ax+by=c$的一组解$\begin{cases}x=x_{tmp} \\ y=y_{tmp}\end{cases}$

即$ax_{tmp}+by_{tmp}=c$

将它加上再减去$\frac{ab}{\gcd(a,b)}$，得到

$ax_{tmp}+\frac{ab}{\gcd(a,b)}+by_{tmp}-\frac{ab}{\gcd(a,b)}=c$

$a(x_{tmp}+\frac{b}{\gcd(a,b)})+b(y_{tmp}-\frac{a}{\gcd(a,b)})=c$

在$x_{tmp}$上减，在$y_{tmp}$上加也同理

所以$\begin{cases}x=x_{tmp}\pm\frac{b}{\gcd(a,b)} \\ y=y_{tmp}\mp\frac{a}{\gcd(a,b)}\end{cases}$也是一组解

这个变换进行多次，即可得到

$\begin{cases}x_{ans}=x_{tmp}+t\times\frac{b}{\gcd(a,b)} \\ y_{ans}=y_{tmp}-t\times\frac{a}{\gcd(a,b)}\end{cases}$（$t$的正负可以代替加和减的分类讨论）

4. $x$和$y$各自的最小正整数解

以$x$的最小正整数解为例：

求出任意一组解$\begin{cases}x=x_{tmp} \\ y=y_{tmp}\end{cases}$

因为将$x_{tmp}$加或减$\frac{b}{\gcd(a,b)}$也成立，所以可设$d=\frac{b}{\gcd(a,b)}$（注意这里分子是$b$）

$x_{min}=(x_{tmp}\mod d+d)\mod d$（因为$x_{tmp}$有可能是负数）

同理对于$y$，设$d=\frac{a}{\gcd(a,b)}$（注意这里分子是$a$）

$y_{min}=(y_{tmp}\mod d+d)\mod d$

5. 完结撒花

至此，你已经学完了扩展欧几里得的基础用法，如有不懂的地方，建议对照着文章自己推一推，悟一悟。

做个题练习一下吧：洛谷 P5656 【模板】二元一次不定方程 (exgcd)