Daily Archives: 31 10 月, 2012

DNA序列 (各点只出现1次的Dp序）

Posted on by

DNA序列(dna)

题目描述

来自JSSI（Jinkela State Scientific Institute）的科学家们尝试制造一个长度为N并且只包含A的DNA序列，不出意外地失败了。他们得到了一个含有A和B两种部件的序列。现在他们打算对实验结果进行篡改，来得到一个全部是A的序列。篡改的方式有两种：

1 更改某一位上部件的状态（A变成B，B变成A）

2 更改某个前缀内所有部件的状态

两种操作的代价都为1。

你的任务自然是求最小代价。

输入

第一行为N，序列长度。

第二行是一个长度为N且只包含A和B的字符串，表示初始序列。

输出

最小代价。

样例输入

12

AAABBBAAABBB

样例输出

4

数据范围

对于10%的数据，N<=10

对于70%的数据，N<=100000

对于100%的数据，N<=1000000

当一个题目有几种只可能出现1次的操作，而某些操作对后续操作的影响相同，且之后的操作不会对前面影响

便可根据对后续情况影响的状况Dp，乃至D成了贪心

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (1000000+10)
int n;
char s[MAXN];
char turn(const char a)
{
	if (a=='A') return 'B';
	else return 'A';
}
int F[2]={0,1};
int main()
{
	freopen("dna.in","r",stdin);
	freopen("dna.out","w",stdout);
	scanf("%d",&n);
	scanf("%s",s);
	for (int i=n-1;i>=0;i--)
	{
//		cout<<F[0]<<' '<<F[1]<<endl;
		int f0=min(F[0]+(s[i]=='B'),F[1]+1+(s[i]=='B'));
		int f1=min(F[0]+1+(s[i]=='A'),F[1]+(s[i]=='A'));
		F[0]=f0;
		F[1]=f1;
	}
	cout<<min(F[0],F[1])<<endl;


//	while (1);
	return 0;
}

求和式 (C++ 坑爹的<<,>>,%lld)

Posted on by

求和式(x3)

题目描述

作为本场考试的第一题，你的任务十分简单：

给定长度为n的序列A[i]，求所有A[i]xor A[j] (i<j)的值之和

 

输入

第一行一个整数N

接下来N行，第i行为A[i]

输出

所需的值

 

样例输入

3

7

3

5

样例输出

12

样例解释

7 xor 3+3 xor 5+7 xor 5 = 4+6+2 = 12

 

数据范围

对于40%的数据，N<=5000

对于100%的数据，N<=1000000

c++中的%lld千万别用啊 ，各种坑人！

统一用cout 

另外C++中(long long)（1<<k)

这里要转，不然必wa

千万要先乘，和别的数乘完不定什么数了……

本题是位运算分解成一位一位运算（重要性质）

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (100+10)
int n,a,c[MAXN][2]={0};// 1<<i =(0.1)
int main()
{
	freopen("x3.in","r",stdin);
	freopen("x3.out","w",stdout);

/*	for (int i=0;i<=100;i++)
	{
		cout<<c[i][0]<<' '<<c[i][1]<<endl;
	}
*/	long long ans=0;
	scanf("%d",&n);
	int len=0;
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		int tot=-1;
		int j=100;
		while (j--) {c[++tot][a%2]++;a/=2;}



		len=len<tot?tot:len;

	}
/*	for (int i=0;i<=100;i++)
	{
		cout<<c[i][0]<<' '<<c[i][1]<<endl;
	}
*/
	for (int i=0;i<=28;i++)
	{
		ans+=(long long)(1<<i)*(long long)c[i][1]*(long long)(n-c[i][1]);

//	cout<<ans<<endl;
	}


/*
	for (int i=0;i<=len;i++) cout<<c[i][0]<<' '<<c[i][1]<<' '<<endl;
*/

//	printf("%lldn",ans);
	cout<<ans<<endl;
//	while (1);

	return 0;
}