FZU2192 位置信息挖掘

FZU2192 位置信息挖掘 Problem Description  题目链接

O2O即Online To Offline,是指将线下的商务机会与互联网结合,让互联网成为线下交易的前台。这些商务机会主要是偏服务类的商品,例如汽车售后服务、摄影服务、餐饮、电影等,其特色是线上购买、线下服务。

因此,对这类垂直行业的商品做移动推荐时,用户和商品的位置信息显得格外重要。但是,可能存在用户、商品的位置信息缺失的情况,例如:用户不共享位置信息、商家未填写位置信息……

现在,Jason给出用户在移动端的购买行为数据,以及商品集合,希望能补全一些缺失的位置信息。为了简化问题,假设:

1、由于是服务类的商品,如果用户位于城市A,那么该用户只会购买位于城市A的商品。

2、数据不存在噪声,即测试数据都是合法的。

FZU2192 位置信息挖掘 Input

包含多组数据

每组输入数据格式如下:

第一行,三个数:N、M、Q,表示N个商品,M条购买行为数据,Q个询问。

接下来N行,每行两个数:itemId、cityId,表示商家填写的服务itemId,位于城市cityId。

接下来M行,每行三个数:userId、itemId、cityId,表示用户userId购买了服务itemId,移动端定位城市cityId。

接下来Q行,每行两个数:0、itemId或者1、userId,表示询问服务itemId所在的城市,或者用户userId所在的城市。

注意:0表示位置信息缺失。

FZU2192 位置信息挖掘 Output

每组输出数据格式如下: Q行,每行一个数:cityId,表示服务itemId位于cityId,或者用户userId位于cityId。

FZU2192 位置信息挖掘 Sample Input

3 2 5 2 0 3 0 1 3 2 2 2 1 1 0 0 1 0 2 0 3 1 1 1 2

FZU2192 位置信息挖掘 Sample Output

3 2 0 3 2

FZU2192 位置信息挖掘 Hint

1<=N<=LIMIT

1<=M<=LIMIT

1<=Q<= N+M

1<=itemId<=N

1<=userId<=M

0<=cityId<=N+M,0表示位置信息缺失

对于60%的数据,LIMIT<=10^2;对于100%的数据,LIMIT<=10^5

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
/*  
    一开始采用简单映射发现事情没那么简单,因为这个对应的user和item不是一对一映射而是多对多
思路:种类并查集,将具有关联user和item映射在一个集合中 */ const int LIMIT = 2e5 + 10; int set[LIMIT]; //表示user和item的并查集 因为有俩种类别不能重复于是用n+i映射表示user i表示item int city[LIMIT]; //city[i]表示祖先节点为i对应的城市id //寻找祖先 并路径压缩 int find(int a) { if (set[a] == a) return a; return set[a] = find(set[a]); } //联合 void united(int a, int b) { int fa = find(a); int fb = find(b); //不在一个集合 if (fa != fb) //优先联合city存在的 if (city[fa]) { set[fb] = fa; } else { set[fa] = fb; } } int main() { //种类并查集的联合 int n, m, q, userId, cityId, itemId; while (~scanf("%d%d%d", &n, &m, &q)) { for (int i = 1; i <= n + m; i++) { set[i] = i; //初始化每个都是头节点 n+i表示user city[i] = 0; } for (int i = 1; i <= n; i++) { scanf("%d%d", &itemId, &cityId); if (cityId) { int itemfa = find(itemId); city[itemfa] = cityId; } } while (m--) { scanf("%d%d%d", &userId, &itemId, &cityId); //俩个先联合下 usetId+n进行映射在一个集合中 united(userId + n, itemId); if (cityId) { int itemfa = find(itemId); city[itemfa] = cityId; } } while (q--) { int a, id; scanf("%d%d", &a, &id); if (a) { //说明是user id += n; //+n映射 } cityId = city[find(id)]; printf("%d\n", cityId); } } }

参考链接:https://zhuanlan.zhihu.com/p/97813717

上一篇:使用Metasploit对MySQL进行渗透测试


下一篇:Mui实现webview侧滑模块