Contest 2050 and Codeforces Round ＃718 (Div. 1 + Div. 2)

2021.4.23

A

The question ： Give a number n, Judge n Can be 2050*10^k Add the numbers taken from to get .

Answer key ： Every number added is 2050 Multiple , So direct judgment n Can be 2050 Get by dividing , If you can, add the number of digits of the quotient and .

#include <cstdio>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
int main()
{
    ll t,n;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        if(n%2050)
            printf("-1\n");
        else
        {
            ll ans=n/2050;
            ll sum=0;
            while(ans)
            {
                sum+=ans%10;
                ans/=10;;
            }
            printf("%lld\n",sum);
        }
    }
    return 0;
}

B

The question ： to n+1 A little bit ,0 To n, Each adjacent point has m side , So there is n Group m side , value =0 To n The length of the smallest side of , Each edge can only be used once , For this m The minimum sum of the group scheme values , Find a specific solution .

Answer key ： Just take out the front of all sides m Small , And then put this front m The small edges are placed on different schemes , The sum of the value thus obtained is the smallest .

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdlib.h>
#include <cstring>
#define ll long long
using namespace std;
struct node
{
    int x,y,v;
}s[100005];
bool cmp(const node &t1,const node &t2)
{
    return t1.v<t2.v;
}
int main()
{
    ll t,n,m,a[105][105],b[105][105];
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&m);
        int l=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%lld",&a[i][j]);
                s[l].x=i;
                s[l].y=j;
                s[l++].v=a[i][j];
            }
        }
        sort(s,s+l,cmp);
        int p=0;
        memset(b,0,sizeof(b));
        for(int i=1;i<=m;i++)
        {
            b[s[p].x][i]=s[p].v;
            p++;
        }
        for(int i=p;i<l;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(!b[s[i].x][j])
                {
                    b[s[i].x][j]=s[i].v;
                    break;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                printf("%lld ",b[i][j]);
            printf("\n");
        }
    }
    return 0;
}

C

The question ： Give a sequence , The sequence is required to be placed on the diagonal of the matrix （ From top left to bottom right ）, Then give the matrix design scheme , The number of areas in the same block is the same , And the number of numbers in the region = The number of , All numbers are in the lower left corner of the matrix , If there is no such matrix, output -1.

Answer key ： First place the sequence on the diagonal of the matrix , Then determine the area from top to bottom , Each area is defined to the left , If the left position has been placed , Just look on the left of the next line , Loop this operation , Know to determine the complete half matrix , If the existing number is not put out and there is no place to put it, it will be output -1（ Practice has proved that there is no such thing -1）.

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <map>
#include <stack>
#include <stdlib.h>
#include <set>
#include <cstring>
#include <string>
using namespace std;
int n,vis[505],x,b[505][505];
void init()
{
    for(int i=1;i<=n;i++)
        vis[i]=i;
}
int main(void)
{
    scanf("%d",&n);
    init();
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        b[i][i]=x;
        vis[x]--;
    }
    for(int i=1;i<=n;i++)
    {
        int k=b[i][i],l=i,r=i;
        while(r<=n)
        {
            if(!vis[k])
                break;
            if(!b[r][l-1]&&l!=1)
            {
                b[r][l-1]=k;
                vis[k]--;
                l--;
                continue;
            }
            r++;
            b[r][l]=k;
            vis[k]--;
        }
        if(vis[k])
        {
            printf("-1\n");
            return 0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
            printf("%d ",b[i][j]);
        printf("\n");
    }
    return 0;
}

D

The question ： Give me a n×m Matrix , Tell you the length of each adjacent grid edge , Ask each point to go k The shortest length to return to the origin after step , You can walk to the same grid many times , But you can't stand still at every step .

Answer key ： When k It is impossible to go to the origin when it is an odd number , Direct output -1.k For even when , It can be understood as walking k/2 The shortest length of a step . Can record each grid walk k/2 The minimum length spent after a step , direct dp,x,y The smallest part of this grid i The step path is the smallest path of the four sided lattice i-2 Walk on foot 2 Step to the target grid （ You can read the code directly if you don't understand it ）

linear equation ：dp[k][i][j]=min(dp[k-2][i-1][y],dp[k-2][i+1][y],dp[k-2][i][j-1],dp[k-2][i][j+1]).

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <map>
#include <stack>
#include <stdlib.h>
#include <set>
#include <cstring>
#include <string>
#include <vector>
#include <iomanip>
#define ll long long
#define pi acos(-1)
#define mod 1000000007
#define INF 111111
#define exp 1e-8
using namespace std;
int n,m,k;
ll dp[25][505][505],b[505][505],c[505][505];
int main(void)
{
    int x,y;
    scanf("%d%d%d",&n,&m,&k);
    memset(b,INF,sizeof(b));
    memset(c,INF,sizeof(c));
    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)
            scanf("%lld",&b[i][j]);
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
            scanf("%lld",&c[i][j]);
    if(k%2)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
                printf("-1 ");
            printf("\n");
        }
    }
    else
    {
        memset(dp,INF,sizeof(dp));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                dp[0][i][j]=0;
        for(int i=2;i<=k;i+=2)
        {
            for(int j=1;j<=n;j++)
            {
                for(int o=1;o<=m;o++)
                {
                    // Here, because the cross-border grid has been counted as the largest , Therefore, it does not affect the minimum value 
                    // Don't drive ll It will explode here , If you add the condition to judge whether the lattice is out of bounds, you can not open it ll
                    dp[i][j][o]=min(dp[i][j][o],dp[i-2][j-1][o]+2*c[j-1][o]);
                    dp[i][j][o]=min(dp[i][j][o],dp[i-2][j+1][o]+2*c[j][o]);
                    dp[i][j][o]=min(dp[i][j][o],dp[i-2][j][o-1]+2*b[j][o-1]);
                    dp[i][j][o]=min(dp[i][j][o],dp[i-2][j][o+1]+2*b[j][o]);
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
                printf("%lld ",dp[k][i][j]);
            printf("\n");
        }
    }
    return 0;
}