Codeforces Round ＃719 (Div. 3)

2021.5.6

B

The question ： Enter a number n, Judge 1-n There are several numbers that can be broken down per digit （ bits , ten ） All equal .

The question ： The decimal system has 1-9, Add the same bit value every time （1->11->111->1111）, It is required to be less than or equal to n Can .

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
int main()
{
    std::ios::sync_with_stdio(false);
    ll t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        ll m=0;
        for(ll i=1;i<=9;i++)
        {
            ll j=i,k=i;
            while(j<=n)
            {
                m++;
                j=j*10+k;
            }
        }
        cout<<m<<endl;
    }
    return 0;
}

D

The question ： Give a length of n Sequence , Judge how many numbers are satisfied （i<j）and.

Answer key ： If you are more careful, you will find that the above formula can be reduced to , Knowing this simplification, you can easily see the answer , Record the value of each element - Index value , And then judge the value of the previous element each time you input - The number of index values equal to this element .

#include <iostream>
#include <algorithm>
#include <map>
#define ll long long
using namespace std;
int main()
{
    std::ios::sync_with_stdio(false);
    ll t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        ll sum=0,x;
        map<ll,ll>m;
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            sum+=m[x-i];
            m[x-i]++;
        }
        cout<<sum<<endl;
    }
    return 0;
}

E

The question ： Give a string , It contains characters * And character ., It is required that all characters * Hyphenated characters * How many steps need to be taken .

Answer key ： Traversal string , Record the characters in each position * How much to move to the left for the center , How much to move to the right , The answer is to minimize the sum of the left and right sides .

#include <iostream>
#include <algorithm>
#include <cstdio>
#define ll long long
using namespace std;
ll l[1000005],r[1000005];
char s[1000005];
int main()
{
    ll t,n;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%s",&n,s);
        for(int i=0;i<n;i++)
        {
            l[i]=0;
            r[i]=0;
        }
        ll k1=0,k2=0,m1=0,m2=0,sum1=0,sum2=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='*')
            {
                l[i]=k1*m1+sum1;
                sum1=l[i];
                k1++;
                m1=0;
            }
            else if(s[i]=='.')
            {
                m1++;
            }
        }
        ll minx=10000000000000000;
        for(int i=n-1;i>=0;i--)
        {
            if(s[i]=='*')
            {
                r[i]=k2*m2+sum2;
                minx=min(minx,l[i]+r[i]);
                sum2=r[i];
                k2++;
                m2=0;
            }
            else if(s[i]=='.')
            {
                m2++;
            }
        }
        if(minx==10000000000000000)
            printf("0\n");
        else
            printf("%lld\n",minx);
    }
    return 0;
}

F1

The question ： Yes n One by one （1,0） The number of components , Every time you can （l-r） Elements and , Judgment No. k individual 0 In that position .

Answer key ： Two points , Find it directly r The location of , front r The sum of the numbers is r-k;

#include <iostream>
#include <algorithm>
using namespace std;
int ask(int l,int r)
{
    int x;
    cout<<"? "<<l<<' '<<r<<endl;
    cin>>x;
    return x;
}
int main()
{
    int t,n,k;
    cin>>n>>t>>k;
    int l=0,r=n,mid;
    while(r-1>l)
    {
        mid=(l+r)/2;
        if(mid-ask(1,mid)>=k)
            r=mid;
        else
            l=mid;
    }
    cout<<"! "<<r<<endl;
    return 0;
}

F2

The question ： stay F1 Under the premise of t A case , Every time you find the first k individual 0 The location of , Put the position of 0 Replace with 1, Continue with the new case and enter a new k.

Answer key ： Use one map Before saving r Number 0 The number of , Then use the same two points to find the first k individual 0 The location of , After the completion of each case, it is necessary to transfer the k Positions and back map Save location 0 The location of -1, This will ensure that each case will 0 Replace with 1.

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
map<int,int>mp;// Before saving r Number 0 The number of 
int ask(int r)
{
    if(mp.find(r)!=mp.end())
        return mp[r];
    int x;
    cout<<"? 1"<<' '<<r<<endl;
    cin>>x;
    return mp[r]=r-x;
}
int main()
{
    int t,n,k;
    cin>>n>>t;
    while(t--){
        cin>>k;
        int l=0,r=n,mid;
        while(r-1>l)
        {
            mid=(l+r)/2;
            if(ask(mid)>=k)
                r=mid;
            else
                l=mid;
        }
        cout<<"! "<<r<<endl;
        map<int,int>::iterator it=mp.lower_bound(r);
        while(it!=mp.end())
        {
            it->second--;
            it++;
        }
    }
    return 0;
}

G

The question ： Find from （1,1） To （n,m） The shortest distance ,a[i][j] by 0 It takes... To take one step w, by -1 You can't go ,>=1 For the portal , It can be transmitted to any other portal , need a[i][j]+ The value of the other portal , The portal can also be empty without using the transport function .

Answer key ： from （1,1） and （n,m） Run twice bfs Find the shortest distance of each point , If you use a portal , Need to compute （1,1） Shortest portal to use +（n,m） Shortest portal to use + The cost of using , The shortest gate is the shortest sum of the three , Finally, compare from （1,1） To （n,m） The shortest distance between using and not using the portal .

#include <queue>
#include <iostream>
#include <algorithm>
#include <map>
#include <stack>
#include <cstring>
#include <vector>
#define ll long long
using namespace std;
int n,m,w;
int dy[4][2]={1,0,0,1,-1,0,0,-1};
void bfs(int sx,int sy,vector<vector<ll> > &d,vector<vector<ll> > &a)
{
    int x,y;
    pair<int,int>pi;
    queue<pair<int,int> >q;
    q.push(make_pair(sx,sy));
    d[sx][sy]=0;
    while(!q.empty())
    {
        pi=q.front();
        q.pop();
        x=pi.first;
        y=pi.second;
        for(int i=0;i<4;i++)
        {
            int fx=x+dy[i][0];
            int fy=y+dy[i][1];
            if(fx>=1&&fy>=1&&fx<=n&&fy<=m&&d[fx][fy]==-1&&a[fx][fy]!=-1)
            {
                d[fx][fy]=d[x][y]+1;
                q.push(make_pair(fx,fy));
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n>>m>>w;
    vector<vector<ll> > a(n+2,vector<ll>(m+2));
    vector<vector<ll> > d1(n+2,vector<ll>(m+2));
    vector<vector<ll> > d2(n+2,vector<ll>(m+2));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            d1[i][j]=-1;
            d2[i][j]=-1;
        }
    }
    bfs(1,1,d1,a);
    bfs(n,m,d2,a);
    ll best=1e18;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]>=1&&d1[i][j]!=-1)
            {
                best=min(best,a[i][j]+w*d1[i][j]);
            }
        }
    }
    ll ans=1e18;
    if(d1[n][m]!=-1)
        ans=w*d1[n][m];
    if(best!=1e18){
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(a[i][j]>=1&&d2[i][j]!=-1)
                    ans=min(ans,a[i][j]+w*d2[i][j]+best);
            }
        }
    }
    if(ans==1e18)
        cout<<-1<<endl;
    else
        cout<<ans<<endl;
    return 0;
}