欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

Codeforces Round #264 (Div. 2)[ABCDE]

程序员文章站 2024-02-12 10:53:04
...

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不都是糖果吗...
反正要注意:

  1. 不能仅仅判断美分找的sweet,还要看能不能买得起
  2. 不要忽略恰好能买得起的

代码

/*
*  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【贪心】

题意
一个游戏,你必须跳过所有塔,游戏规则是:

  1. 初始你在0号塔,生命为0,0号塔高度为0。
  2. 只能从i跳到i+1号塔,生命变化为+(h[i]-h[i+1])
  3. 生命在任何时间都不能小于0
  4. 你可以花钱买一层的塔,让某个塔增高一层。

问通关最少要买几层塔。

分析

看懂题目贪心即可。

代码

/*
*  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,然后你要选择两个位置放棋子:

  1. 一个棋子能沿着对角线走,并吃掉格子上的value
  2. 任意一个格子不能同时被两个棋子走到,就是说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【暴力,非正解】

题意
给出一棵节点有值的树,有两个操作:

  1. 询问从根节点到某节点的路径中,深度最深且与该节点gcd>1的节点的标号。
  2. 修改某个节点的值。

分析

完全想不到暴力能轻易过,只能表示数据太弱...
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;
}