AtCoder Beginner Contest 254 题解
只有 ABCDEFH 的题解。
A
模拟。
Code
void mian(){
int n;scanf("%d",&n);
printf("%02d\n",n%100);
}
B
模拟。
Code
const int N=30;
int n;
ll a[N+10][N+10];
void mian(){
scanf("%d",&n);
a[0][0]=1;
for(int i=1;iC
把整个序列分成若干组：
- \([a_1,a_{1+k},a_{1+2k},\cdots]\)
- \([a_2,a_{2+k},a_{2+2k},\cdots]\)
- \(\cdots\)
那么，每组内部的数可以随便换，组与组之间互不影响。把每组数排序后，再来看整个序列是否有序即可。
Code
const int N=2e5;
int n,k,a[N+10],b[N+10];
bool vis[N+10];
void mian(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
for(int i=1;i<=n-k;i++){
if(vis[i])continue;
int cnt=0;
for(int j=i;j<=n;j+=k)
b[++cnt]=a[j],vis[j]=1;
std::sort(b+1,b+cnt+1);
for(int j=i,kk=1;j<=n&&kk<=cnt;j+=k,kk++)
a[j]=b[kk];
}
if(std::is_sorted(a+1,a+n+1))puts("Yes");
else puts("No");
}
D
做法貌似很多，这里说一下我的。
先枚举 \(i\)，然后看有多少个 \(j\) 满足要求。
把 \(i\) 中所有 \(p^2\) 的因子刨掉，设得到的数是 \(i'\)，那么有 \(\sqrt{\frac n{i'}}\) 个 \(j\)。
枚举 \(p\) 时枚举到 \(\sqrt n\) 就行了，因为再大的数没有意义。
Code
const int N=2e5;
const int M=450;
int n;
int prm[M+10],notPrm[M+10],totp;
void init(){
notPrm[1]=1;
for(int i=2;i<=M;i++){
if(!notPrm[i])prm[++totp]=i;
for(int j=1;j<=totp&&i*prm[j]<=M;j++){
notPrm[i*prm[j]]=1;
if(!i%prm[j])break;
}
}
}
int get(int x){
for(int i=1;i<=totp;i++){
int y=prm[i];
while(x%(y*y)==0)x/=(y*y);
}
return x;
}
void mian(){
scanf("%d",&n);
ll ans=0;
for(int i=1;i<=n;i++){
int x=get(i);
ans+=int(std::sqrt(n/x));
}
printf("%lld\n",ans);
}
E
直接用 std::queue 之类的暴力就行了。
比赛时我想了一个又奇怪又麻烦的做法，这里就不放出来了。
F
\(\gcd\) 有一个最基本的性质：\(\gcd(a,b)=\gcd(a,a-b)\)。
于是要求的就变成了（以 \(h_1=1,h_2=n,w_1=1,w_2=n\) 为例）：
\[\gcd(a_1+b_1,a_2-a_1,\cdots,a_n-a_{n-1},b_2-b_1,\cdots,b_n-b_{n-1}) \]用 ST 表维护 \(a,b\) 差分的 \(\gcd\) 即可。
Code
const int N=2e5;
const int LOGN=20;
int n,q,a[N+10],b[N+10],c[N+10],d[N+10];
struct ST{
int lg[N+10],gcd[N+10][LOGN+5];
void init(int n,int *a){
lg[0]=-1;
for(int i=1;i<=n;i++)
gcd[i][0]=a[i],lg[i]=lg[i>>1]+1;
for(int j=1;j<=LOGN;j++)
for(int i=1;i<=n-(1<H
首先有一个巧妙的转化：给 \(a\) 中某个数 \(\times 2\) 相当于给 \(b\) 中某个偶数 \(\div 2\)。
于是可以做一个贪心：把 \(a,b\) 的数插进大根堆里，每次从两个堆里分别取出堆顶 \(x,y\)。如果 \(x=y\)，则他俩就直接匹配上了；如果 \(x>y\)，则只能将 \(x\gets\left\lfloor\frac x2\right\rfloor\)（前提是 \(x\ne 0\)）；如果 \(x
Code
int n;
std::priority_queue a,b;
void mian(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
a.push(x);
}
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
b.push(x);
}
int ans=0;
while(!(a.empty()&&b.empty())){
int x=a.top();
int y=b.top();
if(x==y){a.pop();b.pop();continue;}
if(x>y){
if(x==0)return puts("-1"),void();
a.pop();
a.push(x/2);
ans++;
}else{
if(y==0||(y&1))return puts("-1"),void();
b.pop();
b.push(y/2);
ans++;
}
}
printf("%d\n",ans);
}