WFYZ-阶段测试20240330
wflengxuenong
·
·
个人记录
测试说明：
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 次操作，分为两种。
- 指定一个区间 [S_i,E_i]，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开）；
- 指定一个区间 [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
提示
| 数据点编号 |
N |
M |
| 1\sim 2 |
\le 100 |
\le 100 |
| 3\sim 4 |
\le 1000 |
\le 1000 |
| 5\sim 6 |
\le 10000 |
\le 10000 |
| 7\sim 8 |
\le 10^5 |
\le 100 |
| 9\sim 10 |
\le 100 |
\le 10^5 |
| 11\sim 12 |
\le 1000 |
\le 10^5 |
| 13\sim 14 |
\le 10^5 |
\le 1000 |
| 15\sim 16 |
\le 10000 |
\le 10000 |
| 17\sim 18 |
\le 10 |
\le 10^5 |
| 19\sim 20 |
\le 2000 |
\le 10^6 |
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小块巧克力，因此你也许需要掰开这块巧克力。
在每一次操作中你可以把任意一块矩形形状的巧克力掰成两块矩形形状的巧克力。你只能沿着巧克力小块之间的分割线掰开巧克力——可以沿着水平方向或是竖直方向掰开。掰开巧克力的花费等于分割线长度的平方。
例如，如果你有一块2*3的巧克力，那么你可以沿着水平方向掰从而得到两块1*3的巧克力，这次操作的花费即为3^2=9。或者你也可以沿着竖直方向掰从而得到一块2*1的巧克力和一块2*2的巧克力，这次操作的花费即为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.把2*2的巧克力掰成两块2*1的巧克力，花费为2^2=4；
2.把2*1的巧克力掰成两块1*1的巧克力，花费为1^2=1。
在样例一的第2行这组数据情况下操作步骤同上。
数据范围
对于100\%的数据范围,1<=t<=40910,1<=n,m<=30,1<=k<=min(n*m,50)