【LGR-290-Div.4】 ARC224 CF2246

发布时间：2026/7/13 12:24:49

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;
}