Raisetsu41's Blog

「I will see your face down here real soon.」

Posted on Edited on In

整除

定义

设$a,b \in \mathbb{Z}$,且$b \neq 0$.如果存在$q\in\mathbb{Z}$，使得$a=bq$,则$b$整除a，记作$b\mid a$，此时$b$为$a$的因数，$a$叫做$b$的倍数.

性质

1
$如果a \mid b 且 b\mid c$,那么$c\mid a$

证明 ： $设an=b, bm=c (n, m \in \mathbb{Z}).$
$\therefore c/a = nm.$
$\therefore c\mid a.$

2
$如果a\mid b且a\mid c，有a\mid (bx+cy)$

证明：
$设 as = b, at = c$
$s,t\in\mathbb{Z^+}$
$\therefore ast = c$
$\therefore a\mid c$

3
$如果c\mid a, c\mid b，那么对于任意m, n\in\mathbb{Z},有c\mid ma+mb$. 证明 $如果m\neq 0,则a\mid b \Leftrightarrow mb\mid ma$ $\because a\mid b$ $\therefore 不妨设an=b$ $\therefore anm = bm$ $\therefore n*am = bm$ $\therefore mb\mid ma$
4
$如果ax+by=1，a\mid n, a\mid n. \Rightarrow ab\mid n$. 证明： $设as=n=1, bt=n, s,t\in\mathbb{Z}且s, t \neq 0$. $\because ax+by=1$. $\therefore \frac{x}{b} + \frac{y}{a}$. $\because ab\mid n$ $\therefore \frac{n}{ab}\in\mathbb{Z}$ $\therefore n \times \frac{1}{ab}$ $=\frac{nx}{b}+\frac{ny}{a}$ $=tx+sy$
5

如果$b=d\times q + c,q\in\mathbb{Z}$
$d\mid c \Leftrightarrow d\mid b$

模运算

定义

对于整数$a,b (b \neq 0)$,求$a \div b$的余数.记作$a$ $mod$ $b$$(a\%b)$.

性质

1.分配率

$(a+b)\%c=(a\%c+b\%c)\%c$ $(a-b)\%c=(a\%c-b\%c)\%c$ $(a\times b)\%c=(a\%c\times b\%c)\%c$ $(a^b)\%c=(a\%b)^b\%c$

统一证明:
设$ka+m_a=c, kb+m_b=c$
带入整理可得:
$\Rightarrow(a+b)\%c=(m_a+m_b)%c$
$\Rightarrow(a-b)\%c=(m_a-m_b)%c$
$\Rightarrow(a*b)\%c=(m_a*m_b)%c$
而幂运算可与看做多个乘法运算

2.缩放性

2.1
$如果a\%b=c,d\neq 0$ $\Rightarrow (ab)\%(bd)=cd$

证明:
设$a=bs+c$
$\Rightarrow ad=(bs+c)d$
$\Rightarrow ad=sbd+cd$
$\Rightarrow (ab)\%(bd)=cd$

2.2
$如果a\%b=c,d\mid a, d\mid b$ $\Rightarrow(a/d)\%(b/d)=(c/d).$

证明：
设$bs+c=a$.
$\frac{b}{d}\times s + \frac{c}{d}=\frac{a}{d}$

2.3
$\frac{a}{b}\%c=\frac{a\%(bc)}{b}$

证明：
两边同时乘$b$，可以得到：
$a\%(bc)=a\%(bc)$

Posted on Edited on In

今天考了一道分层图，本来是一道板题，结果我被误导了，想成了 架设电话线一题，考完写炸了才发现，架设电话线只需要==求出第k+1大的长度，只需要满足局部最优==，但是飞行线路要==使总和最小==，只能用分层图，然后我翻了半天标签，找到了这道题。

但是当旁边LH看到之后，他告诉我，这是一道DP。

结果我没看出来。。。

分层图倒是很简单。

Sulotion

step1
首先，他可以在图上到处走动，所以很自然地可以建一张图，所有的边权都是0。
然后这道题只与水晶球的价格有关，所以我们把点权搬到边权上面。
step2
因为他只进行一次买卖，所以有下面两种情况：
假设从$u$到$v$，水晶球在$u$的价格为$w$.
1.买. 建第二层图，连接第一层图 -> 在$u$和$v$之间建一条边边权为$-w$。
2.卖. 建第三层图，连接第二层图 -> 在$u$和$v$之间建一条边边权为$w$。
step3
我们在最后有两种方法走向终点：
不买卖直接走向终点
直接在第一层图的n号节点建立边权为0的有向边接入一个“大终点”
买卖一次后走向终点
在第三层图的n号节点建立边权为0的有向边接入“大终点”

至此，这道题就只需要求一个最长路即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100005 * 3 + 1;

int n, m, a[MAXN];
bool vis[MAXN];
int dis[MAXN];
queue<int> q;

void read(int& x) {
	x = 0;
	int f = 1;
	char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-') f = -f;
		c = getchar();
	}
	while (c <= '9' && c >= '0') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	x *= f;
}

struct edge {
	int v, w;
	edge(){}
	edge(int V, int W) {
		v = V;
		w = W;
	}
};
vector<edge> G[MAXN];

void AddEdge(int u, int v, int w) {
	G[u + n * 0].push_back(edge(v + n * 0, 0));
	G[u + n * 1].push_back(edge(v + n * 1, 0));
	G[u + n * 2].push_back(edge(v + n * 2, 0));
	G[u + n * 0].push_back(edge(v + n * 1, -w));
	G[u + n * 1].push_back(edge(v + n * 2, w));
}

void Spfa() {
	memset(vis, 0, sizeof(vis));
	memset(dis, 0xcf, sizeof(dis));
	dis[1] = 0;
	vis[1] = 1;
	q.push(1);
	while (q.size()) {
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i].v, w = G[u][i].w;
			if (dis[v] < dis[u] + w) {
				dis[v] = dis[u] + w;
				if (vis[v] == 0) {
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
	printf ("%d\n", dis[n]);
}

int main() {
	read(n);
	read(m);
	for (int i = 1; i <= n; i++) {
		read(a[i]);
	}
	for (int i = 1, u, v, opt; i <= m; i++) {
		read(u), read(v), read(opt);
		AddEdge(u, v, a[u]);
		if (opt == 2) {
			AddEdge(v, u, a[v]);
		}
	}
	G[n].push_back(edge(n * 3 + 1, 0));
	G[n * 3].push_back(edge(n * 3 + 1, 0));
	n *= 3;
	n++;
	Spfa();
	return 0;
}

Posted on Edited on In

假日住宿

题目描述

给出一棵$N$节点的树，每个节点代表一个城市，每个城市有一个人，每个人离开自己的城市到另一个城市，每个城市只能有一个人，问这$N$个人移动距离和的最大值。

Read more »

Posted on Edited on In

刚刚听了jmy讲他的证明方法，大致意思就是树上的任意一点所能到达的最远距离一定会在直径的两个端点上。
但我认为反证法其实来得更快。思路如下：

证明：
反证法。假设已经用两次bfs/dfs求得的直径为$AB$,且$AB$上有一点$N$。如果$AB$不是这颗树的直径，那么一定存在一条链$CD$，使得$CD > AB$，不妨设$CD$与$AB$的交点为$M$，所以$NB > NC$即可以得到$MB > MC$，可以得到$MB + MD > MC + MD$所以$CD$不是树的直径，与假设矛盾。故假设不成立，原命题成立。
证毕。

Posted on Edited on In

数你太美【第一周】

题目描述

PB 获得了两个正整数数列 ${a_i}$ , ${b_i}$ ，长度分别为 n , m ，其中每个数都小于 10。 定义一个正整数是“美丽的正整数”，当且仅当:这个数的十进制表示中，至少有一个 数位上的数在数列 a_i 出现过，至少有一个数位上的数在数列 b_i 出现过。现在 PB 希 望求出最小的“美丽的正整数”。

Read more »

Posted on Edited on In

RMQ

RMQ 即范围最小值问题 $(Range$ $Minimum$ $Query)$
支持==查询从$A_l, A_{l+1},A_{l+2}...，A_r$中的极值$(Max$ $or$ $Min)$==

Read more »

Posted on Edited on In

题目地址

分析

第一眼看到此题，感觉就是一道水题，直接加上前$need$小的白边就行了，再处理到$n-1$条黑边，但是，打完后突然发现有问题。。。 虽然加上了前$need$小的白边，但是会出现树不连通的现象，即无法构成生成树。

Read more »

Posted on Edited on In

叶子清除计划【第五周】

题目描述

⼩Y同学是⼀位数据结构⼤师同时也是⼀位园艺⼤师。

秋天到了，⼩Y同学需要对学校内的⼀棵树展现他顶尖的修叶⽔平。

学校内的这棵树是⼀颗拥有n个点的⽆根树，每次⼩Y会删去所有的叶⼦节点（即度数小于等于1的节点)，直到所有的点都被删除了为⽌。

⼩Y现在想问你对于每个点，求出它是第⼏次操作中被删除的。

Read more »

Posted on Edited on In

题目链接

分析

假设有如下图两个集合 $x$ & $y$。因为要构造一个完全图，所以应该将$x$中的$s[x]$个节点与$y$中的$s[y]$个节点一一连接即连接$s[x] * s[y] - 1$（此处减一是为了在后面单独处理原图中的$dis[i].w$）个节点，为了保证此完全图的最小生成树所以要用$(s[x] * s[y] - 1) * (dis[i].w + 1)$，最后加上原图中的$dis[i].w$。

Read more »

Posted on Edited on In

SCOI 滑雪与时间胶囊

题目描述

a180285 非常喜欢滑雪。
他来到一座雪山，这里分布着$M$条供滑行的轨道和$N$个轨道之间的交点（同时也是景点），而且每个景点都有一编号$i(1<=i<=n)$和一高度$$。a180285 能从景点$i$滑到景点$j$当且仅当存在一条$i$和$j$之间的边，且$i$的高度不小于$j$。

Read more »
© 2025 Raisetsu41