2026.2.7 ABC_444 赛时&补题记录
\(\textup{Link.}\)
打的很烂，全程摸了半小时鱼吧。
A - Repdigit
直接做。
$\textup{Code.}$
#include<bits/stdc++.h>using namespace std;
char a, b, c;
int main(){cin >> a >> b >> c;if( a == b && b == c ) cout << "Yes";else cout << "No";return 0;
}
B - Digit Sum
暴力做，不过我饭堂了 \(dfs\) 细节搞错了好多，浪费了好多时间。
$\textup{Code.}$
#include<bits/stdc++.h>using namespace std;
int N, K, ans;
void dfs( int now, int lst ){if( now > N ) return;if( lst == 0 ) ans ++;// cerr << now << " " << lst << " " << ans << endl;if( lst < 0 ){// cerr << now << " " << lst << " " << ans << endl;return;}for( int i = 0; i <= 9; i ++ ){if( now == 0 && i == 0 ) continue;dfs( now * 10 + i, lst - i );}
}
int main(){cin >> N >> K;dfs( 0, K );cout << ans;return 0;
}
C - AtCoder Riko
偏点子的思维，先读好题意。
考虑到要不然就全都摇不断，要不然就是两两配对。
于是就转化为最大值或者最大值和最小值的和，然后再 \(chk\) 就可以了。
$\textup{Code.}$
#include<bits/stdc++.h>using namespace std;
const int MAXN = 3e5 + 5;
int N;
int a[MAXN];
int maxx, minn = 0x3f3f3f3f;
int b[MAXN], tot;
bool chk1(){sort( b + 1, b + tot + 1 );if( tot % 2 ) return false;for( int i = 1; i <= tot / 2; i ++ ){if( ( b[i] + b[tot - i + 1] ) != maxx )return false;}return true;
}
bool chk2(){sort( a + 1, a + N + 1 );if( N % 2 ) return false;for( int i = 1; i <= N / 2; i ++ ){if( ( a[i] + a[N - i + 1] ) != ( maxx + minn ) )return false;}return true;
}
int main(){cin >> N;for( int i = 1; i <= N; i ++ ){cin >> a[i];maxx = max( maxx, a[i] );minn = min( minn, a[i] );}for( int i = 1; i <= N; i ++ ){if( a[i] != maxx ) b[++ tot] = a[i];}if( chk1() ) cout << maxx << " ";if( chk2() ) cout << minn + maxx;return 0;
}
D - Many Repunit Sum
把题目区间赋值 \(1\) 转化为差分操作，再扫一遍进位即可。
需要注意的就是进位的方向，调了一会儿。
$\textup{Code.}$
#include<bits/stdc++.h>using namespace std;
const int MAXN = 2e5 + 5;
int N;
int a[MAXN], diff[MAXN], sum[MAXN], maxx;
int main(){cin >> N;for( int i = 1; i <= N; i ++ ){cin >> a[i];maxx = max( maxx, a[i] );}for( int i = 1; i <= N; i ++ ){diff[1] += 1, diff[a[i] + 1] -= 1;}for( int i = 1; i <= maxx; i ++ ){sum[i] = sum[i - 1] + diff[i];}for( int i = 1; i <= maxx; i ++ ){if( sum[i] >= 10 ){sum[i + 1] += sum[i] / 10;sum[i] -= ( sum[i] / 10 ) * 10;maxx = max( maxx, i + 1 );}}for( int i = maxx; i >= 1; i -- ){cout << sum[i];}return 0;
}
E - Sparse Range、
本来考虑权值线段树维护，后来看了题解发现可以 \(set\) 直接二分最近的值，又快又好写。
注意使用 \(set\) 的边界条件。
实在没动力写两个版本了。
$\textup{Code.1}$
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 4e5 + 5;
int N, D, ans;
int a[MAXN];
set<int> st;
signed main(){cin >> N >> D;for( int i = 1; i <= N; i ++ ){cin >> a[i];}// st.insert( 1e9 );// st.insert( -1e9 );int r = 1;for( int l = 1; l <= N; l ++ ){// cerr << l << " " << r << endl;while( r <= N ){if( st.empty() ){st.insert( a[r] );r ++;continue; }auto it = st.lower_bound( a[r] );if( it == st.end() ){it --;if( a[r] - *it < D ) break;st.insert( a[r] );r ++;continue;}if( *it - a[r] < D ) break;if( it != st.begin() ){it --;if( a[r] - *it < D ) break;}st.insert( a[r] );r ++;}ans += r - l;//r是第一个不满足条件的位置，所以不用+1if( st.find( a[l] ) != st.end() ) st.erase( a[l] );}cout << ans;return 0;
}