Codeforces 1398 C-Good Subarrays(区間値0の個数変形-思考)
8685 ワード
タイトルリンク:https://codeforces.com/problemset/problem/1398/Cブログ園食用リンク:https://www.cnblogs.com/lonely-wind-/p/13509265.html
You are given an array a 1 , a 2 , … , a n a_1,a_2,…,a_n a1,a2,…,an consisting of integers from 0 to 9. A subarray a l , a l + 1 , a l + 2 , … , a r − 1 a_l,a_{l+1},a_{l+2},…,a_{r−1} al,al+1,al+2,…,ar−1,ar is good if the sum of elements of this subarray is equal to the length of this subarray ∑ i = l r a i = r − l + 1\sum_{i=l}^ra_i=r-l+1 ∑i=lrai=r−l+1.
For example, if a=[1,2,0], then there are 3 good subarrays: a 1 … 1 = [ 1 ] , a 2 … 3 = [ 2 , 0 ] a_{1…1}=[1],a_{2…3}=[2,0] a1…1=[1],a2…3=[2,0] and a 1 … 3 = [ 1 , 2 , 0 ] a_{1…3}=[1,2,0] a1…3=[1,2,0].
Calculate the number of good subarrays of the array a.
Input The first line contains one integer t (1≤t≤1000) — the number of test cases.
The first line of each test case contains one integer n ( 1 ≤ n ≤ 1 0 5 ) n (1≤n≤10^5) n(1≤n≤105) — the length of the array a.
The second line of each test case contains a string consisting of n decimal digits, where the i-th digit is equal to the value of a i a_i ai.
It is guaranteed that the sum of n over all test cases does not exceed 1 0 5 10^5 105.
Output For each test case print one integer — the number of good subarrays of the array a.
input 3 3 120 5 11011 6 600005 output 3 6 1
Note The first test case is considered in the statement.
In the second test case, there are 6 good subarrays: a 1 … 1 , a 2 … 2 , a 1 … 2 , a 4 … 4 , a 5 … 5 a_{1…1}, a_{2…2}, a_{1…2}, a_{4…4}, a_{5…5} a1…1,a2…2,a1…2,a4…4,a5…5 and a 4 … 5 a_{4…5} a4…5.
In the third test case there is only one good subarray: a 2 … 6 a_{2…6} a2…6.
文字列のシーケンスをあげます.区間内の各要素の和が区間長になるように、どのくらいの区間があるかを見つける必要があります.
emmm,その公式については,その区間の平均値が1であることが容易に示され,各数−1を別のものに変更した:区間と値が0のものが何個あるかを求める.では、各接頭辞と出現回数を記録するだけでよい.すなわち、1つの接頭辞と、2回目に出現した場合、0を構成する区間が必ず存在することを説明することができる.では、毎回現れる回数を加えるだけでいいです.
以下はACコードです.
You are given an array a 1 , a 2 , … , a n a_1,a_2,…,a_n a1,a2,…,an consisting of integers from 0 to 9. A subarray a l , a l + 1 , a l + 2 , … , a r − 1 a_l,a_{l+1},a_{l+2},…,a_{r−1} al,al+1,al+2,…,ar−1,ar is good if the sum of elements of this subarray is equal to the length of this subarray ∑ i = l r a i = r − l + 1\sum_{i=l}^ra_i=r-l+1 ∑i=lrai=r−l+1.
For example, if a=[1,2,0], then there are 3 good subarrays: a 1 … 1 = [ 1 ] , a 2 … 3 = [ 2 , 0 ] a_{1…1}=[1],a_{2…3}=[2,0] a1…1=[1],a2…3=[2,0] and a 1 … 3 = [ 1 , 2 , 0 ] a_{1…3}=[1,2,0] a1…3=[1,2,0].
Calculate the number of good subarrays of the array a.
Input The first line contains one integer t (1≤t≤1000) — the number of test cases.
The first line of each test case contains one integer n ( 1 ≤ n ≤ 1 0 5 ) n (1≤n≤10^5) n(1≤n≤105) — the length of the array a.
The second line of each test case contains a string consisting of n decimal digits, where the i-th digit is equal to the value of a i a_i ai.
It is guaranteed that the sum of n over all test cases does not exceed 1 0 5 10^5 105.
Output For each test case print one integer — the number of good subarrays of the array a.
input 3 3 120 5 11011 6 600005 output 3 6 1
Note The first test case is considered in the statement.
In the second test case, there are 6 good subarrays: a 1 … 1 , a 2 … 2 , a 1 … 2 , a 4 … 4 , a 5 … 5 a_{1…1}, a_{2…2}, a_{1…2}, a_{4…4}, a_{5…5} a1…1,a2…2,a1…2,a4…4,a5…5 and a 4 … 5 a_{4…5} a4…5.
In the third test case there is only one good subarray: a 2 … 6 a_{2…6} a2…6.
文字列のシーケンスをあげます.区間内の各要素の和が区間長になるように、どのくらいの区間があるかを見つける必要があります.
emmm,その公式については,その区間の平均値が1であることが容易に示され,各数−1を別のものに変更した:区間と値が0のものが何個あるかを求める.では、各接頭辞と出現回数を記録するだけでよい.すなわち、1つの接頭辞と、2回目に出現した場合、0を構成する区間が必ず存在することを説明することができる.では、毎回現れる回数を加えるだけでいいです.
以下はACコードです.
#include
",ans);
}
return 0;
}