『解题报告』CF1602 (Codeforces Round #751 (Div. 1 + Div. 2))

2023-12-14 14:19:16

这场Div2挺阴间的,不过收获很大 (剩下Div1的两题实在补不动了)

『比赛链接』

A. Two Subsequences

『原题链接』

难度：$800$（签到题）

题目大意 ：

从字符串 $S$ 中拆成两个子串 $A$ 和 $B$ ，使 $A$ 的字典序小于 $B$ 。

思路：

直接令 $A$ 串中只有 $S$ 中最小的字母，$B$ 中有剩余所有字符即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,t;
char str[N];
int pos;
inline void Read()
{
    pos=1;
    scanf("%s",str+1);
    n=strlen(str+1);
}
inline void Work()
{
    for(int i=2;i<=n;i++)
        if(str[i]<str[pos]) pos=i;
    putchar(str[pos]),putchar(' ');
    for(int i=1;i<=n;i++)
        if(pos!=i) putchar(str[i]);
    putchar('\n');
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        Read();
        Work();
    }
    return 0;
}

B. Divine Array

『原题链接』

难度：$1100$（思维题）

题目大意 ：

你有一个序列 $S$ 每次变换会将一个序列中数 $a_i$ 变为它在 $S$ 中的出现次数。

询问第 $x$ 个位置经过 $k$ 次变换后的值是多少

思路：

可以发现，序列在经过一定次数之后会稳定。(官方题解说不超过 $logn$ 次就会稳定)，我这里用的是 $n$ 次。直接拿数组模拟并且记录下每次变换每个位置的值即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int a[N][N],cnt[N];
int n,T,q;
inline void Read()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i][0]);
}
inline void Work()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            cnt[j]=0;
        for(int j=1;j<=n;j++)
            cnt[a[j][i-1]]++;
        for(int j=1;j<=n;j++)
            a[j][i]=cnt[a[j][i-1]];
    }
    scanf("%d",&q);
    while(q--)
    {
        static int x,k;
        scanf("%d%d",&x,&k);
        printf("%d\n",a[x][min(k,n)]);
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        Read();
        Work();
    }
    return 0;
}

C. Array Elimination

『原题链接』

难度：$1300$（思维题）

题目大意 ：

你有一个序列 $S$ 每次可以选择序列中的 $k$ 个值将它们全部减去他们的按位与，请找到所有可以将序列删干净的 $k$ 。

思路：

我们可以给每个数分解成二进制下的位，并且统计每位是 $1$ 分别的个数。可以证明，如果我们拿 $k$ 个在某位是 $1$ 的数可以将那位的个数减少 $k$ ，所以 $k$ 必须是那位出现的次数的因数。所以我们直接枚举 $k$ 的取值 $k\in[1,n]$，看它是不是所有数的约数即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,S=30;
int t,n;
int a[N],cnt[S];
inline void Read()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
}
inline void Work()
{
    for(int i=0;i<30;i++) cnt[i]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<30;j++)
            if(a[i]>>j&1) cnt[j]++;
    for(int i=1;i<=n;i++)
    {
        bool flag=true;
        for(int j=0;j<30;j++)
            if(cnt[j]%i!=0)
            {
                flag=false;
                break;
            }
        if(flag) printf("%d ",i);
    }
    putchar('\n');
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        Read();
        Work();
    }
    return 0;
}

D. Frog Traveler

『原题链接』

难度：$1900$（阴间题）

题目大意 ：

你是一直青蛙，最一开始在井底深 $d$ 处，每次可以跳 $h\in[0,a_i]$ 米，假设到达了 $j$ 位置，将会下滑 $b_j$ 米，请问最少要跳多少次才能到达井外（$0$ 处）。

思路：

可以考虑线段树优化建图的方法 (见代码) ，给每个点建立一个虚点 $i+n$，并将每个点到它的虚点建立一条权值为 $0$ 的边，并对于每个虚点 $i+n$ 连到 $i-b_i$ 一条权值为 $0$ 的边。对于 $i$ 连一条 $i$ 到 $[i+1,i+a_i]$ 的权值为 $1$ 的边。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+10,M=N<<5;
int n,m;
int a[N],b[N];
int h[M],e[M],ne[M],w[M],idx;
int dis[M],pre[M];
bool vis[M];
inline void Add(int a,int b,int c)
{
    e[++idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    w[idx]=c;
}
namespace SegmentTree
{
    struct node
    {
        int id;
        #define id(x) unit[(x)].id
    }unit[M];
    int cnt;
    #define lson(x) ((x)<<1)
    #define rson(x) ((x)<<1|1)
    #define mid (l+r>>1)
    void Build(int k,int l,int r)
    {
        if(l==r) return (void)(id(k)=l+n+1);
        id(k)=++cnt;
        Build(lson(k),l,mid),Build(rson(k),mid+1,r);
        Add(id(k),id(lson(k)),0),Add(id(k),id(rson(k)),0);
    }
    void Update(int k,int l,int r,int L,int R,int st)
    {
        if(L<=l&&R>=r) return Add(st,id(k),1);
        if(L<=mid) Update(lson(k),l,mid,L,R,st);
        if(R>mid) Update(rson(k),mid+1,r,L,R,st);
    }
}
using namespace SegmentTree;
deque<int> q;
inline void Bfs()
{
    memset(dis,0X3f,sizeof(dis));
    dis[n]=0,q.push_back(n);
    while(q.size())
    {
        auto t=q.front();q.pop_front();
        if(vis[t]) continue;
        vis[t]=true;
        for(int i=h[t];i;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>dis[t]+w[i])
            {
                dis[j]=dis[t]+w[i];
                if(w[i]) q.push_back(j);
                else q.push_front(j);
                pre[j]=t;
            }
        }
    }
}
inline void Read()
{
    scanf("%d",&n);
    cnt=2*n+1;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
}
vector<int> path;
inline void Work()
{
    for(int i=0;i<=n;i++) Add(i+n+1,i+b[i],0);
    Build(1,0,n);
    for(int i=1;i<=n;i++)
        Update(1,0,n,i-a[i],i,i);
    Bfs();
    printf("%d\n",dis[0]==0X3f3f3f3f ? -1 : dis[0]);
    if(dis[0]!=0X3f3f3f3f)
    {
        int now=0;
        while(now!=n)
        {
            if(n+1<=now&&now<=2*n+1) path.push_back(now-n-1);
            now=pre[now];
        }
        reverse(path.begin(),path.end());
        for(auto x : path)
            printf("%d ",x);
        putchar('\n');
    }
}
int main()
{
    Read();
    Work();
    return 0;
}

E. Optimal Insertion

『原题链接』

难度：$2300$（阳间题）

题目大意 ：

你有一个序列 $A$ 和一个序列 $B$ ，你要将序列 $B$ 中的每个元素插入 $A$ 的任意位置，使新序列的逆序对数最少。

思路：

可以很容易看出一个结论，将 $B$ 序列排序后按照相对位置插入 $A$ 序列的答案最小，($B$ 中每个元素只会对 $A$ 中原来的元素产生贡献，并不会对自己的元素产生贡献)。那么可以考虑分治插入，每次插入分治区间中的 $b_{mid}$ ，找到贡献最小的位置插入后分治为两个区间即可。注：一个位置可以插入多个数！！！。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n,m,T;
int a[N],b[N],pos[N];
int suml[N],sumr[N];
vector<int> newa,nums;
void Solve(int lb,int rb,int la,int ra)
{
    if(lb>rb) return;
    int mid=lb+rb>>1;
    suml[la-1]=0;
    for(int i=la;i<=ra;i++)
    {
        suml[i]=sumr[i]=0;
        if(a[i]>b[mid]) suml[i]++;
        if(a[i]<b[mid]) sumr[i]++;
    }
    for(int i=la+1;i<=ra;i++) suml[i]+=suml[i-1];
    for(int i=ra-1;i>=la;i--) sumr[i]+=sumr[i+1];
    pos[mid]=la;
    for(int i=la+1;i<=ra;i++)
        if(suml[i-1]+sumr[i]<suml[pos[mid]-1]+sumr[pos[mid]])
            pos[mid]=i;
    Solve(lb,mid-1,la,pos[mid]),Solve(mid+1,rb,pos[mid],ra);
}
namespace BIT
{
    int unit[N<<1],siz;
    #define lowbit(x) ((x)&-(x))
    inline void Clear(int x)
    {
        siz=x;
        for(int i=1;i<=siz;i++) unit[i]=0;
    }
    inline void Add(int x,int val)
    {
        for(x;x<=siz;x+=lowbit(x)) unit[x]+=val;
    }
    inline int Query(int x)
    {
        int res=0;
        for(x;x;x-=lowbit(x)) res+=unit[x];
        return res;
    }
}
using namespace BIT;
inline void Read()
{
    scanf("%d%d",&n,&m);
    nums.clear(),newa.clear();
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        nums.push_back(a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&b[i]);
        nums.push_back(b[i]);
    }
}
inline void Work()
{
    sort(b+1,b+m+1);
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=1;i<=n;i++) a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1;
    for(int i=1;i<=m;i++) b[i]=lower_bound(nums.begin(),nums.end(),b[i])-nums.begin()+1;
    Solve(1,m,1,n+1);
    int now=m;
    for(int i=n+1;i>=0;i--)
    {
        if(i!=n+1&&i!=0) newa.push_back(a[i]);
        while(now&&pos[now]==i) newa.push_back(b[now--]);
    }
    ll ans=0;
    Clear(nums.size());
    for(auto x : newa)
    {
        ans+=Query(x-1);
        Add(x,1);
    }
    printf("%lld\n",ans);

}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        Read();
        Work();
    }
    return 0;
}

F. Difficult Mountain

『原题链接』

难度：$2700$（阴间贪心题）

题目大意 ：

对于一座山有一个初始的 $d$ ，有 $n$ 个准备登山的人，对于每个人有两个属性 $\{s_i,a_i\}$ ，对于每个 $s_i \geq d$ 的人可以登山，并会将 $d$ 变为 $max(d,a_i)$。

请问最多有多少人可以登山。

思路：

先排除初始的 $s_i$ 就小于 $d$ 的人。贪心思路：按照 $max(a_i,s_i)$ 排序后按顺序模拟统计即可。

证明：分类讨论如果现在考虑第 $i$ 个人，如果 $s_i\geq a_i$ 那么 $s_i\geq d$ ，这个人可以被选且一定要选。如果后面有一个人 $max(a_j,s_j)=a_j$ 并且 $s_j<a_i$ 因他不能被选，若一定要选这个人，则要至少将 $i$ 删去并且由于一定有 $ a_j > a_i$ 答案只会变劣。

如果 $a_i > s_i$ 并且在选 $i$ 的情况下，可以同理可证，若不选 $i$ 可以不用考虑。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,d,idx;
struct PII
{
    int s,a;
    inline bool operator<(const PII &t) const
    {
        if(max(a,s)!=max(t.a,t.s)) return max(a,s)<max(t.a,t.s);
        return s<t.s;
    }
}que[N];
inline void Read()
{
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++)
    {
        static int s,a;
        scanf("%d%d",&s,&a);
        if(s<d) continue;
        que[++idx]={s,a};
    }
}
inline void Work()
{
    sort(que+1,que+idx+1);
    int ans=0;
    for(int i=1;i<=idx;i++)
        if(que[i].s>=d)
            d=max(d,que[i].a),ans++;
    printf("%d\n",ans);
}
int main()
{
    Read();
    Work();
    return 0;
}

码农公寓

『比赛链接』

A. Two Subsequences

B. Divine Array

C. Array Elimination

D. Frog Traveler

E. Optimal Insertion

F. Difficult Mountain

相关文章