Znzryb's Blog
0%

The 2026 ICPC Latin America Championship（2026 拉丁美洲决赛）-Gym-106416——G. GATA-CAT（ATAT骨架插入式构造方法）

Posted on Edited on

题目大意

题目描述
构造一个长度不超过 500500 且仅由大写字母 C、G、A、T 组成的非空字符串，使其满足以下两个条件：

  1. 字符串中包含恰好 GG 个子序列 GATA（即字符 G、A、T、A 按顺序出现，中间可以包含其他字符）。

  2. 字符串中包含恰好 CC 个子序列 CAT（即字符 C、A、T 按顺序出现，中间可以包含其他字符）。

输入格式
第一行包含一个整数 QQ（1≤Q≤10001 \le Q \le 1000），表示询问的组数。
接下来的 QQ 行，每行包含两个整数 GG 和 CC（0≤G,C≤1060 \le G, C \le 10^6），分别表示所需的 GATA 子序列的数量和 CAT 子序列的数量。

输出格式
对于每组询问，输出一行满足条件的字符串（长度不超过 500500 且仅包含 C、G、A、T）。如果存在多个解，输出任意一个即可。题目保证在给定限制下一定有解。

样例输入与输出

样例 1：

1
2
3
4
5
6
7
8
9
10
11
12
Input:
4
1 1
2 3
18 1
2 1

Output:
GATCAT
GGCATAT
GATGGATATCAT
GGATCAT

样例 2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input:
5
1 0
0 1
1 1
0 0
0 0

Output:
GATAT
CAT
GATCAT
GG
GG

样例解释

对于样例 1 的第一组询问（G=1,C=1G=1, C=1），输出为 GATCAT：

  • GATA 子序列的数量为 11（由第 1 个字符 G、第 2 个字符 A、第 3 个字符 T、第 5 个字符 A 组成）。

  • CAT 子序列的数量为 11（由第 4 个字符 C、第 5 个字符 A、第 6 个字符 T 组成）。

对于样例 2 的第一组询问（G=1,C=0G=1, C=0），输出为 GATAT：

  • GATA 子序列的数量为 11（由第 1 个字符 G、第 2 个字符 A、第 3 个字符 T、第 5 个字符 A 组成）。

  • 由于字符串中完全不包含字符 C，因此 CAT 子序列的数量为 00。

思路讲解

我确实也是想到了插入式的这个构造方法，但是确实没他想的这个么全。

不难发现如下规律：

image

我采用了过程式编程，模块化的思想，把不同的功能模块拆成了不同的函数，避免了Spaghetti Code，也就是面条代码。

我了解了一下，这个不算函数式编程，函数式编程的要求非常严格。

那么我这个代码更算是什么呢？

逐步求精（Stepwise Refinement）

这是由计算机科学家尼克劳斯·维尔特（Niklaus Wirth，PASCAL 语言的发明者）在 1971 年提出的。指的是将一个复杂的任务，不断分解成更小、更简单的子任务，直到这些子任务简单到可以用几行代码直接实现为止****。

我相信这个代码还是很清楚的。

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
vector<ll> at_ls, ata_ls;
ll siz_AT_repeat = 140;

void init() {
    at_ls.resize(siz_AT_repeat);
    ata_ls.resize(siz_AT_repeat);
    for (int i = 1; i < siz_AT_repeat; ++i) {
        at_ls[i] = i;
        ata_ls[i] = i;
    }
    // 上面是差分数组
    // 下面进行一次这个前缀和或者两次前缀和
    partial_sum(all(at_ls), at_ls.begin());
    partial_sum(all(ata_ls), ata_ls.begin());
    partial_sum(all(ata_ls), ata_ls.begin());
#ifdef LOCAL
    debug1d(ata_ls);
    debug1d(at_ls);
#endif
}

// 贪心地计算需要在哪里插入 G/C
vector<ll> greedy_cal(const vector<ll> &A, ll x) {
    vector<ll> res;
    while (x != 0) {
        auto it = upper_bound(all(A), x);
        if (it == A.begin()) {
            // #ifdef LOCAL
            //             debug(x);
            // #endif
            assert(0);
        } else {
            --it;
	          // 应该在倒数第几个 A 前插入？
            res.push_back(it - A.begin());
            x -= *it;
        }
    }
#ifdef LOCAL
    debug1d(res);
#endif
    return res;
}


struct Ch_Num_CG {
    char ch;
    ll num_g;
    ll num_c;
};

void opls_insert(vector<Ch_Num_CG> &ans, vector<ll> opls, ll offset, char cg) {
    // assert(is_sorted(all(opls),greater<>()));
    sort(all(opls), greater());
    ll cnta = 0;
    for (int i = SZ(ans) - 1; i > offset; --i) {
        if (ans[i].ch == 'A') {
            cnta++;
        }
        while (!opls.empty() && opls.back() == cnta) {
            if (cg == 'G') {
                ans[i - offset].num_g++;
            } else {
                ans[i - offset].num_c++;
            }
            opls.pop_back();
        }
    }
}

string gen_ans(const vector<Ch_Num_CG> &ans) {
    string res;
    for (auto [ch,num_g,num_c]: ans) {
        res += string(num_g, 'G');
        res += string(num_c, 'C');
        res += ch;
    }
    return res;
}

void Solve() {
    ll G, C;
    cin >> G >> C;
    vector<ll> g_opls = greedy_cal(ata_ls, G);
    vector<ll> c_opls = greedy_cal(at_ls, C);
    string s;
    vector<Ch_Num_CG> Ans;
    for (int i = 0; i < siz_AT_repeat + 5; ++i) {
        Ans.push_back({'A', 0, 0});
        Ans.push_back({'T', 0, 0});
    }
    opls_insert(Ans,g_opls,2,'G');
    opls_insert(Ans,c_opls,0,'C');
    cout << gen_ans(Ans) << "\n";
}

AC代码

AC
https://codeforces.com/gym/106416/submission/368168341

心路历程（WA，TLE，MLE……）