1. chess

第一轮，A在(0,0)放棋子。

第二轮，B在每个(x,y)放棋子，满足(x-2,y)或(x-1,y-1)有且仅有1个是A的棋子。

第三轮，A每个(x,y)放棋子，满足(x-2,y)或(x-1,y-1)有且仅有1个是B的棋子。

重复上述过程（2,3），问第t轮后(x0,y0)~(x0+w, y0+h)的棋子情况（A，B，空）

$0\leq t, x0, y0 \leq 10^{12}, 0 \leq w,h \leq 50$

【题解】

有可能有棋子的只可能是点(x,y)，其中x+y为偶数，然后按照(x+y)/2的奇偶性来判断是什么棋子。

然后按照上述规律排列每个棋子，发现C(n,m)为偶数的时候是空格。

如何判断C(n,m)是不是偶数？

如果n&m==m，那么C(n,m)是奇数。

# include <stdio.h>
# include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int M = 60;

int w, h;
ll t, x, y;

char s[M][M];

int main() {
	freopen("chess.in", "r", stdin);
	freopen("chess.out", "w", stdout);
	scanf("%lld%lld%lld%d%d", &t, &x, &y, &w, &h);
	
	for (int i=0; i<w; ++i)
		for (int j=0; j<h; ++j) {
			ll newx = x+i, newy = y+j;
//			printf("%lld %lld\n", newx, newy);
			ll ss = newx + newy;
			if(ss&1) s[i][j] = '.';
			else {
				ss=ss>>1;
				if(ss+1<=t) {
//					printf("ss=%lld\n", ss);
					if(ss&1) s[i][j] = 'B';
					else s[i][j] = 'A';
					if((ss&newy) != newy) s[i][j] = '.';
				} else s[i][j] = '.';
			}
		}
	for (int i=h-1; i>=0; --i, puts(""))
		for (int j=0; j<w; ++j)
			printf("%c", s[j][i]);
	
	return 0;
}

// 5 4 1 3 4

2. shop

给出n个点m条边的无向图，标号为0~n-1，其中前p个点有商店，每个商店在l[i]-r[i]时间卖钻石，你需要花t[i]的时间买钻石，求你最多获得钻石数量。

$n, m \leq 50, p \leq 16$。

【题解】

状态压缩，$O(2^{p}pn)$。

# include <stdio.h>
# include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int M = 60;

ll f[1<<18][M];

int n, m, p;
ll dis[M][M];

int l[M], r[M], t[M];

int main() {
	freopen("shop.in", "r", stdin);
	freopen("shop.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &p);
	for (int i=0; i<n; ++i) {
		for (int j=0; j<n; ++j)
			dis[i][j] = 1ll<<40;
		dis[i][i] = 0;
	}
	for (int i=0; i<(1<<p); ++i)
		for (int j=0; j<n; ++j) f[i][j] = 1ll<<40;
	for (int i=1; i<=m; ++i) {
		int u, v;
		ll c;
		scanf("%d%d%lld", &u, &v, &c);
		dis[u][v] = min(dis[u][v], c);
		dis[v][u] = min(dis[v][u], c);
	}
	for (int k=0; k<n; ++k)
		for (int i=0; i<n; ++i)
			for (int j=0; j<n; ++j)
				dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
	for (int i=0; i<p; ++i) scanf("%d%d%d", &l[i], &r[i], &t[i]);
	f[0][n-1]=0;
	int ans = 0;
	for (int i=1; i<(1<<p); ++i) {
		int mx=0;
		for (int j=0; j<p; ++j) {
			if(i&(1<<j)) {
				++mx;
				for (int k=0; k<n; ++k)
					if(f[i^(1<<j)][k]+dis[j][k]<=r[j])
						f[i][j] = min(f[i][j], max((ll)l[j], f[i^(1<<j)][k]+dis[j][k])+t[j]);
			}
		}
		for (int j=0; j<n; ++j) {
			if(f[i][j] < (1ll<<40)) 
				ans = max(ans, mx);
		}
	}
	printf("%d\n", ans);
	return 0;
}

3. sequence

最大m子段和。

$m \leq n \leq 10^5, a_i \leq 10^9$。

【题解】

合并每个正段和负段。0合并到正段。然后用堆维护正负段（删除正段，加入负段）。

# include <stdio.h>
# include <algorithm>
# include <set>
# include <iostream>
# include <string.h>
# define abs(x) (x>0?x:-x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int M = 1000010;

int n, m;
ll a[M];

ll b[M];
int bn=0;
int S[M];
int fs[M], fsn=0;

struct node {
	ll cur;
	int id;
};

bool operator <(node a, node b) {
	return a.cur>b.cur;
}

set<node> s;

int fa[M];
int fl[M], fr[M];

inline int getf(int x) {
	return fa[x]==x ? x : fa[x] = getf(fa[x]);
}

inline void unions(int fx, int fy) {
	fa[fx] = fy;
	fl[fy] = min(fl[fy], fl[fx]);
	fr[fy] = max(fr[fy], fr[fx]);
}

int main() {
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
	while(~scanf("%d%d", &n, &m)) {
		memset(b,0,sizeof(b));
		memset(S,0,sizeof(S));
		s.clear();
		bn=fsn=0;
		for (int i=1; i<=n; ++i) scanf("%lld", &a[i]);
		int head=1, tail=n;
		while(a[head]<0) ++head;
		while(a[tail]<0) --tail;
		int zf=1;
		++bn;
		for (int i=head; i<=tail; ++i) {
			if(zf*a[i]>0 || (zf==1&&a[i]==0)) {
				b[bn]+=a[i];
				S[bn]++;
			} else {
				++bn;
				b[bn]=a[i];
				S[bn]=1;
				zf=-zf;
			}
		}
		int total1=0, total2=0;
		ll tot=0;
		for (int i=1; i<=bn; ++i) {
			if(b[i]>=0) {
				total1+=S[i];
				total2++;
				tot+=b[i];
			}
		}
		if(m >= total2 && m <= total1) {
			printf("%lld\n", tot);
		} else if(m > total1) {
			sort(a+1, a+n+1);
			ll ans=0;int k=0;
			for (int i=n;i>=1;--i) {
				++k;
				ans+=a[i];
				if(k==m)break;
			}
			printf("%lld\n", ans);
		} else if(m < total2) {
			for (int i=1; i<=bn; ++i) {
				b[i]=-abs(b[i]);
				s.insert((node){b[i],i});
			}
			int res = total2 - m;
			for (int i=1; i<=bn; ++i) fa[i] = i, fl[i] = fr[i] = i;
			for (int i=1; i<=res; ++i) {
				node x = *s.begin();
				s.erase(x);
				int fx = x.id, fll = fl[fx], frr = fr[fx];
				tot=tot+x.cur;
				int left=-1,right=-1;
				if(fll > 1) left=getf(fll-1);
				if(frr < bn) right=getf(frr+1);
				b[fx]=-b[fx];
				if(left!=-1) {
					s.erase((node){b[left], left});
					unions(left, fx);
					b[fx]+=b[left];
				}
				if(right!=-1) {
					s.erase((node){b[right], right});
					unions(right, fx);
					b[fx]+=b[right];
				}
				if(left!=-1 && right!=-1)
					s.insert((node){b[fx],fx});
			}
			printf("%lld\n", tot);
		}
	}
	
	return 0;
}