分类存档：默认分类

SRM 557

最近rating直线下降…

250

给$$a_0$$, $$a_n$$, 在保证$$a_i \geq 0$$和$$|a_i – a_{i + 1}| \leq 1$$以及包含某个+1, -1片段的前提下，问能否构成目标序列。

$$O(n * history.size())$$的应该超级好写…显然整个过程可以看成先加若干再减若干.然后模拟就好了。
$$O(1)$$的也不难，设+1的数目为u，-1的数目为d，则$$u + d = n$$ 且$$u – d = a_n – a_0$$，可以解出u, d，再把+的都放在history前面，看能否可行即可。不过相比上面的略显麻烦。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define clr(a, x) memset(a, x, sizeof(a))
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }

class FoxAndMountainEasy {
public:
	string possible(int, int, int, string);
};

string FoxAndMountainEasy::possible(int n, int h0, int hn, string history) {
	int m = history.size();
	int Min = 0;
	int delta = 0;
	int cu = 0, cd = 0;
	for (int i = 0; i < m; i++) {
		if (history[i] == 'U') {
			delta++;
			cu++;
		} else {
			delta--;
			cd++;
		}
		if (delta < Min) Min = delta;
	}
	DEBUG(Min);
	int d = hn - h0;
	int up, down;
	if ((d + n) & 1) return "NO";
	up = (d + n) / 2;
	down = n - up;
	cout << up << " " << down << endl;
	if (cd > down || cu > up) return "NO";
	int k = h0 + up - cu;
	DEBUG(k);
	if (k + Min < 0) return "NO";
	return "YES";
}


//Powered by [KawigiEdit] 2.0!

550

预处理(把图作传递闭包，然后删除强连通中的点)完以后相当于，给定一个DAG图，若取了一个点，则其可达的点都不能取，问最多能取多少个点。

DAG图以及传递性保证了这是一个偏序集...于是这就是裸的最大反链
和HDOJ3335是一样的...把这个翻出来发现自己做过却完全想不来，太圡了。
反链科普：http://baike.baidu.com/view/2272728.htm
具体做法是传递闭包以后，得出这个有向图的邻接矩阵，把这个看成是点拆成两边的二分图，然后做最大匹配，答案就n-最大匹配。
之前一直不知道这个是怎么证明。
今天去看了一下，发现有个Dilworth's theorem 定理。
这个定理说明了：对于一个偏序集合，最大反链=最小路径覆盖，而且反链里的每个点，都属于不同的路径里面。
于是就是求最小路径覆盖就行了，最大匹配对应最小路径覆盖的证明就很简单了...
嗯，然后就这样...

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

template  void checkmin(T &t, T x){ if (x < t) t = x; }
template  void checkmax(T &t, T x){ if (x > t) t = x; }
template  void _checkmin(T &t, T x){ if (t == -1 || x < t) t = x; }
template  void _checkmax(T &t, T x){ if (t == -1 || x > t) t = x; }
#define clr(a, x) memset(a, x, sizeof(a))
class Incubator {
public:
	int maxMagicalGirls(vector );
};
const int N = 55;
int n;
int Link[N];
int mat[N][N];
int g[N][N];
int cover[N];

bool find(int i) {
	for (int j = 0; j < n; j++) {
		if (g[i][j] && !cover[j]) {
			cover[j] = 1;
			int q = Link[j];
			Link[j] = i;
			if (q == -1 || find(q)) return 1;
			Link[j] = q;
		}
	}
	return 0;
}

int Incubator::maxMagicalGirls(vector  love) {
	n = love.size();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			mat[i][j] = love[i][j] == 'Y';
		}
	}
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				mat[i][j] |= mat[i][k] & mat[k][j];	
			}
		}
	}
	vector  vec;
	for (int i = 0; i < n; i++)
		if (!mat[i][i]) vec.push_back(i);
	clr(g, 0);
	for (int i = 0; i < vec.size(); i++) {
		for (int j = 0; j < vec.size(); j++) {
			g[i][j] = mat[vec[i]][vec[j]];
		}
	}
	n = vec.size();
	int ans = n;
	clr(Link, 0xFF);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			printf("%d%c", g[i][j], j + 1 == n ? '\n' : ' ');
		}
	for (int i = 0; i < n; i++) {
		clr(cover, 0);
		if (find(i)) {
			ans--;
		}
	}
	return ans;
}

1000
给定n($$n \leq 50$$)个非负整数，每个数不超过$$10^15$$，每次可以进行一个操作：取$$a_i$$和$$a_j$$将，$$a_i$$替换成$$a_i \oplus a_j$$，问经过若干次操作以后，$$\sum_{i=1}^na_i$$最大能是多少。

首先注意异或这个初等变换是不会改变矩阵的秩的。
高斯消元求出这个异或空间的基以后，那些不是基的都可以变成空间里的最大值。
然后每个基对应的主元，都跑去把别人的对应位置消成0，于是每个主元在基里有且仅有一个1。
用异或空间的最大值去异或每个基，那么每个主元在对应列上有且仅有1个0(除了主元最大的那个基)。
而显然在不能改变矩阵秩的前提下，这个和是最大的了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

template  void checkmin(T &t, T x){ if (x < t) t = x; }
template  void checkmax(T &t, T x){ if (x > t) t = x; }
template  void _checkmin(T &t, T x){ if (t == -1 || x < t) t = x; }
template  void _checkmax(T &t, T x){ if (t == -1 || x > t) t = x; }

#define clr(a, x) memset(a, x, sizeof(a))
#define FOR(i, x, y) for (int (i) = (x); i < (y); (i)++)
#define REP(i, x) for (int (i) = 0; i < (x); i++)
#define foreach (it, v) for (__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define DEBUG(x) cout << #x " = " << (x) << endl
#define DEBUGARR(a, n) for (int i = 0; i < n; i++) cout << #a "[" << i << "] = " << (a)[i] << endl
#define DEBUGMATRIX(a, m, n) for (int i = 0; i < (m); cout << endl, i++) for (int j = 0; j < (n); j++) cout << (a)[i][j] << " "
typedef long long lld;
class XorAndSum {
public:
	long long maxSum(vector );
};

long long XorAndSum::maxSum(vector  a) {
	int n = a.size();
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++)	
			if (a[j] > a[i]) swap(a[i], a[j]);
		if (!a[i]) break;
		int k = 60;
		while (!(a[i] & 1LL << k)) k--;
		for (int j = 0; j < n; j++)
			if (i != j && a[j] & 1LL << k) {
				a[j] ^= a[i];
			}
	}
	lld maxValue = 0;
	for (int i = 0; i < n; i++) maxValue ^= a[i];
	lld ret = 0;
	for (int i = 0; i < n; i++)
		if (i == 0 || a[i] == 0) {
			ret += maxValue;
		} else {
			ret += maxValue ^ a[i];
		}
	return ret;
}