当前位置: 代码迷 >> 综合 >> ACM-ICPC 2018 徐州赛区网络预赛F. Features Track (数据结构map的使用)
  详细解决方案

ACM-ICPC 2018 徐州赛区网络预赛F. Features Track (数据结构map的使用)

热度:29   发布时间:2023-11-15 16:00:15.0

题目链接:https://nanti.jisuanke.com/t/31458

#include<bits/stdc++.h>
#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define read(x,y) scanf("%d%d",&x,&y)#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long
const int  maxn =1e5+5;
const int mod=1e9+7;
ll powmod(ll x,ll y) {ll t;for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod;return t;}
ll gcd(ll x,ll y)  {  return y==0?x:gcd(y,x%y); }
/*
题目大意:这道题太Codeforces了。
就是给定n个frame ,每个都有k个feature,
然后求连续出现的feature段的长度。不难想到类比整数序列,
用map<node,int>来模拟Dp数组,
几个点注意,重载结构体比较符号大小时必须严格按照第一顺序和第二顺序,
不能像我一样直接随便拟定个顺序。
还有就是,遇到零时数据结构全部清空,答案重新开始计算。
*/
int n,k;
struct node
{int x,y;node(int xx=0,int yy=0){x=xx;y=yy;}bool operator<(const node& q) const{if(x==q.x) return y<q.y;return x<q.x;}bool operator==(const node& q)const{return x==q.x&&y==q.y;}
};
map<node,int> mp1,mp2;
int ans,x,y;
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d",&n);ans=0;mp1.clear();mp2.clear();for(int i=1;i<=n;i++){scanf("%d",&k);if(k==0)  {mp1.clear();mp2.clear(); }for(int j=0;j<k;j++){scanf("%d%d",&x,&y);///该连续段的出现位置int &t=mp1[node(x,y)];if(t==i-1)mp2[node(x,y)]++;else if(t!=i)///如果还在这个frame里出现过,则不进行任何修改mp2[node(x,y)]=1;t=i;  ans=max(ans,mp2[node(x,y)]);}}printf("%d\n",ans);}return 0;
}

 

  相关解决方案