2020 年 8 月水题选做

发表于 2020-08-01 更新于 2022-05-18 分类于题解阅读次数： Valine：本文字数： 3.3k 阅读时长 ≈ 3 分钟

这么快就 8 月了呢…

8/1

$\color{green}{\text{CF875F}}$

又一道想出结论之后就非常简单的题。

考虑把王子当成点，公主当成边，然后就求个最大生成基环树就好了。

求法魔改一下 Kruskal 就完事了。

8/2

打了人生第一场 atcoder 。

ABC 174

T1

sb 题。

int x;
scanf("%d",&x);
if(x>=30)puts("Yes");
else puts("No");

T2

sb 题。

scanf("%d%d",&n,&d);
rep(i,1,n) {
    int x,y;
    scanf("%d%d",&x,&y);
    double k=sqrt(1.0*x*x+1.0*y*y);
    if(k<=d)++ans;
}
printf("%d\n",ans);

T3

考虑模数周期性，然后这就是道 sb 题了。

scanf("%d",&k);
if(k%2==0) puts("-1");
else {
    mo=7%k;
    used[mo]=1;bool flg=0;
    while(mo!=0) {
        ++ans;
        mo*=10;mo+=7;
        mo%=k;
        if(used[mo]) {flg=1;printf("-1\n");break;}
        used[mo]=1;
    }
    if(!flg)printf("%d\n",ans+1);
}

T4

考虑贪心。把所有的 R 移到它该移的位置（前面）即可。根本用不上改变颜色的操作。

scanf("%d%s",&n,s+1);
rep(i,1,n) {
    if(s[i]=='R') ++r;
}
k=r;
rep(i,1,r) {
    if(s[i]=='R') --k;
}
printf("%d\n",k);

T5

二分。二分完了 check 随便写写。

bool check(int x) {
    int now=0;
    rep(i,1,n) {
        int kk=a[i]/x;
        if(a[i]%x==0) kk--;
        now+=kk;
        if(now>k) return false;
    }
    return true;
}
signed main(){
    scanf("%lld%lld",&n,&k);
    rep(i,1,n) scanf("%lld",&a[i]),mx=max(mx,a[i]);
    int l=1,r=mx;
    while(l<r) {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%lld\n",r);
    return 0;
}

T6

HH 的项链。。。

scanf("%d%d",&n,&m);
rep(i,1,n) scanf("%d",&a[i]);
rep(i,1,m) asks[i].id=i,scanf("%d%d",&asks[i].l,&asks[i].r);
sort(asks+1,asks+m+1,cmp);
int now=1;
rep(i,1,m) {
    rep(j,now,asks[i].r) {
        if(used[a[j]]) modify(used[a[j]],-1);
        modify(j,1);
        used[a[j]]=j;
    }
    ans[asks[i].id]=query(asks[i].r)-query(asks[i].l-1);
    now=asks[i].r+1;
}
rep(i,1,m) printf("%d\n",ans[i]);