"Problem solving report" cf1602 (codeworks round #751 (Div. 1 + Div. 2))

This Div2 was a hell of a game, but the harvest was great (the remaining two questions of Div1 really couldn't be filled)

"Game link"

A. Two Subsequences

"Original title link"

Difficulty: \ (800 \) (sign in question)

Main idea of the title:

Split the string \ (S \) into two substrings \ (A \) and \ (B \), so that the dictionary order of \ (A \) is less than \ (B \).

Idea:

Directly make only the smallest letter in \ (S \) in the \ (A \) string and all remaining characters in \ (B \).

code:

#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

"Original title link"

Difficulty: \ (1100 \) (thinking problem)

Main idea of the title:

You have a sequence \ (S \). Each transformation will change the number of times in a sequence \ (a_i \) to its occurrence in \ (S \).

Ask the value of position \ (x \) after \ (k \) transformation

Idea:

It can be found that the sequence will be stable after a certain number of times. (the official explanation will be stable if it does not exceed \ (logn \) times). I use \ (n \) times here. Directly take the array simulation and record the value of each position of each transformation.

code:

#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

"Original title link"

Difficulty: \ (1300 \) (thinking problem)

Main idea of the title:

You have a sequence \ (S \) you can select \ (k \) values in the sequence at a time and subtract their bitwise AND. Please find all \ (k \) that can delete the sequence.

Idea:

We can decompose each number into bits under binary, and count the number of each \ (1 \) respectively. It can be proved that if we take the number of \ (k \) that is \ (1 \) in a bit, we can reduce the number of that person \ (k \), so \ (k \) must be a factor of the number of occurrences of that person. Therefore, we can directly enumerate the value \ (k\in[1,n] \) of \ (k \) to see if it is the divisor of all numbers.

code:

#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

"Original title link"

Difficulty: \ (1900 \) (underworld question)

Main idea of the title:

You are a frog. You can jump \ (h\in[0,a_i] \) meters at the bottom of the well at the beginning. If you reach the position of \ (J \), you will fall \ (b_j \) meters. How many times do you have to jump at least to reach the position outside the well (\ (0 \).

Idea:

You can consider the method of optimizing the drawing of the line segment tree (see the code), establish a virtual point \ (i+n \) for each point, establish an edge with a weight of \ (0 \) from each point to its virtual point, and connect each virtual point \ (i+n \) to an edge with a weight of \ (i-b_i \). For \ (I \) an edge with a weight of \ (1 \) from \ (I \) to \ ([i + 1, I + a_, I] \).

code:

#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

"Original title link"

Difficulty: \ (2300 \) (Yangjian question)

Main idea of the title:

You have A sequence \ (A \) and A sequence \ (B \). You should insert each element in the sequence \ (B \) anywhere in \ (A \) to minimize the reverse logarithm of the new sequence.

Idea:

It is easy to see A conclusion that after sorting the \ (B \) sequence, the answer to insert the \ (A \) sequence according to the relative position is the smallest, ((each element in \ (B \) will only contribute to the original elements of \ (A \) and will not contribute to its own elements). Then divide and conquer insertion can be considered. Insert \ (b_{mid} \) in the divide and conquer interval each time, find the position with the least contribution, and divide and conquer into two intervals after insertion. Note: multiple numbers can be inserted in one position!!!.

code:

#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

"Original title link"

Difficulty: \ (2700 \) (hell greedy question)

Main idea of the title:

For a mountain, there is an initial \ (d \), there are \ (n \) people ready to climb the mountain, and there are two attributes \ (\ {s_i,a_i \} \) for each person. For each person \ (s_i \geq d \), they can climb the mountain and change \ (d \) to \ (max(d,a_i) \).

How many people can climb the mountain at most.

Idea:

Exclude the person whose initial \ (s_i \) is less than \ (d \). Greedy idea: sort according to \ (max(a_i,s_i) \) and then simulate statistics in order.

Proof: for classified discussion, if you now consider the \ (I \) person, if \ (s_i\geq a_i \), then \ (s_i\geq d \), this person can be selected and must be selected. If there is a person behind \ (max(a_j,s_j)=a_j \) and \ (s_j < a_i \) cannot be selected because of him, if this person must be selected, at least delete \ (I \) and because there must be $a_ j > a_ I $the answer will only get worse.

If \ (a_i > s_i \) and \ (I \) is selected, the same can be proved. If \ (I \) is not selected, it can be ignored.

code:

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

Keywords: Algorithm CodeForces div2

Added by subcool on Tue, 09 Nov 2021 08:39:50 +0200