Codeforces Round ＃719 (Div. 3)

2021.5.6

B

题意：输入一个数n，判断1-n有几个数每位数分解出来（个位，十位）都相等。

题意：十进制有1-9，每次加上一样的位数值（1->11->111->1111），要求小于等于n就可以。

#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

题意：给一个长度为n的序列，判断有多少个数满足（i<j）and。

题解：仔细一点就可以发现上面的式子可以化为，知道这个化简就可以很容易看出答案，记录一下每个元素值-索引值，然后每次输入时判断前面元素值-索引值和这个元素相等的个数。

#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

题意：给一个字符串，其中包含字符*和字符.，要求将所有字符*连在一起字符*需要走几步。

题解：遍历字符串，记录以每个位置的字符*为中心需要左边移动多少，右边移动多少，然后取左右边移动的和最小即为答案。

#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

题意：有n个由（1，0）组成的数，每次可以（l-r）的元素和，判断第k个0在那个位置。

题解：二分，直接找到r的位置，前r个数和为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

题意：在F1的前提下有t个案例，每次找到第k个0的位置，将这个位置的0换为1，继续新的案例输入新的k。

题解：用一个map存下前r个数0的个数，然后一样用二分找第k个0的位置，每个案例完需要将第k个位置以及后面map存的位置0的位置-1，这样就可以保证每个案例完将0换为1。

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
map<int,int>mp;//保存前r个数0的个数
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

题意：找从（1，1）到（n，m）的最短距离，a[i][j]为0是空格走一步要花费w，为-1是不可走，>=1的为传送门，可传送到任何其他一个传送门，需要a[i][j]+另一个传送门的值，传送门也可以当空地不使用传送功能。

题解：从（1，1）和（n，m）跑两遍bfs找每个点的最短距离，要是使用传送门，需要计算（1，1）到使用的传送门最短+（n，m）到使用的传送门最短+使用需要的花费，使用传送门最短就是这三个相加最短，最后比较从（1，1）到（n，m）使用和不使用传送门的最短距离。

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