BC31pairs&&hdoj5178&&hdoj5179 pairs beautiful number

80 阅读 0 评论 53 点赞

我是靠谱客的博主纯真大白，最近开发中收集的这篇文章主要介绍BC31pairs&&hdoj5178&&hdoj5179 pairs beautiful number，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

pairs

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1920 Accepted Submission(s): 681

Problem Description

John has

n points on the X axis, and their coordinates are

(x[i],0),(i=0,1,2,…,n−1) . He wants to know how many pairs

<a,b> that

|x[b]−x[a]|≤k.(a<b)

Input

The first line contains a single integer

T (about 5), indicating the number of cases.
Each test case begins with two integers

n,k(1≤n≤100000,1≤k≤109) .
Next

n lines contain an integer

x[i](−109≤x[i]≤109) , means the X coordinates.

Output

For each case, output an integer means how many pairs

<a,b> that

|x[b]−x[a]|≤k .

Sample Input

Sample Output


3
10

Source

BestCoder Round #31

注意要求的是abs(x[b]-x[a])<=k的个数

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<list>
#include<vector>
using namespace std;
const int maxn=100010;
int num[maxn];
int main()
{
int t,i,j,k,n;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
for(i=0;i<n;++i){
scanf("%d",&num[i]);
}
sort(num,num+n);
int pos=0;
long long ans=0;
for(i=0;i<n;++i){
while(num[i]-num[pos]>k)pos++;
ans=ans+i-pos;
}
printf("%lldn",ans);
}
return 0;
}

beautiful number

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 509 Accepted Submission(s): 309

Problem Description

Let

A=∑ni=1ai∗10n−i(1≤ai≤9) (

n is the number of

A 's digits). We call

A as “beautiful number” if and only if

a[i]≥a[i+1] when

1≤i<n and

a[i] mod

a[j]=0 when

1≤i≤n,i<j≤n (Such as 931 is a "beautiful number" while 87 isn't).
Could you tell me the number of “beautiful number” in the interval

[L,R] (including L and R)?

Input

The fist line contains a single integer

T (about 100), indicating the number of cases.
Each test case begins with two integers

L,R(1≤L≤R≤109) .

Output

For each case, output an integer means the number of “beautiful number”.

Sample Input


2
1 11
999999993 999999999

Sample Output


10
2

Source

BestCoder Round #31

找出所有满足条件的数然后逐个判断即可

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<list>
#include<vector>
using namespace std;
const int maxn=2010;
int array[maxn],cnt=0;
void dfs(int d,int bit,int num){
array[cnt++]=num;if(d>=1000000000)return ;
for(int i=bit;i<=9;i+=bit){
dfs(d*10,i,num+d*i);
}
}
int main()
{
cnt=0;
for(int i=1;i<=9;++i){
dfs(10,i,i);
}
int i,j,k,t;
scanf("%d",&t);
while(t--){
int l,r,ans=0;
scanf("%d%d",&l,&r);
for(i=0;i<cnt;++i){
if(array[i]>=l&&array[i]<=r)ans++;
}
printf("%dn",ans);
}
return 0;
}