算法之数学--hash算法 2021-03-11（未完待续）

1.hash算法

刷出一道墙

题目描述

Time Limit: 2000 ms
Memory Limit: 256 mb
在一面很长的墙壁上，工人们用不同的油漆去刷墙，然而可能有些地方刷过以后觉得不好看，他们会重新刷一下。有些部分因为重复刷了很多次覆盖了很多层油漆，小诺很好奇那些地方被刷过多少种颜色的油漆。

输入描述:

若干行输入，每行两个数字B[i],Ei表示这次刷的墙壁是哪一段
（假设每次刷的时候油漆颜色都和之前的不同），以0 0结束
又若干行输入，每行两个数字begin[i],end[i]（0<=begin[i]<=end[i]<=200000）表示小诺询问的段，
以0 0结束

输出描述:

对于每个小诺的询问输出(end[i]-begin[i]+1)行,表示对应询问段的每个点被多少种颜色的油漆覆盖过。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5+5;
int f[maxn];

int main(){
int a,b;
while(1){
scanf("%d%d",&a,&b);
if(a==0&&b==0)
break;
f[a]++;
f[b+1]--;
}
//妙啊 移位
for(int i=0;i<maxn;i++)
f[i] +=f[i-1];

while(1){
scanf("%d%d",&a,&b);
if(a==0&&b==0)
break;
for(int i=a;i<=b;i++){
printf("%d\n",f[i]);
}
}
return 0;
}

原文地址：https://blog.csdn.net/sinat_40546227/article/details/114682087

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！