307657: CF1392A. Omkar and Password

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Omkar and Password

题意翻译

### 题目描述 多组询问,每次给出一个长度为 $n$ 的序列 $a$,对于两个相邻的且不相同的数,你可以将他们合并起来,即将这两个数替换成它们的和。 注意到,你每次进行一次操作后,序列长度会 $-1$,现在你可以随意进行若干次操作,问最后序列长度最短是多少。

题目描述

Lord Omkar has permitted you to enter the Holy Church of Omkar! To test your worthiness, Omkar gives you a password which you must interpret! A password is an array $ a $ of $ n $ positive integers. You apply the following operation to the array: pick any two adjacent numbers that are not equal to each other and replace them with their sum. Formally, choose an index $ i $ such that $ 1 \leq i < n $ and $ a_{i} \neq a_{i+1} $ , delete both $ a_i $ and $ a_{i+1} $ from the array and put $ a_{i}+a_{i+1} $ in their place. For example, for array $ [7, 4, 3, 7] $ you can choose $ i = 2 $ and the array will become $ [7, 4+3, 7] = [7, 7, 7] $ . Note that in this array you can't apply this operation anymore. Notice that one operation will decrease the size of the password by $ 1 $ . What is the shortest possible length of the password after some number (possibly $ 0 $ ) of operations?

输入输出格式

输入格式


Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). Description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the length of the password. The second line of each test case contains $ n $ integers $ a_{1},a_{2},\dots,a_{n} $ ( $ 1 \leq a_{i} \leq 10^9 $ ) — the initial contents of your password. The sum of $ n $ over all test cases will not exceed $ 2 \cdot 10^5 $ .

输出格式


For each password, print one integer: the shortest possible length of the password after some number of operations.

输入输出样例

输入样例 #1

2
4
2 1 3 1
2
420 420

输出样例 #1

1
2

说明

In the first test case, you can do the following to achieve a length of $ 1 $ : Pick $ i=2 $ to get $ [2, 4, 1] $ Pick $ i=1 $ to get $ [6, 1] $ Pick $ i=1 $ to get $ [7] $ In the second test case, you can't perform any operations because there is no valid $ i $ that satisfies the requirements mentioned above.

Input

题意翻译

### 题目描述 多组询问,每次给出一个长度为 $n$ 的序列 $a$,对于两个相邻的且不相同的数,你可以将他们合并起来,即将这两个数替换成它们的和。 注意到,你每次进行一次操作后,序列长度会 $-1$,现在你可以随意进行若干次操作,问最后序列长度最短是多少。

加入题单

上一题 下一题 算法标签: