Codeforces Round# 308 (Div. 2) 总结

http://codeforces.com/contest/552

A:Vanya and Table

题意:给一堆矩形,求各个矩形面积和

直接模拟。。

#include<cstdio>
#include<algorithm>
int main() {
	int n;
	scanf("%d",&n);
	int ans = 0;
	for(int i = 0; i < n; ++i) {
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		ans += (std::abs(x1 - x2) + 1) * (std::abs(y1 - y2) + 1);
	}
	printf("%d\n", ans);
}

B. Vanya and Books

题意:统计1到n有多少十进制位

对于位数小于n的位数的打表统计,等于的直接算就行了。

有个地方忘了开LL FST了。。

 

#include<cstdio>
#include<iostream>
typedef long long LL;
LL f[20] = {0, 9, 180, 2700, 36000, 450000, 5400000, 63000000, 720000000, 8100000000LL};
inline int getdig(int n) {
	int ans=0;
	while(n) ++ans, n /= 10;
	return ans;
}
int main() {
	int n;
	scanf("%d", &n);
	int dig = getdig(n);
	LL ans = 0;
	for(int i = 1; i < dig; ++i) ans+=f[i];
	LL ten=1;
	while(ten * 10 <= n) ten *= 10;
	int t = n - ten + 1;
	ans += (LL) dig * t;
	std::cout << ans << std::endl;
}

C.Vanya and Scales

题意:有100个砝码,\(w^0,w^1,w^2,\dots,w^{100}\),问用这些砝码能不能称出来重量m。

首先把m用w进制表示出来。每一位上必须是0,1或者w-1,否则无解。

如果某一位上是w-1,那么它必定是减去了一个砝码得到的(相当于砝码和物品放在一侧),那么去掉这个砝码并且把砝码的质量给物品加上,天平依然平衡,所以加上这个砝码的质量也要满足要求才可以。

这样模拟一下就好了。。

#include<cstdio>
#include<vector>
using std::vector;
int w, m;
vector<int> ans;
void get(int x) {
	while(x)
		ans.push_back(x % w), x /= w;
}
bool judge() {
	for(int i = 0; i < ans.size(); ++i) {
		if(ans[i] >= w) {
			ans.push_back(0);
			ans[i+1] += ans[i] / w;
			ans[i] %= w;
		}
		if(ans[i] != 0 && ans[i] != w-1 && ans[i] != 1) return 0;
		if(ans[i] == w - 1 && w != 2) ans.push_back(0), ans[i] = 0, ans[i+1]++;
	}
	return 1;
}
int main() {
	scanf("%d%d", &w, &m);
	get(m);
	puts(judge() ? "YES" : "NO");
}

D. Vanya and Triangles

题意:给你n个点,问能组成多少三角形

枚举一个点,算一下它和其它点的斜率。有重复的说明有共线,减一下就行了。

#include<cmath>
#include<vector>
#include<cstdio>
#include<algorithm>
struct Point {
	int x, y;
	Point() {}
	Point(int x, int y) : x(x), y(y) {}
};
using std::vector;
const int MAXN = 2000 + 5;
Point po[MAXN];
const double eps=1e-10;
inline int dcmp(double x) {
	if(fabs(x) <= eps) return 0;
	return x < 0 ? -1 : 1;
}
inline double get_slope(Point A, Point B) {
	if(A.x == B.x) return 1e20;
	return (double)(A.y - B.y)/(double)(A.x - B.x);
}
int main() {
	int n;
	scanf("%d", &n);
	long long ans=(long long)n * (n-1) * (n-2) / 6;
	for(int i = 0; i < n; ++i)
		scanf("%d%d", &po[i].x, &po[i].y);
	for(int i = 0; i < n; ++i) {
		vector<double> vc;
		for(int j = i + 1; j < n; ++j)
			vc.push_back(get_slope(po[i], po[j]));
		std::sort(vc.begin(), vc.end());
		for(int j = 1; j < vc.size(); ++j) if(dcmp(vc[j]-vc[j-1]) == 0) {
			int t = 2;
			for(++j; j < vc.size() && dcmp(vc[j] - vc[j-1]) == 0; ++j) ++t;
			ans -= t * (t - 1) / 2;
		}
	}
	printf("%d\n", (int)ans);
}

E. Vanya and Brackets

给个表达式,运算符只包含+和*。添加一个括号使得表达式的值最大。

枚举一下两个乘号之间加括号就好了。。

python 题,不会python的哭了。。

好吧还是用C++写了一下。。

#include<cstdio>
#include<vector>
#include<cstring>
#include<string>
#include<stack>
#include<iostream>
#include<cctype>
#include<algorithm>
using std::stack;
using std::string;
using std::vector;
typedef long long LL;
inline int priority(char c) {
	if(c == '*') return 2;
	if(c == '+') return 1;
	return 0;
}
void po(stack<LL>& num, stack<char>& opt) {
	char c = opt.top(); opt.pop();
	LL a = num.top(); num.pop();
	LL b = num.top(); num.pop();
	if(c == '+') num.push(a + b);
	else num.push(a * b);
}
LL calc(const char* s) {
	stack<LL> num;
	stack<char> opt;
	int n = strlen(s);
	for(int i = 0; i < n; ++i) {
		if(isdigit(s[i])) {
			LL x = s[i] - '0';
			while(isdigit(s[i + 1]))
				x = x * 10 + s[++i] - '0';
			num.push(x);
		}
		else if(s[i] == '(')
			opt.push(s[i]);
		else if(s[i] == ')') {
			while(opt.top() != '(') po(num, opt);
			opt.pop();
		}
		else {
			while(!opt.empty() && priority(opt.top()) >= priority(s[i]))
				po(num, opt);
			opt.push(s[i]);
		}
	}
	while(!opt.empty()) po(num, opt);
	return num.top();
}
int main() {
	string s;
	std::cin >> s;
	s = "1*" + s +"*1";
	vector<int> mul;
	for(int i = 0; i < s.length(); ++i)
		if(s[i] == '*') mul.push_back(i);
	LL ans=calc(s.c_str());
	for(int i = 0; i < mul.size(); ++i)
		for(int j = i + 1; j<mul.size(); ++j) {
			string ts = s;
			ts.insert(mul[j], ")");
			ts.insert(mul[i] + 1, "(");
			ans = std::max(ans, calc(ts.c_str()));
		}
	std::cout << ans << std::endl;
}

 

发表评论

电子邮件地址不会被公开。