SCAU计算智能

• 作为计算智能题库与期末复习

练习使用多case解题

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll f(ll a, ll b) {
	ll r, A = a, B = b;
	while (b) {
		r = a % b;
		a = b;
		b = r;
	}
	return A * B / a;
}

int main()
{
	ll t, a, b;
	cin >> t;
	while (t--) {
		cin >> a >> b;
		swap(a, b);
		cout << f(a, b) << endl;
	}
	cout << "group 1 done" << endl;
	while (cin >> a >> b && (a || b)) {
		swap(a, b);
		cout << f(a, b) << endl;
	}
	cout << "group 2 done" << endl;
	while (cin >> a >> b) {
		swap(a, b);
		cout << f(a, b) << endl;
	}
	cout << "group 3 done" << endl;
	return 0;
}

走迷宫

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int t, n, m, w, dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 }, s1[110][2], s2[110][2], x, y, z1, z2;

struct p {
	int x, y, step;
	char c;
}a[110][110];

void dfs() {
	queue<p> q;
	a[x][y].c = '1';
	a[x][y].step = 0;
	q.push(a[x][y]);
	while (!q.empty()) {
		p s = q.front();
		q.pop();
		if (s.x == z1 && s.y == z2) {
			cout << s.step << endl;
			return;
		}
		int f = 1;
		for (int i = 0; i < w; ++i) {
			if (s.x == s1[i][0] && s.y == s1[i][1]) {
				a[s2[i][0]][s2[i][1]].c = '1';
				a[s2[i][0]][s2[i][1]].step = s.step + 1;
				q.push(a[s2[i][0]][s2[i][1]]);
				f = 0;
				break;
			}
		}
		if (f) {
			for (int i = 0; i < 4; ++i) {
				int x = s.x + dx[i], y = s.y + dy[i];
				if (x == -1 || x == n || y == -1 || y == m || a[x][y].c == '1')
					continue;
				a[x][y].c = '1';
				a[x][y].step = s.step + 1;
				q.push(a[x][y]);
			}
		}
	}
	cout << "die" << endl;
}

int main()
{
	cin >> t;
	while (t--) {
		cin >> n >> m;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				cin >> a[i][j].c;
				a[i][j].x = i;
				a[i][j].y = j;
			}
		}
		cin >> w;
		for (int i = 0; i < w; ++i)
			cin >> s1[i][0] >> s1[i][1] >> s2[i][0] >> s2[i][1];
		cin >> x >> y >> z1 >> z2;
		dfs();
	}
	return 0;
}

走迷宫2

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int t, n, m, dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 }, x, y, z1, z2;

struct p {
	int x, y, step;
	char c;
}a[110][110];

void dfs() {
	queue<p> q;
	a[x][y].c = '1';
	a[x][y].step = 0;
	q.push(a[x][y]);
	while (!q.empty()) {
		p s = q.front();
		q.pop();
		if (s.x == z1 && s.y == z2) {
			cout << s.step << endl;
			return;
		}
		for (int i = 0; i < 4; ++i) {
			int x = s.x + dx[i], y = s.y + dy[i];
			if (x == -1) x = n - 1;
			if (x == n) x = 0;
			if (y == -1) y= m - 1;
			if (y == m) y = 0;
			if (a[x][y].c == '1') continue;
			a[x][y].c = '1';
			a[x][y].step = s.step + 1;
			q.push(a[x][y]);
		}
	}
	cout << "die" << endl;
}

int main()
{
	cin >> t;
	while (t--) {
		cin >> n >> m;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				cin >> a[i][j].c;
				a[i][j].x = i;
				a[i][j].y = j;
			}
		}
		cin >> x >> y >> z1 >> z2;
		dfs();
	}
	return 0;
}

丑数

#include <iostream>
#include <algorithm>
using namespace std;

int t, n, dp[100010];

void f() {
	dp[1] = 1;
	int p2 = 1, p3 = 1, p5 = 1;
	for (int i = 2; i <= n; ++i) {
		dp[i] = min(dp[p2] * 2, min(dp[p3] * 3, dp[p5] * 5));
		if (dp[i] == dp[p2] * 2)
			p2++;
		if (dp[i] == dp[p3] * 3)
			p3++;
		if (dp[i] == dp[p5] * 5)
			p5++;
	}
}

int main()
{
	cin >> t;
	while (t--) {
		cin >> n;
		f();
		cout << dp[n] << endl;
	}
	return 0;
}

它不是丑数

#include <iostream>
#include <algorithm>
using namespace std;

int t, n, dp[1000010];

void f() {
	dp[1] = 1;
	int p2 = 1, p3 = 1, p5 = 1;
	for (int i = 2; i <= 3000; ++i) {
		dp[i] = min(dp[p2] * 2, min(dp[p3] * 3, dp[p5] * 5));
		if (dp[i] == dp[p2] * 2)
			p2++;
		if (dp[i] == dp[p3] * 3)
			p3++;
		if (dp[i] == dp[p5] * 5)
			p5++;
	}
}

int main()
{
	cin >> t;
	while (t--) {
		cin >> n;
		f();
		int res1 = 0, res2 = 1;
		while (res1 < n) {
			res1 += dp[res2 + 1] - dp[res2] - 1;
			res2++;
		}
		res2--;
		res1-= dp[res2 + 1] - dp[res2] - 1;
		cout << dp[res2] + n - res1 << endl;
	}
	return 0;
}

小明手上的牌

#include <iostream>
#include <algorithm>
using namespace std;

int n, m,res, a[100010];

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	for (int i = 0; i < m; ++i)
		if (a[n - 1] < n - i)
			res++;
	if (res == m) cout << a[n - 1];
	else cout << n - m + 1;
	return 0;
}

银行的叫号顺序

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int main()
{
	int n, time, vip, t = 99999, rt = -5;
	string name;
	priority_queue<pair<int, string>> q;
	cin >> n;
	while (n--) {
		cin >> time >> vip >> name;
		while (time > rt) {
			if (!q.empty()) {
				cout << q.top().second << endl;
				q.pop();
			}
			rt += 5;
		}
		q.push(make_pair(vip * 100000 + t, name));
		t--;
	}
	while (!q.empty()) {
		cout << q.top().second << endl;
		q.pop();
	}
	return 0;
}

银行服务

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int main()
{
	int n, stop, time, vip, t = 99999, rt = -5;
	string name;
	priority_queue<pair<int, string>> q;
	cin >> n >> stop;
	for (int i = 0; i < n; ++i) {
		cin >> time >> vip >> name;
		while (time > rt) {
			if (!q.empty()) {
				cout << q.top().second << endl;
				q.pop();
			}
			rt += 5;
		}
		q.push(make_pair(vip * 100000 + t, name));
		t--;
	}
	while (!q.empty()) {
		if (rt >= stop)
			break;
		cout << q.top().second << endl;
		q.pop();
		rt += 5;
	}
	return 0;
}

勇者斗恶龙

#include <iostream>
#include <algorithm>
using namespace std;

int n, m, a[200010], b[200010];

int main()
{
	while (cin >> n >> m && (n || m)) {
		for (int i = 0; i < n; ++i) cin >> a[i];
		for (int i = 0; i < m; ++i) cin >> b[i];
		sort(a, a + n);
		sort(b, b + m);
		int i = 0, j = 0, ans = 0;
		while (i < n && j < m) {
			if (a[i] > b[j])
				j++;
			else {
				ans += b[j];
				i++;
				j++;
			}
		}
		if (i == n) cout << ans << endl;
		else cout << "Loowater is doomed!" << endl;
	}
	return 0;
}

校赛排名

#include <iostream>
#include <algorithm>
using namespace std;

struct stu {
	int ac, time, c;
	char name[20];
	bool operator<(const stu b)const {
		if (ac != b.ac)
			return ac > b.ac;
		if (time != b.time)
			return time < b.time;
		return c < b.c;
	}
}s[1000010];

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> s[i].ac >> s[i].time >> s[i].name;
		s[i].c = i;
	}
	sort(s, s + n);
	for (int i = 0; i < n; ++i)
		cout << s[i].name << endl;
	return 0;
}

校赛排名2

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

struct stu {
	int ac = 0, time = 0, wa[50];
	char name[20];
	bool operator<(const stu b)const {
		if (ac != b.ac)
			return ac > b.ac;
		return time < b.time;
	}
}s[1000010];

int main()
{
	int t, re, snum = 0, i;
	char na[20], ti;
	while (cin >> t >> na >> ti >> re) {
		for (i = 0; i < snum; ++i)
			if (!strcmp(s[i].name, na))
				break;
		if (i == snum)
			strcpy(s[snum++].name, na);
		if (!re) {
			s[i].ac++;
			s[i].time += t;
			s[i].time += s[i].wa[ti - 'A'] * 20;
		}
		else s[i].wa[ti - 'A']++;
	}
	sort(s, s + snum);
	for (int i = 0; i < snum; ++i)
		if (s[i].ac)
			cout << s[i].name << " " << s[i].ac << " " << s[i].time << endl;
	return 0;
}

巡逻的士兵

#include <iostream>
#include <algorithm>
using namespace std;

int n, a[100010];

int f(int n) {
	if (n < 100000 && a[n])
		return a[n];
	if (n < 3) return 0;
	if (n == 3) return 1;
	int t = f(n / 2) + f((n + 1) / 2);
	if (n < 100000)
		a[n] = t;
	return t;
}

int main()
{
	while (cin >> n && n)
		cout << f(n) << endl;
	return 0;
}

偷懒的士兵

#include <iostream>
#include <algorithm>
using namespace std;

int n, a[100010];

int f(int n) {
	if (n < 100000 && a[n])
		return a[n];
	if (n < 3) return 0;
	if (n == 3) return 1;
	int t = f(n / 2) + f((n + 1) / 2);
	if (n < 100000)
		a[n] = t;
	return t;
}

int main()
{
	while (cin >> n && n)
		cout << n - 3 * f(n) << endl;
	return 0;
}

偷懒的士兵2

#include <iostream>
#include <algorithm>
using namespace std;

int f(int n, int l, int d) {
	if (n < 3) return l;
	if (n == 3) return 0;
	int ji = f(n / 2, l + d, d * 2);
	int ou = f((n + 1) / 2, l, d * 2);
	if (ji && ou)
		return min(ji, ou);
	if (ji) return ji;
	if (ou) return ou;
}

int main()
{
	int n;
	while (cin >> n && n)
		cout << f(n, 1, 1) << endl;
	return 0;
}

偷懒的士兵3

#include <iostream>
#include <algorithm>
using namespace std;

bool f(int n, int m) {
	if (n < 3) return false;
	if (n == 3) return true;
	if (m % 2) return f((n + 1) / 2, (m + 1) / 2);
	else return f(n / 2, m / 2);
}

int main()
{
	int n, m;
	while (cin >> n >> m && (n || m)) {
		if (f(n, m))
			cout << 'Y' << endl;
		else cout << 'N' << endl;
	}
	return 0;
}

除法等式

#include <iostream>
#include <algorithm>
using namespace std;

bool pan(int a, int b) {
	int f[10] = { 0 };
	while (a) {
		f[a % 10]++;
		a /= 10;
	}
	while (b) {
		f[b % 10]++;
		b /= 10;
	}
	for (int i = 1; i <= 9; ++i)
		if (f[i] > 1)
			return false;
	return true;
}

int main()
{
	int n;
	while (cin >> n && n) {
		for (int b = 1; b < 99999; ++b) {
			int a = b * n;
			if (a >= 100000) {
				cout << endl;
				break;
			}
			if (pan(a, b))
				printf("%05d/%05d=%d\n", a, b, n);
		}
	}
	return 0;
}

三角形

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		int a = n * n;
		for (int i = 1; i <= a; ++i) {
			int b = a / i - i, c = a / i + i;
			if (a % i == 0 && b > 0 && b % 2 == 0)
				printf("%d,%d\n", c / 2, b / 2);
		}
		for (int i = 1; i < n; ++i) {
			for (int j = i; j < n; ++j) {
				if (i * i + j * j == a)
					printf("%d,%d\n", j, i);
			}
		}
		cout << endl;
	}
	return 0;
}

龙龙

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;

ll f(int n) {
	ll s = 0, q = sqrt(n);
	for (int i = 1; i <= q; ++i)
		s += (n / i - n / (i + 1)) * i;
	for (int i = 1; i <= n / (q + 1); ++i)
		s += n / i;
	return s;
}

int main()
{
	int t, n;
	cin >> t;
	while (t--) {
		cin >> n;
		cout << f(n) << endl;
	}
	return 0;
}

分数拆分

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int main()
{
	ll n, x, y, z;
	while (cin >> n && n) {
		for (x = n + 1; x <= 3 * n; ++x) {
			for (y = ((n * x) / (x - n)) > x ? (n * x) / (x - n) : x; y <= 2 * n * x / (x - n); ++y) {
				if (x * y == (x + y) * n)
					printf("1/%lld=1/%lld+1/%lld\n", n, y, x);
				else if ((n * x * y) % (x * y - n * x - n * y) == 0 && (x * y - n * x - n * y) > 0) {
					z = (n * x * y) / (x * y - n * x - n * y);
					printf("1/%lld=1/%lld+1/%lld+1/%lld\n", n, z, y, x);
				}
			}
		}
		cout << endl;
	}
	return 0;
}

N皇后问题

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;

int a[20] = { 0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712 };

int main()
{
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		cout << a[n] << endl;
	}
	return 0;
}

最小的特殊数字

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll n, k, ans, a[100];

int main()
{
	cin >> n >> k;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	if (n == 1) {
		if (a[0] % k == 0) cout << a[0];
		else cout << -1;
		return 0;
	}
	sort(a, a + n);
	do {
		if (a[0] == 0)
			continue;
		ll t = 0;
		for (int i = 0; i < n; ++i)
			t = t * 10 + a[i];
		if (t % k == 0) {
			ans = t;
			break;
		}
	} while (next_permutation(a, a + n));
	if (!ans) cout << -1;
	else cout << ans;
	return 0;
}

最长公共子序列

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1010][1010];
string s1, s2;

int main()
{
	cin >> s1 >> s2;
	for (int i = 1; i <= s1.size(); ++i) {
		for (int j = 1; j <= s2.size(); ++j) {
			if (s1[i] == s2[j])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}
	cout << dp[s1.size()][s2.size()];
	return 0;
}

快乐

#include <iostream>
#include <algorithm>
using namespace std;

int n, a[100], b[100], dp[2010];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) cin >> b[i];
	for (int i = 1; i <= n; ++i)
		for (int j = 1999; j >= b[i]; --j)
			dp[j] = max(dp[j], dp[j - b[i]] + a[i]);
	cout << dp[1999] + 1;
	return 0;
}

万湖之国的形成

#include <iostream>
#include <algorithm>
using namespace std;

int n, ans, b[100010];

struct a {
	double x, y, r;
	bool operator<(const a b)const {
		return x + r < b.x + b.r;
	}
}a[100010];

int find(int x) {
	if (x != b[x])
		return b[x] = find(b[x]);
	return b[x];
}

int main()
{
	cin >> n;
	ans = n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i].x >> a[i].y >> a[i].r;
		b[i] = i;
	}
	sort(a, a + n);
	for (int i = 0; i < n; ++i) {
		for (int j = i - 1; j >= 0; --j) {
			if (a[i].x - a[i].r > a[j].x + a[j].r)
				break;
			if (((a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y)) < (a[i].r + a[j].r) * (a[i].r + a[j].r)) {
				int r = find(i), l = find(j);
				if (r != l) ans--;
				b[r] = l;
			}
		}
	}
	cout << ans;
	return 0;
}

繁忙的公路

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll n, m, a[1000010];

ll f(ll x) {
	ll s = 0;
	while (x) {
		s += a[x];
		x -= x & (-x);
	}
	return s;
}

void add(ll x, ll y) {
	while (x <= n) {
		a[x] += y;
		x += x & (-x);
	}
}

int main()
{
	cin >> n >> m;
	while (m--) {
		ll x, y;
		char c;
		cin >> c >> x >> y;
		if (c == 'Q') cout << f(y) - f(x - 1) << endl;
		else add(x, y);
	}
	return 0;
}

计分规则

#include <iostream>
#include <algorithm>
using namespace std;

int n, a[20];

void f(int x, int s) {
	if (x == n + 1) {
		if (s == 100) {
			for (int i = 1; i <= n; ++i)
				cout << a[i];
			cout << endl;
		}
		return;
	}
	else {
		a[x] = 0;
		f(x + 1, s - x);
		a[x] = 1;
		f(x + 1, s * 2);
	}
}

int main()
{
	cin >> n;
	f(1, 10);
	return 0;
}

圆覆盖

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;

long double r;
ll f, a, b, ans;

int main()
{
	cin >> r;
	f = r * r;
	for (a = 1; a <= r; ++a) {
		b = sqrt(1.0 * f - a * a);
		if (a * a + b * b != f)
			ans += 4 * b;
		else if (b > 0)
			ans += 4 * (b - 1);
	}
	f = r;
	ans += 4 * f;
	ans++;
	if (abs(f - r) < 1e-9)
		ans -= 4;
	cout << ans;
	return 0;
}