[jzoj100047]【NOIP2017提高A组模拟7.14】基因变异

145 阅读 0 评论 96 点赞

我是靠谱客的博主顺心唇膏，这篇文章主要介绍[jzoj100047]【NOIP2017提高A组模拟7.14】基因变异，现在分享给大家，希望可以做个参考。

Description

21 世纪是生物学的世纪，以遗传与进化为代表的现代生物理论越来越多的进入了我们的视野。如同大家所熟知的，基因是遗传因子，它记录了生命的基本构造和性能。因此生物进化与基因的变异息息相关，考察基因变异的途径对研究生物学有着至关重要的作用……

其实完整题意被囚禁了

Solution

其实是一道很水的题目。不过做法多样。

简单的，因为每次操作代价相同，可以运用 bfs 或奇怪的图论知识实现。

不过呢，亦可以考虑 DP

~~杀鸡焉用牛刀~~

显然的每个数字最多至多被使用一次

所以设fi,j仅使用前i个量[具体见方程]到达j的最小步数

那么 f20,S⨁T 即答案

方程较显然不再赘述具体见 Code

Code

复制代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define oo 2139062143
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-x))
#define abs(x) (((x)>=0)?(x):(-(x)))
#define max(x,y) (((x)>(y))?(x):(y))
#define min(x,y) (((x)<(y))?(x):(y))
#define fo(i,x,y) for (int i = (x);i <= (y);++ i)
#define fd(i,x,y) for (int i = (x);i >= (y);-- i)
using namespace std;
typedef double db;
typedef long long ll;
const int N = 22,Q = 100100,NUM = 1048576;
int n,q;
int a[N + 10];
int f[N + 10][NUM * 2];
void dfs(int x)
{
if (x > 21) return;
fo(i,0,NUM)
{
f[x][i] = min(f[x][i],f[x - 1][i]);
f[x][i] = min(f[x][i],f[x - 1][i ^ a[x]] + 1);
if (1 << (x - 1) <= NUM)
{
f[x][i] = min(f[x][i],f[x - 1][i ^ (1 << (x - 1))] + 1);
f[x][i] = min(f[x][i],f[x - 1][i ^ (1 << (x - 1)) ^ a[x]] + 2);
}
}
dfs(x + 1);
}
int main()
{
scanf("%d%d", &n, &q);
memset(f,127,sizeof f);
fo(i,1,n) scanf("%d", &a[i]);
f[0][0] = 0;
dfs(1);
fo(i,1,q)
{
int x,y;
scanf("%d%d", &x, &y);
printf("%dn", f[21][x ^ y]);
}
}

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
47
48
49
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define oo 2139062143
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-x))
#define abs(x) (((x)>=0)?(x):(-(x)))
#define max(x,y) (((x)>(y))?(x):(y))
#define min(x,y) (((x)<(y))?(x):(y))
#define fo(i,x,y) for (int i = (x);i <= (y);++ i)
#define fd(i,x,y) for (int i = (x);i >= (y);-- i)
using namespace std;
typedef double db;
typedef long long ll;
const int N = 22,Q = 100100,NUM = 1048576;
int n,q;
int a[N + 10];
int f[N + 10][NUM * 2];
void dfs(int x)
{
if (x > 21) return;
fo(i,0,NUM)
{
f[x][i] = min(f[x][i],f[x - 1][i]);
f[x][i] = min(f[x][i],f[x - 1][i ^ a[x]] + 1);
if (1 << (x - 1) <= NUM)
{
f[x][i] = min(f[x][i],f[x - 1][i ^ (1 << (x - 1))] + 1);
f[x][i] = min(f[x][i],f[x - 1][i ^ (1 << (x - 1)) ^ a[x]] + 2);
}
}
dfs(x + 1);
}
int main()
{
scanf("%d%d", &n, &q);
memset(f,127,sizeof f);
fo(i,1,n) scanf("%d", &a[i]);
f[0][0] = 0;
dfs(1);
fo(i,1,q)
{
int x,y;
scanf("%d%d", &x, &y);
printf("%dn", f[21][x ^ y]);
}
}