赛时 6/8.
A
根据题意模拟即可。
#include<bits/stdc++.h>
#define ll long long
int T;
void solve() {
int n, m;
std::string a, b, c;
std::cin >> n;
std::cin >> a;
std::cin >> m;
std::cin >> b;
std::cin >> c;
for(int i = 0; i < m; i++) {
if(c[i] == 'V') a = b[i] + a;
else a = a + b[i];
}
std::cout << a << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin>>T;
while(T--) {
solve();
}
return 0;
}B
$y = 10^kx$ ，所以 $n = (10^k +1)x$，枚举 $k$ 即可求出 $x$ 与 $y$.
#include<bits/stdc++.h>
#define ll long long
int T;
void solve() {
ll n;
std::cin >> n;
std::vector<ll> ans;
ll x = 10;
while(x + 1 <= n) {
if(n % (x + 1) == 0) ans.push_back(n / (x + 1));
x *= 10;
}
sort(ans.begin(), ans.end());
std::cout << ans.size() << "\n";
for(auto x: ans) std::cout << x << " ";
if(ans.size()) std::cout << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin>>T;
while(T--) {
solve();
}
return 0;
}
C1
交易数量最少，所以按照三进制表示来交易即可。
#include<bits/stdc++.h>
#define ll long long
int T;
ll qpow(ll x, ll y) {
if(!y) return 1;
ll t = qpow(x, y / 2);
if(y & 1) return t * t * x;
return t * t;
}
void solve() {
ll n;
std::cin >> n;
ll x = 1, y = 0;
while(x * 3 <= n) {
x *= 3;
y++;
}
ll ans = 0;
while(n) {
while(n >= x) {
n -= x;
ans += qpow(3, y + 1) + y * qpow(3, y - 1);
}
x /= 3;
y--;
}
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin>>T;
while(T--) {
solve();
}
return 0;
}
C2
一个 $x$ 可以换成 $3$ 个 $x-1$. 要求总个数不超过 $k$.
由 $\dfrac{3^{x+1} + x\cdot 3^{x - 1}}{3^x} = 3 +$ $\dfrac{ x }{3}$ ，所以发现 $x$ 越大，西瓜的单价越高。
且 $3^{x+1} + x\cdot 3^{x - 1} - 3\times (3^x +(x - 1)\cdot 3^{x - 2}) = 3^{x-1}$，所以 $x$ 越大，换成 $x-1$ 所减少的金币数越多。
于是先求出三进制表示，然后从高位来向下换即可。
#include<bits/stdc++.h>
#define ll long long
int T;
ll qpow(ll x, ll y) {
if(!y) return 1;
ll t = qpow(x, y / 2);
if(y & 1) return t * t * x;
return t * t;
}
ll f(ll x) {
ll res = 0;
while(x) {
res += x % 3;
x /= 3;
}
return res;
}
void solve() {
ll n, k;
std::cin >> n >> k;
if(n <= k) {
std::cout << n * 3 << "\n";
return ;
} else if(k < f(n)) {
std::cout << "-1\n";
return ;
} else {
std::vector<ll> a;
ll x = n;
while(x) {
a.push_back(x % 3);
x /= 3;
}
std::reverse(a.begin(), a.end());
ll t = f(n);
int sz = a.size();
for(int i = 0; i + 1 < sz; i++) {
if(t + a[i] * 2 <= k) {
t += a[i] * 2;
a[i + 1] += 3 * a[i];
a[i] = 0;
} else {
ll tmp = (k - t) / 2;
t += tmp * 2;
a[i + 1] += 3 * tmp;
a[i] -= tmp;
}
}
std::reverse(a.begin(), a.end());
ll ans = 0;
for(ll i = 0; i < sz; i++) {
ans += a[i] * (qpow(3, i + 1) + i * qpow(3, i - 1));
}
std::cout << ans << "\n";
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin>>T;
while(T--) {
solve();
}
return 0;
}
D
#include<bits/stdc++.h>
#define ll long long
int T;
ll f(ll x) {
if(x <= 0) return 0;
ll tot = 0;
ll i = 1;
while(i <= x) {
ll a = i * 10;
ll b = x / a;
ll c = x % a;
tot += b * i * 45;
ll d = c / i;
tot += d * (c % i + 1);
tot += i * (d - 1) * d / 2;
i *= 10;
}
return tot;
}
ll ff(ll a, ll b) {
if(a > b) return 0;
return f(b) - f(a - 1);
}
void solve() {
ll k;
std::cin >> k;
ll ans = 0, len = 1, cnt = 9, st = 1;
while(k > 0) {
ll tt = cnt * len;
if(k >= tt) {
ll end = st + cnt - 1;
ans += ff(st, end);
k -= tt;
st = end + 1;
cnt *= 10;
len++;
} else {
ll a = k / len, b = k % len;
ll end = st + a - 1;
if(a > 0) {
ans += ff(st, end);
}
if(b > 0) {
ll c = st + a;
std::string s = std::to_string(c);
for(ll i = 0; i < b; i++) {
ans += s[i] - '0';
}
}
k = 0;
}
}
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin>>T;
while(T--) {
solve();
}
return 0;
}
E
把 $a, b$ 放在一个数组里并从大到小排序。
对于一个询问 $x, y, z$，若前 $z$ 个数中原先在 $a$ 数组的数的个数小于 $x$， 且原先在 $b$ 数组的数的个数小于 $y$，那么答案就是前 $z$ 个数之和。否则，假设原先在 $a$ 数组的数的个数大于 $x$，那么答案就是 $a$ 数组的前 $x$ 个最大的数之和加上 $b$ 数组的前 $z-x$ 个数之和；反之同理。
#include<bits/stdc++.h>
#define ll long long
#define N 200010
int T;
ll a[N], b[N], ca[N << 1], cb[N << 1], s[N << 1], sa[N], sb[N];
void solve() {
ll n, m, q;
std::cin >> n >> m >> q;
for(int i = 1; i <= n; i++) {
std::cin >> a[i];
}
for(int i = 1; i <= m; i++) {
std::cin >> b[i];
}
std::sort(a + 1, a + n + 1);
std::reverse(a + 1, a + n + 1);
std::sort(b + 1, b + m + 1);
std::reverse(b + 1, b + m + 1);
for(int i = 1; i <= n; i++) {
sa[i] = sa[i - 1] + a[i];
}
for(int i = 1; i <= m; i++) {
sb[i] = sb[i - 1] + b[i];
}
int x = 1, y = 1;
for(int i = 1; i <= n + m; i++) {
if(x > n) {
s[i] += b[y];
ca[i] = 0;
cb[i] = 1;
y++;
} else if(y > m) {
s[i] += a[x];
ca[i] = 1;
cb[i] = 0;
x++;
} else if(a[x] > b[y]) {
s[i] += a[x];
ca[i] = 1;
cb[i] = 0;
x++;
} else{
s[i] += b[y];
ca[i] = 0;
cb[i] = 1;
y++;
}
}
for(int i = 1; i <= n + m; i++) {
ca[i] += ca[i - 1];
cb[i] += cb[i - 1];
s[i] += s[i - 1];
}
for(int i = 1; i <= q; i++) {
ll xx, yy, zz;
std::cin >> xx >> yy >> zz;
if(ca[zz] <= xx && cb[zz] <= yy) {
std::cout << s[zz] << "\n";
}
else {
if(ca[zz] > xx) {
std::cout << sa[xx] + sb[zz - xx] << "\n";
}
else {
std::cout << sb[yy] + sa[zz - yy] << "\n";
}
}
}
for(int i = 1; i <= n; i++) {
a[i] = sa[i] = 0;
}
for(int i = 1; i <= m; i++) {
b[i] = sb[i] = 0;
}
for(int i = 1; i <= n + m; i++) {
ca[i] = cb[i] = s[i] = 0;
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin>>T;
while(T--) {
solve();
}
return 0;
}
评论 (0)