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

2021.4.23

A

题意：给一个数n，判断n能否被2050*10^k中取的数相加得到。

题解：每个相加的数都是2050的倍数，所以直接判断n能否被2050整除得到，可以的话直接加上商的位数和。

#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

题意：给n+1个点，0到n，每个相邻点的具有m条边，所以共有n组m条边，价值=0到n的最小边的长度，每条边只能被用一次，求这m组方案价值和的最小，求具体的方案。

题解：只需取出所有边的前m小，然后将这前m小的边放在不同的方案数上，这样取得的价值和就是最小的。

#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

题意：给一串序列，要求序列的顺序放在矩阵的对角线上（从左上往右下），然后给矩阵设计方案，同一块区域数都相同，且区域中数的个数=这个数，所有的数都是位于矩阵的左下角，如果没有这样的矩阵则输出-1。

题解：先将序列放到矩阵的对角线上，然后从上往下确定区域，每个区域往左确定，如果左边的位置已经被放了，就往下一行的左边找，循环此操作，知道确定完整个半边矩阵，如果存在数没放完且没地方放了就输出-1（实践证明没有这个-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

题意：给一个n×m的矩阵，告诉你每个相邻格子边的长度，求每个点走k步之后回到原点的最短长度，可以多次走到同一格子，但每一步都不能原地踏步。

题解：当k为奇数时必不可能走到原点，直接输出-1。k为偶数时，可以理解为走k/2步出去的最短长度。可以记录每个格子走k/2步后最小花费的长度，直接dp，x,y这个格子最小的第i步路就是四面的格子的最小那条路的第i-2步路走2步到目标格子（可以看不懂直接看代码）

线性方程：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++)
                {
                    //这里因为越界的格子已经计为最大，所以不影响取最小值
                    //不开ll这里会炸，如果加上判断格子越界的条件就可以不开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;
}