ACM-ICPC 2018 徐州赛区网络赛 F. Features Track(哈希+暴力)

2024-04-09 12:58

本文主要是介绍ACM-ICPC 2018 徐州赛区网络赛 F. Features Track(哈希+暴力),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Morgana is learning computer vision, and he likes cats, too. One day he wants to find the cat movement from a cat video. To do this, he extracts cat features in each frame. A cat feature is a two-dimension vector <xx, yy>. If x_ixi​= x_jxj​ and y_iyi​ = y_jyj​, then <x_ixi​, y_iyi​> <x_jxj​, y_jyj​> are same features.

So if cat features are moving, we can think the cat is moving. If feature <aa, bb> is appeared in continuous frames, it will form features movement. For example, feature <aa , bb > is appeared in frame 2,3,4,7,82,3,4,7,8, then it forms two features movement 2-3-42−3−4 and 7-87−8 .

Now given the features in each frames, the number of features may be different, Morgana wants to find the longest features movement.

Input

First line contains one integer T(1 \le T \le 10)T(1≤T≤10) , giving the test cases.

Then the first line of each cases contains one integer nn (number of frames),

In The next nn lines, each line contains one integer k_iki​ ( the number of features) and 2k_i2ki​ intergers describe k_iki​features in ith frame.(The first two integers describe the first feature, the 33rd and 44th integer describe the second feature, and so on).

In each test case the sum number of features NN will satisfy N \le 100000N≤100000 .

Output

For each cases, output one line with one integers represents the longest length of features movement.

样例输入复制

1
8
2 1 1 2 2
2 1 1 1 4
2 1 1 2 2
2 2 2 1 4
0
0
1 1 1
1 1 1

样例输出复制

3

题目来源

ACM-ICPC 2018 徐州赛区网络预赛

 

题意:

给了N个集合,每个集合都有许多的二维向量,如果存在一个向量在两个不同的集合中则可以看出是连续的。问最多有多少个连续的相等的集合。

 

思路:

将二维的向量哈希转化成数字存入集合中,判断每个元素连续出现的次数,判断完了之后就将这些元素删除,避免查找的时候会超时。

 

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
set<ll> se[maxn];
set<ll> ::iterator it,itt;
int main()
{int t,n,k,x,y,ans;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&k);for(int j=1;j<=k;j++){scanf("%d%d",&x,&y);se[i].insert((ll)x*(100007)+y*(11));}}ans=0;for(int i=1;i<=n;i++){if(se[i].size()==0)continue;while((it=se[i].begin())!=se[i].end()){it=se[i].begin();int cnt=1;for(int j=i+1;j<=n;j++){if((itt=se[j].find(*it))!=se[j].end()){cnt++;se[j].erase(itt);}else{ans=max(ans,cnt);break;}}se[i].erase(it);}}printf("%d\n",ans);}return 0;
}

 

这篇关于ACM-ICPC 2018 徐州赛区网络赛 F. Features Track(哈希+暴力)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp

Linux系统之主机网络配置方式

《Linux系统之主机网络配置方式》:本文主要介绍Linux系统之主机网络配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、查看主机的网络参数1、查看主机名2、查看IP地址3、查看网关4、查看DNS二、配置网卡1、修改网卡配置文件2、nmcli工具【通用

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解

如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别详解

《如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别详解》:本文主要介绍如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别的相关资料,描述了如何使用海康威视设备网络SD... 目录前言开发流程问题和解决方案dll库加载不到的问题老旧版本sdk不兼容的问题关键实现流程总结前言作为

SSID究竟是什么? WiFi网络名称及工作方式解析

《SSID究竟是什么?WiFi网络名称及工作方式解析》SID可以看作是无线网络的名称,类似于有线网络中的网络名称或者路由器的名称,在无线网络中,设备通过SSID来识别和连接到特定的无线网络... 当提到 Wi-Fi 网络时,就避不开「SSID」这个术语。简单来说,SSID 就是 Wi-Fi 网络的名称。比如

Java实现任务管理器性能网络监控数据的方法详解

《Java实现任务管理器性能网络监控数据的方法详解》在现代操作系统中,任务管理器是一个非常重要的工具,用于监控和管理计算机的运行状态,包括CPU使用率、内存占用等,对于开发者和系统管理员来说,了解这些... 目录引言一、背景知识二、准备工作1. Maven依赖2. Gradle依赖三、代码实现四、代码详解五

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。