Codeforces Round #264 (Div. 2)[ABCDE]
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 = 100000 print n, n for i in range(n - 1): print 2, print 3 for i in range(n - 1): print i + 1, i + 2 for 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; }
上一篇: git 代码强制覆盖
下一篇: Python 更新所有包
推荐阅读
-
Codeforces Round #264 (Div. 2)[ABCDE]
-
Codeforces Round #256 (Div. 2) 题解_html/css_WEB-ITnose
-
Educational Codeforces Round 81 (Rated for Div. 2) - D. Same GCDs - 扩欧+欧拉函数
-
Codeforces Round #231 (Div. 2)
-
Codeforces Round #220 (Div. 2) D 树状数组 && 二分_html/css_WEB-ITnose
-
Codeforces Round #247 (Div. 2) ABC
-
Codeforces Round #FF (Div. 2) 题解
-
Codeforces Beta Round #4 (Div. 2 Only) D. Mysterious Present_html/css_WEB-ITnose
-
Codeforces Round #201 (Div. 2) ABC 水题3道
-
Codeforces Round #277 (Div. 2)_html/css_WEB-ITnose