1139. First Contact (30)

题目:

https://www.patest.cn/contests/pat-a-practise/1139

大概描述:

找出A与B之间的连接的两个节点

特征词:

模拟 图

使用语言:

C++

解题思想:

利用邻接表建立出图,然后将A,B的同性朋友找出然后判断他们是否存在关系,需要注意A的朋友不能包含B,B的朋友不能包含A

题目得分:

26

提交次数:

3

时间

120分钟

代码

#include<cstdio>
#include<algorithm>
#include<vector>
const int MAXI = 100000;
using namespace std;
vector<int> link[MAXI];
vector<int> s1;
vector<int> s2;
int sex[MAXI] = {0};
int aa,bb;
int aas = 0,bbs = 0;
vector<int> yyy ;
void o(){
 //printf("%d1003\n\n",sex[1003]);
 int i = 0;
 int s = link[aa].size();
 s1.clear();
 s2.clear();
 for(i = 0;i < s;i++){
 //printf("添加可能人%d%d\n",sex[link[aa][i]] ,link[aa][i]);
 if(sex[link[aa][i]] == aas&&link[aa][i] != bb){
 //printf("添加没人%d\n",link[aa][i]);
 s1.push_back(link[aa][i]);
 }
 }
 // printf("\n");
 s = link[bb].size();
 for(i = 0;i < s;i++){
 //printf("添加可能人%d%d\n",sex[link[bb][i]] ,link[bb][i]);
 if(sex[link[bb][i]] == bbs&&link[bb][i] != aa){
 // printf("添加媒人%d\n",link[bb][i]);
 s2.push_back(link[bb][i]);
 }
 }
 //printf("双方媒人准备完毕\n");
 for(i = 0;i < s1.size();i++){
 //printf("%d ",s1[i]);
 }
 //printf("\n");
 for(i = 0;i < s2.size();i++){
 //printf("%d ",s2[i]);
 }

}
bool qq(int a,int b){
 return a < b;
}
int find1(int a,int b){
 int i = 0;
 for(i = 0;i < link[a].size();i++){
 if(link[a][i] == b){
 return 1;
 }
 }
 return 0;
}
void oo(){
 yyy.clear();
 int i = 0;
 int j = 0;
 int k = s1.size();
 int kk = s2.size();
 //printf("进行匹配\n");
 for(i = 0;i < k;i++){
 for(j = 0;j < kk;j++){
 if(find1(s1[i],s2[j]) == 1){
 yyy.push_back(s1[i]);
 yyy.push_back(s2[j]);
 // printf("%d %d\n",s1[i],s2[j]);
 }
 }
 }
}


int main(){
 int i = 0;
 int j = 0;
 int a,b;
 int pnum,lnum;
 scanf("%d %d",&pnum,&lnum);
 for(i = 0;i < lnum;i++){
 scanf("%d %d",&a,&b);
 if(a > 0){
 sex[a] = 1;
 }else{
 a = -a;
 sex[a] = 0;
 }
 if(b > 0){
 sex[b] = 1;
 }else{
 b = -b;
 sex[b] = 0;
 }
 //printf("%d%d %d%d\n",sex[a],a,sex[b],b);
 // printf("000k");
 link[a].push_back(b);
 //printf("llll");
 link[b].push_back(a);
 // printf("")
 //printf("999");
 }
 //printf("关系读取完毕\n");
 //printf("%d1003\n\n",sex[1003]);
 int qnum = 0;
 scanf("%d",&qnum);
 //printf("%d1003\n\n",sex[1003]);
 for(i = 0;i < qnum;i++){
 scanf("%d %d",&a,&b);
 //printf("%d1003\n\n",sex[1003]);
 if(a > 0){
 aa = a;
 aas = 1;
 }else{
 aa = -a;
 aas = 0;
 }
 if(b > 0){
 bb = b;
 bbs = 1;
 }else{
 bb = -b;
 bbs = 0;
 }
 //printf("问题读取完毕\n");
 //printf("%d1003\n\n",sex[1003]);
 o();
 sort(s1.begin(),s1.end(),qq);
 sort(s2.begin(),s2.end(),qq);
 //printf("排序完毕\n");
 oo();
 int u = yyy.size();
 printf("%d\n",u/2);
 for(j = 0;j < u/2;j++){
 printf("%04d %04d\n",yyy[j * 2],yyy[j * 2 + 1]);
 }
 }
}

运行结果

26

 成长

对vector进行排序需要 sort(n1[1].begin(),n1[1].end(),pp);

在涉及到正负号时,要能够记得对能0得思考从而选择较为完备得思路

 

简单搜索引擎的开发

一直有个小想法,就是开发出一个很方便的搜索引擎,可以自定义,自己设计,完全自己组装,依照自己的搜索习惯,减少搜索语句的设计。听听就觉得有意思。

于是到网上找了教程进行学习。先把教程放这儿

dySE:一个 Java 搜索引擎的实现,第 1 部分

dySE:一个 Java 搜索引擎的实现,第 2 部分

dySE:一个 Java 搜索引擎的实现,第 3 部分

教程讲解的很详细。也是有源码下载的。

我也仿照他的代码,学习,并且自己敲了一个,代码中注释超多,其实也相当于学习笔记,大家可以参考,交流,我的项目上传到我的Github上了。大家可以下载,交流。

这个搜索引擎还很小,问题也有不少,比如网页编码不同造成的乱码现象,抓取网页时,无效url的筛选,网页的分词,网页排名,界面外观,等各类情况,只能目前只能算个用java写的小爬虫,但是接下来的阶段,会将他进行简要的完善,然后分阶段的将他的每个模块重新打磨,提高质量,我也会在之后,将每次重新打磨的模块的方法介绍。望以能成为一个有用的工具。

对了,还没有给他起名字,要不就叫他,Forest吧。哈哈哈