BestCoder Round #67

【N bulbs】

#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
	int T,n;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
		int cnt=0;
		for (int i=1,x;i<=n;i++) scanf("%d",&x),cnt+=x==0;
		if (cnt&1) printf("NO\n");else printf("YES\n");
	}
	return 0;
}

【N*M bulbs】

  显然，如果走两个0的格子，至少需要走两格，也就是走偶数步。走1的格子等同于走奇数步。判断走的步数的奇偶性即可。

#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
	int T,n,m;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d%d",&n,&m);
		int cnt=0,x;
		for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			scanf("%d",&x),cnt+=x;
		if ((n+m-2-cnt+1000000)&1) printf("YES\n");else printf("NO\n");
	}
	return 0;
}

【Black Jack】

  一个比较经典的概率DP。

  设f2[i][j]为闲家点数为i后停止叫牌，庄家此时点数为j时庄家的胜率（平局当作庄家赢），则f2[i][j]等于取一张点数为k的牌的概率乘上f2[i][j+k]。

  设f1[i][j]为庄家初始点数为j，闲家当前点数为i时闲家的胜率，f1[i][j]为闲家抽一张牌的胜率与不抽牌胜率的最大值。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

double f1[40][40],f2[40][40];

void DP()
{
	for (int i=1;i<=21;i++)
	for (int j=i;j<=21;j++)
		f2[i][j]=1;
	for (int i=1;i<=21;i++)
	for (int j=i-1;j>=1;j--)
	{
		for (int k=1;k<=9;k++) f2[i][j]+=f2[i][j+k]/13.0;
		f2[i][j]+=f2[i][j+10]*4.0/13.0;
	}
	for (int i=21;i>=1;i--)
	for (int j=21;j>=1;j--)
	{
		for (int k=1;k<=9;k++) f1[i][j]+=f1[i+k][j]/13.0;
		f1[i][j]+=f1[i+10][j]*4.0/13.0;
		f1[i][j]=max(f1[i][j],1.0-f2[i][j]);
	}
}

int Change(char ch) {if (ch>='2' && ch<='9') return ch-'0';else if (ch=='A') return 1;else return 10;}

int main()
{
	DP();
	int T;
	scanf("%d",&T);
	while (T--)
	{
		char cor[5];
		scanf("%s",cor);
		if (f1[Change(cor[0])+Change(cor[1])][Change(cor[2])+Change(cor[3])]>0.5) puts("YES");else puts("NO");
	}
}

【the soldier of love】

  记录下所有的点以及它们对应的组号，以及每个点同组的前一个点的位置，然后把它们在数轴上按顺序排成一排。

  用一个长度为数轴长的树状数组记录线段的左端点（即如果有一条线段左端点为x，则树状数组上这个点的值+1），维护前缀和。

  从左往右遍历点，对每个点p对应的组的答案加上树状数组里区间[p.prev_position+1,p.position]的和。在这过程中将右端点在当前点左边的线段标记从树状数组中删除。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=300010,maxl=1000010;

struct Segment {int l,r;}S[maxn];
struct Point {int x,id,prev;}P[maxn];
bool cmps(const Segment &a,const Segment &b) {return a.r<b.r;}
bool cmpp(const Point &a,const Point &b) {return a.x<b.x;}

int f[maxl];
int ans[maxn];
int n,m,T;

inline int lowbit(int x) {return x&-x;}
void Change(int x,int o) {while (x<maxl) f[x]+=o,x+=lowbit(x);}
int Query(int x) {int res=0;while (x) res+=f[x],x-=lowbit(x);return res;}

int main()
{
	while (scanf("%d%d",&n,&T)==2)
	{
		memset(f,0,sizeof(f));
		memset(ans,0,sizeof(ans));
		m=0;
		for (int i=1;i<=n;i++) scanf("%d%d",&S[i].l,&S[i].r);
		sort(S+1,S+1+n,cmps);
		for (int i=1;i<=T;i++)
		{
			int ki,lastpos=0;
			scanf("%d",&ki);
			while (ki--) scanf("%d",&P[++m].x),P[m].id=i,P[m].prev=lastpos,lastpos=P[m].x;
		}
		sort(P+1,P+1+m,cmpp);
		for (int i=1;i<=n;i++) Change(S[i].l,1);
		for (int i=1,p=0;i<=m;i++)
		{
			int id=P[i].id,x=P[i].x;
			while (p<n && x>S[p+1].r) Change(S[++p].l,-1);
			ans[id]+=Query(x)-Query(P[i].prev);
		}
		for (int i=1;i<=T;i++) printf("%d\n",ans[i]);
	}
	return 0;
}

【merge】

  你TM倒是告诉我题目到底是什么意思......