CF1567 - Codeforces Round 742 (Div. 2)

link: Codeforces Round #742 (Div. 2)

C - Carrying Conundrum

题意

Alice给出一种特殊的加法规则，每一位进位后会进位到更高的一位上，现在给出一个数 $n$ ，求有多少对数 $(a, b)$ 使其通过Alice加法相加能得到 $n$ 。

数据范围： $2\leqslant n \leqslant 10^9$ 。

思路

考虑将 $n$ 拆分成奇偶分开看，因为奇数位的数字进位只会进位到奇数位上，偶数位同理，所以他们互不影响。

比如 $12345$ ，拆分为 $135$ 和 $24$ ，那么这样拆分后，再找两个数通过正常加法得到他们，最后再将他们合并即可。

比如 $135 = 90 + 45$ ， $24=20+4$ ，那么通过Alice加法 $12345$ 是 $2900$ 和 $445$ 的和。

于是问题转换为 $n$ 在正常加法下有多少种分解， $n+0,n-1+1,\cdots,1+n-1,0+n$
一共 $n+1$ 种。

所以答案就是 $(135+1)\cdot(24+1) - 2$ =(奇数位数+1)(偶数位数+1)-2，减二原因是会有两对 $(0,0)$ 需要减去。

复杂度 $O(\log_{10}n)$ 。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		string s;
		s = to_string(n);
		int a = 0, b = 0;
		for (int i = 0; i < s.size(); i += 2) a = a * 10 + s[i] - '0';
		for (int i = 1; i < s.size(); i += 2) b = b * 10 + s[i] - '0';
		cout << (a + 1) * (b + 1) - 2 << '\n';
	}
	return 0;
}

D - Expression Evaluation Error

题意

给出 $n$ 个数在10进制下的和为 $s$ ，求他们最小在11进制下和的最小值。

数据范围： $1\leqslant s\leqslant 10^9,1\leqslant n\leqslant \min(100,s)$ 。

思路

这道题主要是要搞清楚，为什么11进制下和数会变小，我们记11进制下的10为字母A。

如果我们将 $1000$ 拆成两种： $900+100, 990+10$ ，那么第一种： $900+100=A00$ ，第二种： $990+10=9A0$ ，通过从高到低位置上数字大小比较，容易看出 $1000 > A00 > 9A0$ ，具体原因就是11进制下如果发生进位，就会导致数字减小1，从而总和下降，所以要尽可能不进位。

如果不进位呢？可以考虑将 $s$ 每一位尽可能平铺到 $n$ 位上面，比如 $s=354$ ， $n=5$ ，那么我们先铺 $300$ 拆分为三个 $100$ ，顺着放到 $n$ 个位子上

$\{100, 100, 100, 0, 0\}$

再拆 $50$ 拆成5个 $10$ ，接着上次结束的位置继续放，放满了就从头开始继续放：

先放2个： $\{100, 100, 100, 10, 10\}$ 放满了，从头接着再放3个： $\{110,110,110,10,10\}$

再拆 $4$ 拆成4个 $1$ ：

接着放4个： $\{111,111,110,11,11\}$

这样就完成题意了。

但如果遇到了，这样一次放不满的情况比如 $110 3$ ，拆成最后是 $\{100,10,0\}$ ，这时候就需要拆位：

将10拆成9和1，或100拆成90和10，可以发现 $90+10+10=100$ ，而 $100+9+1=1A0$ ，后者更大，这提醒我们要从低位开始拆。

所以最后得到的数组就是 $\{100,9,1\}$ 。

方法主要就是找到当前最小的10的倍数，拆分成比他小10倍的10个数，用贪心的思想，把后面的0都补全即可。

如果使用优先队列维护10的倍数和位置，以数字大小为键值，便可降低时间复杂度。

时间复杂度 $O(10\log_{10}s+n\log n)$ 。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 1e9+7;
int ksm(int a, int b) {int ret = 1; while (b) {if (b & 1) ret = (ret * a) % P; a = a * a % P; b >>= 1;} return ret;}
signed main(){
#ifdef _DEBUG
	//FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		priority_queue<pii, vp, greater<pii>> q;
		int n;
		string s;
		cin >> s >> n;
		vi ans(n);
		int p = 0, base = ksm(10, s.size() - 1);
		for (int i = 0; i < s.size(); i++, base /= 10) {
			for (int j = 0; j < s[i] - '0'; j++) {
				ans[p] += base;
				if (base != 1) q.push({base, p});
				p = (p + 1) % n;
			}
		}
		while (p < n && ans[p] == 0) {
			int x = q.top().second;
			q.pop();
			int base = ans[x] / 10;
			for (; p < n && ans[x] > base; p++) {
				ans[x] -= base;
				ans[p] += base;
				if (ans[p] != 1) q.push({ans[p], p});
			}
			if (ans[x] != 1) q.push({ans[x], x});
		}
		for (auto i : ans) cout << i << ' ';
		cout << '\n';
	}
	return 0;
}

E - Non-Decreasing Dilemma

题意

给出一个长度为 $n$ 的数组， $a_1,a_2,\ldots,a_n$ ，和 $q$ 次询问，每次询问有两种操作：

$1\ x\ y$ ：操作1，将 $a_x$ 变为 $y$ 。
$2\ l\ r$ ：操作2，求区间 $[l,r]$ 中非降序列（保持连续）的个数。

对于每次操作2输出你的答案。

数据范围： $1\leqslant n, q\leqslant 2\times 10^5, 1\leqslant a_i\leqslant 10^9$ 。

思路

由于一个长度为 $n$ 非降序列可以拆分成 $\frac{n(n+1)}{2}$ 个非降序列，所以我们只需要维护一个区间内的最长非降序列段的个数和长度即可。

可以通过线段树来实现，只需要维护下列4个参数：

从左端点开始的最长非降序列的长度（整型）
从右端点结束的最长非降序列的长度（整型）
是否一整段是一个非降序列（布尔型）
除去包含左端点和右端点的最长非降序列，中间段非降序列个数（注意不是最长，也就是拆分后的）（整型）

置于 $merge$ 操作有点复杂，但只要细心讨论，其实并不难实现，注意分类的情况（我分了8种😂）。

总复杂度： $\mathcal{O}(q\log n)$ 。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
#define ls (p<<1)
#define rs (p<<1|1)
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
const int N = 2e5 + 10;
int a[N];
struct SEG {
	struct Node {
		int l, r, lmx, rmx, tot;
		bool fg;
	}t[N<<2];
	void calc(Node &p, Node &l, Node &r) {
		p.lmx = l.lmx;
		p.rmx = r.rmx;
		int mid = (p.l + p.r) >> 1, tmp = l.rmx + r.lmx;
		p.fg = 0;
		if (l.fg && r.fg) {
			if (a[mid] <= a[mid+1]) {
				p.lmx = p.rmx = l.lmx + r.rmx;
				p.fg = 1;
			}
			p.tot = 0;
		} else if (l.fg) {
			if (a[mid] <= a[mid+1]) {
				p.lmx += r.lmx;
				p.tot = r.tot;
			} else {
				p.tot = r.tot + (r.lmx + 1) * r.lmx / 2;
			}
		} else if (r.fg) {
			if (a[mid] <= a[mid+1]) {
				p.rmx += l.rmx;
				p.tot = l.tot;
			} else {
				p.tot = l.tot + (l.rmx + 1) * l.rmx / 2;
			}
		} else {
			if (a[mid] <= a[mid+1]) p.tot = (tmp + 1) * tmp / 2;
			else p.tot = (l.rmx + 1) * l.rmx / 2 + (r.lmx + 1) * r.lmx / 2;
			p.tot += l.tot + r.tot;
		}
	}
	void pushup(int p) {
		calc(t[p], t[ls], t[rs]);
	}
	void build(int p, int l, int r) {
		t[p].l = l, t[p].r = r;
		if (l == r) {
			t[p].lmx = t[p].rmx = t[p].tot = 1;
			t[p].fg = 1;
			cin >> a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(ls, l, mid);
		build(rs, mid+1, r);
		pushup(p);
	}
	void update(int p, int x, int k) {
		if (t[p].l > x || t[p].r < x) return;
		if (t[p].l == x && t[p].r == x) {
			a[x] = k;
			return;
		}
		update(ls, x, k);
		update(rs, x, k);
		pushup(p);
	}
	Node query(int p, int l, int r) {
		if (t[p].l == l && t[p].r == r) return t[p];
		int mid = (t[p].l + t[p].r) >> 1;
		if (r <= mid) return query(ls, l, r);
		else if (l > mid) return query(rs, l, r);
		else {
			Node L = query(ls, l, mid), R = query(rs, mid+1, r);
			Node now = t[p];
			calc(now, L, R);
			return now;
		}
	}
	void solve() {
		int n, m;
		cin >> n >> m;
		build(1, 1, n);
		while (m--) {
			int opt, l, r;
			cin >> opt >> l >> r;
			if (opt == 1) {
				update(1, l, r);
			} else {
				Node ans = query(1, l, r);
				if (ans.fg) cout << (ans.lmx + 1) * ans.lmx / 2 << '\n';
				else cout << (ans.lmx + 1) * ans.lmx / 2 + (ans.rmx + 1) * ans.rmx / 2 + ans.tot << '\n';
			}
		}
	}
}seg;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	seg.solve();
	return 0;
}

coding > cf

#线段树 #贪心 #构造题 #模拟题

CF1567 - Codeforces Round 742 (Div. 2)

https://wty-yy.github.io/posts/29690/

作者

wty

发布于

2021年9月7日

许可协议

CF1569 - Educational Codeforces Round 113 (Rated for Div. 2) 上一篇

Linux系统使用pip成功安装软件包，但不能从命令行找到可执行文件？下一篇