Contest 2050 and Codeforces Round #718 (Div. 1 + Div. 2)ABCDEFGH题解_综合

A - Sum of 2050

题意:问你一个数能否由只2050或20500或20500或205000或2050000…组成

所以只要看能不能被2050整除
然后把结果每一位加起来就是答案

#include<iostream>
#define ll long long
using namespace std;
ll t, n, m, sum;
int main(){
    cin>>t;while(t--) {
    cin>>n;if(n%2050!=0) cout<<-1<<endl;else {
    m=n/2050;sum=0;while(m) {
    sum+=m%10;m/=10;}cout<<sum<<endl;}}return 0;
}

B - Morning Jogging

题目链接
题意： $m$ 个区间有 $n$ 条路，你要选 $m$ 条路之和的最短

我们先给所有的长度进行排序，选择前面 $m$ 个放在原数组的第 $1 ? m$ 的位置
比赛的时候被这道题卡住了想直接swap交换然后更改他们的位置坐标但是就是一直wa

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 105;ll n, m, t, v[N][N], b[N][N], a[N][N];bool vis[N][N];struct node {
    int x, y;ll z;}mi[10005];bool cmp(node k, node l) {
    return k.z<l.z;}
int main(){
    cin>>t;while(t--) {
    cin>>n>>m;ll cnt=0;ll q=0;memset(mi, 0, sizeof mi);memset(v, 0, sizeof v);memset(vis, 0, sizeof vis);memset(a, 0, sizeof a);for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) {
    cin>>mi[++cnt].z;mi[cnt].x=i;mi[cnt].y=j;b[i][j]=mi[cnt].z;}}sort(mi+1, mi+1+cnt, cmp);for(int i=1; i<=m; i++) {
    a[mi[i].x][i]=mi[i].z;vis[mi[i].x][mi[i].y]=1;//标记用过的}for(int i=1; i<=n; i++) {
    q=0;for(int j=1; j<=m; j++) {
    //取没用过的if(!vis[i][j]) v[i][++q]=b[i][j];}}for(int i=1; i<=n; i++) {
    q=0;for(int j=1; j<=m; j++) {
    if(!a[i][j]) a[i][j]=v[i][++q];}}for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) {
    cout<<a[i][j]<<" \n"[j==m];}}}return 0;
}

C - Fillomino 2

题目链接
题意：给你一个 $n$ 和长为 $n$ 的数组在对角线上要放 $a 1, a 2, . . a n$
问你能否建立一个包括主对角线的下三角，使每个相同元素连通，每个数组元素个数等于该元素的值

建立是肯定能建立的因为元素个数刚好等于下三角的个数，最好的构造方法就是先往左再往下假如还不够就往右
比赛的时候没考虑到往左往下了还不够的情况

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 505;ll n, m, t, v[N][N], b[N][N], a[N][N];
void dfs(ll x, ll y, ll k) {
    if(b[k][k]<=1)return ;if(y-1>=1&&!a[x][y-1]) {
    a[x][y-1]=a[k][k];b[k][k]--;dfs(x,y-1,k);}else if(x+1<=n&&!a[x+1][y]) {
     a[x+1][y]=a[k][k];b[k][k]--;	dfs(x+1,y,k);}else {
    b[k][k]--;	a[x][y+1]=a[k][k];dfs(x,y+1,k);}
}
int main(){
    	cin>>n;for(int i=1; i<=n; i++) {
    cin>>b[i][i];a[i][i]=b[i][i];}for(int i=1; i<=n; i++) dfs(i, i, i);for(int i=1; i<=n; i++) {
    for(int j=1; j<=i; j++) {
    cout<<a[i][j]<<" \n"[j==i];}}  return 0;
}

D. Explorer Space

题目链接
题意：给你 $n ? m$ 的矩阵，求每一个点 $(i, j)$ 走 $k$ 步回到 $(i, j)$ 的的最短路径

所以问题变为 $(i, j)$ 到某点走了 $k / 2$ 步的最短路， $k$ 一定要是偶数，奇数就不能回到原点了
记忆化搜索不然可能会t 每个点可能从他的周边转移过来
比赛的时候没看

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 505;ll n, m, t, v[N][N], b[N][N], a[N][N], d[N][N][25], k;//三维数组表示(x, y)这个点走了step步的最小值bool in(int x, int y) {
    return 1<=x&&x<=n&&1<=y&&y<=m;}
ll dfs(ll x, ll y, ll step) {
    if(d[x][y][step]) return d[x][y][step];//有就返回if(step==0) return d[x][y][0];ll ans=1e18;if(in(x, y+1)) ans=min(dfs(x, y+1, step-1)+a[x][y], ans);if(in(x+1, y)) ans=min(dfs(x+1, y, step-1)+b[x][y], ans);if(in(x, y-1)) ans=min(dfs(x, y-1, step-1)+a[x][y-1], ans);if(in(x-1, y)) ans=min(dfs(x-1, y, step-1)+b[x-1][y], ans);d[x][y][step]=ans;//记忆一下避免反反复复return ans;
}
int main(){
    cin>>n>>m>>k;for(int i=1; i<=n; i++) {
    for(int j=1; j<m; j++) {
    cin>>a[i][j];}}for(int i=1; i<n; i++) {
    for(int j=1; j<=m; j++) {
    cin>>b[i][j];}}if(k%2==1) {
    for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) {
    cout<<-1<<" \n"[j==m];}}}else {
    for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) {
    cout<<2*dfs(i, j, k/2)<<" \n"[j==m];//必须要从k/2到0 不然可能被更新坏了 像背包一样}}}return 0;
}

E - Group Photo

F - Reunion

G - Starry Night Camping

1楼gg会大家快%

Contest 2050 and Codeforces Round #718 (Div. 1 + Div. 2)ABCDEFGH题解