2026/7/12 打了三场比赛。
第一次 Rated 打 ARC。
上一次打 ARC 是受到 zt17 邀请，Unrated 打 ARC223。为了 Rated 打 ARC 在 7/11 打了 ABC466。
洛谷入门赛 #49
19:00~21:00
没什么好说的。打完了才发现等级分限制 \(1200\)，我 \(1387\)，不能涨等级分。
很快写完了，太简单了不放了。
AtCoder ARC224
20:00~22:00
A
猜测答案为 \(\mathcal O(1)\times k\)，所以直接打了个暴力，过了。
容易发现 \(100k\) 是有 \(2\) 个连续零的，所以暴力增加的次数 \(\leq100\)。\(T\leq10^5\)，可以通过。
赛时代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
int k;
bool check(ll ans){bool zero=false;do{if(ans%10==0){if(zero){return true;}zero=true;}else{zero=false;}ans/=10;}while(ans);return false;
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){cin>>k;ll ans=k;for(;!check(ans);ans+=k);cout<<ans<<'\n';}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}
B
手玩一下，发现最优构造就是把它尽量拼成一个正方形，多出来的就在右边和下面。因为你增加一个正方形，只会增加 \(1\sim 2\) 条共边。增加 \(3,4\) 条共边的可调整顺序变成每次 $$
令 \(x=\left\lfloor\sqrt n\right\rfloor,r=n-x^2\)，则有答案为：
\[\begin{cases}
2x(x-1)&r=0\\
2x(x-1)+2r-1&0<r\leq x\\
2x(x-1)+2r-2&x<r
\end{cases}
\]
赛时代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
ll n;
ll f(ll n){ll x=sqrt((long double)n);ll ans=2*x*(x-1);ll r=n-x*x;if(r==0){return ans;}else if(r<=x){ans+=r*2-1;}else{ans+=r*2-2;}return ans;
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){cin>>n;cout<<f(n)<<'\n';}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}
C
考虑如果是棵树，显然构造 \(a_x=a_{\operatorname{father}(x)}+1\) 即可。但是这是张图。
考虑类似于 Tarjan 的 DFS 树，再构造 \(a_x=a_{\operatorname{father}(x)}+1\) 即可。DFS 过程中如果 \(a_x\) 有值就返回。
赛时代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=3e5,M=3e5;
int n,a[N+1];
vector<int>g[N+1];
void dfs(int x,int fx){if(a[x]||x==1){return;}a[x]=a[fx]+1;for(int v:g[x]){dfs(v,x);}
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){int m;cin>>n>>m;for(int i=1;i<=n;i++){g[i].resize(0);a[i]=0;}while(m--){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}for(int v:g[1]){dfs(v,1);}for(int i=1;i<=n;i++){cout<<a[i]<<' ';}cout<<'\n';}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}
D
赛时代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=1e6,K=1e6,V=7;
int n,k,cnt[V+1];
int cost(int n){int ans=0;do{ans++;n/=10;}while(n);return ans;
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){cin>>n>>k;if(n<=20&&k>(1<<n)){cout<<"-1\n";continue;}memset(cnt,0,sizeof(cnt));for(int i=1;i<=k;i++){cnt[cost(i)]++;}ll ans=0,last=k,p=0,f=1,C=1;for(int d=7;1<=d;d--){while(cnt[d]>0){if(!f){p++;C=C*(n-p+1)/p;C=min(C,last+1);f=min(C,last);}ll pl=min(1ll*cnt[d],f);ans+=pl*p*d;cnt[d]-=pl;f-=pl;last-=pl;}}cout<<ans<<'\n';}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}
/*
1
3 55
*/
E
赛时一直在写 D。然后还有 9min 的时候 zt17 问我怎么不写 E。
我写完 D 后还剩 7min，询问 zt17 7min 能不能写完 E。
他说他 4min 就写完了 /bx/bx。
然而我因为 switch 没写 break 被创飞了。赛后发现，被人机验证一直卡，最后加 break 就过了。
非常简单的发现不能删除的字符会把字符串分割成一个个部分。之后每次字符就贪心和前面匹配，不能匹配就清空前面的并记录答案。
栈模拟即可。
赛时代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){string s;cin>>s;vector<char>v;int ans=0;for(char ch:s){switch(ch){case 'A':v.push_back('A');break;case 'B':while(v.size()&&v.back()=='D'){v.pop_back();}if(v.size()&&v.back()=='A'){v.pop_back();v.push_back('D');}else{v.resize(0);ans++;}break;case 'C':while(v.size()&&v.back()=='A') {v.pop_back();}if(v.size()&&v.back()=='D'){v.pop_back();}else{v.resize(0);ans++;}break;}}cout<<ans<<'\n';}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}
Codeforces Round 1108(Div.2)
C
没看懂「non-decreasing」和 DeepSeek、CodeForces Better 翻译的「非递减」就是「单调不降」的意思，虚空思考 20min。