题目链接

在B题上卡了一下，没排序debug半个小时，难受。

A题

题意：
给你一个n，定义2050乘以\(10^k\)（k取自然数）为"2050-number"
问你n最少是多少个"2050-number"的和

思路：
先判断\(n % 2050\)是否为0，然后答案就是\(n/2050\)的各位数之和。

ll n; 
 
int main()
{
    IOS;
	int T;
	cin >> T;
	while(T --)
	{
		cin >> n;
		ll res = 0;
		if(n % 2050 == 0)
			res += n / 2050;
		ll ans = 0;
		while(res)
		{
			ans += res % 10;
			res /= 10;
		}
		if(!ans) cout << -1 << endl;
		else cout << ans << endl;
	}
}

B题

题意：
让你组m条路径，每条路径的权重是路径上边的最小值，问你怎么可以让所有路径的权重之和最小。

思路：
将所有的边排序，每次拿出最小的边，然后其它边尽肯能拿大的即可。
显然这样可以留下更多小的边给其它路径。

ll n, m; 
int g[N][N];
pii cnt[N];
vector<int> v;
vector<int> ans[N];
 
int main()
{
    IOS;
	int T;
	cin >> T;
	while(T --)
	{
		v.clear();
		cin >> n >> m;
		for(int i = 0 ; i < n ; i ++)
		{
			for(int j = 0 ; j < m ; j ++)
				cin >> g[i][j], v.push_back(g[i][j]);	
			sort(g[i], g[i] + m);	
			cnt[i] = {0, m - 1};		
		}
		
		sort(v.begin(), v.end());
		for(int i = 0 ; i < m ; i ++)
		{
			int t = v[i];
			bool flag = false;
			for(int j = 0 ; j < n ; j ++)
			{
				if(g[j][cnt[j].x] == t && !flag)
				{
					ans[i].push_back(g[j][cnt[j].x ++]);
					flag = true;
				}
				else
				{
					ans[i].push_back(g[j][cnt[j].y --]);
				}
			}
		}
		
		for(int i = 0 ; i < n ; i ++)
		{
			for(int j = 0 ; j < m ; j ++)
				cout << ans[j][i] << " ";
			cout << "\n";			
		}
 
			
		for(int i = 0 ; i < m ; i ++)	ans[i].clear();
	}
}

C题

题意：
给你n个数，它们依次位于主对角线上的位置上，要求输出一个主对角线的下三角，使得对角线上每个数x都能连通和自己数值相等的数，并且有x个。

思路：
选择两个方向构造。我是依次处理每个对角线上的点，优先向左放，左边放不了再向下放。

ll n, m; 
int g[N][N];
 
int main()
{
    IOS;
	{
		cin >> n;
		for(int i = 1 ; i <= n ; i ++)	
			cin >> g[i][i];
		
		for(int i = 1 ; i <= n ; i ++)	
		{
			int d = g[i][i], cnt = g[i][i] - 1;
			int x = i, y = i;
			while(cnt)
			{
				if(y - 1 >= 1 && !g[x][y - 1])
				{
					g[x][y - 1] = d;
					cnt --;
					y = y - 1;
				}
				else
				{
					g[x + 1][y] = d;
					cnt --;
					x = x + 1;
				}				
			}
		}
		
		for(int i = 1 ; i <= n ; i ++)
		{
			for(int j = 1 ; j <= i ; j ++)
				cout << g[i][j] << " ";
			cout << endl;			
		}
 
	}
}

D题

题意：
给你一个网格图，问你从每个点出发，经过确定k步再回到该点的最小距离。

思路：
DP，f[i][j][k] 表示 点(i, j)经过k步回到该点的最短距离。

ll n, m, k; 
ll r[N][N], d[N][N];
ll f[N][N][21];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
 
int main()
{
    IOS;
	{
		cin >> n >> m >> k;
				
		for(int i = 1 ; i <= n ; i ++)
			for(int j = 1 ; j < m ; j ++)
				cin >> r[i][j];
 
		for(int i = 1 ; i < n ; i ++)
			for(int j = 1 ; j <= m ; j ++)
				cin >> d[i][j];
		
		memset(f, 0x3f, sizeof f);
		for(int i = 1 ; i <= n ; i ++)
			for(int j = 1 ; j <= m ; j ++)
				f[i][j][0] = 0;
		
		if((k & 1) == 0)
		{
			for(int p = 2 ; p <= k ; p += 2)	//总步数 
			{
				for(int q = 2 ; q <= p ; q += 2)	//转移步数 
				{
					for(int i = 1 ; i <= n ; i ++)
						for(int j = 1 ; j <= m ; j ++)
						{
							for(int w = 0 ; w < 4 ; w ++)
							{
								int x = i + dx[w], y = j + dy[w];
								if(x < 1 || x > n || y < 1 || y > m) continue;
								ll c;
								if(x < i) c = d[x][y];
								else if(x > i) c = d[i][y];
								else if(y < j) c = r[x][y];
								else c = r[x][j];
								
								f[i][j][p] = min(f[i][j][p], f[x][y][p - q] + q * c);
							}
						}
				}
			}
		}
		
		for(int i = 1 ; i <= n ; i ++)
		{
			for(int j = 1 ; j <= m ; j ++)
			{
				if(f[i][j][k] == 0x3f3f3f3f3f3f3f3f)
					cout << -1 << " ";
				else cout << f[i][j][k] << " ";
			}
			cout << "\n";			
		}
		
	}
}