如何将数据离散化操作转化为一个长尾关键词的？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1197个文字，预计阅读时间需要5分钟。
日记+外面好热啊！🌞🌞🌞现在在学校训练，机房门都不想出，上下学快走前进步，不敢停下一步。内容定义+把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时间效率。— 百度 百度
diary外面好热啊!!!现在在学校训练,机房门都不想出,上下学快走前进,不敢停留一步
内容 定义个人看法把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。 ———百度百科
离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。已达到节约时间、空间复杂度.进行去重,在去地址进行访问
(节省了重复数字占用的时间、空间)
其实也没什么的
void discrete(){
sort(a+1,a+n+1);
for (int i=1;i<=n;i++)
if (i==1||a[i]!=a[i-1])
b[++m]=a[i];
}
int query(int x){
return lower_bound(b+1,b+1+m,x)-b;
}
题目
P1496 火烧赤壁
题目大意
有\(n\)条线段(有重复,重合)
给定每个线段的起点和终点，请你求出线段的长度之和
3 11
-1 1
5 11
2 9
思路
用\(a_i\)输入,离散化(去重)后的线段用\(b_j(1 \leq j \leq h)\)表示
判断一下是否能和上一条线段合并,否则线段个数\(+1\),
#include <bits/stdc++.h>
#define LL long long
#define N 20005
using namespace std;
LL n;
struct node{
LL x,y;
}a[N],b[N];int h=0;
bool cmp(node a,node b){
return a.x<b.x;
}
inline LL read(){
LL x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int main(){
n=read();for (int i=1;i<=n;i++){a[i].x=read();a[i].y=read();}
sort(a+1,a+1+n,cmp);
b[++h].x=a[1].x;
b[h].y=a[1].y;
for (int i=2;i<=n;i++){
if (a[i].x<b[h].y){ //判断是否能合并
if (a[i].y>b[h].y)
b[h].y=a[i].y;
}else{
b[++h].x=a[i].x;
b[h].y=a[i].y;
}
}LL ans=0;
for (int i=1;i<=h;i++){
ans+=b[i].y-b[i].x;
}printf("%lld",ans);
return 0;
}
P3670 [USACO17OPEN]Bovine Genomics S
题目
题目描述
FJ有n头有斑点的牛和n头没有斑点的牛。由于他刚刚学完牛的基因学的课程，他想知道牛有没有斑点是否
与牛的基因有关。
FJ花了巨大的代价测出了每个牛的基因，每头牛的基因用一个长度为M的由“A,C,G,T”的串构成。FJ将这
些串写成一个表/矩阵，就像图中这样
（\(N\) = 3的例子）
Positions: 1 2 3 4 5 6 7 ... M
Spotty Cow 1: A A T C C C A ... T
Spotty Cow 2: G A T T G C A ... A
Spotty Cow 3: G G T C G C A ... A
Plain Cow 1: A C T C C C A ... G
Plain Cow 2: A G T T G C A ... T
Plain Cow 3: A G T T C C A ... T
FJ仔细的观察这个表，他发现通过观测2,4位置的字符串可以预测牛是否有斑点。
（在这个例子中，假如他看到24位置是GC、AT或者AC就可以断定其有斑点，因为1号有斑点的牛24位置基因为AC，2号为AT，3号为GC，而且没有任何一头无斑点的牛的24位置出现过这三个串）
FJ认为，1个或者两个位点是不能够区分品种的，必须是刚好3个位点。他想知道能用多少组三个本质不同的位置判断牛的斑点，{1,2,3}和{1,3,2}是本质相同的
思路看到 \((1 \leq N \leq 500 )\) \((3 \leq M \leq 50)\)
我直接暴力大循环 搞里头
判断是否重复即可
代码没什么难度,码风清晰~~
#include <bits/stdc++.h>
#define LL long long
#define N 505
#define M 55
using namespace std;
bool ff[1005];
int f[N][M],s[N][M];
int m,n;char ch;
int main(){
scanf("%d%d",&n,&m);
ch=getchar();for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
ch=getchar();if (ch=='A') f[i][j]=1;
else if (ch=='C') f[i][j]=2;
else if (ch=='G') f[i][j]=3;
else f[i][j]=4;
}ch=getchar();
}for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
ch=getchar();if (ch=='A') s[i][j]=1;
else if (ch=='C') s[i][j]=2;
else if (ch=='G') s[i][j]=3;
else s[i][j]=4;
}ch=getchar();
}int ans=0;for (int a=1;a<=m-2;a++)
for (int b=a+1;b<=m-1;b++)
for (int c=b+1;c<=m;c++){
memset(ff,0,sizeof(ff));
for (int i=1;i<=n;i++){
ff[f[i][a]*100+f[i][b]*10+f[i][c]]=true;
}bool flag=true;for (int i=1;i<=n;i++){
if (ff[s[i][a]*100+s[i][b]*10+s[i][c]]){flag=false;break;}
}if (flag) ans++;
}
printf("%d",ans);
return 0;
}
本文共计1197个文字，预计阅读时间需要5分钟。
日记+外面好热啊！🌞🌞🌞现在在学校训练，机房门都不想出，上下学快走前进步，不敢停下一步。内容定义+把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时间效率。— 百度 百度
diary外面好热啊!!!现在在学校训练,机房门都不想出,上下学快走前进,不敢停留一步
内容 定义个人看法把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。 ———百度百科
离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。已达到节约时间、空间复杂度.进行去重,在去地址进行访问
(节省了重复数字占用的时间、空间)
其实也没什么的
void discrete(){
sort(a+1,a+n+1);
for (int i=1;i<=n;i++)
if (i==1||a[i]!=a[i-1])
b[++m]=a[i];
}
int query(int x){
return lower_bound(b+1,b+1+m,x)-b;
}
题目
P1496 火烧赤壁
题目大意
有\(n\)条线段(有重复,重合)
给定每个线段的起点和终点，请你求出线段的长度之和
3 11
-1 1
5 11
2 9
思路
用\(a_i\)输入,离散化(去重)后的线段用\(b_j(1 \leq j \leq h)\)表示
判断一下是否能和上一条线段合并,否则线段个数\(+1\),
#include <bits/stdc++.h>
#define LL long long
#define N 20005
using namespace std;
LL n;
struct node{
LL x,y;
}a[N],b[N];int h=0;
bool cmp(node a,node b){
return a.x<b.x;
}
inline LL read(){
LL x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int main(){
n=read();for (int i=1;i<=n;i++){a[i].x=read();a[i].y=read();}
sort(a+1,a+1+n,cmp);
b[++h].x=a[1].x;
b[h].y=a[1].y;
for (int i=2;i<=n;i++){
if (a[i].x<b[h].y){ //判断是否能合并
if (a[i].y>b[h].y)
b[h].y=a[i].y;
}else{
b[++h].x=a[i].x;
b[h].y=a[i].y;
}
}LL ans=0;
for (int i=1;i<=h;i++){
ans+=b[i].y-b[i].x;
}printf("%lld",ans);
return 0;
}
P3670 [USACO17OPEN]Bovine Genomics S
题目
题目描述
FJ有n头有斑点的牛和n头没有斑点的牛。由于他刚刚学完牛的基因学的课程，他想知道牛有没有斑点是否
与牛的基因有关。
FJ花了巨大的代价测出了每个牛的基因，每头牛的基因用一个长度为M的由“A,C,G,T”的串构成。FJ将这
些串写成一个表/矩阵，就像图中这样
（\(N\) = 3的例子）
Positions: 1 2 3 4 5 6 7 ... M
Spotty Cow 1: A A T C C C A ... T
Spotty Cow 2: G A T T G C A ... A
Spotty Cow 3: G G T C G C A ... A
Plain Cow 1: A C T C C C A ... G
Plain Cow 2: A G T T G C A ... T
Plain Cow 3: A G T T C C A ... T
FJ仔细的观察这个表，他发现通过观测2,4位置的字符串可以预测牛是否有斑点。
（在这个例子中，假如他看到24位置是GC、AT或者AC就可以断定其有斑点，因为1号有斑点的牛24位置基因为AC，2号为AT，3号为GC，而且没有任何一头无斑点的牛的24位置出现过这三个串）
FJ认为，1个或者两个位点是不能够区分品种的，必须是刚好3个位点。他想知道能用多少组三个本质不同的位置判断牛的斑点，{1,2,3}和{1,3,2}是本质相同的
思路看到 \((1 \leq N \leq 500 )\) \((3 \leq M \leq 50)\)
我直接暴力大循环 搞里头
判断是否重复即可
代码没什么难度,码风清晰~~
#include <bits/stdc++.h>
#define LL long long
#define N 505
#define M 55
using namespace std;
bool ff[1005];
int f[N][M],s[N][M];
int m,n;char ch;
int main(){
scanf("%d%d",&n,&m);
ch=getchar();for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
ch=getchar();if (ch=='A') f[i][j]=1;
else if (ch=='C') f[i][j]=2;
else if (ch=='G') f[i][j]=3;
else f[i][j]=4;
}ch=getchar();
}for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
ch=getchar();if (ch=='A') s[i][j]=1;
else if (ch=='C') s[i][j]=2;
else if (ch=='G') s[i][j]=3;
else s[i][j]=4;
}ch=getchar();
}int ans=0;for (int a=1;a<=m-2;a++)
for (int b=a+1;b<=m-1;b++)
for (int c=b+1;c<=m;c++){
memset(ff,0,sizeof(ff));
for (int i=1;i<=n;i++){
ff[f[i][a]*100+f[i][b]*10+f[i][c]]=true;
}bool flag=true;for (int i=1;i<=n;i++){
if (ff[s[i][a]*100+s[i][b]*10+s[i][c]]){flag=false;break;}
}if (flag) ans++;
}
printf("%d",ans);
return 0;
}