归档：220807 | 开门水题：STL 系列模板题

2022/8/8 6:22:51

编程Tag： int while FA so STL std maxn 水题 220807

本文主要是介绍归档：220807 | 开门水题：STL 系列模板题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

所有题目都在橙到绿之间。梦回小学。

UVA [101] - The Blocks Problem

用一个前驱数组和一个后继数组维护一个类似于链表的结构。

然后每次更改根据题意要求，依次递进地更改结点的前驱 / 后继即可。

namespace XSC062 {
using namespace fastIO;
const int maxn = 35;
char t, t1;
int n, x, y;
int fa[maxn], so[maxn];
inline void moto(int a, int b) {
	so[fa[a]] = 0;
	int x = a, y;
	while (so[x]) {
		y = x;
		x = so[x];
		so[y] = 0;
	}
	while (x != a) {
		y = x;
		x = fa[x];
		fa[y] = 0;
	}
	x = b;
	while (so[x]) {
		y = x;
		x = so[x];
		so[y] = 0;
	}
	while (x != b) {
		y = x;
		x = fa[x];
		fa[y] = 0;
	}
	fa[a] = b;
	so[b] = a;
	return;
}
inline void moer(int a, int b) {
	so[fa[a]] = 0;
	int x = a, y;
	while (so[x]) {
		y = x;
		x = so[x];
		so[y] = 0;
	}
	while (x != a) {
		y = x;
		x = fa[x];
		fa[y] = 0;
	}
	x = b;
	while (so[x]) 
		x = so[x];
	fa[a] = x;
	so[x] = a;
	return;
}
inline void pito(int a, int b) {
	so[fa[a]] = 0;
	int x = b;
	while (so[x]) {
		y = x;
		x = so[x];
		so[y] = 0;
	}
	while (x != b) {
		y = x;
		x = fa[x];
		fa[y] = 0;
	}
	fa[a] = b;
	so[b] = a;
	return;
}
inline void pier(int a, int b) {
	so[fa[a]] = 0;
	int x = b;
	while (so[x]) 
		x = so[x];
	fa[a] = x;
	so[x] = a;
	return;
}
inline bool check(int x, int y) {
	while (fa[x])
		x = fa[x];
	while (fa[y])
		y = fa[y];
	return x != y;
}
int main() {
	scanf("%d", &n);
	do {
		scanf("%1s%*s", &t);
		if (t == 'q')
			break;
		scanf("%d %*1s%1s%*s %d", &x, &t1, &y);
		if (!check(++x, ++y))
			continue;
		if (t == 'm') {
			if (t1 == 'n')
				moto(x, y);
			else moer(x, y);
		}
		else {
			if (t1 == 'n')
				pito(x, y);
			else pier(x, y);
		}
	} while (1);
	for (int i = 1; i <= n; ++i) {
		printf("%d:", i - 1);
		if (!fa[i]) {
			x = i;
			do {
				printf(" %d", x - 1);
				x = so[x];
			} while (x);
		}
		putchar('\n');
	}
	return 0;
}
} // namespace XSC062

UVA [1594] - Ducci Sequence

发现题目保证最多循环 \(10^3\) 次，考虑暴力模拟 \(10^3\) 次，若中间任意时刻整个数组为 \(0\)，则输出 ZERO，否则输出 LOOP。

优化：使用 std::map 或 std::set 存储某个序列是否出现过（可以采用 std::vector 实现），若出现过则输出 LOOP，不过不优化时间上也完全没有问题，故没有优化。

namespace XSC062 {
const int maxn = 25;
int T, n;
int a[maxn], b[maxn];
inline int abs(int x) {
	return x >= 0 ? x : -x;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i)
			scanf("%d", &a[i]);
		for (int _t = 1; _t <= 1000; ++_t) {
			a[n + 1] = a[1];
			bool flag = 1;
			for (int i = 1; i <= n; ++i) {
				b[i] = abs(a[i] - a[i + 1]);
				if (b[i])
					flag = 0;
			}
			if (flag)
				goto ZEROOOOO;
			memcpy(a, b, sizeof(a));
		}
		puts("LOOP");
		continue;
		ZEROOOOO:
			puts("ZERO");
	}
	return 0;
}
} // namespace XSC062

CodeChef [SGARDEN] - Garden Game

题意：有若干个环，求其大小的最小公倍数，结果对 \(10^9+7\) 取模。

一个典型的错解是，使用 \(x \times y \div \gcd(x,y)\) 与逆元 依次 求最小公倍数，因为取模会改变因子，从而使最大公约数的值 unexpected。

一个好的解决方案是模拟人工计算，将每一个 \(x\) 分解质因数并计算每个质因子最多的出现次数，最后相乘即可。

#define int long long
namespace XSC062 {
using namespace fastIO;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int T, n, x, cnt, res, tmp;
int a[maxn], u[maxn], p[maxn], tot[maxn];
inline int qkp(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1)
			(res *= x) %= mod;
		(x *= x) %= mod;
		y >>= 1;
	}
	return res;
}
inline int max(int x, int y) {
	return x > y ? x : y;
}
int main() {
	read(T);
	while (T--) {
		cnt = 0;
		res = 1;
		read(n);
		for (int i = 1; i <= n; ++i) {
			read(a[i]);
			u[i] = p[i] = tot[i] = 0;
		}
		for (int i = 1; i <= n; ++i) {
			if (p[i])
				continue;
			++cnt;
			x = i;
			do {
				p[x] = cnt;
				x = a[x];
				++u[cnt];
			} while (x != i);
		}
		for (int i = 1; i <= cnt; ++i) {
			for (int j = 2; j <= u[i]; ++j) {
				if (u[i] % j)
					continue;
				tmp = 0;
				while (!(u[i] % j)) {
					++tmp;
					u[i] /= j;
				}
				tot[j] = max(tot[j], tmp);
			}
		}
		for (int i = 1; i <= n; ++i)
			(res *= qkp(i, tot[i])) %= mod;
		printf("%lld\n", res);
	}
	return 0;
}
} // namespace XSC062
#undef int

UVA [400] - Unix ls

可以预先计算出共有几行几列。设最大长度为 \(m\)，则列数 \(l = \lfloor 62 \div m \rfloor\)，行数 \(c = \lceil n \div l \rceil\)。

为什么是 \(62\) 呢？因为有一列要少输出 \(2\) 个空格，为了方便，我们加上这 \(2\) 个空格使得其与其他列统一。

然后模拟行、列增加的过程（枚举行列或枚举字符串均可），最后输出即可。

namespace XSC062 {
const int maxn = 505;
std::string t;
std::string s[maxn];
std::string op[maxn][maxn];
int n, mx, l, c, m, tc, tl;
inline int max(int x, int y) {
	return x > y ? x : y;
}
int main() {
	while (std::cin >> m) {
		mx = 0;
		n = 0;
		std::getline(std::cin, t);
		for (int i = 1; i <= m; ++i) {
			std::getline(std::cin, t);
			std::stringstream temp(t);
			while (temp >> s[++n])
				mx = max(mx, s[n].length());
			--n;
		}
		n = m;
		std::sort(s + 1, s + n + 1);
		l = 62 / (mx + 2);
		c = (n + l - 1) / l;
		tc = tl = 1;
		for (int i = 1; i <= c; ++i) {
			for (int j = 1; j <= l; ++j)
				op[i][j].clear();
		}
		for (int i = 1; i <= n; ++i) {
			op[tc++][tl] = s[i];
			if (tc == c + 1) {
				++tl;
				tc = 1;
			}
		} 
		for (int i = 1; i <= 60; ++i)
			putchar('-');
		putchar('\n');
		for (int i = 1; i <= c; ++i) {
			for (int j = 1; j <= l; ++j) {
				if (op[i][j].size())
					std::cout << op[i][j];
				for (int k = s[(j - 1) * c + i].size() + 1;
					 k <= mx; ++k) {
					putchar(' ');
				}
				if (!op[i][j + 1].size())
					break;
				putchar(' ');
				putchar(' ');
			}
			putchar('\n');
		}
	}
	return 0;
}
} // namespace XSC062

UVA [1593] - Alignment of Code

一个简单的对齐输出。简单到我认为没有可讲的。

namespace XSC062 {
const int maxn = 1e4 + 5;
int n, lin;
int mx[maxn];
std::string t, t1;
std::vector<std::string> s[maxn];
inline int max(int x, int y) {
	return x > y ? x : y;
}
int main() {
	while (std::getline(std::cin, t)) {
		++lin;
		s[lin].clear();
//		s[lin].shrink_to_fit(); 
		std::stringstream temp(t);
		int cnt = 0;
		while (temp >> t1) {
			s[lin].push_back(t1);
			++cnt;
			mx[cnt] = max(mx[cnt], t1.length());
		}
	}
	for (int i = 1; i <= lin; ++i) {
		for (int j = 0; j < (int)s[i].size(); ++j) {
			std::cout << s[i][j];
			for (int k = s[i][j].size() + 1;
				 k <= mx[j + 1] + 1; ++k)
				putchar(' ');
		}
		putchar('\n');
	}
	return 0;
}
} // namespace XSC062

Codeforces [727B] - Bill Total Value

难点在于判断一个数为整数还是浮点数。

令某个存储了一整个数的字符串为 \(s\)。

不难发现，当 \(|s|\le 3\) 时，\(s\) 一定表示一个整数。

否则，若 \(s\) 表示整数，则位数 \(>3\)，至少分一段，此时 \(s_{|s|-4}\) 为 .（从 \(0\) 开始存储）。

其余情况，\(s\) 为浮点数。

namespace XSC062 {
using namespace fastIO;
bool f;
char inp;
std::string s, t;
int x, y, tx, ty, cnt;
int main() {
	std::getline(std::cin, s);
	s.push_back('#');
	std::stringstream temp(s);
	while (temp >> inp) {
		if (inp >= '0' && inp <= '9') {
			std::string tmp;
			tx = ty = 0;
			do tmp.push_back(inp); while (temp >> inp
				&& ((inp >= '0' && inp <= '9') || inp == '.'));
			if (tmp.size() <= 3)
				tx = std::stoi(tmp);
			else if (tmp[tmp.size() - 4] == '.') {
				for (auto i : tmp) {
					if (i >= '0' && i <= '9')
						tx = tx * 10 + i - '0';
				}
			}
			else {
				for (int i = 0; i < (int)tmp.size() - 2; ++i) {
					if (tmp[i] >= '0' && tmp[i] <= '9')
						tx = tx * 10 + tmp[i] - '0';
				}
				ty = (tmp[tmp.size() - 2] - '0') * 10
					 + tmp[tmp.size() - 1] - '0';
			}
			x += tx;
			y += ty;
		}
	}
	x += y / 100;
	y %= 100;
	if (!x)
		t.push_back('0');
	while (x) {
		t.push_back((x % 10) + '0');
		x /= 10;
	}
	std::reverse(t.begin(), t.end());
	cnt = t.length();
	for (const auto &i : t) {
		putchar(i);
		if (!((--cnt) % 3)) {
			if (cnt)
				putchar('.');
		}
	}
	if (y) {
		putchar('.');
		if (y < 10)
			putchar('0');
		std::cout << y;
	}
	return 0;
}
} // namespace XSC062


这篇关于归档：220807 | 开门水题：STL 系列模板题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！


相关编程文章

更多>
本站官方QQ
官方QQ:
23002807

沪ICP备2023033072号-1

     

扫一扫关注最新编程教程