离散化

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;
}