Codeforces上的新年赛，有些题目难度较大。链接。

A. New Year and Naming

        水题，根据周期性可以轻松解决这个题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
char sa[25][20], sb[25][20];
int n, m;
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", sa[i]);
    for (int i = 0; i < m; i++) scanf("%s", sb[i]);
    int q;
    scanf("%d", &q);
    while (q--) {
        int ss;
        scanf("%d", &ss), --ss;
        printf("%s%s\n", sa[ss % n], sb[ss % m]);
    }
    // PAUSE;
    return 0;
}

B. New Year and Ascent Sequence

        拼起来没有正序对只需要两个都是完全逆序的，然后前一个的最小元素不小于后一个的最大元素，统计一波即可，可以使用树状数组维护。

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
By t3018210153, contest: Hello 2020, problem: (B) New Year and Ascent Sequence, Accepted, #
#include <bits/stdc++.h>
using namespace std;
int n, op[100005], sum[1100005];
vector<int> vec;
long long ans;
void add(int x)
{
    for (; x <= 1000010; x += x & -x) sum[x]++;
}
int s(int x)
{
    int a = 0;
    for (; x >= 1; x -= x & -x) a += sum[x];
    return a;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        for (int j = 1; j <= x; j++) {
            scanf("%d", op + j);
            ++op[j];
        }
        for (int j = 2; j <= x; j++) {
            if (op[j] > op[j - 1]) {
                goto to;
            }
        }
        add(op[x]);
        vec.push_back(op[1]);
    to:;
    }
    for (int ss : vec) {
        ans += s(1000001) - s(ss - 1);
    }
    printf("%lld", 1ll * n * n - ans);
    // PAUSE;
    return 0;
}

C. New Year and Permutation

        数学题。容易发现符合条件的区间中的数必然是自然数上连续的一段。
        枚举长度。对于长度为$k$的区间，首先先从自然数上找一段，显然有$n-k+1$段，然后对其进行排列并放到排列中，有$(n-k+1)k!$种情况。剩下的部分有$(n-k)!$种，这样长度为$k$的所有区间贡献为：$(n-k+1)^2k!(n-k)!$。
        答案就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int p, fac[250005];
 
int main()
{
    int n;
    scanf("%d%d", &n, &p);
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % p;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = (ans + 1ll * (n - i + 1) * (n - i + 1) % p * fac[i] % p * fac[n - i] % p) % p;
    }
    printf("%d", ans);
    // PAUSE;
    return 0;
}

D. New Year and Conference

        数据结构题。由于每一个元素都包含两个区间，我们可以固定一个区间，然后维护另一个区间。
        容易发现两个区间相互包含等价于其中一个区间的左（右）端点被另一个区间包含。于是我们可以构造两棵平衡树，第一棵按第一个区间的左端点升序排序，第二个平衡树按第一个区间的右端点升序排序。每一个平衡树维护两个值，一个是第二个区间的右端点最小值，另一个是第二个区间的左端点最大值。
        遍历所有元素的第一个区间，在平衡树中剖离右端点小于其左端点的部分以及左端点大于右端点的部分，剩下的就是与第一个区间有交集的元素。若这一部分的右端点最小值小于被遍历元素的第二个区间左端点或者左端点最大值大于右端点，则可以判断存在一个元素第一个区间与其相交而第二个区间与其分离，即可得到答案。之后需要交换第一个和第二个区间再执行一遍算法。
        本题也可以用线段树去做，不过需要先进行离散化。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
#define N 400005
using namespace std;
struct Node
{
    int sa, ea, sb, eb;
} op[N];
struct T
{
    int ch[2], l, r, lvalue, rvalue, lv, rv, key;
} nd[N << 2];
int n, tot = 1, l_root, r_root;
inline int newNode(int l, int r, int lv, int rv)
{
    nd[tot].l = l, nd[tot].r = r;
    nd[tot].lvalue = nd[tot].lv = lv;
    nd[tot].rvalue = nd[tot].rv = rv;
    nd[tot].key = rand();
    return tot++;
}
inline void update(int k)
{
    nd[k].lvalue = min(nd[k].lv, min(nd[nd[k].ch[0]].lvalue, nd[nd[k].ch[1]].lvalue));
    nd[k].rvalue = max(nd[k].rv, max(nd[nd[k].ch[0]].rvalue, nd[nd[k].ch[1]].rvalue));
}
void splitl_less(int rt, int& a, int& b, int k)  //find l<=k
{
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (nd[rt].l <= k)
        a = rt, splitl_less(nd[rt].ch[1], nd[a].ch[1], b, k);
    else
        b = rt, splitl_less(nd[rt].ch[0], a, nd[b].ch[0], k);
    update(rt);
}
void splitr_less(int rt, int& a, int& b, int k)  //find r<=k
{
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (nd[rt].r <= k)
        a = rt, splitr_less(nd[rt].ch[1], nd[a].ch[1], b, k);
    else
        b = rt, splitr_less(nd[rt].ch[0], a, nd[b].ch[0], k);
    update(rt);
}
void merge(int& rt, int a, int b)
{
    if (a == 0 || b == 0) {
        rt = a + b;
        return;
    }
    if (nd[a].key < nd[b].key)
        rt = b, merge(nd[rt].ch[0], a, nd[b].ch[0]);
    else
        rt = a, merge(nd[rt].ch[1], nd[a].ch[1], b);
    update(rt);
}
void add(int x)
{
    int a, b, c;
    splitl_less(l_root, a, b, op[x].sa);
    merge(a, a, newNode(op[x].sa, op[x].ea, op[x].eb, op[x].sb));
    merge(l_root, a, b);
    splitr_less(r_root, a, b, op[x].ea);
    merge(a, a, newNode(op[x].sa, op[x].ea, op[x].eb, op[x].sb));
    merge(r_root, a, b);
}
int get(int x)
{
    int a, b, c, d, ans = 0;
    splitl_less(l_root, a, c, op[x].ea), splitl_less(a, a, b, op[x].sa - 1);
    if (nd[b].lvalue < op[x].sb || nd[b].rvalue > op[x].eb) ans = 1;
    merge(a, a, b), merge(l_root, a, c);
    splitr_less(r_root, a, c, op[x].ea), splitr_less(a, a, b, op[x].sa - 1);
    if (nd[b].lvalue < op[x].sb || nd[b].rvalue > op[x].eb) ans = 1;
    merge(a, a, b), merge(r_root, a, c);
    return ans;
}
int main()
{
    srand(time(0));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &op[i].sa, &op[i].ea, &op[i].sb, &op[i].eb);
    }
    nd[0].lvalue = 0x7fffffff, nd[0].rvalue = 0x80000000;
    for (int i = 1; i <= n; i++) add(i);
    for (int i = 1; i <= n; i++) {
        if (get(i)) {
            printf("NO");
            return 0;
        }
    }
    tot = 1, l_root = 0, r_root = 0;
    memset(nd, 0, sizeof(nd));
    nd[0].lvalue = 0x7fffffff, nd[0].rvalue = 0x80000000;
    for (int i = 1; i <= n; i++) swap(op[i].sa, op[i].sb), swap(op[i].ea, op[i].eb);
    for (int i = 1; i <= n; i++) add(i);
    for (int i = 1; i <= n; i++) {
        if (get(i)) {
            printf("NO");
            return 0;
        }
    }
    printf("YES");
    return 0;
}

E. New Year and Castle Construction

        枚举$p$，然后统计剩下的所有四边形，显然有$nC_{n-1}^4$种可能。对于某一个点$p$，剩下的所有四边形必然分两种，一种包含$p$，另一种不包含。通过画图可以发现，如果我们将$p$当做原点，则一个四边形包含$p$等价于这四个点的跨度大于${\pi}$（题目已经保证没有共线的三点）。
        于是我们有了一个做法：将其余的$n-1$个点按照到$p$的极角排序，然后对其进行遍历，固定一个点，然后找出跨度小于$\pi$的区间，若其中有不少于3个点，则对答案产生$C_k^3$的贡献（$k$是这一段的点的数目）。
        本题需要比较好的精度要求，尽可能使用long double。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lb;
struct Point
{
    lb x, y;
} op[2600];
vector<lb> vec;
ll ans;
const lb PI = acos(-1.0l);
inline bool check(lb a, lb b)
{
    lb tmp = b - a;
    if (tmp < 0) tmp += 2 * PI;
    return tmp < PI;
}
ll C3(int x)
{
    return 1ll * x * (x - 1) * (x - 2) / 6;
}
ll C4(int x)
{
    return 1ll * x * (x - 1) * (x - 2) * (x - 3) / 24;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1, x, y; i <= n; i++) scanf("%Lf%Lf", &op[i].x, &op[i].y);
    for (int i = 1; i <= n; i++) {
        vec.clear();
        for (int j = 1; j <= n; j++)
            if (i != j) vec.push_back(atan2(op[j].x - op[i].x, op[j].y - op[i].y));
        sort(vec.begin(), vec.end());
        for (int j = 0, at = 0; j < vec.size(); j++) {
            while (at + 1 < j + n - 1 && check(vec[j], vec[(at + 1) % (n - 1)])) ++at;
            if (at - j >= 3) ans += C3(at - j);
        }
    }
    printf("%lld", 1ll * n * C4(n - 1) - ans);
    // PAUSE;
    return 0;
}

F. New Year and Social Network

        看起来是一个二分图匹配，但是$O(n^2)$复杂度肯定不可以，并且这个复杂度似乎降不下来，直接建二分图不可取。
        不建二分图，只能利用题目性质贪心地匹配。
        对于$T_2$上的某一个叶子结点$x$及其父节点$f$，可以发现$x-f$是连接$x$与$f$的唯一边，此时在$T_1$上从$x$到$f$的树链上的所有边都可以得到覆盖，为了使答案更优，我们应该覆盖尽可能与$x$较近的边。
        于是化边为一个点，建立LCT，令这些边对应的点的点权为1，每一次在树链上找第一个权值为1的点，这就是可以覆盖的边。即用LCT维护某一条树链上距一个端点最近的未选边。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <bits/stdc++.h>
 
#define N 600005
using namespace std;
 
int n, m, v[N], son[N][2], fa[N], lazy[N], sta[N], val[N], ea[N], eb[N], deg[N];
struct Edge
{
    int next, to;
} edge[N << 1];
int head[N], cnt = 1;
queue<int> que;
inline void update(int x)
{
    val[x] = max(v[x], max(val[son[x][0]], val[son[x][1]]));
}
 
inline bool isNotRoot(int x)
{
    return son[fa[x]][0] == x || son[fa[x]][1] == x;
}
 
inline int identify(int x)
{
    return son[fa[x]][1] == x;
}
 
inline void change(int f, int s, int w)
{
    fa[s] = f, son[f][w] = s;
}
 
inline void rotate(int x)
{
    int f = fa[x], g = fa[f], i = identify(x), j = identify(f);
    if (!isNotRoot(f))
        fa[x] = g;
    else
        change(g, x, j);
    change(f, son[x][i ^ 1], i), change(x, f, i ^ 1);
    update(f), update(x);
}
 
inline void pushr(int x)
{
    swap(son[x][0], son[x][1]), lazy[x] ^= 1;
}
 
inline void pushdown(int x)
{
    if (lazy[x]) pushr(son[x][0]), pushr(son[x][1]), lazy[x] = 0;
}
 
inline void splay(int x)
{
    int i = 0, y = x;
    sta[++i] = y;
    while (isNotRoot(y)) sta[++i] = y = fa[y];
    while (i) pushdown(sta[i--]);
    while (isNotRoot(x)) {
        int f = fa[x];
        if (isNotRoot(f)) {
            if (identify(x) == identify(f))
                rotate(f);
            else
                rotate(x);
        }
        rotate(x);
    }
}
 
inline void access(int x)
{
    for (int i = 0; x; x = fa[i = x]) splay(x), son[x][1] = i, update(x);
}
 
inline void makeRoot(int x)
{
    access(x), splay(x), pushr(x);
}
 
inline int findRoot(int x)
{
    access(x), splay(x);
    while (son[x][0]) pushdown(x), x = son[x][0];
    splay(x);
    return x;
}
 
inline void link(int x, int y)
{
    makeRoot(x);
    if (x != findRoot(y)) fa[x] = y;
}
 
inline void cut(int x, int y)
{
    makeRoot(x);
    if (findRoot(y) == x && fa[y] == x && !son[y][0]) fa[y] = 0, son[x][1] = 0, update(x);
}
 
inline void add(int x, int y)
{
    edge[cnt].next = head[x], edge[cnt].to = y, head[x] = cnt++;
}
inline int get(int x)
{
    pushdown(x);
    if (val[son[x][0]])
        return get(son[x][0]);
    else if (v[x] == 1)
        return x;
    return get(son[x][1]);
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", ea + i, eb + i);
        v[i + n] = 1, link(ea[i], i + n), link(eb[i], i + n);
    }
    for (int i = 1, x, y; i < n; i++) {
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
        ++deg[x], ++deg[y];
    }
    for (int i = 1; i <= n; i++)
        if (deg[i] == 1) que.push(i);
    printf("%d\n", n - 1);
    while (!que.empty()) {
        int f = que.front();
        que.pop(), deg[f] = -1;
        for (int i = head[f], rt; i; i = edge[i].next) {
            if (deg[edge[i].to] == -1) continue;
            --deg[edge[i].to];
            if (deg[edge[i].to] == 1) que.push(edge[i].to);
            makeRoot(f), access(edge[i].to), splay(f), rt = get(f);
            printf("%d %d %d %d\n", ea[rt - n], eb[rt - n], f, edge[i].to);
            splay(rt), v[rt] = 0, update(rt);
        }
    }
    // PAUSE;
    return 0;
}

G. Seollal

        题目难度较大。
        容易发现本题的目标就是生成一棵生成树，使得某一些点不能为叶子。
        这里的相关理论出自官方比赛的题解。
        我们称这些不能为叶子的节点集合为$S$，可以证明满足题意的生成树存在等价于可以找到一个无环的边集使得每一个$x\in S$节点的度数为2。
        充分性：每一个$x\in S$的度数都是2，并且没有环，这样我们必然可以通过加入一些边将其变为生成树。由于度数为2，$S$中的点必然不会是叶子，于是得到了满足题意的生成树。
        必要性：注意到$S$中的点都是独立的，也就是说它们彼此必然不会相邻。在满足题意的生成树上，$S$中的点的度数必然至少为2，这样可以通过删去一些边，使得得到一个森林，其中$S$中的点度数为2。
        接下来，我们需要借助拟阵这一个数学工具来找一个无环边集，使$S$中度数都为2。
        将所有与$S$中的点相连的边集记为$P$，构造其环拟阵$M_1=(P,I_1)$；然后根据$S$中的点度数不超过2，构造拟阵$M_2=(P,I_2)$，可以证明$M_2$满足拟阵的三条公理，这里不再证明。
        然后我们求两个拟阵的交，若最大的集合数量为$2|S|$，说明存在合法的生成树，之后再补上其它的边使所有点连通即可。
        对于拟阵$M_1$，可以用并查集辅助维护，对于$M_2$用数组记即可。这里不要用LCT来动态维护连通性，多一个$log$的代价对于本题来说会T。复杂度$O(n^3m^3)$。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <bits/stdc++.h>
using namespace std;
#define N 800
#define ID(x, y) (((x)*m + y) + 1)
#define X(x) ((x - 1) / m + 1)
#define Y(x) ((x - 1) % m + 1)
int n, m, color[N], S, vis[N], pre[N], adj[N][N], deg[N];
set<int> A, X1, X2, P, tmp;
char ee[50][50], ans[50][50];
vector<pair<int, int>> e;
struct bcj
{
    int fa[N];
    void init()
    {
        for (int i = 1, t = n * m; i <= t; i++) fa[i] = i;
    }
    int ff(int x)
    {
        return fa[x] == x ? x : fa[x] = ff(fa[x]);
    }
    void merge(int x, int y)
    {
        fa[ff(x)] = ff(y);
    }
} op[N + 1];
 
inline bool canAdd1(int x)
{
    return op[N].ff(e[x].first) != op[N].ff(e[x].second);
}
inline bool canAdd2(int x)
{
    if (color[e[x].first] && deg[e[x].first] >= 2) return false;
    if (color[e[x].second] && deg[e[x].second] >= 2) return false;
    return true;
}
inline bool canAdd1(int a, int b)
{
    return op[a].ff(e[b].first) != op[a].ff(e[b].second);
}
inline bool canAdd2(int a, int b)
{
    int ans = 0;
    --deg[e[a].first], --deg[e[a].second], ans = canAdd2(b), ++deg[e[a].first], ++deg[e[a].second];
    return ans;
}
inline void get(int x)
{
    do {
        P.insert(x), x = pre[x];
    } while (x != -1);
}
queue<int> que;
inline void solve()
{
    A.clear(), memset(deg, 0, sizeof(deg));
    while (true) {
        X1.clear(), X2.clear(), op[N].init();
        for (int i = 0; i < e.size(); i++) op[i].init();
        for (int i = 0; i < e.size(); i++) {
            for (int s : A) {
                if (s != i) op[i].merge(e[s].first, e[s].second);
            }
        }
        for (int s : A) op[N].merge(e[s].first, e[s].second);
        for (int i = 0; i < e.size(); i++) {
            if (!A.count(i) && canAdd1(i)) X1.insert(i);
            if (!A.count(i) && canAdd2(i)) X2.insert(i);
        }
        for (int i = 0; i < e.size(); i++) {
            for (int j = 0; j < e.size(); j++) adj[i][j] = 0;
        }
        for (int i = 0; i < e.size(); i++) {
            if (A.count(i)) continue;
            for (int j : A) {
                if (canAdd1(j, i)) adj[j][i] = 1;
                if (canAdd2(j, i)) adj[i][j] = 1;
            }
        }
        while (!que.empty()) que.pop();
        memset(vis, 0, sizeof(vis)), P.clear();
        for (int s : X1) que.push(s), vis[s] = 1, pre[s] = -1;
        while (!que.empty()) {
            int f = que.front();
            que.pop();
            if (X2.count(f)) {
                get(f);
                break;
            }
            for (int i = 0; i < e.size(); i++) {
                if (vis[i] || adj[f][i] == 0) continue;
                que.push(i), pre[i] = f, vis[i] = 1;
            }
        }
        if (P.empty()) break;
        tmp.clear(), set_intersection(A.begin(), A.end(), P.begin(), P.end(), inserter(tmp, tmp.begin()));
        for (int s : tmp) A.erase(s), --deg[e[s].first], --deg[e[s].second];
        for (int s : P) {
            if (!tmp.count(s)) A.insert(s), ++deg[e[s].first], ++deg[e[s].second];
        }
    }
}
int main()
{
    // DEBUG;
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        memset(color, 0, sizeof(color)), S = 0, e.clear();
        for (int i = 0; i < n; i++) {
            scanf("%s", ee + i);
            for (int j = 0; j < m; j++) {
                if (ee[i][j] == 'O' && i + j > 0 && i % 2 == j % 2) {
                    color[ID(i, j)] = 1, ++S;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i + j == 0) continue;
                if (j + 1 < m && ee[i][j] == 'O' && ee[i][j + 1] == 'O') {
                    e.push_back(make_pair(ID(i, j), ID(i, j + 1)));
                }
                if (i + 1 < n && ee[i][j] == 'O' && ee[i + 1][j] == 'O') {
                    e.push_back(make_pair(ID(i, j), ID(i + 1, j)));
                }
            }
        }
        solve();
        if (A.size() != 2 * S) {
            printf("NO\n");
            continue;
        }
        printf("YES\n");
        for (int i = 1; i <= 2 * n - 1; i++) {
            for (int j = 1; j <= 2 * m - 1; j++) ans[i][j] = ' ';
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) ans[2 * i + 1][2 * j + 1] = ee[i][j];
        }
        for (int s : A) {
            if (e[s].second == e[s].first + 1) {
                ans[2 * X(e[s].first) - 1][2 * Y(e[s].first)] = 'O';
            }
            else {
                ans[2 * X(e[s].first)][2 * Y(e[s].first) - 1] = 'O';
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (j + 1 < m && ee[i][j] == 'O' && ee[i][j + 1] == 'O' && op[N].ff(ID(i, j)) != op[N].ff(ID(i, j + 1))) {
                    op[N].merge(ID(i, j), ID(i, j + 1));
                    ans[2 * i + 1][2 * j + 2] = 'O';
                }
                if (i + 1 < n && ee[i][j] == 'O' && ee[i + 1][j] == 'O' && op[N].ff(ID(i, j)) != op[N].ff(ID(i + 1, j))) {
                    op[N].merge(ID(i, j), ID(i + 1, j));
                    ans[2 * i + 2][2 * j + 1] = 'O';
                }
            }
        }
        for (int i = 1; i <= 2 * n - 1; i++) {
            for (int j = 1; j <= 2 * m - 1; j++) putchar(ans[i][j]);
            putchar('\n');
        }
    }
    // PAUSE;
    return 0;
}