观察到:我们可以从高位到第低位枚举第一个l和r不同的位置,记为diff,那么使得m取得最大的n有两种情况:要么n=r,要么n!=r,如果n!=r,那么要使得m最大,只有在
\[diff<=x<最大的位数 \]时,在[0,x-1]位上,n与r相同,x位上n=mr[x]-1,[x+1,最大位数]上全部填上k-1,故可以枚举x,加一个前缀和优化,复杂度是O(Tlogkr)
#include <iostream> #include <cstring> #include <algorithm> #include <vector> #define int long long using namespace std; int T, k, l, r; int l_k[110], r_k[110], sumr_k[110];//l_k是l的k进制表示,从最高位向最低位排序,r_k是r的k进制表示,sumr_k是r_k的前缀和 int kplus[110]; int kbit, ma; vector<int> max_num, min_num; signed main() { scanf("%lld", &T); int cnt = 0; while (T--) { scanf("%lld%lld%lld", &k, &l, &r); kbit = 0; //将l,r分解成k进制 int t = r; while (t)t /= k, kbit++; kplus[0] = 1; for (int i = 1; i <= kbit; i++)kplus[i] = kplus[i - 1] * k; for (int i = 0, j = kbit - 1; i < kbit; i++, j--) { l_k[i] = l / kplus[j] % k, r_k[i] = r / kplus[j] % k; //前缀和 if (!i)sumr_k[i] = r_k[0]; else sumr_k[i] = sumr_k[i - 1] + r_k[i]; } max_num.clear(); min_num.clear(); //找出第一个不同的位置 int diff = 0; for (; diff < kbit; diff++) if (l_k[diff] != r_k[diff])break; //特判第一位填0 bool zero = 0; if (!diff&&r_k[0] == 1)zero = 1; ma = 0; int min_id = kbit, maid = -1; //枚举x for (int i = diff; i < kbit; i++) { if (!r_k[i])continue; int tot = kbit; if (zero && !i)tot--; if (i)tot += sumr_k[i - 1]; tot += r_k[i] - 1; tot += (kbit - i - 1)*(k - 1); if (tot > ma) { ma = tot; maid = min_id = i; } else if (tot == ma) { maid = max(maid, i); min_id = min(min_id, i); } } //两种情况取最大 vector<int>ans1, ans2; int ma2 = 0; for (int i = 0; i < kbit; i++)ma2 += r_k[i]; ma2 += kbit; if (ma2 > ma) { for (int i = 0; i < kbit; i++)max_num.push_back(r_k[i]), min_num.push_back(r_k[i]); } else if (ma2 == ma) { for (int i = 0; i < kbit; i++)min_num.push_back(r_k[i]); for (int i = 0; i < min_id; i++)max_num.push_back(r_k[i]); max_num.push_back(r_k[min_id] - 1); for (int i = min_id + 1; i < kbit; i++)max_num.push_back(k - 1); } else { for (int i = 0; i < min_id; i++)max_num.push_back(r_k[i]); max_num.push_back(r_k[min_id] - 1); for (int i = min_id + 1; i < kbit; i++)max_num.push_back(k - 1); for (int i = 0; i < maid; i++)min_num.push_back(r_k[i]); min_num.push_back(r_k[maid] - 1); for (int i = maid + 1; i < kbit; i++)min_num.push_back(k - 1); } //输出 int xiao = 0, da = 0; for (int i = 0, j = kbit - 1; i < kbit; i++, j--)xiao += max_num[i] * kplus[j]; for (int i = 0, j = kbit - 1; i < kbit; i++, j--)da += min_num[i] * kplus[j]; printf("Case #%lld: %lld %lld %lld\n", ++cnt, max(ma, ma2) - 2, xiao, da); } }