Contest 2050 and Codeforces Round #718 (Div. 1 + Div. 2) A B C 題解

A Sum of 2050

題意：給定一個數字n，要求将n表示為一些2050*數字(不一定是不同的)的和。計算所需的最小2050個數。

思路：如果不能整除2050則輸出-1，否則輸出商的每個位上的數字之和。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
long long res;
int main() {
	int t;
	scanf("%d", &t);
	
	while (t--) {
		scanf("%lld", &res);

		if (res % 2050 == 0) {
			res /= 2050;
			long long ans = 0;
			while (res) {
				ans += res % 10;

				res /= 10;
			}
			printf("%lld", ans);
		}

		else
			printf("-1");

		printf("\n");
	}
	return 0;
}
           

B Morning Jogging

題意：給你n個長度為m的數組，要求對其按行進行排列，使得每一列上的最小值之和最小，如果有多個答案，列印任何一個。

思路：讀懂題意之後就會發現，将所有n*m個數按升序排序，第i小的數（1<=i<=m）一定在第i列，而其餘數随機排列即可，注意每一個數的行是不變的。

到這一步之後，唯一糾結的地方就是這些資料應該怎樣存儲，怎樣處理，又怎樣進行輸出。

剛開始想着用小根堆的性質存儲會不會賊友善，（然而菜雞對于STL容器實在是太生疏了），于是用二維數組存儲加上雙指針标記暴力AC，事實上我認為開bool數組标記會更友善一些，當時有些着急了……

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int n, m;
int s[110][2];
//這裡相當于每一行的都有兩個指針，在之後将元素插入輸出的數組時用的到。
long d[110][110],q[110][110];
//q中存的是初始元素，d中存的是輸出的元素以及其順序。
int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d", &n, &m);

		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				scanf("%ld", &q[i][j]);

		for (int i = 1; i <= n; i++) {
			sort(q[i] + 1, q[i] + m + 1);
			s[i][1] = m;
			s[i][0] = 1;
		/**
這裡排序和雙指針放到一起就好了解了：
這樣處理的目的是為了在n*m個元素中找出前m小的元素（這裡要用到行首的指針s[i][0]）依次放在第i列，但是行數不變。
這樣在n*m的二維數組中已經确定m個了，剩下的（n-1）*m個元素就随意填充進去吧……
但是這個填充的話也比較困難（應該是我比較菜吧），是以我就幹脆将那些每行需要随意填充的位置依次從大到小塞進去（這裡要用到行首的指針s[i][1]）
		**/
		}
//我是從列開始周遊，即找出第i小的數放在第i列，這一列剩餘位置放置本列尚未用到最大值。
		for (int j = 1; j <= m; j++) {
			int k = 1;
			for (int i = 2; i <= n; i++)
				if (q[i][s[i][0]] < q[k][s[k][0]])
					k = i;
//這裡找到第i小的值

			for (int i = 1; i < k; i++)
				d[i][j] = q[i][s[i][1]--];

			d[k][j] = q[k][s[k][0]++];

			for (int i = k + 1; i <= n; i++)
				d[i][j] = q[i][s[i][1]--];
//這裡是第i列從上到下存入d數組，我為了了解友善故意寫了三段（應該不會影響時間複雜度吧）
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++)
				printf("%d ", d[i][j]);

			printf("\n");
		}
	}
	return 0;
}
           

C Fillomino 2

題意：給你一個n個數的全排列的其中一種排列方式

其中這n個數分别為n*n矩陣的對角線

求是否可以構造一個下三角矩陣

滿足這個矩陣對角線的每一個元素

都有

旁邊與它相等的數的個數（包括它本身）等于這個元素的值

如果存在這個矩陣，輸出這個下三角矩陣

如果不存在，輸出-1

思路：

看懂題目的條件下，很明顯這題答案一定存在

因為你舉不出反例去反對它

然後就是一個簡單的貪心的做法了

在不超過下三角矩陣範圍的情況下

每次優先把它左邊的數變成和它一樣的

如果超了左邊界

就把下面的數變成和它一樣的

且一定不會超過下邊界

一共變a[i][i] - 1 次

代碼如下

#include<bits/stdc++.h>
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define re register int
#define x first
#define y second
typedef long long ll ;
using namespace std;
const int N =  1e6 + 10 , M = 1010 , inf = 0x3f3f3f3f , mod = 1e9 + 7 ;
int n ;
int a[N] ;
int s[M][M] ;
bool st[M][M] ;
int k ;
void dfs(int i , int j , int res)    // i ，j 表示目前這個點的坐标 ， res 表示總次數
{
    if(k == res) return ;
    if(i <= 0 || i > n || j <= 0 || j > n) return ;
    if(st[i][j]) return ;
    st[i][j] = true ;
    s[i][j] = res ;
    k ++ ;
    dfs(i,j-1,res) ;
    dfs(i+1,j,res) ;
}
int main()
{
    cin >> n ;
    fer(i,1,n)
    {
        cin >> a[i] ;
        s[i][i] = a[i] ;
    }
    
    fer(i,1,n)
        fer(j,1,n)
            if(i == j)
            {
                k = 0 ;
                dfs(i,j,s[i][j]) ; 
            }
                
    fer(i,1,n)
    {
        fer(j,1,n)
            if(s[i][j] != 0) cout << s[i][j] << " " ;
        cout << endl;
    }
    return 0;
}