
壁纸链接
题目链接:https://atcoder.jp/contests/abc475/tasks
A - mnclr
先输出字符串的首字符,随后从第二个字符开始,在输出每个字符前额外输出一个o。这样恰好在原字符串的每对相邻字符之间插入一个o,不会在字符串首尾产生多余字符。时间复杂度为。
void solve(){ string s; cin >> s; cout << s[0]; for(int i = 1; i < (int)s.size();i++){ cout << "o" << s[i]; } cout << '\n';}B - Change
设一次购买的价格为。最少需要支付张纸币,因此找零金额只与有关,可写为 。 外层取模用于处理恰好是倍数的情况,此时无需找零。
由于硬币面值为,且每个面值都是较小面值的倍,要使硬币总数最少,只需从大到小使用硬币。于是元硬币数是的百位,元硬币数是十位,元硬币数是个位。代码分别用除法和取模提取这三个数位,并累加每次购买得到的硬币。时间复杂度为。
void solve(){ int n; cin >> n; ll r1 = 0, r10 = 0, r100 = 0; for(int i = 1; i <= n;i++){ ll cost; cin >> cost; cost %= 1000; r100 += (1000 - cost) % 1000 / 100; r10 += (1000 - cost) % 100 / 10; r1 += (1000 - cost) % 10; } cout << r1 << " " << r10 << " " << r100 << '\n';}C - Walk the Line
在线性结构上,从起点出发后所有访问过的点必然构成一个包含的连续区间。用前缀和表示第个点到第个点的距离,并记 , 分别表示起点到区间左右端点的距离。
要访问整个区间,必须到达左右两个端点。可以先到左端点再移动到右端点,路程为;也可以先到右端点再移动到左端点,路程为。因此最短路程为 。 枚举所有,若该最短路程不超过,就用更新答案。随着向左移动,单调增大;一旦,更靠左的端点也不可能合法,可以停止外层枚举。
前缀和预处理为,区间枚举为,空间复杂度为。
void solve(){ int n, s; ll L; cin >> n >> s >> L; vector<ll> a(n); for(int i = 1; i < n;i++){ cin >> a[i]; } vector<ll> pos(n + 1, 0); for(int i = 1; i < n;i++){ pos[i + 1] = pos[i] + a[i]; } int ans = 1; for(int l = s; l >= 1;l--){ ll x = pos[s] - pos[l]; if(x > L) break; for(int r = s; r <= n;r++){ ll y = pos[r] - pos[s]; if(x + y + min(x, y) <= L){ ans = max(ans, r - l + 1); } } } cout << ans << '\n';}D - Alphametic Prime
设。合法答案必须是位素数,因此先使用埃氏筛预处理区间内的素数,再依次枚举中的素数。枚举范围本身保证十进制表示长度为且没有前导零。
对于某个候选素数的十进制字符串,题目的等价条件要求:相同字符必须对应相同数字,不同字符也必须对应不同数字。代码同时维护字符到数字的映射和数字到字符的映射。扫描每个位置时,若任一方向与已经确定的映射冲突,则该候选不合法;两个方向都不冲突时,字符与数字之间就形成双射,满足题意。
令。埃氏筛的时间复杂度为,逐个检查候选数的复杂度上界为,空间复杂度为。由于,可以直接预处理到。
void solve(){ string s; cin >> s; int n = static_cast<int>(s.size()); int L = static_cast<int>(pow(10, n- 1)); int R = static_cast<int>(pow(10, n));
//埃氏筛 vector<bool> prime(R, true); prime[0] = prime[1] = false; for(int i = 2; i * i < R;i++){ if(!prime[i]) continue; for(int j = i * i; j < R;j += i){ prime[j] = false; } };
for(int i = L; i < R;i++){ if(!prime[i]) continue; string t = to_string(i);
vector<int> ctod(256, -1); vector<int> dtoc(10, -1); bool ok = true;
for(int i = 0; i < n;i++){ char c = s[i]; int d = t[i] - '0'; if(ctod[c] == -1){ ctod[c] = d; } else if(ctod[c] != d){ ok = false; break; }
if(dtoc[d] == -1) dtoc[d] = c; else if(dtoc[d] != c){ ok = false; break; } } if(ok) {cout << t << '\n'; return;} } cout << -1 << '\n';}E - Quiz Competition: Qualifiers
先把每名参赛者的回答转换为长度为的二进制串:第位回答正确记为,否则记为。原判定过程等价于按照这些二进制串的字典序从大到小处理参赛者。某一位为的参赛者优先于该位为的参赛者;只有当前前缀对应的整组人数不超过剩余名额时,这一组才会全部通过。因此,对正确性串不全为的参赛者,其能够通过当且仅当 , 其中比较采用字典序。全零串即使人数满足该不等式,也不会在任何一题被选为通过者,需要单独排除。
每次询问只会翻转一名参赛者正确性串中的一位,但需要动态查询不小于当前串的总人数。字符串不能直接作为树状数组下标,因此先离线重放所有询问,收集每名参赛者初始状态以及每次翻转后可能出现的状态。将这些字符串排序去重并离散化后,字典序就等价于离散编号的大小关系。
树状数组维护每个离散状态当前对应的人数。处理一次询问时,先删除该参赛者旧状态的计数,翻转对应位,再加入新状态。设新状态编号为,则小于它的人数为,所以不小于它的人数为。结合全零串判定即可得到答案。
设不同状态数为。离线收集、排序和查找字符串的总时间复杂度可写为,树状数组更新与查询为,空间复杂度为。
void solve(){ int n, m, k; cin >> n >> m >> k; string t; cin >> t; vector<string> b(n + 1); for(int i = 1; i <= n;i++){ string s; cin >> s; b[i].resize(k); for(int j = 0; j < k;j++){ b[i][j] = (s[j] == t[j] ? '1' : '0'); } }
int Q; cin >> Q; vector<pii> query(Q);
for(int q = 0; q < Q;q++){ cin >> query[q].first >> query[q].second; query[q].second--; }
vector<string> all; for(int i = 1; i <= n;i++) all.push_back(b[i]);
vector<string> temp = b; for(auto [i, j] : query){ temp[i][j] ^= 1; all.push_back(temp[i]); }
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
auto get_id = [&](const string &s) -> int { return lower_bound(all.begin(), all.end(), s) - all.begin() + 1; };
int S = all.size(); BIT bit(S);
for(int i = 1; i <= n;i++){ bit.add(get_id(b[i]), 1); }
for(auto [i, j] : query){ int old_id = get_id(b[i]); bit.add(old_id, -1); b[i][j] ^= 1;
int new_id = get_id(b[i]); bit.add(new_id, 1);
int cnt = n - bit.sum(new_id - 1);
bool all_zero = true;
for(char ch : b[i]){ if(ch == '1'){ all_zero = false; break; } }
if(!all_zero && cnt <= m) cout << "Yes" << '\n'; else cout << "No" << '\n'; }}模板:
#include <bits/stdc++.h>
using namespace std;using ll = long long;using ull = unsigned long long;#define mod 998244353typedef pair<int, int> pii;typedef pair<ll, ll> pll;
ll fast_pow(ll a, ll b, ll MOD){ ll ans = 1; while(b){ if(b & 1) ans = (ans * a) % MOD; b >>= 1; a = (a * a) % MOD; } return ans;}
vector<ll> get_inverse(ll n, ll MOD){ vector<ll> inverse(n + 1, 0); inverse[1] = 1; for(int i = 2; i <= n;i++){ inverse[i] = MOD - (MOD / i) * inverse[MOD % i] % MOD; } return inverse;}
struct DSU{ vector<int> fa, sz; DSU(int n){ fa.resize(n + 1); sz.resize(n + 1, 1); for(int i = 1; i <= n;i++){ fa[i] = i; } } int find(int x){ if(fa[x] == x) return x; return fa[x] = find(fa[x]); }
bool merge(int x, int y){ x = find(x); y = find(y); if(x == y) return false; if(sz[x] > sz[y]) swap(x, y); fa[y] = x; sz[x] += sz[y]; return true; }};
struct BIT{ int n; vector<int> tr;
BIT(int n) { this -> n = n; tr.assign(n + 1, 0); }
void add(int x, int v){ while(x <= n){ tr[x] += v; x += x & -x; } }
int sum(int x) { int ans = 0; while(x > 0){ ans += tr[x]; x -= x & -x; } return ans; }};
void solve(){}
int main(){ ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int _ = 1; //cin >> _; while(_--){ solve(); } return 0;}