#include <cstdio>#include <cmath>#include <iostream>#include <cstring>#include <algorithm>using namespace std;int n,k,now,nowl,nowr;int main(){	scanf("%d%d",&n,&k);	now=0;nowl=1;nowr=n;	if (n==3)	{		if (k==1) printf("1 2 3");		else printf("1 3 2");		return 0;	}	for (int i=1;i<=k;++i) 	{	if (!now) 			{				printf("%d ",nowl);				nowl++;			}			else			{				printf("%d ",nowr);				nowr--;			}		now^=1;	}	if (now==1)	for (int i=nowl;i<=nowr;++i) printf("%d ",i);	else 	for (int i=nowr;i>=nowl;--i) printf("%d ",i);	return 0;}

 B:

题意：求一个N个数的序列，使得满足M个限制条件，限制条件如下给出：

Li Ri Ki 要求a[li]&a[li+1]&a[li+2]&...&a[ri]=ki

题解：按位来做，对于每一位，我们先开一个数组x[i]来表示数列中第i个数这一位是否为1，我们来检索每一个条件，若ki这一位是1，则给li到ri这一段的每个xi都加1，这个可以通过差分在O(N)得到，这样对于每一位我们得到一个x数组，然后我们再来检索每一个条件，若ki这一位不为1，而x[li]到x[ri]均为1，则此时必为无解的情况，否则更新答案即可。

#include <cstdio>#include <cmath>#include <cstring>#include <iostream>#include <algorithm>using namespace std;struct node{	int l,r,w;}q[100005];int a[100005],t[100005],sum[100005],n,m,flag;int work(int x){	memset(sum,0,sizeof(sum));	memset(t,0,sizeof(t));	for (int i=1;i<=m;++i)	{		int dq=q[i].w&x;		if (dq)		{t[q[i].l]++;t[q[i].r+1]--;}	}	for (int i=1;i<=n;++i) t[i]=t[i-1]+t[i];	for (int i=1;i<=n;++i) if (t[i]>0) t[i]=1;else t[i]=0;	for (int i=1;i<=n;++i) sum[i]=sum[i-1]+t[i];	for (int i=1;i<=m;++i)	{		int dq=q[i].w&x;		if (!dq)		{			if (sum[q[i].r]-sum[q[i].l-1]==q[i].r-q[i].l+1) return 0;		}		else		{			if (sum[q[i].r]-sum[q[i].l-1]!=q[i].r-q[i].l+1) return 0;		}	}	for (int i=1;i<=n;++i) if (t[i]>0) a[i]|=x;	return 1;}int main(){	scanf("%d %d",&n,&m);	memset(a,0,sizeof(a));	for (int i=1;i<=m;++i) scanf("%d %d %d",&q[i].l,&q[i].r,&q[i].w);	for (int i=0;i<=31;++i)	{		flag=work(1<<i);		if (!flag) 		{			printf("NO\n");			return 0;		}	}	printf("YES\n");	for (int i=1;i<=n;++i) printf("%d ",a[i]);	return 0;}

C:

题意：给定N个长度相同的字符串，一个人选出了一个串，你想要知道他选的是哪个，你每次等概率询问一个位置i，他告诉你他选的串第i位是什么字母，求你确定他选的是哪个串的次数期望。

题解：串的长度不超过20让人不难想到状压DP，预处理出对应位置相同的串的集合。对应位置可以用一个二进制数表示，比如第0 1 2位相同就可以用7表示，第1，3位相同可以用10表示，这个集合也可以用二进制表示，因为n=50还可以在long long的承受范围之内。这样我们预处理得到了A[I]，接下来就是一个概率DP。用DP[I]表示询问了状态I对应这些位后期望的天数，不难想到转移：DP[I]=SIGMA(DP[I^(1<<J)])/SUM 若第j位还没有询问 那么自然转移就要加上询问了第j位的情况，sum为一共有多少个位还没有被询问，这样保证了等概率的询问每一位。这时候还要加上这一天的期望值，因为到这一天的概率为A[I]中1的个数/N 所以DP[I]还要加上A[I]中1的个数/N ，至此问题解决。

#include <cstdio>#include <cmath>#include <cstring>#include <iostream>#include <algorithm>using namespace std;typedef long long LL;LL a[1<<21];double dp[1<<21];char ch[100][100];int n,l;long long dq;int main(){	scanf("%d",&n);	for (int i=0;i<n;++i) scanf("%s",ch[i]);	l=strlen(ch[0]);	for (int i=0;i<n;++i)		for (int j=i+1;j<n;++j)		{			dq=0;			for (int k=0;k<l;++k) if (ch[i][k]==ch[j][k]) dq|=1LL<<k;			a[dq]=a[dq]|(LL)1<<i|(LL)1<<j; 		}	memset(dp,0,sizeof(dp));	for (int i=(1<<l)-1;i>=0;--i)	{		for (int j=0;j<l;++j) if (i>>j&1) a[i^(1<<j)]|=a[i];		dq=0;		for (int j=0;j<l;++j) if (!(i>>j&1)) 		{			dp[i]+=dp[i|(1<<j)];			dq++;		}		if (dq==0) continue;		dp[i]/=dq;		dq=0;		for (int j=0;j<n;++j) if (a[i]&(LL)1<<j) dq++;		dp[i]+=dq/(double)n;	}	printf("%.9lf\n",dp[0]);	return 0;}