Nezzar and Colorful Balls

2024-01-04 08:38
文章标签 colorful balls nezzar

本文主要是介绍Nezzar and Colorful Balls,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:
Nezzar has n balls, numbered with integers 1,2,…,n. Numbers a1,a2,…,an are written on them, respectively. Numbers on those balls form a non-decreasing sequence, which means that ai≤ai+1 for all 1≤i<n.

Nezzar wants to color the balls using the minimum number of colors, such that the following holds.

For any color, numbers on balls will form a strictly increasing sequence if he keeps balls with this chosen color and discards all other balls.
Note that a sequence with the length at most 1 is considered as a strictly increasing sequence.

Please help Nezzar determine the minimum number of colors.

Input
The first line contains a single integer t (1≤t≤100) — the number of testcases.

The first line of each test case contains a single integer n (1≤n≤100).

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤n). It is guaranteed that a1≤a2≤…≤an.

Output
For each test case, output the minimum number of colors Nezzar can use.

Example
inputCopy
5
6
1 1 1 2 3 4
5
1 1 2 2 3
4
2 2 2 2
3
1 2 3
1
1
outputCopy
3
2
4
1
1
Note
Let’s match each color with some numbers. Then:

In the first test case, one optimal color assignment is [1,2,3,3,2,1].

In the second test case, one optimal color assignment is [1,2,1,2,1].

题解:

#include <bits/stdc++.h>
using namespace std;
int a[200];
int main()
{int t;cin>>t;while(t--){int b[200]={0};int n;cin>>n;int ans=-1;for(int i=0;i<n;i++){scanf("%d",&a[i]);b[a[i]]++;if(b[a[i]]>ans) ans=b[a[i]];}cout<<ans<<endl;}return 0;
}

这篇关于Nezzar and Colorful Balls的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/568753

相关文章

【HDU】5574 Colorful Tree【子树染色,询问子树颜色数——线段树+bit+lca+set】

题目链接:【HDU】5574 Colorful Tree 题目大意:对一个子树染色,询问一个子树的颜色数。 题目分析: set set维护每种颜色所在的 dfs dfs序区间,修改均摊 nlogn nlogn。 #include <bits/stdc++.h>using namespace std ;typedef long long LL ;typedef pair < int , i

poj 3687 Labeling Balls(拓扑排序)

http://poj.org/problem?id=3687 非常坑的一道题,最后快要绕晕了。。 题意:有N个球,重量分别是1~N,给着n个球贴上标签。输入n,m代表n个球和m条边(a b),代表 标签为a的要比标签为b的轻。最后输出标签1~N对应的重量(注意是重量,而不是轻重关系),还有要注意“ you should output the one with the smallest weig

HDU 3635 Dragon Balls(带权并查集)

题目地址:HDU 3635 加权并查集水题。 用num数组维护该城市有多少龙珠,用times数组维护每个龙珠运输了多少次。num数组在合并的时候维护。times数组由于每个都不一样,所以要在找根的时候递归来全部维护。 最终,x龙珠所在的城市就是x节点所在的根,x结点所在的跟的num数组值是该城市的龙珠数。times[x]为该龙珠运输了多少次。 代码如下: #include <iost

hdu 4611 Balls Rearrangement(数学:推理+模拟)

一道很蛋疼的题 列出几组数据会发现是有规律的 一个数字可能会连续出现多次 虽然发现了规律,但是不知道该怎么写 看了大牛的博客。。。也是醉了 因为一个最小公倍数周期内结果是固定的,所以如果n>lcm,可以优化处理 这道题比较奇葩的地方是用scanf就wa,用cin就过了 代码如下: #include <cstdio>#include <iostream>#include <a

hdu3635Dragon Balls

并查集 对于转移次数,开始我自以为想出了一个效率很高的解法,就是在路径压缩的时候统计结点所在的层数,加到该结点的times值里面,也就是这样:  自己感觉还很良好,因为这样效率和原来几乎差不多,交上去却wa,原来,是没有考虑这样的情况: 如果在结点E或F进行查找并且压缩路径,就会成为这样(以find(e)为例): 这样在这里得到的C B E F的time

codeforces 553A Kyoya and Colored Balls 组合数学

题意: 有k种球,每种球有a[i]个。现在它们都放到一个袋子里,要求取出来的时候,第i种球完全取出来要在第i+1种球前面。问你有多少种取法。 思路: 比赛时没想出来。。。结果其实是很简单的。 倒过来统计就好了。 假设n = sum(a[i]); 首先先看第k种球,如果先把其中一个球放到最后一个位置,那么剩下的a[k]-1个球就是随便放,则有c[n-1][a[k]-1]种放法。

Poj 3687 Labeling Balls[拓扑排序]

题目链接:点击打开链接 很给力的道题,拓扑排序的应用,算是对TopSort认识更深了吧。 拓扑排序这里不做过多的解释,主要来说这道题的应用。 题目的意思就是给1——N质量的N个球贴标签,要求就是满足要求下的标签小的尽量轻。 没什么深入想,直接TopSort。果断WA,WA的。后来看题,发现了很多的问题。输出的是Label1-LabelN标签的重量。还有很多的问题没有看太清晰。 再看了几

hdu 5570 balls(高效)

题目链接:hdu 5570 balls 代码 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 1005;int N, M;double A[maxn][maxn];int main () {while (scanf("%d%d", &N, &M) ==

dp + 计数,1954D - Colored Balls

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 Problem - 1954D - Codeforces 二、解题报告 1、思路分析 本题前置题目: 1953. 你可以工作的最大周数 通过前置题目可以知道如何计算两两不同数对序列的最大长度 我们记最大数量为ma,总数目为N 如果ma > N / 2, 那么划

[ABC215G]Colorful Candies 2

Colorful Candies 2 题解 首先对于一个球,它对答案产生贡献当且仅当有至少一个它这种颜色的球被选中。 我们记颜色为 i i i的球有 c i c_{i} ci​个,当我们选择 j j j个时,我们可以用容斥的方法的到它被选择的概率, ( n j ) − ( n − c i j ) ( n j ) \frac{\binom{n}{j}-\binom{n-c_{i}}{j}}{\b