1209 字
3 分钟
Atcoder_Beginner_Contest_475(A~E题)
2026-09-24
浏览量 142 · 访客 37

壁纸链接
题目链接:https://atcoder.jp/contests/abc475/tasks

A - mnclr#

先输出字符串的首字符,随后从第二个字符开始,在输出每个字符前额外输出一个o。这样恰好在原字符串的每对相邻字符之间插入一个o,不会在字符串首尾产生多余字符。时间复杂度为O(∣S∣)O(|S|)。

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#

设一次购买的价格为AA。最少需要支付⌈A1000⌉\lceil\frac{A}{1000}\rceil张纸币,因此找零金额只与A mod 1000A\bmod1000有关,可写为 C=(1000−A mod 1000) mod 1000C=(1000-A\bmod1000)\bmod1000。 外层取模用于处理AA恰好是10001000倍数的情况,此时无需找零。

由于硬币面值为1,10,1001,10,100,且每个面值都是较小面值的1010倍,要使硬币总数最少,只需从大到小使用硬币。于是100100元硬币数是CC的百位,1010元硬币数是十位,11元硬币数是个位。代码分别用除法和取模提取这三个数位,并累加每次购买得到的硬币。时间复杂度为O(N)O(N)。

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#

在线性结构上,从起点SS出发后所有访问过的点必然构成一个包含SS的连续区间[l,r][l,r]。用前缀和posipos_i表示第11个点到第ii个点的距离,并记 x=posS−posl,y=posr−posSx=pos_S-pos_l,\qquad y=pos_r-pos_S, 分别表示起点到区间左右端点的距离。

要访问整个区间,必须到达左右两个端点。可以先到左端点再移动到右端点,路程为2x+y2x+y;也可以先到右端点再移动到左端点,路程为x+2yx+2y。因此最短路程为 min⁡(2x+y,x+2y)=x+y+min⁡(x,y)\min(2x+y,x+2y)=x+y+\min(x,y)。 枚举所有l≤S≤rl\leq S\leq r,若该最短路程不超过LL,就用r−l+1r-l+1更新答案。随着ll向左移动,xx单调增大;一旦x>Lx>L,更靠左的端点也不可能合法,可以停止外层枚举。

前缀和预处理为O(N)O(N),区间枚举为O(N2)O(N^2),空间复杂度为O(N)O(N)。

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#

设n=∣S∣n=|S|。合法答案必须是nn位素数,因此先使用埃氏筛预处理区间[0,10n)[0,10^n)内的素数,再依次枚举[10n−1,10n)[10^{n-1},10^n)中的素数。枚举范围本身保证十进制表示长度为nn且没有前导零。

对于某个候选素数的十进制字符串TT,题目的等价条件要求:相同字符必须对应相同数字,不同字符也必须对应不同数字。代码同时维护字符到数字的映射ctodctod和数字到字符的映射dtocdtoc。扫描每个位置时,若任一方向与已经确定的映射冲突,则该候选不合法;两个方向都不冲突时,字符与数字之间就形成双射,满足题意。

令R=10nR=10^n。埃氏筛的时间复杂度为O(Rlog⁡log⁡R)O(R\log\log R),逐个检查候选数的复杂度上界为O(Rn)O(Rn),空间复杂度为O(R)O(R)。由于n≤7n\leq7,可以直接预处理到10710^7。

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#

先把每名参赛者的回答转换为长度为KK的二进制串:第jj位回答正确记为11,否则记为00。原判定过程等价于按照这些二进制串的字典序从大到小处理参赛者。某一位为11的参赛者优先于该位为00的参赛者;只有当前前缀对应的整组人数不超过剩余名额时,这一组才会全部通过。因此,对正确性串ss不全为00的参赛者,其能够通过当且仅当 #{x∣x≥s}≤M\#\{x\mid x\geq s\}\leq M, 其中比较采用字典序。全零串即使人数满足该不等式,也不会在任何一题被选为通过者,需要单独排除。

每次询问只会翻转一名参赛者正确性串中的一位,但需要动态查询不小于当前串的总人数。字符串不能直接作为树状数组下标,因此先离线重放所有询问,收集每名参赛者初始状态以及每次翻转后可能出现的状态。将这些字符串排序去重并离散化后,字典序就等价于离散编号的大小关系。

树状数组维护每个离散状态当前对应的人数。处理一次询问时,先删除该参赛者旧状态的计数,翻转对应位,再加入新状态。设新状态编号为idid,则小于它的人数为BIT.sum(id−1)BIT.sum(id-1),所以不小于它的人数为N−BIT.sum(id−1)N-BIT.sum(id-1)。结合全零串判定即可得到答案。

设不同状态数为V≤N+QV\leq N+Q。离线收集、排序和查找字符串的总时间复杂度可写为O((N+Q)Klog⁡V)O((N+Q)K\log V),树状数组更新与查询为O((N+Q)log⁡V)O((N+Q)\log V),空间复杂度为O((N+Q)K+V)O((N+Q)K+V)。

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 998244353
typedef 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;
}
分享

如果这篇文章对你有帮助,欢迎分享给更多人!

Atcoder_Beginner_Contest_475(A~E题)
https://mkrari.cn/posts/abc_475/
作者
Mkrari
发布于
2026-09-24
许可协议
CC BY-NC-SA 4.0