• 洛谷P1102 A-B数对 详细解析及AC代码


    前言

    酷!阅读量突破2000了!写一篇简单的题目奖励一下自己。

    题目

    题目背景

    出题是一件痛苦的事情!

    相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的 A+B Problem,改用 A-B 了哈哈!

    题目描述

    给出一串正整数数列以及一个正整数 C C C,要求计算出所有满足 A − B = C A - B = C AB=C 的数对的个数(不同位置的数字一样的数对算不同的数对)。

    输入格式

    输入共两行。

    第一行,两个正整数 N , C N,C N,C

    第二行, N N N 个正整数,作为要求处理的那串数。

    输出格式

    一行,表示该串正整数中包含的满足 A − B = C A - B = C AB=C 的数对的个数。

    样例 #1

    样例输入 #1

    4 1
    1 1 2 3
    
    • 1
    • 2

    样例输出 #1

    3
    
    • 1

    提示

    对于 75 % 75\% 75% 的数据, 1 ≤ N ≤ 2000 1 \leq N \leq 2000 1N2000

    对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 2 × 1 0 5 1 \leq N \leq 2 \times 10^5 1N2×105 0 ≤ a i < 2 30 0 \leq a_i <2^{30} 0ai<230 1 ≤ C < 2 30 1 \leq C < 2^{30} 1C<230

    2017/4/29 新添数据两组

    题目分析

      显然我们第一时间想到的朴素暴力算法是行不通的,两个循环一看就是O(n2),然后我们就想到了用两个O(nlgn)来过,先一个快排nlgn再来两个个二分的nlgn就可以解决本题。
      但是我们是卷王,怎么能少得了O(n)的方法呢?于是我又看到一个hash的解法,一起整理了一下。好耶!✌

    注意事项

    1.第三个点需要将sum改成long long不然会WE,可能是因为超了。
    2.不同位置的数字一样的数对算不同的数对。我感觉第三个点就是有一大堆重复的数字!

    代码

    经典二分(O(nlgn))

    尝试了一下我的想法,竟然有两个TLE,我猜是有一个样例直接是几乎全部满足,所以不行,我稍微修改了一下还是错了第三个,后来发现有个陷阱,改了就AC了
    耶

    #include
    #include
    using namespace std;
    
    
    long long a[200007]= {0};
    int main()
    {
    	long long  n,c,t,sum=0;
    	cin>>n>>c;
    	for(int i=0; i<n; i++) {
    		cin>>a[i];
    	}
    	sort(a,a+n);
    	for(int i = 0 ; i < n ; i ++) {
    		int b=a[i]-c;
    		if(b<0)continue;
    		else {
    			int l1=0,r1=n-1;
    			while(l1<r1) {
    				int mid = (l1+r1)>>1;
    				if(a[mid]>=b)
    					r1=mid;
    				else
    					l1=mid+1;
    			}
    			//此时a[l1]满足a[mid]>=b的最小值
    			if(a[l1]!=b)continue;
    			else {
    				int l2=l1,r2=n-1;
    				while(l2<r2) {
    					int mid = (l2+r2)>>1;
    					if(a[mid]>b)
    						r2=mid;
    					else
    						l2=mid+1;
    				}
    				//此时a[l2]满足a[mid]>b的最小值
    				sum+=(r2-r1);
    			}
    
    		}
    	}
    	cout<<sum;
    	return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    酷炫哈希(O(n))

    感谢大佬的灵感支持,献上Ajwallet的题解

    #include
    #define p 1000003//这个数越大就越好,最好是质数,这样冲突会减少,但至少要大于200000才行,这里1000003可以轻松AC
    #define hash(a) a%p//hash函数
    using namespace std;long long n,m,a[p],ans;
    struct node
    {
    	long long x;int y;//x为这个位置对应的数,y为这个数出现了几次
    }h[p];
    long long abs(long long x){return x<0?-x:x;}//绝对值
    int find(long long x)//找到x的位置
    {
    	int y=hash(abs(x));//因为x可能是负数,所以要abs
    	while(h[y].x&&h[y].x!=x) y=hash(++y);
    	return y;
    }
    void push(long long x){int y=find(x);h[y].y++;h[y].x=x;}//先找到此数在hash表中的位置,并将这个位置对应的数量+1,并且将数放进去
    int check(long long x){return h[find(x)].y;}//输出这个数在hash表中出现的次数
    int main()
    {
    	scanf("%lld%lld",&n,&m);
    	for(long long i=1;i<=n;i++) scanf("%lld",&a[i]),push(a[i]);//输入并放入
    	for(long long i=1;i<=n;i++) ans+=check(a[i]-m);//统计
    	printf("%lld",ans);//输出
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    后话

    额外测试用例

    因为忘记输出路径而获得了一个用例

    样例输入 #2

    3
    10 20 5
    0 1
    0
    
    • 1
    • 2
    • 3
    • 4

    样例输出 #2

    2
    20
    
    • 1
    • 2

    王婆卖瓜

    感觉有收获或者想跟上我的进度刷题的,可以点个关注,或者点赞收藏评论都可以!

    题目来源

    洛谷链接

  • 相关阅读:
    黑客动态播报 | 一封假offer,盗取6.25亿美元
    webpack打包js文件
    Java学习笔记43——函数式接口
    设计高并发系统的关键策略
    bootz启动 Linux内核过程总结
    不使用比较和条件判断实现min函数的一种方法
    ROS1云课→08基础实践(CLI命令行接口)
    5、架构-负载均衡
    python requests请求一个api接口报错
    28. 使用 k8e 玩转 kube-vip with Cilium‘s Egress Gateway 特性
  • 原文地址:https://blog.csdn.net/flyunicorninsky/article/details/134164641