Codeforces gym 100738 做题记录

minstdfx · 2023-09-20 14:46:58 · 个人记录

没能参加的校队选拔赛...

做完打算补题，好啊，全网都没搜到题解，那我来吧。

Gym 100738B Board with lights and switches

简要题意：一次操作把 x 变成 a\times(x-a)，问几次操作让 x 不小于 10^9。

手玩发现 1,2,3,4 不行，对于一个 x(x>4) 最优解显然是 \lfloor\dfrac x 2 \rfloor\times\lceil\dfrac x 2 \rceil。次数不会很多，暴力判断就行。

注意至少需要执行一次操作。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll k;
    cin>>k;
    if(k==1 || k==2 || k==3) // impossible
        cout<<"-1\n";
    else if(k==4) // infinity
        cout<<"-1\n";
    else
    {
        int count=0;
        do {
            ++count;
            k=k&1?(k/2)*(k/2+1):(k/2)*(k/2);
        } while(k<1e9);
        cout<<count<<"\n";
    }
    cout.flush();
    return 0;
}

Gym 100738D Degree Sequence Tree

题面完全不说人话。

简要题意：从度数还原一棵树。

每次取一个度数为 1 的点和一个度数不为 1 的点连边就行，记得最后一条边别忘了连了。

如果度数不合法直接输出 -1。

复杂度 \Theta(n)，可以通过本题。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200000+9;
queue<int> q1,q2;
int n;
int deg[maxn];
int fa[maxn];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    int total=0;
    for(int i=1;i<=n;++i)
        cin>>deg[i],total+=deg[i];
    if(total!=2*(n-1))
    {
        cout<<-1<<endl;
        return 0;
    }
    for(int i=1;i<=n;++i)
        if(deg[i]==1) q1.push(i);
        else q2.push(i);
    while(q1.size()+q2.size()>2)
    {
        int u=q1.front();q1.pop();
        int v=q2.front();q2.pop();
        fa[u]=v;
        if(--deg[v]>1) q2.push(v);
        else q1.push(v);
    }
    if(q1.size()!=2 || q2.size()!=0)
    {
        cout<<-1<<endl;
        return 0;
    }

    int u=q1.front();q1.pop();
    int v=q1.front();q1.pop();
    fa[u]=v;
    for(int i=1;i<=n;++i)
        if(fa[i]) cout<<fa[i]<<" "<<i<<"\n";
    cout.flush();
    return 0;
}

Gym 100738K New GPU

题面又不说人话。

人话：找到最小的正整数 n 使得 P(n)=An^{\frac 1 3}+B\sqrt n \ge P。

傻逼二分题，就是卡我精度卡了四发。有点难绷。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll a,b,p;
    cin>>a>>b>>p;
    ll l=1,r=1e18,mid,res;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(a*pow(mid,1.0/3)+b*sqrt(mid)>=p) r=mid-1,res=mid;
        else l=mid+1;
    }
    cout<<res<<endl;
    cout.flush(); return 0;
}

Gym 100738A Fitting boxes

这个还算人话。

人话：判断两个长方形能不能把其中一个塞到另一个里面去。

显然如果一个的长和宽都小于另一个的长和宽肯定可以。

否则我们假设两个长方形分别为 a\times b,c\times d(a\le b,c\le d,b<d,a>c)。

如果 d>\sqrt{a^2+b^2}那必然塞不下。

否则，假设 d 贴着边，与 a夹角为 \theta，那么，另一条边能取的最大长度为 \min\{\dfrac{b-d\sin\theta}{\cos\theta},\dfrac{a-d\cos\theta}{\sin\theta}\}。

求导发现这玩意是个单峰函数，直接三分求最值和 c 比较即可。注意三分边界。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double a,b,c,d;
const double eps=1e-6;
const double pi=std::acos(-1);
double f(double angle)
{
    return std::min((b-d*std::sin(angle))/std::cos(angle),
    (a-d*std::cos(angle))/std::sin(angle));
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>a>>b>>c>>d;
    if(a>b) swap(a,b);
    if(c>d) swap(c,d);
    if(b>d) swap(a,c),swap(b,d);
    if(a<=c)
    {
        puts("Yes");
        return 0;
    }
    if(b*b+a*a<d*d)
    {
        puts("No");
        return 0;
    }
    double l=std::acos(a/d); // dcosx=a
    double r=std::asin(b/d);
    double delta,mid1,mid2;
    assert(l<=r);
    while(r-l>eps)
    {
        delta=r-l;
        mid1=l+delta/3;
        mid2=r-delta/3;
        if(f(mid1)<f(mid2)) l=mid1;
        else r=mid2;
    }
    if(f(l)>=c) puts("Yes");
    else puts("No");
    cout.flush(); return 0;
}

Gym 100738C Rating Shuffle

人话：给定一个数组，每次操作给每个数 +d 或者 -d，问能把数组变成严格降序的最小操作次数。

一眼二分（怎么又一个二分，算上可以求导二分的三分题已经三个了），关键在于怎么 check。

先假定每个数在每次操作都是被加上了 d，考虑一个一个处理，对于已经处理好的 a_1,a_2,\cdots,a_{i-1}，考虑把 a_i 加进去，如果 a_i<a_{i-1} 说明不用动，否则，每把一个加换成减就减少了 2d，如果 k \le \dfrac{a_i-a_{i-1}}{2d} 说明不行，否则减去最少的可行的次数（\lfloor\dfrac{a_i-a_{i-1}}{2d}\rfloor+1 次，因为是严格降序）。

复杂度 \Theta(n\log_2 n)，可以通过本题。

#include <bits/stdc++.h>
#include <memory.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+4;
int n;
ll d;
ll a[maxn],b[maxn];
int check(ll k)
{
    memcpy(b,a,sizeof(ll)*(n+1));
    for(int i=1;i<=n;++i) b[i]+=d*k;
    for(int i=2;i<=n;++i)
    {
        ll delt=b[i]-b[i-1];
        if(delt<0) continue;
        if(k<=delt/(2*d)) return false;
        b[i]-=((delt)/(2*d)+1)*d*2;
    }
    return 114514;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>d;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    ll l=0,r=1e14,mid,res=114514;
    while(l<=r)
    {
        mid=(l+r)>>1ll;
        if(check(mid)) res=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<res<<"\n";
    cout.flush(); return 0;
}

Gym 100738L Plantations

究极垃圾题，题目让你找到最大的对角线上和不大于 W 的子方阵，但是没告诉你输出什么。

不对，他说了一句 Outout the answer for each of the T test cases，还不加句号。outout 是什么玩意？？

这个题面 LaTex 也不加，数据范围 W is a 32-bit number (can be stored in int type) 又是什么勾吧。

做法也是依托，暴力就艹过去了，我已经无语了。

真的是让我，大开眼界，叹为观止。

#include <bits/stdc++.h>
#include <memory.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+4;
ll a[maxn][maxn],W;
int n,t;/*
ll a1[maxn][maxn],a2[maxn][maxn];
ll get(int x,int y,ll a[maxn][maxn])
{
    return (1<=x && x<=n && 1<=y && y<=n)?a[x][y]:0;
}
bool check(ll k)
{
    if(!k) return true;
    for(int i=1;i+k-1<=n;++i)
        for(int j=1;j+k-1<=n;++j)
        {
            ll s1=get(i+k-1,j+k-1,a1)-get(i-1,j-1,a1);
            ll s2=get(i+k-1,j,a2)-get(i-1,j+k,a2);
            ll s3=(k&1)?-(a[i+k/2][j+k/2]):0;
            if(s1+s2+s3<=W) return true;
        }
    return false;
}*/
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>W;
        int limit;
        ll res=0,cur;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                cin>>a[i][j];
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
            {
                limit=min({i-1,j-1,n-i,n-j});
                if(a[i][j]>W) continue;
                cur=a[i][j];
                if(!res) res=1;
                for(ll k=1;k<=limit;++k)
                {
                    cur+=a[i-k][j-k];
                    cur+=a[i+k][j-k];
                    cur+=a[i-k][j+k];
                    cur+=a[i+k][j+k];
                    if(cur>W) break;
                    res=max(res,k*2+1);
                }
            }
        for(int i=1;i<n;++i)
            for(int j=1;j<n;++j)
            {
                limit=min({i-1,j-1,n-i-1,n-j-1});
                if(a[i][j]+a[i][j+1]+a[i+1][j+1]+a[i+1][j]>W) continue;
                cur=a[i][j]+a[i][j+1]+a[i+1][j+1]+a[i+1][j];
                if(res<2) res=2;
                for(ll k=1;k<=limit;++k)
                {
                    cur+=a[i-k][j-k];
                    cur+=a[i+k+1][j-k];
                    cur+=a[i-k][j+k+1];
                    cur+=a[i+k+1][j+k+1];
                    if(cur>W) break;
                    res=max(res,(k+1)*2);
                }
            }
        cout<<res<<"\n";
    }
    cout.flush(); return 0;
}

Gym 100738E Pretty Buses

简要题意：简要不起来了，看原题吧。

首先，如果每条边都只用一辆车运输，显然最优的方案是最小生成树。这个应该是一眼的吧。

然后，考虑它的奇怪限制，在往根爬的过程中，使用重链剖分，每辆车的行进路线都是一条重链，就能保证每个点到根的路径上只需要经过 \Theta(\log n) 条重链。

然后结束了。

复杂度 \Theta(m\log_2 m+n\log_2 n)，可以通过本题。

#include <bits/stdc++.h>
#include <memory.h>
using namespace std;
typedef long long ll;
const int maxn=400000+4;
int dsu[maxn];
int n,m,total;
int u[maxn],v[maxn],w[maxn],id[maxn];
bool cmp(int a,int b)
{
    return w[a]<w[b];
}
vector<int> e[maxn];
int findfa(int u){return u==dsu[u]?u:dsu[u]=findfa(dsu[u]);}
int son[maxn];
int sz[maxn];
void dfs1(int u,int fa)
{
    sz[u]=1;
    for(int v:e[u])
        if(v!=fa)
        {
            dfs1(v,u);
            sz[u]+=sz[v];
            if(son[u]==0 || sz[son[u]]<sz[v]) son[u]=v;
        }
}
vector<int> drivers[maxn];
int bus[maxn];
void dfs2(int u,int fa)
{
    drivers[u].push_back(u);
    bus[u]=u;
    if(!son[u]) return;
    dfs2(son[u],u);
    printf("Drive %d %d %d\n",bus[son[u]],son[u],u);
    bus[u]=bus[son[u]];
    printf("Move %d %d %d\n",u,u,bus[u]);
    drivers[bus[u]].push_back(u);
    for(int v:e[u])
    {
        if(v==son[u] || v==fa) continue;
        dfs2(v,u);
        printf("Drive %d %d %d\n",bus[v],v,u);
        for(int kkksb:drivers[bus[v]])
            drivers[bus[u]].push_back(kkksb),
            printf("Move %d %d %d\n",kkksb,bus[v],bus[u]);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i) cin>>u[i]>>v[i]>>w[i];
    for(int i=1;i<=n;++i) dsu[i]=i;
    for(int i=1;i<=m;++i) id[i]=i;
    sort(id+1,id+m+1,cmp); total=0;
    for(int i=1,U,V;i<=m;++i)
    {
        U=findfa(u[id[i]]);V=findfa(v[id[i]]);
        if(U==V) continue;
        total+=w[id[i]];
        e[u[id[i]]].push_back(v[id[i]]);
        e[v[id[i]]].push_back(u[id[i]]);
        dsu[V]=U;
    }
    printf("%d\n",total);
    dfs1(1,0);
    dfs2(1,0);
    puts("Done");
    cout.flush(); return 0;
}

Gym 100738F Sequence of words

简要题意：给定字符串 s，每次查询 s 所有长度为 l 的子串中，字典序排行第 k 的开头位置。如有相同，任意输出一个。

给同长度的子串排序，考虑到每个这样的子串都是一个后缀的前缀，而且假设有两个子串相同，那么它们对应的后缀必然排序时连续，立刻想到后缀数组。（然而板子是抄的）

但是查询长度为 l 的子串时，只有 n-l+1 个这样的开头位置需要被查询。考虑把所有询问离线下来按照 l 从大到小排序，我们都学过后缀数组，知道 sa[i] 代表按字典序排列后的第 i 个后缀的开始位置，而 rk[i] 代表一个从 i 开始的后缀的字典序序数。每次访问到长度为 l' 的所有询问时，我们需插入以 n-i+1 开头的后缀，并需要按照字典序查询当前第 k 个前缀的开始位置。利用 sa,rk 数组和线段树上二分即可做到。

复杂度 \Theta(n\log_2 n)，可以通过本题。

#include <bits/stdc++.h>
#include <memory.h>
using namespace std;
typedef long long ll;
const int maxn=100000+4;
char s[maxn];
int n,m,sa[maxn],rk[maxn],tmp[maxn],c[maxn];
void calc_sa()
{
    int m;
    auto sortc=[&](int m)->void {
        memset(c,0,sizeof(int)*(m+1));
        for(int i=1;i<=n;++i) ++c[rk[i]];
        for(int i=1;i<=m;++i) c[i]+=c[i-1];
        for(int i=n;i;--i) sa[c[rk[tmp[i]]]--]=tmp[i];
    };
    for(int i=1;i<=n;++i)
        rk[i]=s[i],tmp[i]=i;
    sortc(m=256);
    for(int k=1;k<n;k<<=1)
    {
        int tail=0;
        for(int i=n-k+1;i<=n;++i) tmp[++tail]=i;
        for(int i=1;i<=n;++i) if(sa[i]>k) tmp[++tail]=sa[i]-k;
        sortc(m);
        swap(rk,tmp);
        rk[sa[1]]=m=1;
        for(int i=2;i<=n;++i)
            rk[sa[i]]=tmp[sa[i]]==tmp[sa[i-1]]&&tmp[sa[i]+k]==tmp[sa[i-1]+k]?m:++m;
        if(m==n) break;
    }
}
int q,ans[maxn];
struct querys
{
    int len,k,id;
    friend bool operator<(const querys &a,const querys &b)
    {
        return a.len>b.len;
    }
}op[maxn];
int st[maxn<<2];
void pushup(int rt)
{
    st[rt]=st[rt<<1]+st[rt<<1|1];
}
void update(int pos,int l,int r,int rt)
{
    if(l==r) return void(st[rt]=1);
    int mid=(l+r)>>1;
    if(pos<=mid) update(pos,l,mid,rt<<1);
    else update(pos,mid+1,r,rt<<1|1);
    pushup(rt);
}
int query(int k,int l,int r,int rt)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(k<=st[rt<<1]) return query(k,l,mid,rt<<1);
    return query(k-st[rt<<1],mid+1,r,rt<<1|1);
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    calc_sa();
    scanf("%d",&q);
    for(int i=1;i<=q;++i)
    {
        scanf("%d %d",&op[i].len,&op[i].k);
        op[i].id=i;
    }
    sort(op+1,op+q+1);
    for(int i=n,j=1;i;--i)
        for(update(rk[n-i+1],1,n,1);j<=q && op[j].len==i;++j)
            ans[op[j].id]=sa[query(op[j].k,1,n,1)];
    for(int i=1;i<=q;++i)
        printf("%d\n",ans[i]);
}

Gym 100738I Lazy mobile users

简要题意：给定一棵树，开始时在根，每次可以走到一个相邻的点，如果走过了 k+1 次相同的一个点就退出，求退出之前可以经过的点的最大个数。

一眼树形 dp，dp_{u,0} 表示访问完了以 u 为根的子树并退回 u，能访问到的最大点数。显然有