2025年4月28日CF补题
Educational Codeforces Round 178 补题
此次排名情况：
- 共1w2+，排名3905，做出ABCD四题。
- Rating+20，当前为
1326。 - 比赛链接
A. Three Decks
签到题
int a,b,c;
cin>>a>>b>>c;
c-=abs(a-b);
c-=max(a,b);
if(c<0) cout<<"NO\n";
else if(c%3==0) cout<<"YES\n";
else cout<<"NO\n";
B. Move to the End
从后往前贪心，看最大的元素和从后往前的第 \(i\) 个元素哪个更大。
int n,m;
struct nod{
ll zhi;
ll id;
friend bool operator <(nod x,nod y){
if(x.zhi!=y.zhi) return x.zhi<y.zhi;
else return x.id<y.id;
}
}a[N];
void solve(){
priority_queue<nod> pq;
map<ll,bool> mp;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].zhi;
a[i].id=i;
pq.push(a[i]);
}
ll sum=0;
for(int i=n;i>=1;i--){
sum+=a[i].zhi;
mp[i]=1;
ll x=pq.top().id;
while(mp[x]&&!pq.empty()){
pq.pop();
x=pq.top().id;
}
if(a[x].zhi>a[i].zhi){
sum-=a[i].zhi;
sum+=a[x].zhi;
cout<<sum<<" ";
sum+=a[i].zhi;
sum-=a[x].zhi;
}else cout<<sum<<" ";
}
cout<<"\n";
}
C. Card Game
判断多种情况即可。
void solve(){
int n;cin>>n;
string s;cin>>s;
if(n==2){
if(s=="AA"||s=="AB") cout<<"Alice\n";
else cout<<"Bob\n";
return;
}
int a1=0,a2=0,a3=0,a4=0,b1=0,b2=0,b3=0,b4=0;
if(s[0]=='A') a1=1;
else b1=1;
if(s[n-1]=='A') a2=1;
else b2=1;
for(int i=1;i<n-1;i++){
if(s[i]=='A') a3=1;
else b3=1;
}
if(s[n-2]=='A') a4=1;
else b4=1;
if(a1&&a2) cout<<"Alice\n";
else if(a1&&b3==0) cout<<"Alice\n";
else if(a2&&a4) cout<<"Alice\n";//a全部大于b//a有n和n-1,
else cout<<"Bob\n";
}
D. Array and GCD
我们可以通过\(+1\) 或 \(-1\) 的操作，在数组的和不变的情况下，更改任意数。
因为需要删除数最少，所以质数和也要最小。看在这个数组和的情况下，最小的质数和是哪一些。要求质数不能相同，所以就从2开始依次取质数。
因为数据范围的原因，不能 \(O(n^2)\) 的筛法，什么筛法最快？欧拉筛，又叫线性筛。
每次测试都筛太慢，预处理即可，我们其实只需要得到前 \(x\) 个质数的和。
根据数据范围可以得知 \(6e6\) 可以处理到 \(5e5\) 的质数。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+1;
ll n,a[N];
bool vis[6000000];
ll primes[N], tot; //素数表
vector<ll> v;
void sieve(int n){
v.push_back(0);
vis[1] = true;
for(int i = 2; i <= n; i ++){
if(!vis[i]){
primes[ ++ tot] = i;
v.push_back(v[tot-1]+i);
}
for(int j = 1; i * primes[j] <= n; j ++){
vis[i * primes[j]] = true;
if(i % primes[j] == 0)
break;
}
}
}
void solve(){
cin>>n;ll m=n;
ll sum=0,ans=0,k=1;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
sort(a+1,a+n+1);
ll tmp=v[m];
while(sum<tmp){
sum-=a[k++];
m--;
ans++;
tmp=v[m];
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
sieve(5999999);
int T;cin>>T;
while(T--){
solve();
}
return 0;
}
E. Unpleasant Strings
题意：
给定一个字符串 \(s\) 与一些字符串 \(t_i\) ，\(t_i\) 是 \(s\) 子序列，可以 \(t_i\) 后面加字符使得 \(t_i\) 不是 \(s\) 的子序列，最小添加字符是多少？有一个限制，\(s\) 和 \(t\) 以及添加的字符都是给定的前 \(k\) 个字符。
题解：
对每个位置 \(i\) 预处理出对于 \(s[i\sim n]\) 来说，至少要几个字母可以拼出不是子序列的字符串。对每个询问字符串 \(t\) ，找到 \(t\) 作为子序列匹配的末尾位置，直接用之前预处理的答案来回答就好了。
如何预处理？
设 \(nxt[j][i]\) 表示字母 ‘a’ 开始的第 \(j\) 个字母，在 \(i\) 位置之后第一次出现的位置。
\(dp[i]\) 表示对于 \(s[i\sim n]\) ，至少要几个字母可以拼出不是子序列的字符串。
则对从 ‘a’ 开始的前 \(k\) 个字母，若某字母在 \(i\) 的位置之后没有出现过，则 \(dp[i]\) 直接为 \(1\) ，因为直接添加这个字符串就不是子序列。否则 \(dp[i]=min(dp[i],dp[nxt[j][i]]+1)\) ，表示判断先加一个字母 \(j\) ，以此匹配到 \(i\) 之后的下一个字母 \(j\) 所在的位置，再加上此位置的答案是否更优。
高效寻找询问的 \(t\) 作为子序列匹配的末尾位置，也用到了 \(nxt\) 数组。
const ll inf=0x3f3f3f3f;
void solve(){
int n,k,q;
string s;
cin>>n>>k;
cin>>s;
s=" "+s;//下标从1开始
cin>>q;
//相当于int nxt[30][n+5]=-1;
vector<vector<int> > nxt(30,vector<int>(n+5,-1));
for(int i=n-1;i>=0;--i){
for(int j=1;j<=k;j++){
nxt[j][i]=nxt[j][i+1];
}
//nxt[x][i]=字母x在i位置后第一次出现的位置
nxt[s[i+1]-'a'+1][i]=i+1;
}
vector<int> dp(n+10,inf);
for(int i=n;i>=1;--i){
bool f=0;//如果出现了没有某个字母的情况,dp[i]直接=1,不用继续min
for(int j=1;j<=k&&f==0;++j){
if(nxt[j][i]==-1) dp[i]=1,f=1;
else dp[i]=min(dp[i],dp[nxt[j][i]]+1);
}
}
vector<int> ans;
while(q--){
string t;
cin>>t;
t=" "+t;
int p=0;
bool f=0;
for(int i=1;i<t.size()&&f==0;++i){
//如果某个字母没有出现，t就不是s的子序列
if(nxt[t[i]-'a'+1][p]==-1) ans.push_back(0),f=1;
else p=nxt[t[i]-'a'+1][p];
}
if(f) continue;
else ans.push_back(dp[p]);
}
for(int i=0;i<ans.size();i++) cout<<ans[i]<<"\n";
}
F. Numbers and Strings
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k;
map<string,int> mp;
vector<int> v;
int b[15];
int cnt[15];
void solve(){
int n;cin>>n;
cout<<upper_bound(v.begin(),v.end(),n)-v.begin()<<"\n";
}
void push(int x){
string g;
for(int i=0;i<=9;i++){
for(int j=1;j<=cnt[i];j++)
g+=(char)('0'+i);
}
if(!mp.count(g)) mp[g]=x;
else mp[g]=min(mp[g],x);
}
int get(){
int p=-1;
int all=0;
for(int i=0;i<=9;i++) all+=cnt[i];
if(all==0) return 0;
for(int i=1;i<=9;i++){
if(cnt[i]){
p=i;
break;
}
}
if(p==-1) return -1;
int ans=p;cnt[p]--;
for(int i=0;i<=9;i++){
for(int j=1;j<=cnt[i];j++){
ans=ans*10+i;
}
}
cnt[p]++;
return ans;
}
void work(int len){
for(int i=0;i<=9;i++) cnt[i]=0;
for(int i=1;i<=len;i++) cnt[b[i]]++;
if(cnt[9]==len){
cnt[1]++;
cnt[0]+=cnt[9];
int ans=0;
for(int i=1;i<=len;i++) ans=ans*10+9;
push(ans);
return;
}
for(int i=0;i<=cnt[9];i++){
for(int j=0;j<9;j++){
if(!cnt[j]) continue;
int ans=0;;
cnt[9]-=i;
cnt[j]--;
ans=get();
if(ans==-1){
cnt[9]+=i;cnt[j]++;
continue;
}
if(ans==0&&j==0) continue;
ans=(ans*10+j);
for(int k=1;k<=i;k++) ans=ans*10+9;
cnt[9]+=i;cnt[j]++;
for(int k=0;k<=9;k++) cnt[k]*=2;
cnt[9]-=i;cnt[j]--;
cnt[0]+=i;cnt[j+1]++;
push(ans);
cnt[0]-=i;cnt[j+1]--;
cnt[9]+=i;cnt[j]++;
for(int k=0;k<=9;k++) cnt[k]/=2;
}
}
}
void dfs(int u){
if(u>1&&b[u-1]) work(u-1);
if(u==10) return;
for(int i=b[u-1];i<=9;i++){
b[u]=i;
dfs(u+1);
}
}
void init(){
dfs(1);
for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++){
v.push_back((*it).second);
}
sort(v.begin(),v.end());
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;cin>>t;
init();
while(t--) solve();
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...) void(0)
#endif
using i64 = long long;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
string s;
unordered_map<string, int> mp;
auto add = [&](int u) {
if (u == 0 or u >= 999'999'999) return;
auto s = to_string(u) + to_string(u + 1);
ranges::sort(s);
if (not mp.contains(s)) {
mp[s] = u;
} else {
mp[s] = min(mp[s], u);
}
};
auto dfs = [&](this auto& dfs) -> void {
for (int i = 0; i < 10; i += 1) {
auto t = s + char('0' + i);
while (t.size() <= 9) {
add(stoi(t));
t += '9';
}
}
int d = 10;
if (s.empty()) d = 1;
if (s.size() == 1) d = 0;
if (1 < s.size() and s.size() <= 8) d = s.back() - '0';
for (int i = d; i < 10; i += 1) {
s.push_back(i + '0');
dfs();
s.pop_back();
}
};
dfs();
debug(mp.size());
vector<int> ans;
for (auto [x, y] : mp) ans.push_back(y);
ranges::sort(ans);
int t;
cin >> t;
for (int i = 0, n; i < t; i += 1) {
cin >> n;
cout << ranges::upper_bound(ans, n) - ans.begin() << "\n";
}
}
//jiangly的代码
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
void solve() {
int n;
std::cin >> n;
int ans = 0;
for (i64 x = 1; x <= n + 1; x *= 10) {
ans += std::min<i64>((n + 1) / x, 9);
}
ans--;
for (int len = 2; len <= 8; len += 2) {
std::string s;
s += '9';
s += std::string(len / 2, '0');
s += std::string(len / 2 - 1, '9');
for (int x = 1; x <= 8; x++) {
s += '0' + x;
if (std::stoi(s) <= n) {
ans--;
}
s.pop_back();
}
}
for (int len = 3; len <= 7; len += 2) {
std::string s;
s += '9';
s += std::string(len / 2, '0');
s += std::string(len / 2 - 1, '9');
for (int x = 1; x <= 8; x++) {
s += '0' + x;
s += '9';
if (std::stoi(s) <= n) {
ans--;
}
s.pop_back();
s.pop_back();
}
}
int d[9];
for (int i = 0, x = n; i < 9; x /= 10, i++) {
d[i] = x % 10;
}
std::array<std::array<int, 2>, 10> dp {};
for (int i = 8; i >= 1; i--) {
int ni = n;
for (int j = 0; j < i; j++) {
ni /= 10;
}
std::array<std::array<int, 2>, 10> ndp {};
for (int x = 1; x <= 9; x++) {
for (i64 y = x; y <= ni; y *= 10) {
ndp[x][y < ni]++;
}
}
for (int x = 0; x < 10; x++) {
for (int l = 0; l < 2; l++) {
for (int y = x; y <= (l ? 9 : d[i]); y++) {
ndp[y][l || y < d[i]] += dp[x][l];
}
}
}
dp = ndp;
if (i == 2) {
for (int x = 0; x <= 9; x++) {
ans += dp[x][0] * std::min(9, (n % 100 + 1) / 10);
ans += dp[x][1] * 9;
}
}
}
for (int x = 0; x <= 9; x++) {
ans += dp[x][0] * (std::min(d[0], 8) + 1);
ans += dp[x][1] * 9;
}
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
G. Modulo 3
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned int u32;
struct DSU {
vector<pair<int &, int>> his;
int n;
vector<int> f, g, bip;
DSU(int n_) : n(n_), f(n, -1), g(n, 0), bip(n, 1) {}
pair<int, int> find(int x) {
if (f[x] < 0)
return make_pair(x, 0);
pair<int, int> res = find(f[x]);
return make_pair(res.first, res.second ^ g[x]);
}
void set(int &a, int b) {
his.emplace_back(a, a);
a = b;
}
void merge(int a, int b, int &ans) {
pair<int, int> u_res = find(a);
pair<int, int> v_res = find(b);
int u = u_res.first, xa = u_res.second;
int v = v_res.first, xb = v_res.second;
int w = xa ^ xb ^ 1;
if (u == v) {
if (bip[u] && w) {
set(bip[u], 0);
ans--;
}
return;
}
if (f[u] > f[v]) {
std::swap(u, v);
}
ans -= bip[u];
ans -= bip[v];
set(bip[u], bip[u] && bip[v]);
set(f[u], f[u] + f[v]);
set(f[v], u);
set(g[v], w);
ans += bip[u];
}
int timeStamp() {
return his.size();
}
void rollback(int t) {
while (his.size() > t) {
pair<int &, int> &back = his.back();
back.first = back.second;
his.pop_back();
}
}
};
void add(vector<vector<array<int, 2>>> &edges, int p, int l, int r, int x, int y, array<int, 2> e, int N) {
if (l >= y || r <= x)
return;
if (l >= x && r <= y) {
edges[p].push_back(e);
return;
}
int m = (l + r) / 2;
add(edges, 2 * p, l, m, x, y, e, N);
add(edges, 2 * p + 1, m, r, x, y, e, N);
}
void dfs(vector<vector<array<int, 2>>> &edges, int p, int l, int r, int res, DSU &dsu, vector<int> &ans, const vector<int> &k, int N) {
int t = dsu.timeStamp();
int ores = res;
for (size_t i = 0; i < edges[p].size(); ++i) {
int x = edges[p][i][0];
int y = edges[p][i][1];
dsu.merge(x, y, res);
}
if (r - l == 1) {
if (k[l] % 3 != 2) {
ans[l] = k[l] % 3;
} else {
ans[l] = (N - res) % 2 ? 2 : 1;
}
} else {
int m = (l + r) / 2;
dfs(edges, 2 * p, l, m, res, dsu, ans, k, N);
dfs(edges, 2 * p + 1, m, r, res, dsu, ans, k, N);
}
res = ores;
dsu.rollback(t);
}
int main() {
ios::sync_with_stdio(false),cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> g(n);
for (int i = 0; i < n; i++) {
cin >> g[i];
g[i]--;
}
const int N = 4 << (31 - __builtin_clz(q));
vector<vector<array<int, 2>>> edges(N);
vector<int> t(n), k(q);
for (int i = 0; i < q; i++) {
int x, y;
cin >> x >> y >> k[i];
x--;
y--;
add(edges, 1, 0, q, t[x], i, , N);
g[x] = y;
t[x] = i;
}
for (int x = 0; x < n; x++) {
add(edges, 1, 0, q, t[x], q, , N);
}
vector<int> ans(q);
DSU dsu(n);
dfs(edges, 1, 0, q, n, dsu, ans, k, n);
for (int i = 0; i < q; i++) {
cout << ans[i] << "\n";
}
return 0;
}
