Codeforces Round #264 (Div. 2)[ABCDE]
來(lái)源：程序員人生 發(fā)布時(shí)間：2014-09-03 15:19:23 閱讀次數(shù)：2771次
Codeforces Round #264 (Div. 2)[ABCDE]
ACM
題目地址: Codeforces Round #264 (Div. 2)
這場(chǎng)只出了兩題TAT，C由于cin給fst了，D想到正解快敲完了卻game over了...
掉rating掉的厲害QvQ...
A - Caisa and Sugar【模擬】
題意：
Caisa拿s美元去超市買sugar，有n種sugar，每種為xi美元yi美分，超市找錢時(shí)不會(huì)找美分，而是用sweet代替，當(dāng)然能用美元找就盡量用美元找。他想要盡量得到多的sweet。問(wèn)最多能得到幾個(gè)sweet，買不起任何種的sugar的話就輸出-1。
分析：
表示題目略蛋疼，sugar和sweet不都是糖果嗎...
反正要注意：
- 不能僅僅判斷美分找的sweet，還要看能不能買得起
- 不要忽略恰好能買得起的
代碼：
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: A.cpp
* Create Date: 2014-08-30 15:41:45
* Descripton:
*/
#include <bits/stdc++.h>
using namespace std;
#define repf(i,a,b) for(int i=(a);i<=(b);i++)
typedef long long ll;
const int N = 110;
int x[N], y[N];
int n, s;
int main() {
int mmax = -1;
scanf("%d%d", &n, &s);
repf (i, 1, n) {
scanf("%d%d", &x[i], &y[i]);
if (x[i] < s) {
mmax = max(mmax, (100 - y[i]) % 100);
}
if (x[i] == s && y[i] == 0) {
mmax = max(mmax, 0);
}
}
printf("%d
", mmax);
return 0;
}
B - Caisa and Pylons【貪心】
題意：
一個(gè)游戲，你必須跳過(guò)所有塔，游戲規(guī)則是：
- 初始你在0號(hào)塔，生命為0，0號(hào)塔高度為0。
- 只能從i跳到i+1號(hào)塔，生命變化為
+(h[i]-h[i+1]) - 生命在任何時(shí)間都不能小于0
- 你可以花錢買一層的塔，讓某個(gè)塔增高一層。
問(wèn)通關(guān)最少要買幾層塔。
分析：
看懂題目貪心即可。
代碼：
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: B.cpp
* Create Date: 2014-08-30 15:57:02
* Descripton:
*/
#include <bits/stdc++.h>
using namespace std;
#define repf(i,a,b) for(int i=(a);i<=(b);i++)
typedef long long ll;
const int N = 1e5 + 10;
ll n, h[N];
ll energy, cast;
int main() {
while (cin >> 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 < 0) {
cast += -energy;
energy = 0;
}
}
cout << cast << endl;
}
return 0;
}
C - Gargari and Bishops【預(yù)處理，黑白棋】
題意：
給你一個(gè)棋盤，格子上有些value，然后你要選擇兩個(gè)位置放棋子：
- 一個(gè)棋子能沿著對(duì)角線走，并吃掉格子上的value
- 任意一個(gè)格子不能同時(shí)被兩個(gè)棋子走到，就是說(shuō)value不能重復(fù)吃
問(wèn)能吃到的最大value和，以及兩個(gè)棋子的位置。
分析：
對(duì)于規(guī)則2，就像黑白棋一樣，只要放的顏色不一樣就可以了，也就是(x+y)%2不一樣就行了。
接下來(lái)就是求value和了。
棋盤大小為2000*2000，如果暴力每個(gè)格子放棋子能吃到的value和會(huì)超時(shí)。
很明顯，(x,y)的value和就等于它所屬的對(duì)角線和+斜對(duì)角線和-value(i,j)就行了。
我們只要預(yù)處理出每條對(duì)角線和斜對(duì)角線的和就行了。
我們發(fā)現(xiàn)(x+y)相同的格子都屬于同個(gè)對(duì)角線，(x-y)相同的屬于同個(gè)斜對(duì)角線。我們開兩個(gè)數(shù)組來(lái)記錄就行了，由于x-y會(huì)有負(fù)數(shù)，我們給它們+2000就行了。
這樣，計(jì)算某個(gè)格子的value和的時(shí)候，直接取(x+y)對(duì)角線和及(x-y)斜對(duì)角線來(lái)做就行了。
代碼：
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: C.cpp
* Create Date: 2014-08-30 16:26:14
* Descripton:
*/
#include <bits/stdc++.h>
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<int, int> 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個(gè)長(zhǎng)度為n的序列的最長(zhǎng)公共子序列。(2<=k<=5)
分析：
不能求前兩個(gè)序列的LCS，然后拿結(jié)果去跟下面的求。
因?yàn)榍皟蓚€(gè)序列的LCS是不唯一的。
我們預(yù)處理(i,j)，如果對(duì)于每個(gè)序列都有pos[i] < pos[j]，就說(shuō)明作為L(zhǎng)CS的話，i后面可以跟j，然后在i,j間連一條邊。
這樣就會(huì)轉(zhuǎn)化為一個(gè)DAG了，求下最長(zhǎng)路就行了。
代碼：
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: D.cpp
* Create Date: 2014-08-30 17:06:04
* Descripton:
*/
#include <bits/stdc++.h>
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<int> 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【暴力，非正解】
題意：
給出一棵節(jié)點(diǎn)有值的樹，有兩個(gè)操作：
- 詢問(wèn)從根節(jié)點(diǎn)到某節(jié)點(diǎn)的路徑中，深度最深且與該節(jié)點(diǎn)gcd>1的節(jié)點(diǎn)的標(biāo)號(hào)。
- 修改某個(gè)節(jié)點(diǎn)的值。
分析：
完全想不到暴力能輕易過(guò)，只能表示數(shù)據(jù)太弱...
dfs建樹，記錄下每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)。
查詢時(shí)用循環(huán)從查詢節(jié)點(diǎn)向上找到符合的節(jié)點(diǎn)然后輸出就行了。
數(shù)據(jù)太弱了，如果樹是一條長(zhǎng)鏈，最底端和其他節(jié)點(diǎn)的gcd=1，然后每次都查詢最后一個(gè)節(jié)點(diǎn)，這樣就會(huì)超時(shí)。
剛才試了下，貌似Solution里面沒有一個(gè)能夠避免TLE，全是暴力。
坐等官方正解。
下面是python寫的TLE數(shù)據(jù)的數(shù)據(jù)生成器：
#!/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 <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: E.cpp
* Create Date: 2014-08-30 19:20:17
* Descripton: brute force, gcd
*/
#include <bits/stdc++.h>
using namespace std;
#define repf(i,a,b) for(int i=(a);i<=(b);i++)
typedef long long ll;
const int N = 1e5 + 10;
vector<int> 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
");
else
printf("%d
", i);
} else {
scanf("%d %d", &x, &y);
v[x] = y;
}
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
