CFGYM104077E

数位dp一般题

CFGYM104077 Find Maximum

大意

求l和r之间三进制下popcount的大小

代码

也用到了两个数字之间限制的tirck

#include <bits/stdc++.h>

using i64 = long long;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);


	int t;
	std::cin >> t;
	while (t--) {
		i64 l, r;
		std::cin >> l >> r;
		auto getstr = [&](i64 x) {
			std::vector<int> ret;
			do {
				ret.emplace_back(x % 3);
				x /= 3;
			} while (x);
//			std::reverse(ret.begin(), ret.end());
			return ret;
		};
		auto a = getstr(l), b = getstr(r);
		int n = b.size();
		if (a.size() != b.size())a.resize(b.size());
		std::reverse(a.begin(), a.end());
		std::reverse(b.begin(), b.end());
		std::vector dp(n, std::array<int, 8>{-1, -1, -1, -1, -1, -1, -1, -1});
		std::function<int(int, int)> dfs = [&](int pos, int stat) {
			int qd0 = stat >> 2 & 1;
			int limita = stat >> 1 & 1;
			int limitb = stat & 1;
			if (pos == n) {
				return qd0;
			}
			if (dp[pos][stat] != -1)return dp[pos][stat];
			int l = limita ? a[pos] : 0;
			int r = limitb ? b[pos] : 2;
			int ans = 0;
			for (int i = l; i <= r; ++i) {
				int nxt = 0;
				nxt |= (qd0 && i == 0) << 2;
				nxt |= (limita && i == l) << 1;
				nxt |= (limitb && i == r);
				ans = std::max(ans, (!(qd0 && i == 0)) + i + dfs(pos + 1, nxt));
			}
			return dp[pos][stat] = ans;
		};
		std::cout << dfs(0, 7) << '\n';
	}

	return 0;
}