本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-29 20:38:14

测试说明：

• 0. 2023班做A-D，78级做B-F

• 1.每人建立自己的名字命名的考试文件夹，里面放对应的A.CPP,B.CPP等（大小写均可）。

• 2.不用文件输入输出。

• 3.完成后通过极域学生端提交自己的试题文件夹。

A： 翻转求和

题目描述

给你一个$n$，让你求出从$1$到$n$的和，但是其中每当遇到一个数是$2$的次幂时，就要变加为减。例如输入$n=4$，那么计算算式为-1-2+3-4=-4，因为$1$是$2^0$，$2$是$2^1$，$4$是$2^2$。 该题目有$T$组数据。

输入格式

第一行给出数据组数 $ T $ ( $ 1<=T<=100 $ ),接下来$T$行，每行一个整数$n$( $ 1\leq n\leq10^{9} $ ).

输出格式

共 $ T $行，每行表示$ 1 $到$ n$在$2$的幂次取反后的和。

样例 #1

样例输入 #1

2
4
1000000000

样例输出 #1

-4
499999998352516354

数据范围

对于$100\%$的数据范围，$ 1<=T<=100 $ ,$1\leq n\leq10^{9} $

B 字符串循环移位

题目描述

给你一个字符串$s$，接着有$m$次循环移位。

循环移位的一个操作就是将$s$的最后一个字符移动到第一个字符的位置，并且将所有其他的字符向右移动一个位置。

例如，$s='abacaba'$，查询是$L_1=3，R_1=6，K_1=1$，那么答案是$’abbacaa’$。循环移位的过程是从$s$第三个位置到第六个位置$’acab’$，循环$1$次，把$b$移到第一位，其他往后移一位，就是$’baca’$，替换之前的$’acab’$，之后如果我们再做处理$L_2=1，R_2=4，K_2=2$，那么答案就变$’baabcaa’$。循环移位的过程是：首先从第一个位置到第四个位置$’abba’$，第一次通过移位得到$’aabb’$，第二次就得到$’baab’$，替换之前的$’abba’$。

输入格式

第一行一个字符串$s$,$(1 \leq |s|\leq10000)$，$s$全是小写字母；

第二行一个整数$m$，有$m$次操作；

接下来有$m$行，包含三个整数$L_i，R_i， K_i（1<=L_i<=R_i<=|s|，K_i<=1000000）$。

输出格式

输出经过$m$个操作后的$s$。

样例 #1

样例输入 #1

abacaba
2
3 6 1
1 4 2

样例输出 #1

baabcaa

数据范围

对于$100\%$的数据范围， $ 1<=m<=300 $， $ 1<=l_{i}<=r_{i}<=|s|,1<=k_{i}<=1000000 $

C 参观博物馆

题目描述

小容到博物馆里看画,博物馆是一个$n·m $的区域$，'.'表示可以走的房间,'*'表示墙。

每个房间都是矩形，最多可能有四面墙。每面墙上贴有一幅画，每个四联通的 ' .'区域是一个展馆，小容参观了$k$个展馆。现在给出小容的位置，求他在每个展馆最多看到多少幅画？

输入格式

第一行$3$个整数 $ n $ , $ m $ 和 $ k $ ,分别表示博物馆区域 和小容可能出现位置的个数.

接下来 $ n $行，每行 $ m $ 个 '.', '\*' 表示博物馆的布局。

接下来 $ k $ 行，每行包含两个整数 $ x $ 和 $ y $ , $ 1\leq x \leq n,1\leq y \leq m $ ) 表示小容所在的位置.

输出格式

输出 $ k $ 个整数 ，表示小容在每个展厅可能看到最多所少幅画。

样例 #1

样例输入 #1

5 6 3
******
*..*.*
******
*....*
******
2 2
2 5
4 3

样例输出 #1

6
4
10

样例 #2

样例输入 #2

4 4 1
****
*..*
*.**
****
3 2

样例输出 #2

8

样例解释 #2

第三行第三列的分别在不同方向的房间上各挂一幅画。所以总共是$8$。

数据范围

对于$100 \%$的数据， $ 3 \leq n,m\leq1000,1\leq k \leq min(n·m,100000) $

D 开灯

题目描述

农夫约翰试图让奶牛玩智力玩具来保持它们的敏锐。谷仓里的灯是较大的玩具之一。$N (2 \le N \le 10^5)$ 个牛栏编号为 $1 \ldots N$，每个牛栏上面都有一盏灯。起初所有的灯都关着。

共有 $M$ 次操作，分为两种。

1. 指定一个区间 $[S_i,E_i]$，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开）；
2. 指定一个区间 $[S_i,E_i]$，要求你输出这个区间内有多少盏灯是打开的。

输入格式

第 $1$ 行: 用空格隔开的两个整数 $N$ 和 $M$，$N$ 是灯数。

第 $2\ldots M+1$ 行: 每行表示一个操作, 有三个用空格分开的整数: 指令号, $S_i$ 和 $E_i$。

若指令号为 $0$，则表示改变 $[S_i,E_i]$ 区间内的灯的状态（把开着的灯关上，关着的灯打开）。

若指令号为 $1$，则表示输出 $[S_i,E_i]$ 这个区间内有多少盏灯是打开的。

输出格式

样例 #1

样例输入 #1

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

样例输出 #1

1
2

提示

E 苹果树

题面翻译

题目描述

给你一棵有 $n$ 个节点的苹果树，下标从 $0$ 开始。

第 $i$ 个节点可以为白色或黑色，其中至少有一个节点为黑色。

现在你可以从中删去若干条边，使得剩下的每个部分恰有一个黑色节点。

问有多少种符合条件的删边方法，答案对 $10^9+7$ 取模。

输入格式

第一行一个整数 $n(1\leq n\leq 10^5)$，表示节点个数。

接下来一行 $n-1$ 个整数 $(p_0,p_1,\cdots,p_{n-2},0\leq p_i\leq i)$，表示树中有一条连接节点 $p_i$ 和节点 $i+1$ 的边。

接下来一行 $n$ 个整数 $(x_0,x_1,\cdots,x_{n-1},0\leq x_i\leq 1)$，若 $x_i$ 为 $1$，则节点 $i$ 为黑色，否则为白色。

输出格式

第一行一个整数，表示符合条件的删边方法的方案数对 $10^9+7$ 取模后的值。

样例 #1

样例输入 #1

3
0 0
0 1 1

样例输出 #1

2

样例 #2

样例输入 #2

6
0 1 1 0 4
1 1 0 0 1 0

样例输出 #2

1

样例 #3

样例输入 #3

10
0 1 2 1 4 4 4 0 8
0 0 0 1 0 1 1 0 0 1

样例输出 #3

27

数据范围

对于$100\%$的数据范围，$ 2\leq n\leq 10^{5} $ ，$ (0\leq k<n) $

$(p_0,p_1,\cdots,p_{n-2},0\leq p_i\leq i)$

F 吃巧克力

题目描述

你有一块长方形的巧克力，这块巧克力共有$n*m$小块。你想吃$k$小块巧克力，因此你也许需要掰开这块巧克力。

在每一次操作中你可以把任意一块矩形形状的巧克力掰成两块矩形形状的巧克力。你只能沿着巧克力小块之间的分割线掰开巧克力——可以沿着水平方向或是竖直方向掰开。掰开巧克力的花费等于分割线长度的平方。

例如，如果你有一块$23$的巧克力，那么你可以沿着水平方向掰从而得到两块$13$的巧克力，这次操作的花费即为$3^2=9$。或者你也可以沿着竖直方向掰从而得到一块$21$的巧克力和一块$22$的巧克力，这次操作的花费即为$2^2=4$。

对于每一个给出的$n，m$和$k$，计算出最小花费。你可以用多块巧克力凑出$k$小块巧克力。剩余的巧克力可以不是完整的一块。

输入格式

输入数据的第一行包括1个整数$t(1<=t<=40910)$，表示数据组数。

接下来的$t$行每一行都包含$3$个整数$n，m$和$k(1<=n,m<=30,1<=k<=min(n*m,50))$，其意义见上文。

输出格式

输出t行，分别表示每一组数据的最小花费。

样例 #1

样例输入 #1

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

样例输出 #1

5
5
4
0

提示

在样例一的第1行这组数据情况下一共需要进行$2$次操作： 1.把$22$的巧克力掰成两块$21$的巧克力，花费为$2^2=4$；

2.把$21$的巧克力掰成两块$11$的巧克力，花费为$1^2=1$。

在样例一的第2行这组数据情况下操作步骤同上。

数据范围

对于$100\%$的数据范围,$1<=t<=40910,1<=n,m<=30,1<=k<=min(n*m,50)$