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 m m個區間有 n n n條路，你要選 m m m條路之和的最短

我們先給所有的長度進行排序，選擇前面 m m m個放在原陣列的第 1 ? m 1-m 1?m的位置
比賽的時候被這道題卡住了 想直接swap交換然后更改他們的位置坐標但是就是一直wa

//輸入
2
2 3
2 3 4
1 3 5
3 2
2 3
4 1
3 5
//輸出
2 3 4
5 3 1
2 3
4 1
3 5

#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 n和長為 n n n的陣列 在對角線上要放 a 1 , a 2 , . . a n a1,a2,..an a1,a2,..an
問你能否建立一個包括主對角線的下三角，使每個相同元素連通，每個陣列元素個數等于該元素的值

建立是肯定能建立的 因為元素個數剛好等于下三角的個數，最好的構造方法就是先往左再往下假如還不夠就往右
比賽的時候沒考慮到往左往下了還不夠的情況

#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 n*m n?m的矩陣，求每一個點 ( i , j ) (i, j) (i,j)走 k k k步回到 ( i , j ) (i, j) (i,j)的的最短路徑

所以問題變為 ( i , j ) (i, j) (i,j)到某點走了 k / 2 k/2 k/2步的最短路， k k 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會大家快%