[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]);
}
}

最后

以上就是顺心唇膏为你收集整理的[jzoj100047]【NOIP2017提高A组模拟7.14】基因变异的全部内容，希望文章能够帮你解决[jzoj100047]【NOIP2017提高A组模拟7.14】基因变异所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。