309510: CF1691C. Sum of Substrings
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Sum of Substrings
题意翻译
## 题目描述 给定由 $0$ 和 $1$ 组成的长度为 $n$ 的字符串 $ s $ 。 定义一个十进制数字 $ d_i $ 十位和个位分别为 $ s_i $ 和 $ s_{i+1} $ 。 定义 $ f(s) $ 为所有合法的 $ d_i $ 的和。也就是说 $ f(s) = \sum\limits_{i=1}^{n-1} d_i $ 。 比如, 对于字符串 $ s = 1011 $ : - $ d_1 = 10 $ ; - $ d_2 = 01 $ ; - $ d_3 = 11 $ ; - $ f(s) = 10 + 01 + 11 = 22 $ 。 在一次操作中你可以交换两个相邻的元素。 找到经过不多于 $k$ 次操作后 $ f(s) $ 的最小值。 ## 输入格式 每个测试点有多组数据。 第一行一个整数 $t$ 表示数据个数。 接下来 $2t$ 行,每组数据 $2$ 行。 每组数据的第一行两个整数 $ n $ 和 $ k $ ( $ 2 \le n \le 10^5 $ , $ 0 \le k \le 10^9 $ ) ,分别表示字符串长度和最大操作数。 每组数据的第二行包含一个长度为 $n$ 的字符串 $ s $ (详见题目描述)。 保证所有数据中 $ n $ 的和不超过 $ 10^5 $ 。 ## 输出格式 共 $t$ 行,每一行一个整数,表示经过不多于 $k$ 次操作后 $ f(s) $ 的最小值。 ## 提示 - 对于第一组数据,不能做任何操作。$ f(s) = f(1010) = 10 + 01 + 10 = 21 $ 。 - 对于第二组数据,可以将字符串变成 $0011000$。 此时 $ f $ 的值为 $ 22 $ 。 - 对于第三组数据,可以将字符串变成 $00011$。 此时 $ f $ 的值为 $ 12 $ 。题目描述
You are given a binary string $ s $ of length $ n $ . Let's define $ d_i $ as the number whose decimal representation is $ s_i s_{i+1} $ (possibly, with a leading zero). We define $ f(s) $ to be the sum of all the valid $ d_i $ . In other words, $ f(s) = \sum\limits_{i=1}^{n-1} d_i $ . For example, for the string $ s = 1011 $ : - $ d_1 = 10 $ (ten); - $ d_2 = 01 $ (one) - $ d_3 = 11 $ (eleven); - $ f(s) = 10 + 01 + 11 = 22 $ . In one operation you can swap any two adjacent elements of the string. Find the minimum value of $ f(s) $ that can be achieved if at most $ k $ operations are allowed.输入输出格式
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^5 $ ). Description of the test cases follows. First line of each test case contains two integers $ n $ and $ k $ ( $ 2 \le n \le 10^5 $ , $ 0 \le k \le 10^9 $ ) — the length of the string and the maximum number of operations allowed. The second line of each test case contains the binary string $ s $ of length $ n $ , consisting of only zeros and ones. It is also given that sum of $ n $ over all the test cases doesn't exceed $ 10^5 $ .
输出格式
For each test case, print the minimum value of $ f(s) $ you can obtain with at most $ k $ operations.
输入输出样例
输入样例 #1
3
4 0
1010
7 1
0010100
5 2
00110
输出样例 #1
21
22
12
说明
- For the first example, you can't do any operation so the optimal string is $ s $ itself. $ f(s) = f(1010) = 10 + 01 + 10 = 21 $ . - For the second example, one of the optimal strings you can obtain is "0011000". The string has an $ f $ value of $ 22 $ . - For the third example, one of the optimal strings you can obtain is "00011". The string has an $ f $ value of $ 12 $ .Input
题意翻译
## 题目描述 给定由 $0$ 和 $1$ 组成的长度为 $n$ 的字符串 $ s $ 。 定义一个十进制数字 $ d_i $ 十位和个位分别为 $ s_i $ 和 $ s_{i+1} $ 。 定义 $ f(s) $ 为所有合法的 $ d_i $ 的和。也就是说 $ f(s) = \sum\limits_{i=1}^{n-1} d_i $ 。 比如, 对于字符串 $ s = 1011 $ : - $ d_1 = 10 $ ; - $ d_2 = 01 $ ; - $ d_3 = 11 $ ; - $ f(s) = 10 + 01 + 11 = 22 $ 。 在一次操作中你可以交换两个相邻的元素。 找到经过不多于 $k$ 次操作后 $ f(s) $ 的最小值。 ## 输入格式 每个测试点有多组数据。 第一行一个整数 $t$ 表示数据个数。 接下来 $2t$ 行,每组数据 $2$ 行。 每组数据的第一行两个整数 $ n $ 和 $ k $ ( $ 2 \le n \le 10^5 $ , $ 0 \le k \le 10^9 $ ) ,分别表示字符串长度和最大操作数。 每组数据的第二行包含一个长度为 $n$ 的字符串 $ s $ (详见题目描述)。 保证所有数据中 $ n $ 的和不超过 $ 10^5 $ 。 ## 输出格式 共 $t$ 行,每一行一个整数,表示经过不多于 $k$ 次操作后 $ f(s) $ 的最小值。 ## 提示 - 对于第一组数据,不能做任何操作。$ f(s) = f(1010) = 10 + 01 + 10 = 21 $ 。 - 对于第二组数据,可以将字符串变成 $0011000$。 此时 $ f $ 的值为 $ 22 $ 。 - 对于第三组数据,可以将字符串变成 $00011$。 此时 $ f $ 的值为 $ 12 $ 。Output
题目大意:
给定一个由0和1组成的长度为n的字符串s。定义一个十进制数字di,十位和个位分别为si和si+1。定义f(s)为所有合法的di的和,即f(s)=Σdi (i从1到n-1)。每次操作可以交换两个相邻的元素。求经过不多于k次操作后f(s)的最小值。
输入数据格式:
第一行一个整数t表示数据个数。
接下来2t行,每组数据2行。
每组数据的第一行两个整数n和k (2≤n≤10^5, 0≤k≤10^9),分别表示字符串长度和最大操作数。
每组数据的第二行包含一个长度为n的字符串s(详见题目描述)。
保证所有数据中n的和不超过10^5。
输出数据格式:
共t行,每一行一个整数,表示经过不多于k次操作后f(s)的最小值。
例如:
输入:
3
4 0
1010
7 1
0010100
5 2
00110
输出:
21
22
12题目大意: 给定一个由0和1组成的长度为n的字符串s。定义一个十进制数字di,十位和个位分别为si和si+1。定义f(s)为所有合法的di的和,即f(s)=Σdi (i从1到n-1)。每次操作可以交换两个相邻的元素。求经过不多于k次操作后f(s)的最小值。 输入数据格式: 第一行一个整数t表示数据个数。 接下来2t行,每组数据2行。 每组数据的第一行两个整数n和k (2≤n≤10^5, 0≤k≤10^9),分别表示字符串长度和最大操作数。 每组数据的第二行包含一个长度为n的字符串s(详见题目描述)。 保证所有数据中n的和不超过10^5。 输出数据格式: 共t行,每一行一个整数,表示经过不多于k次操作后f(s)的最小值。 例如: 输入: 3 4 0 1010 7 1 0010100 5 2 00110 输出: 21 22 12
给定一个由0和1组成的长度为n的字符串s。定义一个十进制数字di,十位和个位分别为si和si+1。定义f(s)为所有合法的di的和,即f(s)=Σdi (i从1到n-1)。每次操作可以交换两个相邻的元素。求经过不多于k次操作后f(s)的最小值。
输入数据格式:
第一行一个整数t表示数据个数。
接下来2t行,每组数据2行。
每组数据的第一行两个整数n和k (2≤n≤10^5, 0≤k≤10^9),分别表示字符串长度和最大操作数。
每组数据的第二行包含一个长度为n的字符串s(详见题目描述)。
保证所有数据中n的和不超过10^5。
输出数据格式:
共t行,每一行一个整数,表示经过不多于k次操作后f(s)的最小值。
例如:
输入:
3
4 0
1010
7 1
0010100
5 2
00110
输出:
21
22
12题目大意: 给定一个由0和1组成的长度为n的字符串s。定义一个十进制数字di,十位和个位分别为si和si+1。定义f(s)为所有合法的di的和,即f(s)=Σdi (i从1到n-1)。每次操作可以交换两个相邻的元素。求经过不多于k次操作后f(s)的最小值。 输入数据格式: 第一行一个整数t表示数据个数。 接下来2t行,每组数据2行。 每组数据的第一行两个整数n和k (2≤n≤10^5, 0≤k≤10^9),分别表示字符串长度和最大操作数。 每组数据的第二行包含一个长度为n的字符串s(详见题目描述)。 保证所有数据中n的和不超过10^5。 输出数据格式: 共t行,每一行一个整数,表示经过不多于k次操作后f(s)的最小值。 例如: 输入: 3 4 0 1010 7 1 0010100 5 2 00110 输出: 21 22 12