codeforces round #264 (div. 2)[abcde] acm 题目地址:codeforces round #264 (div. 2) 这场只出了两题tat，c由于cin给fst了，d想到正解快敲完了却game over了... 掉rating掉的厉害qvq... a - caisa and sugar 【模拟】 题意 ： caisa拿s美元去超市买sugar，
codeforces round #264 (div. 2)[abcde]acm
题目地址: codeforces round #264 (div. 2)
这场只出了两题tat，c由于cin给fst了，d想到正解快敲完了却game over了... 
掉rating掉的厉害qvq...
a - caisa and sugar【模拟】题意： 
caisa拿s美元去超市买sugar，有n种sugar，每种为xi美元yi美分，超市找钱时不会找美分，而是用sweet代替，当然能用美元找就尽量用美元找。他想要尽量得到多的sweet。问最多能得到几个sweet，买不起任何种的sugar的话就输出-1。
分析： 
表示题目略蛋疼，sugar和sweet不都是糖果吗... 
反正要注意：
不能仅仅判断美分找的sweet，还要看能不能买得起不要忽略恰好能买得起的代码：
/** author: illuz * blog: http://blog.csdn.net/hcbbt* file: a.cpp* create date: 2014-08-30 15:41:45* descripton: */#include using namespace std;#define repf(i,a,b) for(int i=(a);i
b - caisa and pylons【贪心】题意： 
一个游戏，你必须跳过所有塔，游戏规则是：
初始你在0号塔，生命为0，0号塔高度为0。只能从i跳到i+1号塔，生命变化为+(h[i]-h[i+1])生命在任何时间都不能小于0你可以花钱买一层的塔，让某个塔增高一层。问通关最少要买几层塔。
分析：
看懂题目贪心即可。
代码：
/** author: illuz * blog: http://blog.csdn.net/hcbbt* file: b.cpp* create date: 2014-08-30 15:57:02* descripton: */#include using namespace std;#define repf(i,a,b) for(int i=(a);i> n) { energy = 0, cast = 0; repf (i, 1, n) { cin >> h[i]; } repf (i, 0, n - 1) { energy += h[i] - h[i + 1]; if (energy
c - gargari and bishops【预处理，黑白棋】题意： 
给你一个棋盘，格子上有些value，然后你要选择两个位置放棋子：
一个棋子能沿着对角线走，并吃掉格子上的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 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
d - gargari and permutations【多序列lcs，dag】题意： 
求k个长度为n的序列的最长公共子序列。(2
分析： 
不能求前两个序列的lcs，然后拿结果去跟下面的求。 
因为前两个序列的lcs是不唯一的。
我们预处理(i,j)，如果对于每个序列都有pos[i] 这样就会转化为一个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 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
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 = 100000print n, nfor i in range(n - 1): print 2,print 3for i in range(n - 1): print i + 1, i + 2for i in range(n): print 1, n
代码：
/** author: illuz * blog: http://blog.csdn.net/hcbbt* file: e.cpp* create date: 2014-08-30 19:20:17* descripton: brute force, gcd*/#include using namespace std;#define repf(i,a,b) for(int i=(a);i mp[n];int n, q, v[n], fa[n], x, y;void dfs(int x, int f) { fa[x] = f; int sz = mp[x].size(); repf (i, 0, sz - 1) { if (mp[x][i] != f) { dfs(mp[x][i], x); } }}int main() { scanf(%d%d, &n, &q); repf (i, 1, n) { scanf(%d, &v[i]); } repf (i, 1, n - 1) { scanf(%d%d, &x, &y); mp[x].push_back(y); mp[y].push_back(x); } dfs(1, 0); repf (i, 1, q) { scanf(%d, &x); if (x == 1) { scanf(%d, &y); int i; for (i = fa[y]; i; i = fa[i]) if (__gcd(v[i], v[y]) > 1) break; if (!i) printf(-1\n); else printf(%d\n, i); } else { scanf(%d %d, &x, &y); v[x] = y; } } return 0;}