CF1517C

发表于 | 分类于 |

我好菜QAQ

题面:https://codeforces.com/problemset/problem/1517/C

题意:给定边长为n的正方形方格的下半部分(包含对角线)

给定对角线上的数字，填满该三角形使其满足:数字i出现i次，且属于同一区域

题解:易得，对角线上存在一个数字1，其已经满足条件，不需要再填，故我们取对角线上在1之前的数字向下衍生一格，在1之下的数字向左衍生一格，将问题转化为了n-1规模，此时2也满足条件，继续衍生，直至解完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<cstdio>
#include<list>
#include<stack>
#include<deque>
#include<unordered_set>
using namespace std;
using ll = long long;
ll T,n,m,k;
ll tmp;
ll a[505][505];
vector<ll> ans[505];
int main()
{
    cin >> n;
    for (ll i = 1; i <= n;i++)
    {
        cin >> a[i][i];
    }
    bool flag = 1;
    for (ll i = 1; i <=n;i++)
    {
        for (ll j = 1; j <= n - i+1;j++)
        {
           if(a[i+j-1][j]==i)
           {
               flag = 0;
           }else if(flag)
           {
               a[i + j ][j ] = a[i + j - 1][j];
           }else if(!flag)
           {
               a[i + j -1][j-1] = a[i + j - 1][j];
           }
            
        }
        flag = 1;
    }
    for (ll i = 1; i <= n;i++)
    {
        for (ll j = 1; j <= i;j++)
        {
            cout << a[i][j] << ' ';
        }
        cout << '\n';
    }
        return 0;
}