一个棋子能沿着对角线走，并吃掉格子上的value任意一个格子不能同时被两个棋子走到，就是说value不能重复吃
问能吃到的最大value和，以及两个棋子的位置。
分析：
对于规则2，就像黑白棋一样，只要放的颜色不一样就可以了，也就是(x+y)%2不一样就行了。
接下来就是求value和了。
棋盘大小为2000*2000，如果暴力每个格子放棋子能吃到的value和会超时。
很明显，(x,y)的value和就等于它所属的对角线和+斜对角线和-value(i,j)就行了。
我们只要预处理出每条对角线和斜对角线的和就行了。
我们发现(x+y)相同的格子都属于同个对角线，(x-y)相同的属于同个斜对角线。我们开两个数组来记录就行了，由于x-y会有负数，我们给它们+2000就行了。
这样，计算某个格子的value和的时候，直接取(x+y)对角线和及(x-y)斜对角线来做就行了。
代码：
/*
* Author: illuz
* Blog: http://blog.csdn.net/hcbbt
* File: C.cpp
* Create Date: 2014-08-30 16:26:14
* Descripton:
*/
#include
using namespace std; #define repf(i,a,b) for(int i=(a);i<=(b);i++) typedef long long ll; const int N = 2010; int n; ll v; ll x[N*2], y[N*2], mp[N][N]; pair
A, B; ll am, bm; int main() { scanf("%d", &n); A.first = 1; A.second = 2; B.first = 1; B.second = 1; repf (i, 1, n) repf (j, 1, n) { scanf("%lld", &v); x[i + j] += v; y[i - j + N] += v; mp[i][j] = v; } repf (i, 1, n) repf (j, 1, n) { v = x[i + j] + y[i - j + N] - mp[i][j]; if ((i + j) % 2) { if (am < v) { am = v; A.first = i; A.second = j; } } else { if (bm < v) { bm = v; B.first = i; B.second = j; } } } cout << am + bm << endl; cout << A.first << ' ' << A.second << ' '; cout << B.first << ' ' << B.second << endl; return 0; }
D - Gargari and Permutations【多序列LCS，DAG】
题意：
求k个长度为n的序列的最长公共子序列。(2<=k<=5)
分析：
不能求前两个序列的LCS，然后拿结果去跟下面的求。
因为前两个序列的LCS是不唯一的。
我们预处理(i,j)，如果对于每个序列都有pos[i] < pos[j]，就说明作为LCS的话，i后面可以跟j，然后在i,j间连一条边。
这样就会转化为一个DAG了，求下最长路就行了。
代码：
/*
* Author: illuz
* Blog: http://blog.csdn.net/hcbbt
* File: D.cpp
* Create Date: 2014-08-30 17:06:04
* Descripton:
*/
#include
using namespace std; #define repf(i,a,b) for(int i=(a);i<=(b);i++) typedef long long ll; const int N = 1010; int a[6][N], vis[N]; int n, k, v; int dp[N], mmax; vector
G[N]; bool check(int x, int y) { repf (i, 0, k - 1) { if (a[i][x] >= a[i][y]) return 0; } return 1; } int dfs(int x, int d) { int ret = 0; if (vis[x]) return vis[x]; int sz = G[x].size(); repf (i, 0, sz - 1) { ret = max(ret, dfs(G[x][i], d + 1)); } return vis[x] = ret + 1; } int main() { while (cin >> n >> k) { memset(vis, 0, sizeof(vis)); repf (i, 0, n) G[i].clear(); repf (i, 0, k - 1) { repf (j, 1, n) { cin >> v; a[i][v] = j; } } repf (i, 1, n) { repf (j, 1, n) { if (check(i, j)) { G[i].push_back(j); } } } mmax = 0; repf (i, 1, n) { if (!vis[i]) mmax = max(dfs(i, 0), mmax); } cout << mmax << endl; } return 0; }
E - Caisa and Tree【暴力，非正解】
题意：
给出一棵节点有值的树，有两个操作：
询问从根节点到某节点的路径中，深度最深且与该节点gcd>1的节点的标号。修改某个节点的值。
分析：
完全想不到暴力能轻易过，只能表示数据太弱...
dfs建树，记录下每个节点的父节点。
查询时用循环从查询节点向上找到符合的节点然后输出就行了。
数据太弱了，如果树是一条长链，最底端和其他节点的gcd=1，然后每次都查询最后一个节点，这样就会超时。
刚才试了下，貌似Solution里面没有一个能够避免TLE，全是暴力。
坐等官方正解。
下面是python写的TLE数据的数据生成器：
#!/usr/bin/python
# by hcbbt 2014-08-30 17:30:33
#
n = 100000
print n, n
for i in range(n - 1):
prin