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 <iilluzen>
* Blog: http://blog.csdn.net/hcbbt
* File: A.cpp
* Create Date: 2014-08-30 15:41:45
* Descripton:
*/
#include <bits>
using namespace std;
#define repf(i,a,b) for(int i=(a);i<br>
<br>
<hr>
<h2>
<span>B - Caisa and Pylons</span>【贪心】</h2>
<p>
<span>题意</span>： <br>
一个游戏，你必须跳过所有塔，游戏规则是：</p>
<ol>
<li>初始你在0号塔，生命为0，0号塔高度为0。</li>
<li>只能从i跳到i+1号塔，生命变化为<code>+(h[i]-h[i+1])</code>
</li>
<li>生命在任何时间都不能小于0</li>
<li>你可以花钱买一层的塔，让某个塔增高一层。</li>
</ol>
<p>
问通关最少要买几层塔。</p>
<p>
<span>分析</span>：</p>
<p>
看懂题目贪心即可。</p>
<p>
<span>代码</span>：</p>
<pre class="brush:php;toolbar:false">/*
* Author: illuz <iilluzen>
* Blog: http://blog.csdn.net/hcbbt
* File: B.cpp
* Create Date: 2014-08-30 15:57:02
* Descripton:
*/
#include <bits>
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 <br>
<br>
<hr>
<h2>
<span>C - Gargari and Bishops</span>【预处理，黑白棋】</h2>
<p>
<span>题意</span>： <br>
给你一个棋盘，格子上有些value，然后你要选择两个位置放棋子：</p>
<ol>
<li>一个棋子能沿着对角线走，并吃掉格子上的value</li>
<li>任意一个格子不能同时被两个棋子走到，就是说value不能重复吃</li>
</ol>
<p>
问能吃到的最大value和，以及两个棋子的位置。</p>
<p>
<span>分析</span>：</p>
<p>
对于规则2，就像黑白棋一样，只要放的颜色不一样就可以了，也就是(x+y)%2不一样就行了。</p>
<p>
接下来就是求value和了。 <br>
棋盘大小为2000*2000，如果暴力每个格子放棋子能吃到的value和会超时。 <br>
很明显，(x,y)的value和就等于它所属的对角线和+斜对角线和-value(i,j)就行了。 <br>
我们只要预处理出每条对角线和斜对角线的和就行了。 <br>
我们发现(x+y)相同的格子都属于同个对角线，(x-y)相同的属于同个斜对角线。我们开两个数组来记录就行了，由于x-y会有负数，我们给它们+2000就行了。</p>
<p>
这样，计算某个格子的value和的时候，直接取(x+y)对角线和及(x-y)斜对角线来做就行了。</p>
<p>
<span>代码</span>：</p>
<pre class="brush:php;toolbar:false">/*
* Author: illuz <iilluzen>
* Blog: http://blog.csdn.net/hcbbt
* File: C.cpp
* Create Date: 2014-08-30 16:26:14
* Descripton:
*/
#include <bits>
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 <br>
<br>
<hr>
<h2>
<span>D - Gargari and Permutations</span>【多序列LCS，DAG】</h2>
<p>
<span>题意</span>： <br>
求k个长度为n的序列的最长公共子序列。(2
</p>
<p>
<span>分析</span>： <br>
不能求前两个序列的LCS，然后拿结果去跟下面的求。 <br>
因为前两个序列的LCS是不唯一的。</p>
<p>
我们预处理(i,j)，如果对于每个序列都有pos[i]
这样就会转化为一个DAG了，求下最长路就行了。</p>
<p>
<span>代码</span>：</p>
<pre class="brush:php;toolbar:false">/*
* Author: illuz <iilluzen>
* Blog: http://blog.csdn.net/hcbbt
* File: D.cpp
* Create Date: 2014-08-30 17:06:04
* Descripton:
*/
#include <bits>
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 <br>
<br>
<hr>
<h2>
<span>E - Caisa and Tree</span>【暴力，非正解】</h2>
<p>
<span>题意</span>： <br>
给出一棵节点有值的树，有两个操作：</p>
<ol>
<li>询问从根节点到某节点的路径中，深度最深且与该节点gcd>1的节点的标号。</li>
<li>修改某个节点的值。</li>
</ol>
<p>
<span>分析</span>：</p>
<p>
完全想不到暴力能轻易过，只能表示数据太弱... <br>
dfs建树，记录下每个节点的父节点。 <br>
查询时用循环从查询节点向上找到符合的节点然后输出就行了。</p>
<p>
数据太弱了，如果树是一条长链，最底端和其他节点的gcd=1，然后每次都查询最后一个节点，这样就会超时。 <br>
刚才试了下，貌似Solution里面没有一个能够避免TLE，全是暴力。</p>
<p>
坐等官方正解。</p>
<p>
下面是python写的TLE数据的数据生成器：</p>
<pre class="brush:php;toolbar:false">#!/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
Nach dem Login kopieren
代码：
/*
* Author: illuz <iilluzen>
* Blog: http://blog.csdn.net/hcbbt
* File: E.cpp
* Create Date: 2014-08-30 19:20:17
* Descripton: brute force, gcd
*/
#include <bits>
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;
}
</bits></iilluzen>Nach dem Login kopieren
