Best coder 2014-3-14例题

Best coder 2014-3-14题解

 zhx's submissions  题目链接

	签到题，模拟大数加法，不用进位（要用char[]读入，string超时）

zhx's contest 题目链接
      可以很快推导出公式为2^n -2, 这里由于n和mod都是在long long范围内，因此需要快速乘，但是也会导致long long * long long 溢出，因此将乘法改造成快速加。
zhx and contest 题目链接
搜索+剪枝 水过。。。
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <fstream>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <utility>
#include <cstring>
#include <list>
#include <stack>
#include <cstdio>
using namespace std;

#define ft first
#define sd second

typedef long long LL;
typedef unsigned int UI;

const int MAXN = 511111;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const LL MAXL = (0x7fffffffffffffffLL);
const int MAXI = 0x7fffffff;


//java BigInteger ¿ÉÒÔ×Ô¶¨Òå½øÖÆ 

inline int toInt(char c) {
	if (c >= '0' && c <= '9') return c - '0';
	return c - 'a' + 10;
}

inline char toChar(int c, int base) {
	c %= base;
	if (c >= 0 && c <= 9) {
		return (char)(c + '0');
	}
	return (char)('a' + c - 10);
}
inline void add(string &res, const string &number, int base) {
	for (int i = 0; i < number.length(); i++) {
		int c = toInt(res[i]) + toInt(number[i]);
		res[i] = toChar(c, base);
	}
}

int main() {
	int n, b;
	while (cin >> n >> b) {
		string res(222, '0');
		for (int i = 0; i < n; i++) {
			char s[222];
			scanf("%s", s);
			string number(s);
			reverse(number.begin(), number.end());
			add(res, number, b);
		}
		reverse(res.begin(), res.end());
		if (res.find_first_not_of('0') == string::npos) {
			cout << 0 << endl;
		}
		else {
			cout << res.substr(res.find_first_not_of('0')) << endl;
		}
	}
}


#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <fstream>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <utility>
#include <cstring>
#include <list>
#include <stack>
#include <cstdio>
using namespace std;

#define ft first
#define sd second

typedef long long LL;
typedef unsigned int UI;

const int MAXN = 511111;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const LL MAXL = (0x7fffffffffffffffLL);
const int MAXI = 0x7fffffff;

long long mul(long long n, long long m, long long mod) {
	long long ret = 0, base = m;
	for (; n; base = base * 2 % mod, n >>= 1) {
		if (n & 1) {
			ret = (ret + base) % mod;
		}
	}
	return ret;
}

long long solve(long long n, long long m, long long mod) {
	long long ret = 1, b = m;
	for (; n; n >>= 1, b = mul(b, b, mod)) {
		if (n & 1) {
			ret = mul(ret, b, mod);
		}
	}
	return ret;
}

// 这题推导出公式很简单，2^n -2
// 由于n和p的范围都是long long 的，直接二分乘法会溢出，因此乘法应该用快速乘（即用加法模拟乘法）
// 乘方复杂度logn , 加法复杂度log(MAX_Longlong)
int main() {
	long long n, p;
	while (cin >> n >> p) {
		cout << (solve(n, 2, p) - 2 + p) % p << endl;
	}
}
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <fstream>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <utility>
#include <cstring>
#include <list>
#include <stack>
#include <cstdio>
using namespace std;

#define ft first
#define sd second

typedef long long LL;
typedef unsigned int UI;

const int MAXN = 511111;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const LL MAXL = (0x7fffffffffffffffLL);
const int MAXI = 0x7fffffff;

struct Problem {
	int t, l;
	long long v;
	Problem(int t, long long v, int l) : t(t), v(v), l(l) {}

};
bool operator<(const Problem&a, const Problem &b) {
	return a.l - a.t < b.l - b.t;
}
vector<Problem> problems;
int n, w;
void dfs(int s, int ct, int score, int &ans) {
	if (score >= w) {
		ans = ct;
		return;
	}
	for (int i = s; i < problems.size(); i++) {
		int t = max(ct + problems[i].t, problems[i].l);
		if (t < ans) {
			dfs(i+1, t, score+problems[i].v, ans);
		}
	}
}

int main() {

	while (cin >> n >> w) {
		problems.clear();
		long long total = 0;
		for (int i = 0; i < n; i++) {
			int t, l; long long v;
			scanf("%d %lld %d", &t, &v, &l);
			problems.push_back(Problem(t, v, l));
			total += v;
		}
		if (total < w) {
			puts("zhx is naive!");
			continue;
		}
		sort(problems.begin(), problems.end());
		int ans = MAXI;
		dfs(0, 0, 0, ans);
		cout << ans << endl;

	}
}