CF1245D Shichikuji and Power Grid（建图）

题面翻译

已知一个平面上有 n n n 个城市，需要个 n n n 个城市均通上电。
一个城市有电，必须在这个城市有发电站或者和一个有电的城市用电缆相连。

在一个城市建造发电站的代价是 c [ i ] c[i] c[i]，将 i i i 和 j j j 两个城市用电缆相连的代价是 k [ i ] + k [ j ] k[i]+k[j] k[i]+k[j] 乘上两者的曼哈顿距离。

求最小代价的方案。

题目描述

Shichikuji is the new resident deity of the South Black Snail Temple. Her first job is as follows:

There are $ n $ new cities located in Prefecture X. Cities are numbered from $ 1 $ to $ n $ . City $ i $ is located $ x_i $ km North of the shrine and $ y_i $ km East of the shrine. It is possible that $ (x_i, y_i) = (x_j, y_j) $ even when $ i \ne j $ .

Shichikuji must provide electricity to each city either by building a power station in that city, or by making a connection between that city and another one that already has electricity. So the City has electricity if it has a power station in it or it is connected to a City which has electricity by a direct connection or via a chain of connections.

• Building a power station in City $ i $ will cost $ c_i $ yen;
• Making a connection between City $ i $ and City $ j $ will cost $ k_i + k_j $ yen per km of wire used for the connection. However, wires can only go the cardinal directions (North, South, East, West). Wires can cross each other. Each wire must have both of its endpoints in some cities. If City $ i $ and City $ j $ are connected by a wire, the wire will go through any shortest path from City $ i $ to City $ j $ . Thus, the length of the wire if City $ i $ and City $ j $ are connected is $ |x_i - x_j| + |y_i - y_j| $ km.

Shichikuji wants to do this job spending as little money as possible, since according to her, there isn’t really anything else in the world other than money. However, she died when she was only in fifth grade so she is not smart enough for this. And thus, the new resident deity asks for your help.

And so, you have to provide Shichikuji with the following information: minimum amount of yen needed to provide electricity to all cities, the cities in which power stations will be built, and the connections to be made.

If there are multiple ways to choose the cities and the connections to obtain the construction of minimum price, then print any of them.

输入格式

First line of input contains a single integer $ n $ ( $ 1 \leq n \leq 2000 $ ) — the number of cities.

Then, $ n $ lines follow. The $ i $ -th line contains two space-separated integers $ x_i $ ( $ 1 \leq x_i \leq 10^6 $ ) and $ y_i $ ( $ 1 \leq y_i \leq 10^6 $ ) — the coordinates of the $ i $ -th city.

The next line contains $ n $ space-separated integers $ c_1, c_2, \dots, c_n $ ( $ 1 \leq c_i \leq 10^9 $ ) — the cost of building a power station in the $ i $ -th city.

The last line contains $ n $ space-separated integers $ k_1, k_2, \dots, k_n $ ( $ 1 \leq k_i \leq 10^9 $ ).

输出格式

In the first line print a single integer, denoting the minimum amount of yen needed.

Then, print an integer $ v $ — the number of power stations to be built.

Next, print $ v $ space-separated integers, denoting the indices of cities in which a power station will be built. Each number should be from $ 1 $ to $ n $ and all numbers should be pairwise distinct. You can print the numbers in arbitrary order.

After that, print an integer $ e $ — the number of connections to be made.

Finally, print $ e $ pairs of integers $ a $ and $ b $ ( $ 1 \le a, b \le n $ , $ a \ne b $ ), denoting that a connection between City $ a $ and City $ b $ will be made. Each unordered pair of cities should be included at most once (for each $ (a, b) $ there should be no more $ (a, b) $ or $ (b, a) $ pairs). You can print the pairs in arbitrary order.

If there are multiple ways to choose the cities and the connections to obtain the construction of minimum price, then print any of them.

样例 #1

样例输入 #1

3 2 3 1 1 3 2 3 2 3 3 2 3 

样例输出 #1

8 3 1 2 3  0 

样例 #2

样例输入 #2

3 2 1 1 2 3 3 23 2 23 3 2 3 

样例输出 #2

27 1 2  2 1 2 2 3 

提示

For the answers given in the samples, refer to the following diagrams (cities with power stations are colored green, other cities are colored blue, and wires are colored red):

For the first example, the cost of building power stations in all cities is $ 3 + 2 + 3 = 8 $ . It can be shown that no configuration costs less than 8 yen.

For the second example, the cost of building a power station in City 2 is 2. The cost of connecting City 1 and City 2 is $ 2 \cdot (3 + 2) = 10 $ . The cost of connecting City 2 and City 3 is $ 3 \cdot (2 + 3) = 15 $ . Thus the total cost is $ 2 + 10 + 15 = 27 $ . It can be shown that no configuration costs less than 27 yen.

思路

新建一个虚点，和其相连表示新建电厂，跑最小生成树

AC代码

#include  using namespace std; typedef long long ll; typedef pair pil; typedef pair > plii; const int N = 2010; int n, cnt, cot; ll tot,x[N], y[N],c[N], k[N], dis[N]; bool vis[N], ok[N]; vector son[N]; priority_queue, greater > q;  struct edge { 	int u, v; 	ll w; } ans[N];  inline void prim(int s) { 	q.push({0, {s, 0}}); 	for (int i = 0; i <= n; i++) 		dis[i] = 1e18; 	dis[s] = 0; 	while (! q.empty()) { 		plii it = q.top(); 		q.pop(); 		int u = it.second.first; 		if (vis[u])	continue; 		cnt++; 		tot += dis[u]; 		vis[u] = 1; 		ans[cnt] = edge{it.second.second, it.second.first, dis[u]}; 		if (it.second.second == 0) {  			ok[u] = 1; 			cot++; 		} 		if (cnt >= n + 1)return ; 		for (auto it : son[u]) { 			int v = it.first; 			ll w = it.second; 			if (dis[v] > w) { 				dis[v] = w; 				q.push({dis[v], {v, u}}); 			} 		} 	} }  int main() { 	scanf("%d", &n); 	for (int i = 1; i <= n; i++) 		scanf("%lld%lld", &x[i], &y[i]); 	for (int i = 1; i <= n; i++) { 		scanf("%lld", &c[i]); 		son[0].push_back({i, c[i]}); 	} 	for (int i = 1; i <= n; i++) { 		scanf("%lld", &k[i]); 		for (int j = 1; j < i; ++ j) { 			ll dis = abs(x[i] - x[j]) + abs(y[i] - y[j]); 			dis = dis * (k[i] + k[j]); 			son[i].push_back({j, dis}); 			son[j].push_back({i, dis}); 		} 	} 	prim(0); 	printf("%lld\n%d\n", tot, cot - 1);  	for (int i = 1; i <= n; i++) { 		if (ok[i]) { 			printf("%d ", i); 		} 	} 	putchar('\n'); 	int res = 0; 	for (int i = 1; i <= cnt; i++) { 		if (ans[i].u != 0 && ans[i].v != 0) { 			++ res; 		} 	} 	printf("%d\n", res); 	for (int i = 1; i <= cnt; i++) { 		if (ans[i].u != 0 && ans[i].v != 0) { 			if(ans[i].u>ans[i].v)swap(ans[i].u, ans[i].v); 			printf("%d %d\n", ans[i].u, ans[i].v); 		} 	} 	return 0; } 

P8074 [COCI2009-2010#7] SVEMIR（去除冗边）

题目描述

太空帝国要通过建造隧道来联通它的 N N N 个星球。

每个星球用三维坐标 ( x i , y i , z i ) (x_i,y_i,z_i) (xi​,yi​,zi​) 来表示，而在两个星球 A , B A,B A,B 之间建造隧道的价格为 min ⁡ { ∣ x A − x B ∣ , ∣ y A − y B ∣ , ∣ z A − z B ∣ } \min\{|x_A-x_B|,|y_A-y_B|,|z_A-z_B|\} min{∣xA​−xB​∣,∣yA​−yB​∣,∣zA​−zB​∣}。

现要建造 N − 1 N-1 N−1 条隧道使得所有的星球都能直接或间接相连。求完成该任务所需的最小总价。

输入格式

第一行，一个整数 N N N。

接下来的 N N N 行，每行三个整数 x i , y i , z i x_i,y_i,z_i xi​,yi​,zi​，表示第 i i i 个星球的坐标。

数据保证不存在两个具有相同坐标的星球。

输出格式

输出所需的最小总价。

样例 #1

样例输入 #1

2 1 5 10 7 8 2 

样例输出 #1

3 

样例 #2

样例输入 #2

3 -1 -1 -1 5 5 5 10 10 10 

样例输出 #2

11 

样例 #3

样例输入 #3

5 11 -15 -15 14 -5 -15 -1 -1 -5 10 -4 -1 19 -4 19 

样例输出 #3

4 

提示

【数据规模与约定】

• 对于 100 % 100\% 100% 的数据， 1 ≤ N ≤ 1 0 5 1 \le N \le 10^5 1≤N≤105， − 1 0 9 ≤ x i , y i , z i ≤ 1 0 9 -10^9 \le x_i,y_i,z_i \le 10^9 −109≤xi​,yi​,zi​≤109。

【提示与说明】

题目译自 COCI 2009-2010CONTEST #7Task 4 SVEMIR。

本题分值按 COCI 原题设置，满分 100 100 100。

思路

最小生成树，但代价比较特殊。
不妨设两个点的距离由 x 决定，代价为 ∣ x A − x B ∣ |x_A-x_B| ∣xA​−xB​∣，
我们发现在数轴上 x A x_A xA​和 x B x_B xB​必定是相邻的，否则不如把邻居加进来。
所以我们只需 3n 条边，只考虑 x,y,z 相邻权值连边，跑最小生成树即可。

AC代码

#include using namespace std; const int N=1e5+10,M=1e7+10; int n,m,ans,k; int fa[N]; struct Edge{ 	int u,v,w; }edge[M]; bool operator < (const Edge &a ,const Edge &b){ 	return a.w 	int x,y,z,id; 	inline void putin(int i){ 		scanf("%d%d%d",&x,&y,&z); 		id=i; 	} }planet[N]; inline bool cmpx (Planet a, Planet b) {return a.x < b.x;} inline bool cmpy (Planet a, Planet b) {return a.y < b.y;} inline bool cmpz (Planet a, Planet b) {return a.z < b.z;} inline int find(int x){ 	if(x!=fa[x])fa[x]=find(fa[x]); 	return fa[x]; } inline void add (Planet a, Planet b) { 	edge[++m].u = a.id;edge[m].v = b.id; 	edge[m].w = min (abs (a.x - b.x), min (abs (a.y - b.y), abs (a.z - b.z)));  } void Kruska () { 	sort (edge + 1, edge + m + 1); 	for (int i = 1; i <= m; i++) 	{ 		int r1 = find (edge[i].u), r2 = find (edge[i].v); 		if (r1 == r2)	continue; 		fa[r2] = r1; 		k++;ans += edge[i].w; 		if (k == n - 1)	return; 	} } int main(){ 	scanf ("%d", &n); 	for (int i = 1; i <= n; i++)planet[i].putin (i); 	for (int i = 1; i <= n; i++)fa[i] = i; 	sort (planet + 1, planet + n + 1, cmpx); 	for (int i = 2; i <= n; i++)add (planet[i - 1], planet[i]); 	sort (planet + 1, planet + n + 1, cmpy); 	for (int i = 2; i <= n; i++)add (planet[i - 1], planet[i]); 	sort (planet + 1, planet + n + 1, cmpz); 	for (int i = 2; i <= n; i++)add (planet[i - 1], planet[i]); 	Kruska (); 	printf ("%d", ans); 	return 0; } 

P5994 [PA2014] Kuglarz（思维题）

题目描述

魔术师的桌子上有 n n n 个杯子排成一行，编号为 1 , 2 , … , n 1,2,…,n 1,2,…,n，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。

花费 c i j c_{ij} cij​ 元，魔术师就会告诉你杯子 i , i + 1 , … , j i,i+1,…,j i,i+1,…,j 底下藏有球的总数的奇偶性。

采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？

输入格式

第一行一个整数 n n n。

第 i + 1 i+1 i+1 行（ 1 ≤ i ≤ n 1\le i\le n 1≤i≤n）有 n + 1 − i n+1-i n+1−i 个整数，表示每一种询问所需的花费。

其中 c i j c_{ij} cij​（对区间 [ i , j ] [i,j] [i,j] 进行询问的费用， 1 ≤ i ≤ j ≤ n 1\le i\le j\le n 1≤i≤j≤n）为第 i + 1 i+1 i+1 行第 j + 1 − i j+1-i j+1−i 个数。

输出格式

输出一个整数，表示最少花费。

样例 #1

样例输入 #1

5 1 2 3 4 5 4 3 2 1 3 4 5 2 1 5 

样例输出 #1

7 

提示

对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 2 × 1 0 3 1\le n\le 2\times 10^3 1≤n≤2×103， 1 ≤ c i j ≤ 1 0 9 1\le c_{ij}\le 10^9 1≤cij​≤109。

思路

第一步要做前缀和 S i S_i Si​，那么每次询问相当于求 S j − S i − 1 S_j-S_{i-1} Sj​−Si−1​的奇偶性，我们可以连一条
边。
也就是求出 S j S_j Sj​和S_{i-1}的奇偶关系。
假设我们得到了最终答案，相当于我们知道了所有 S i S_i Si​的奇偶性。而我们知道所有 S i S_i Si​的
奇偶性后，我们可以通过 S i − S i − 1 S_i-S_{i-1} Si​−Si−1​求出第 i 个位置的答案。
所以说原问题等价于求出所有 S i S_i Si​的奇偶性，因为我们知道 S 0 S_0 S0​是偶数，所以就是求最小
生成树！

AC代码

#include using namespace std; template inline void read(T &x) { 	x=0;long long f=0;char ch=getchar(); 	while(!isdigit(ch))	f=ch=='-',ch=getchar(); 	while(isdigit(ch))	x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 	x=f?-x:x; } const long long N=2e3+5; long long a[N][N],n,m; struct edge{ 	long long ne,to,w; }e[N*N*2]; long long h[N*N],cnt,ans,dis[N*N],vis[N*N]; inline void add(long long u,long long v,long long w) { 	e[++cnt]={h[u],v,w}; 	h[u]=cnt; } int  main() { 	read(n); 	for(long long i=1;i<=n;i++) 		for(long long j=i,w;j<=n;j++) 			read(w),add(i-1,j,w),add(j,i-1,w); 	priority_queue > q; 	memset(dis,0x3f,sizeof(dis)); 	q.push(make_pair(0,1)),dis[1]=0; 	while(!q.empty()) 	{ 		long long x=q.top().second;q.pop(); 		if(vis[x])	continue; 		vis[x]=1,ans+=dis[x]; 		for(long long i=h[x];i;i=e[i].ne) 		{ 			long long y=e[i].to; 			if(dis[y]>e[i].w)	dis[y]=e[i].w,q.push(make_pair(-dis[y],y)); 		} 	} 	printf("%lld\n",ans); 	return 0; } 

P1967 [NOIP2013 提高组] 货车运输（经典题）

题目背景

NOIP2013 提高组 D1T3

题目描述

A 国有 n n n 座城市，编号从 1 1 1 到 n n n，城市之间有 m m m 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 q q q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式

第一行有两个用一个空格隔开的整数 $ n,m$，表示 A 国有 $ n$ 座城市和 m m m 条道路。

接下来 m m m 行每行三个整数 x , y , z x, y, z x,y,z，每两个整数之间用一个空格隔开，表示从 $x $ 号城市到 $ y $ 号城市有一条限重为 z z z 的道路。
注意： x ≠ y x \neq y x=y，两座城市之间可能有多条道路 。

接下来一行有一个整数 q q q，表示有 q q q 辆货车需要运货。

接下来 q q q 行，每行两个整数 x , y x,y x,y，之间用一个空格隔开，表示一辆货车需要从 x x x 城市运输货物到 y y y 城市，保证 x ≠ y x \neq y x=y

输出格式

共有 q q q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。
如果货车不能到达目的地，输出 − 1 -1 −1。

样例 #1

样例输入 #1

4 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3 

样例输出 #1

3 -1 3 

提示

对于 30 % 30\% 30% 的数据， 1 ≤ n < 1000 1 \le n < 1000 1≤n<1000， 1 ≤ m < 10 , 000 1 \le m < 10,000 1≤m<10,000， 1 ≤ q < 1000 1\le q< 1000 1≤q<1000；

对于 60 % 60\% 60% 的数据， 1 ≤ n < 1000 1 \le n < 1000 1≤n<1000， 1 ≤ m < 5 × 1 0 4 1 \le m < 5\times 10^4 1≤m<5×104， 1 ≤ q < 1000 1 \le q< 1000 1≤q<1000；

对于 100 % 100\% 100% 的数据， 1 ≤ n < 1 0 4 1 \le n < 10^4 1≤n<104， 1 ≤ m < 5 × 1 0 4 1 \le m < 5\times 10^4 1≤m<5×104，$1 \le q< 3\times 10^4 $， 0 ≤ z ≤ 1 0 5 0 \le z \le 10^5 0≤z≤105。

思路

最优情况下一定是走最大生成树，所以相当于询问最大生成树上两点之间的最小边权，
我们用倍增维护即可。

倍增求 LCA

int lca(int x,int y) { if (d[x] > d[y]) swap(x, y); for (int i = t;i >= 0; i--) if (d[f[y][i]] >= d[x]) y = f[y][i]; if (x == y) return x; for (int i = t;i >= 0; i--) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i]; return f[x][0]; } 

AC代码

#include using namespace std; const int N=100010; bool f; int n,m,q; struct T{ 	int st,ed,v; }edge[N]; int pre[N]; bool inline cmp( T a,T b){ 	return a.v>b.v; } inline int found(int x){ 	if(pre[x]==x)return x; 	return pre[x]=found(pre[x]); } vectorG[N]; int F[N][20],num[N][20],lg[N],deep[N],root[N]; bool mark[N],vis[N]; void DFS(int x,int fa,int val,int rt){     root[x]=rt;     F[x][0]=fa;     num[x][0]=val;     deep[x]=deep[fa]+1;     for(int i=1;(1<             int t=G[x][i].ed,val=G[x][i].v;             if(t==fa)continue;                 DFS(t,x,val,rt);             }     } inline int LCA(int x,int y){     if(deep[x]deep[y]){         res=min(res,num[x][lg[deep[x]-deep[y]]-1]);         x=F[x][lg[deep[x]-deep[y]]-1];     }     if(x==y)return res;     for(int i=lg[deep[x]]-1;i>=0;i--){         if(F[x][i]==F[y][i])continue;         res=min(res,num[x][i]);         res=min(res,num[y][i]);         x=F[x][i],y=F[y][i]; }     res=min(res,num[x][0]);     res=min(res,num[y][0]);     return res; } inline void work(){      for(int i=1;i<=N-10;i++)lg[i]=lg[i-1]+((1<         int x,y,z;         scanf("%d %d %d",&x,&y,&z);         edge[i]=T {x,y,z};     }     sort(edge+1,edge+1+m,cmp);     for(int i=1;i<=m;i++){         int fx=found(edge[i].st),fy=found(edge[i].ed);         if(fx==fy)continue;         mark[edge[i].st]=mark[edge[i].ed]=true;         pre[fx]=fy;         G[edge[i].st].push_back(T{0,edge[i].ed,edge[i].v});         G[edge[i].ed].push_back(T{0,edge[i].st,edge[i].v});     }     for(int i=1;i<=n;i++)         if(!root[i])             DFS(i,0,0,i);         scanf("%d",&q);     for(int i=1;i<=q;i++){         int x,y;         scanf("%d %d",&x,&y);         if(root[x]!=root[y]){                 puts("-1");                 continue;         }     	printf("%d\n",LCA(x,y));     } } int main(){ 	scanf("%d %d",&n,&m);     work();     return 0; }  

P4180 [BJWC2010] 严格次小生成树

题目描述

小 C 最近学了很多最小生成树的算法，Prim 算法、Kruskal 算法、消圈算法等等。正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是 E M E_M EM​，严格次小生成树选择的边集是 E S E_S ES​，那么需要满足：( v a l u e ( e ) value(e) value(e) 表示边 e e e 的权值) ∑ e ∈ E M v a l u e ( e ) < ∑ e ∈ E S v a l u e ( e ) \sum_{e \in E_M}value(e)<\sum_{e \in E_S}value(e) ∑e∈EM​​value(e)<∑e∈ES​​value(e)。

这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

输入格式

第一行包含两个整数 N N N 和 M M M，表示无向图的点数与边数。

接下来 M M M 行，每行 3 3 3 个数 x , y , z x,y,z x,y,z 表示，点 x x x 和点 y y y 之间有一条边，边的权值为 z z z。

输出格式

包含一行，仅一个数，表示严格次小生成树的边权和。

样例 #1

样例输入 #1

5 6 1 2 1  1 3 2  2 4 3  3 5 4  3 4 3  4 5 6 

样例输出 #1

11 

提示

数据中无向图不保证无自环。

对于 50 % 50\% 50% 的数据， N ≤ 2000 N\le 2000 N≤2000， M ≤ 3000 M\le 3000 M≤3000。

对于 80 % 80\% 80% 的数据， N ≤ 5 × 1 0 4 N\le 5\times 10^4 N≤5×104， M ≤ 1 0 5 M\le 10^5 M≤105。

对于 100 % 100\% 100% 的数据， N ≤ 1 0 5 N\le 10^5 N≤105， M ≤ 3 × 1 0 5 M\le 3\times10^5 M≤3×105，边权 ∈ [ 0 , 1 0 9 ] \in [0,10^9] ∈[0,109]，数据保证必定存在严格次小生成树。

思路

次小生成树一定是将某个非树边代替换上的一条边形成的。
那么一定代替最大值或严格次大值，倍增记录即可。

AC代码

#include  #include  #include  #include  #include  #include  #include 

CF827D Best Edge Weight

题面翻译

给定一个点数为 n n n，边数为 m m m，权值不超过 1 0 9 10^9 109 的带权连通图，没有自环与重边。
现在要求对于每一条边求出，这条边的边权最大为多少时，它还能出现在所有可能的最小生成树上，如果对于任意边权都出现，则输出 − 1 -1 −1。
($ 2 \le n \le 2 \times 10^5, n - 1 \le m \le 2 \times 10^5$)

感谢 @WJiannan 提供的翻译

题目描述

You are given a connected weighted graph with $ n $ vertices and $ m $ edges. The graph doesn’t contain loops nor multiple edges. Consider some edge with id $ i $ . Let’s determine for this edge the maximum integer weight we can give to it so that it is contained in all minimum spanning trees of the graph if we don’t change the other weights.

You are to determine this maximum weight described above for each edge. You should calculate the answer for each edge independently, it means there can’t be two edges with changed weights at the same time.

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 2<=n<=2·10^{5} $ , $ n-1<=m<=2·10^{5} $ ), where $ n $ and $ m $ are the number of vertices and the number of edges in the graph, respectively.

Each of the next $ m $ lines contains three integers $ u $ , $ v $ and $ c $ ( $ 1<=v,u<=n $ , $ v≠u $ , $ 1<=c<=10^{9} $ ) meaning that there is an edge between vertices $ u $ and $ v $ with weight $ c $ .

输出格式

Print the answer for each edge in the order the edges are given in the input. If an edge is contained in every minimum spanning tree with any weight, print -1 as the answer.

样例 #1

样例输入 #1

4 4 1 2 2 2 3 2 3 4 2 4 1 3 

样例输出 #1

2 2 2 1 

样例 #2

样例输入 #2

4 3 1 2 2 2 3 2 3 4 2 

样例输出 #2

-1 -1 -1 

思路

分别考虑树边和非树边
非树边：只需比环上最大的边小即可，倍增维护即可
树边：需要小于所有跨过这个树边的非树边中的最小值，倍增打 tag
我要炸了，这道题代码自己写吧

这是我的第十七篇文章，如有纰漏也请各位大佬指正
辛苦创作不易，还望看官点赞收藏打赏，后续还会更新新的内容。