第十六届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组(个人见解，已完结)

*一、移动距离

问题描述

小明初始在二维平面的原点 (0,0)，他想前往坐标 (233,666). 在移动过程中，他只能采用以下两种移动方式，并且这两种移动方式可以交替、不限次数地使用：

在这种条件下，他到达目的地最少移动多少单位距离？

只需输出答案四舍五入到整数的结果。

输入输出及限制

输入格式 无输入。

输出格式 输出一个整数，表示到达目的地最少移动的距离（四舍五入到整数）。

运行限制

个人见解

最短的路线一定是先走一个半径，然后再走一段弧。

知道对应函数就比较无脑的一道填空题，但是不得不承认up主忘记了 atan() (正切反函数)以及 round() (四舍五入函数)😅。我们都明白 sqrt() 和 round() 的返回值都是 double ，up主这里想着强转成 long long ，但是没想到 cout 非常聪明，在处理浮点数（double）时，会有默认的格式化行为。会自动省略末尾无效的 .000，如果一个浮点数恰好是整数值，cout 默认只输出整数部分。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

void solve()
{
double r=sqrt(233*233+666*666);
double ans=r+r*atan(666.0/233);
cout<<(ll)round(ans);
}

int main( )
{
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}

*二、客流量上限

问题描述

一家连锁旅馆在全国拥有

2025

2025

2025 个分店，分别编号为

1

1

1 至

2025

2025

2025。随着节日临近，总部决定为每家分店设定每日客流量的上限，分别记作

A

1

,

A

2

,

…

,

A

2025

A_1,A_2,…,A_{2025}

A1​,A2​,…,A2025​。这些上限并非随意分配，而是需要满足以下约束条件：

• $A_1,A_2,\dots ,A_{2025}$
• 对于任意分店 $i$

这些约束旨在平衡各分店客流压力，确保服务质量和运营稳定性。

现在，请你计算这样的分配方案究竟有多少种。由于答案可能很大，你只需输出其对

10

9

+

7

10^9+7

109+7 取余后的结果即可。

输入输出及限制

答案提交 这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

运行限制

个人见解

好吧，第二题就遇见可爱的数学真的让人很难开心起来😅，难道说本题 up 主要跟大家一起证明数学公式 ？已经证明睡着了😴哈哈不对，我来打表了，遇见不会的数学题，先找找看有没有规律总结，果不其然这题就有！😉

由于题目给出两个约束条件，其实转变成代码就是全排列问题外加题目要求的判定，这里我直接举出

n

=

=

10

n == 10

n==10 来观察规律。

1
1
2
2
4
4
8
8
16
16

通过输出结果可以总结出规律

a

n

s

=

2

(

n

−

1

)

/

2

ans=2^{(n-1)/2}

ans=2(n−1)/2。

有人可能会问，与其举例子，为什么不直接算出来答案 ？ 害，代码中的 //solve(100) 已经说明一切😭，其实不要说

n

=

2025

n=2025

n=2025 ，当

n

=

12

n=12

n=12 的时候，编译器就需要很久才能算出来了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll mod=1e9+7;

vector<ll> v;
ll used[2025];
ll num=0;

void dfs(ll step,ll n)
{
if(step==n+1)
{
for(ll i=0;i<n;i++)
{
for(ll j=0;j<n;j++)
{
if(v[i]*v[j]>((i+1)*(j+1)+n))return;
}
}
num++;
num=num%mod;
}

for(ll i=1;i<=n;i++)
{
if(!used[i])
{
v.push_back(i);
used[i]=1;
dfs(step+1,n);
v.pop_back();
used[i]=0;
}
}
}

void solve(ll n)
{
v.clear();
num=0;
memset(used,0,sizeof(used));
dfs(1,n);
cout<<num<<endl;
}

int main( )
{
ios::sync_with_stdio(0);
cin.tie(0);

for(ll i=1;i<=10;i++)
{
solve(i);
}
//solve(2025);

return 0;
}

AC代码

那么既然知道答案是

2

1012

2^{1012}

21012 ，直接快速幂即可，然后就 ac 啦！🎉

#include<bits/stdc++.h>
#define ll long long
using namespace std;

void solve()
{
ll ans=1;
ll a=2,b=1012,mod=1e9+7;;
while(b)
{
if(b&1)
{
ans=ans*a%mod;
}
a=a*a%mod;
b=b>>1;
}

cout<<ans;
}

int main( )
{
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}

三、可解的正整数

问题描述

定义一种特殊的整数序列：这种序列由连续递增的整数组成，并满足以下条件：

例如，

[

1

,

2

,

3

]

、

[

4

,

5

,

6

,

7

]

[1,2,3]、[4,5,6,7]

[1,2,3]、[4,5,6,7] 和

[

−

1

,

0

,

1

]

[−1,0,1]

[−1,0,1] 是符合条件的序列，而

[

1

,

2

]

[1,2]

[1,2]（长度不足）和

[

1

,

2

,

4

]

[1,2,4]

[1,2,4]（不连续）不符合要求。

现给定一组包含

N

N

N 个正整数的数据

A

1

,

A

2

,

…

,

A

N

A_1,A_2,…,A_N

A1​,A2​,…,AN​。如果某个

A

i

A_i

Ai​ 能够表示为符合上述条件的连续整数序列中所有元素的和，则称

A

i

A_i

Ai​ 是可分解的。

请你统计这组数据中可分解的正整数的数量。

输入输出及限制

输入格式

输入的第一行包含一个正整数

N

N

N，表示数据的个数。

第二行包含

N

N

N 个正整数

A

1

,

A

2

,

…

,

A

N

A_1,A_2,…,A_N

A1​,A2​,…,AN​，表示需要判断是否可分解的正整数序列。

输出格式

输出一个整数，表示给定数据中可分解的正整数的数量。

样例输入

3
3 6 15

样例输出

3

样例说明

• $A_i=3$
• $A_i=6$
• $A_i=15$

所以可分解的正整数的数量为

3

3

3。

评测用例规模与约定

对于 30% 的评测用例，

1

≤

N

≤

100

1≤N≤100

1≤N≤100，

1

≤

A

i

≤

100

1≤A_i≤100

1≤Ai​≤100。

对于所有评测用例，

1

≤

N

≤

10

5

1≤N≤10^5

1≤N≤105，

1

≤

A

i

≤

10

9

1≤A_i≤10^9

1≤Ai​≤109。

运行限制

个人见解

脑筋急转弯，细想一下会发现只有

−

1

-1

−1 和

1

1

1 不满足题意。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

void solve()
{
ll N;
cin>>N;
ll ans=0;
for(ll i=1;i<=N;i++)
{
ll a;
cin>>a;
if(a%3==0)ans++;
}
cout<<ans;
}

int main( )
{
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}

四、产值调整

问题描述

偏远的小镇上，三兄弟共同经营着一家小型矿业公司“兄弟矿业”。公司旗下有三座矿山：金矿、银矿和铜矿，它们的初始产值分别用非负整数

A

A

A、

B

B

B 和

C

C

C 表示。这些矿山的产出是小镇经济的核心，支撑着三兄弟和许多矿工家庭的生计。

然而，各矿山的产值波动剧烈，有时金矿收益高而银矿、铜矿低迷，有时则相反。这种不稳定性让公司收入难以预测，也常引发兄弟间的争执。为了稳定经营，三兄弟设计了一个公平的产值调整策略，每年执行一次，每次调整时，将根据当前的产值

A

A

A、

B

B

B、

C

C

C，计算新产值：

• 金矿新产值 $A\prime =\lfloor \frac{B+C}{2}\rfloor$
• 银矿新产值 $B\prime =\lfloor \frac{A+C}{2}\rfloor$
• 铜矿新产值 $C\prime =\lfloor \frac{A+B}{2}\rfloor$

其中，

⌊

⌋

⌊⌋

⌊⌋ 表示向下取整。例如，

⌊

3.7

⌋

=

3

⌊3.7⌋=3

⌊3.7⌋=3，

⌊

5.2

⌋

=

5

⌊5.2⌋=5

⌊5.2⌋=5。

计算出

A

′

A′

A′、

B

′

B′

B′、

C

′

C′

C′ 后，同时更新：

A

A

A 变为

A

′

A′

A′，

B

B

B 变为

B

′

B′

B′，

C

C

C 变为

C

′

C′

C′，作为下一年调整的基础。

三兄弟认为这个方法能平衡产值波动，于是计划连续执行

K

K

K 次调整。现在，请你帮他们计算，经过

K

K

K 次调整后，金矿、银矿和铜矿的产值分别是多少。

输入输出及限制

输入格式

输入的第一行包含一个整数

T

T

T ，表示测试用例的数量。

接下来的

T

T

T 行，每行包含四个整数

A

A

A，

B

B

B，

C

C

C，

K

K

K，分别表示金矿、银矿和铜矿的初始产值，以及需要执行的调整次数。

输出格式

对于每个测试用例，输出一行，包含三个整数，表示经过

K

K

K 次调整后金矿、银矿和铜矿的产值，用空格分隔。

样例输入

2
10 20 30 1
5 5 5 3

样例输出

25 20 15
5 5 5

评测用例规模与约定

对于 30% 的评测用例，

1

≤

T

≤

100

1≤T≤100

1≤T≤100，

1

≤

A

,

B

,

C

,

K

≤

10

5

1≤A,B,C,K≤10^5

1≤A,B,C,K≤105。

对于所有评测用例，

1

≤

T

≤

10

5

1≤T≤10^5

1≤T≤105，

1

≤

A

,

B

,

C

,

K

≤

10

9

1≤A,B,C,K≤10^9

1≤A,B,C,K≤109。

运行限制

个人见解

一道模拟题，但是跟着暴力只能过一半的数据，因为

K

≤

10

9

K\\leq10^9

K≤109 会导致超时，依然可以输一些数据查看结果，会发现

A

A

A，

B

B

B，

C

C

C 到最后会变成相同的数字，因此加个判定即可。

if(a==b && b==c)break;

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

void solve()
{
ll a,b,c,k;
cin>>a>>b>>c>>k;

for(ll i=1;i<=k;i++)
{
ll A=b+c>>1,B=a+c>>1,C=a+b>>1;
a=A,b=B,c=C;
if(a==b && b==c)break;
}
cout<<a<<" "<<b<<" "<<c<<endl;
}

int main( )
{
ios::sync_with_stdio(0);
cin.tie(0);

ll t=1;
cin>>t;
while(t—)
{
solve();
}

return 0;
}

五、画展布置

问题描述

画展策展人小蓝和助理小桥为即将举办的画展准备了 NN 幅画作，其艺术价值分别为

A

1

,

A

2

,

…

,

A

N

A_1,A_2,…,A_N

A1​,A2​,…,AN​。他们需要从这

N

N

N幅画中挑选

M

M

M 幅，并按照一定顺序布置在展厅的

M

M

M 个位置上。如果随意挑选和排列，艺术价值的变化可能会过于突兀，导致观众的观展体验不够流畅。

为了优化布置，他们查阅了《画展布置指南》。指南指出，理想的画展应使观众在欣赏画作时，艺术价值的过渡尽量平缓。指南建议，选择并排列

M

M

M 幅画，应使艺术价值的变化程度通过一个数值

L

L

L 来衡量，且该值越小越好。数值

L

L

L 的定义为：

L

=

∑

i

=

1

M

−

1

∣

B

i

+

1

2

−

B

i

2

∣

L=\\sum_{i=1}^{M−1}∣B_{i+1}^2−B_i^2∣

L=i=1∑M−1​∣Bi+12​−Bi2​∣ 其中

B

i

B_i

Bi​ 表示展厅第

i

i

i 个位置上画作的艺术价值。

现在，他们希望通过精心挑选和排列这

M

M

M 幅画作，使

L

L

L 达到最小值，以提升画展的整体协调性。请你帮他们计算出这个最小值是多少。

输入输出及限制

输入格式

输入共两行。

第一行包含两个正整数

N

N

N 和

M

M

M，分别表示画作的总数和需要挑选的画作数量。

第二行包含

N

N

N 个正整数

A

1

,

A

2

,

…

,

A

N

A_1,A_2,…,A_N

A1​,A2​,…,AN​，表示每幅画作的艺术价值。

输出格式

输出一个整数，表示

L

L

L 的最小值。

样例输入

4 2
1 5 2 4

样例输出

3

评测用例规模与约定

对于 40% 的评测用例，

2

≤

M

≤

N

≤

10

3

2≤M≤N≤10^3

2≤M≤N≤103，

1

≤

A

i

≤

10

3

1≤A_i≤10^3

1≤Ai​≤103。

对于所有评测用例，

2

≤

M

≤

N

≤

10

5

2≤M≤N≤10^5

2≤M≤N≤105，

1

≤

A

i

≤

10

5

1≤A_i≤10^5

1≤Ai​≤105。

运行限制

个人见解

看到

L

L

L 的表达式，其实可以发现，最好的策略其实就是让

A

i

A_i

Ai​ 按照艺术价值从小到大排列，原因是因为绝对值不等式恒成立：

∣

a

−

b

∣

+

∣

b

−

c

∣

≥

∣

a

−

c

∣

|a-b|+|b-c|\\geq|a-c|

∣a−b∣+∣b−c∣≥∣a−c∣ 因此最小值其实就是

L

=

B

i

2

−

B

i

−

M

+

1

2

L=B_i^2-B_{i-M+1}^2

L=Bi2​−Bi−M+12​ ，因此只需要滑动一遍取出最小值即可。

不知道是否有人和我一样开始猜测出错的情况，认为

L

m

i

n

=

B

M

2

−

B

1

2

L_{min}=B_M^2-B_1^2

Lmin​=BM2​−B12​ ，但其实反例比较好举，

e

g

：

M

=

3

,

A

=

[

1

,

10

,

11

,

12

,

20

]

。

eg：M=3,A=[1, 10, 11, 12, 20]。

eg：M=3,A=[1,10,11,12,20]。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n,m;
ll a[100005];

void solve()
{
cin>>n>>m;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);

ll ans=LONG_LONG_MAX;
for(ll i=m;i<=n;i++)
{
ans=min(ans,a[i]*a[i]–a[i–m+1]*a[i–m+1]);
}
cout<<ans;
}

int main( )
{
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}

*六、水质检测

问题描述

小明需要在一条

2

×

n

2×n

2×n 的河床上铺设水质检测器。在他铺设之前，河床上已经存在一些检测器。如果两个检测器上下或左右相邻，那么这两个检测器就是互相连通的。

连通具有传递性，即如果

A

A

A 和

B

B

B 连通，

B

B

B 和

C

C

C 连通，那么

A

A

A 和

C

C

C 也连通。现在他需要在河床上增加铺设一些检测器，使得所有检测器都互相连通。他想知道最少需要增加铺设多少个检测器？

输入输出及限制

输入格式

输入共两行，表示一个

2

×

n

2×n

2×n 的河床。

每行一个长度为

n

n

n 的字符串，仅包含 # 和 ., 其中 # 表示已经存在的检测器，. 表示空白。

输出格式

输出共

1

1

1 行，一个整数，表示最少需要增加的检测器数量。

样例输入

.##…..#
.#.#.#…

样例输出

5

样例说明

其中一种方案： ###….# .#.######

增加了

5

5

5 个检测器。

评测用例规模与约定

对于

100

%

100\\%

100% 的评测用例，保证

n

≤

1000000

n≤1000000

n≤1000000。

运行限制

个人见解

写的第一道

01

b

f

s

01bfs

01bfs 。过程充满坎坷，up主最开始尝试的其实是 并查集

+

01

b

f

s

+

K

r

u

s

k

a

l

+01bfs+Kruskal

+01bfs+Kruskal 的解法，但是遗憾逻辑漏洞，后续会发出，感兴趣可以关注当前博客。重构并非毫无意义，至少学习了新算法不是嘛…

在普通

b

f

s

bfs

bfs 中，我们默认每走一步的代价（距离）都是一样的。如果图里的边权不再全是 1，而是混杂着 0 和 1，普通的 BFS 就失效了。为什么？因为走权值为 0 的边不需要付出代价。

核心数据结构： Deque (双端队列)

逻辑（核心差异）：

• 当你从点 $u$
• 如果边权是 0：说明 $v$
• 如果边权是 1：说明 $v$

直观理解： 0-1 BFS 保证了队列始终是单调递增且两段性的（队列里只会有当前层

d

d

d 和下一层

d

+

1

d+1

d+1 的元素）。

其实核心代码就两行：

dist[nx][ny]=min(dist[nx][ny],dist[x][y]+w);

if(v[x][y]=='#')ans=max(ans,dist[x][y]);

其实在写这题的时候，最先疑惑的点是该怎么确定起点和终点，这彷佛和传统的

b

f

s

bfs

bfs 不太一样。 我有想过起点设为第一个 ‘#’ ，终点设为最后一个 ‘#’ ，但是位置关系依然难确定，因此使用了上方所述的更新方式来取代寻找唯一的终点。这道题还有个很神奇的点：

for(ll i=0;i<n;i++)
{
if(v[0][i]=='#')
{
cout<<bfs(0,i);
return;
}
if(v[1][i]=='#')
{
cout<<bfs(1,i);
return;
}
}
// for(ll i=0;i<2;i++)
// {
// for(ll j=0;j<n;j++)
// {
// if(v[i][j]=='#')
// {
// cout<<bfs(i,j);
// return;
// }
// }
// }

不知道大家能不能看出来这段代码和注释的区别，前者是按列优先寻找起点，注释部分是按行优先寻找起点，神奇的点在于，注释部分只能过

60

%

60\\%

60% 的数据，然而现在的代码可以完全

a

c

ac

ac ，非常之玄学。

AC代码($01BFS$

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll N=1e6+5;

ll n;
string v[2];
ll dist[2][N]; //记录从起点到每个点的距离
ll vis[2][N]; //标记是否访问
ll dx[4]={0, 0,–1,1};
ll dy[4]={1,–1, 0,0};

ll bfs(ll p,ll q)
{
for(ll i=0;i<n;i++)
{
dist[0][i]=LONG_LONG_MAX;
dist[1][i]=LONG_LONG_MAX;
}
dist[p][q]=0;
ll ans=0;

deque<pair<ll,ll>> dq;
dq.push_back({p,q});
while(!dq.empty())
{
auto [x,y]=dq.front();
dq.pop_front();
if(vis[x][y])continue;
vis[x][y]=1;

if(v[x][y]=='#')ans=max(ans,dist[x][y]);
for(ll i=0;i<4;i++)
{
ll nx=x+dx[i],ny=y+dy[i];
if(nx<0||nx>=2||ny<0||ny>=v[0].length()||vis[nx][ny])continue;

ll w=v[nx][ny]=='#'?0:1;
dist[nx][ny]=min(dist[nx][ny],dist[x][y]+w);
if(w)dq.push_back({nx,ny});
else dq.push_front({nx,ny});
}
}
return ans;
}

void solve()
{
cin>>v[0]>>v[1];
n=v[0].length();

for(ll i=0;i<n;i++)
{
if(v[0][i]=='#')
{
cout<<bfs(0,i);
return;
}
if(v[1][i]=='#')
{
cout<<bfs(1,i);
return;
}
}
// for(ll i=0;i<2;i++)
// {
// for(ll j=0;j<n;j++)
// {
// if(v[i][j]=='#')
// {
// cout<<bfs(i,j);
// return;
// }
// }
// }
}

int main( )
{
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}

*七、生产车间

问题描述

小明正在改造一个生产车间的生产流水线。这个车间共有

n

n

n 台设备，构成以 1 为根结点的一棵树，结点

i

i

i 有权值

w

i

w_i

wi​。

其中，叶结点的权值

w

i

w_i

wi​ 表示每单位时间产出

w

i

w_i

wi​ 单位材料并送往父结点；根结点的权值

w

i

w_i

wi​ 表示每单位时间内能打包

w

i

w_i

wi​ 单位成品； 其他结点的权值

w

i

w_i

wi​ 表示每单位时间最多能加工

w

i

w_i

wi​ 单位材料并送往父结点。

由于生产线中某些结点产能不足，导致无法正常运行，即某些结点每单位时间收到的材料超过其加工能力上限。小明计划删除一些结点使所有结点都能正常运行，想知道删除后根结点每单位时间最多能打包多少单位成品。

输入输出及限制

输入格式

输入共

n

+

1

n+1

n+1 行。

第一行为一个正整数

n

n

n.

第二行为

n

n

n 个由空格分开的正整数

w

1

,

w

2

,

…

,

w

n

w_1,w_2,…,w_n

w1​,w2​,…,wn​.

后面

n

−

1

n−1

n−1 行，每行两个整数，表示树上的一条边连接的两个结点。

输出格式

输出共一行，一个整数，表示根结点每单位时间最多能打包的成品单位数。

样例输入

9
9 7 3 7 1 6 2 2 7
1 2
1 3
2 4
2 5
2 6
6 7
6 8
6 9

样例输出

8

样例说明

删掉结点

4

,

9

4,9

4,9 后生产线满足条件，根结点

1

1

1 每单位时间将打包

8

8

8 单位成品。

评测用例规模与约定

对于

20

20%

20 的评测用例，

2

≤

n

≤

100

2≤n≤100

2≤n≤100。

对于

100

%

100\\%

100% 的评测用例，

2

≤

n

≤

1000

,

w

i

≤

1000

2≤n≤1000,w_i\\leq1000

2≤n≤1000,wi​≤1000。

运行限制

个人见解

树形

d

p

dp

dp+分组背包

比较模版的一题，up主写这题的时候一直被卡到的点其实是

d

p

dp

dp 的初始化。

下面的

A

C

AC

AC 代码中看似只对叶子结点初始化：

if(leaf[u]) //叶子节点直接更新dp后返回
{
dp[u][w[u]]=w[u]; //只有叶子节点固定产出，中间节点的加工流量初始值是0
return;
}

但其实由于数组

d

p

dp

dp 定义在全局，默认初始值为 0 。这里说下为什么要区分吧：

• 叶子节点：
  • $j<w[u]：$
  • $j\ge [u]：$
• 中间结点：
  • 还没有任何子节点贡献材料，所以无论给多少容量，能传递的都是 0 。因此该部分的数组 $dp$

AC代码(树形$dp$

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n;
ll w[1005];
vector<ll> t[1005]; //邻接表
ll sum[1005]; //真实产出
ll dp[1005][1005]; //dp[u][j]表示以u为根节点最多能处理j单位材料时，u能传递的最大流量
ll leaf[1005];

ll cal(ll u,ll fa) //初始化：叶子节点判断数组leaf，以及实际加工能力值数组sum
{
bool isleaf=true;
for(auto& son:t[u])
{
if(son==fa)continue;
isleaf=false;
sum[u]+=cal(son,u);
}

if(isleaf) //如果是叶子节点
{
sum[u]=w[u];
leaf[u]=1;
}
else sum[u]=min(sum[u],w[u]); //如果是中间节点，传送到父亲的流量不能超过加工能力

return sum[u];
}

void dfs(ll u,ll fa) //u：当前节点，fa：父节点
{
if(leaf[u]) //叶子节点直接更新dp后返回
{
dp[u][w[u]]=w[u]; //只有叶子节点固定产出，中间节点的加工流量初始值是0
return;
}

for(auto& son:t[u]) //遍历组
{
if(son==fa)continue;
dfs(son,u);

for(ll j=w[u];j>=0;j—) //遍历背包容积
{
for(ll k=min(j,sum[son]);k>=0;k—) //遍历大小，并通过实际可达到的加工值来进行剪枝
{
ll cur=min(dp[u][j–k]+dp[son][k],w[u]); //限制一下，当前最大加工值也不可超过固定值
dp[u][j]=max(dp[u][j],cur); //更新最大值
}
}
}
}

void solve()
{
cin>>n;
for(ll i=1;i<=n;i++)
{
cin>>w[i];
}
for(ll i=1;i<=n–1;i++)
{
ll a,b;
cin>>a>>b;
t[a].push_back(b);
t[b].push_back(a);
}
cal(1,–1);
dfs(1,–1);

cout<<dp[1][w[1]];
}

int main( )
{
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}

八、装修报价

问题描述

老王计划装修房子，于是联系了一家装修公司。该公司有一套自动报价系统，只需用户提供

N

N

N 项装修相关费用

A

1

,

A

2

,

…

,

A

N

A_1,A_2,…,A_N

A1​,A2​,…,AN​，系统便会根据这些费用生成最终的报价。

然而，当老王提交数据后，他发现这套系统的运作方式并不透明：系统只会给出一个最终报价，而不会公开任何运算过程或中间步骤。

公司对此解释称，这套系统会依据某种内部算法，在每对相邻数字之间插入

+

+

+（加法）、

−

−

−（减法）或

⊕

⊕

⊕（异或）运算符，并按照特定优先级规则计算总和：异或运算优先级最高，其次是加减。但由于保密性，具体的运算符组合以及中间过程都不会对外公开。

为了验证系统报价是否合理，老王决定模拟其运作方式，尝试每种可能的运算符组合，计算出所有可能出现的总和。如果最终报价明显超出这个范围，他就有理由怀疑系统存在异常或误差。只是老王年事已高，手动计算颇为吃力，便向你求助。

现在，请你帮老王算出所有可能的总和。由于该总和可能很大，你只需提供其对

10

9

+

7

10^9+7

109+7 取余后的结果即可。

输入输出及限制

输入格式

第一行输入一个整数

N

N

N，表示装修相关费用的项数。

第二行输入

N

N

N 个非负整数

A

1

,

A

2

,

…

,

A

N

A_1,A_2,…,A_N

A1​,A2​,…,AN​，表示各项费用。

输出格式

输出一个整数，表示所有可能的总和对

10

9

+

7

10^9+7

109+7 取余后的结果。

样例输入

3
0 2 5

样例输出

11

样例说明

对于输入样例中的三个数

A

=

[

0

,

2

,

5

]

A=[0,2,5]

A=[0,2,5]，所有可能的运算符组合共有

9

9

9 种。计算结果如下：

0

⊕

2

⊕

5

=

7

,

0

⊕

2

+

5

=

7

,

0

⊕

2

−

5

=

−

3

,

0

+

2

⊕

5

=

7

,

0

+

2

+

5

=

7

,

0

+

2

−

5

=

−

3

,

0

−

2

⊕

5

=

−

7

,

0

−

2

+

5

=

3

,

0

−

2

−

5

=

−

7.

0 \\oplus 2 \\oplus 5 = 7, \\ 0 \\oplus 2 + 5 = 7, \\ 0 \\oplus 2 – 5 = -3,\\\\ 0 + 2 \\oplus 5 = 7, \\ 0 + 2 + 5 = 7, \\ 0 + 2 – 5 = -3,\\\\\\ \\ \\ 0 – 2 \\oplus 5 = -7, \\ 0 – 2 + 5 = 3, \\ 0 – 2 – 5 = -7.

0⊕2⊕5=7, 0⊕2+5=7, 0⊕2−5=−3,0+2⊕5=7, 0+2+5=7, 0+2−5=−3,   0−2⊕5=−7, 0−2+5=3, 0−2−5=−7. 所有结果的总和为：

7

+

7

+

(

−

3

)

+

7

+

7

+

(

−

3

)

+

(

−

7

)

+

3

+

(

−

7

)

=

11

7+7+(−3)+7+7+(−3)+(−7)+3+(−7)=11

7+7+(−3)+7+7+(−3)+(−7)+3+(−7)=11

11

11

11 对

10

9

+

7

10^9+7

109+7 取余后的值依然为

11

11

11，因此，输出结果为

11

11

11。

评测用例规模与约定

对于

30

%

30\\%

30% 的评测用例，

1

≤

N

≤

13

1≤N≤13

1≤N≤13，

0

≤

A

i

≤

10

3

0≤A_i≤10^3

0≤Ai​≤103。

对于

60

%

60\\%

60% 的评测用例，

1

≤

N

≤

10

3

1≤N≤10^3

1≤N≤103，

0

≤

A

i

≤

10

5

0≤A_i≤10^5

0≤Ai​≤105。

对于所有评测用例，

1

≤

N

≤

10

5

，

0

≤

A

i

≤

10

9

1≤N≤10^5，0≤A_i≤10^9

1≤N≤105，0≤Ai​≤109。

运行限制

个人见解(快速幂+数学)

把所有可能的组合罗列出来之后会发现，形如

+

(

.

.

.

)

+(…)

+(…) 和

−

(

.

.

.

)

−(…)

−(…) 是会成对出现的，求和之后会抵消。因此，只有前缀全部都是异或运算，才会对结果产生贡献。

设只有异或运算的前缀为

a

1

∼

a

k

a_1∼a_k

a1​∼ak​，异或和为

s

u

m

sum

sum，此时下一个运算只能是

+

/

−

+/−

+/−，接下来的运算就是二者中任取其一，还剩余

n

−

k

−

1

n-k-1

n−k−1 个格子，每个格子有三种填法。因此，这段异或和对总结果的贡献为

s

u

m

×

2

×

3

n

−

k

−

1

sum×2×3^{n−k−1}

sum×2×3n−k−1。

注意

a

1

∼

a

n

a_1∼a_n

a1​∼an​ 这个区间只会对结果产生 1 的贡献，特殊处理一下。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll N=1e5+5;
ll n;
ll mod=1e9+7;
ll a[N];
ll ans=0;

ll qpow(ll u,ll v) //快速幂
{
ll ret=1;
while(v)
{
if(v&1)ret=(ret*u)%mod;
v>>=1;
u=(u*u)%mod;
}
return ret;
}

void solve()
{
cin>>n;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
}
ll cur=0;
for(ll i=1;i<n;i++)
{
cur=cur^a[i];
ans=(ans+(cur*2*qpow(3,n–i–1))%mod)%mod;
}
ans=(ans+(cur^a[n]))%mod;

cout<<ans;
}

int main( )
{
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}