首页程序设计基础C6 - 2024级程序设计基础第六次上机赛
时间限制 空间限制
1000 ms 65536 KB

# 题目描述

给定整数序列 a1,a2,⋯ ,ana_1, a_2, \cdots , a_n 和 b1,b2,⋯ ,bmb_1, b_2, \cdots , b_m，严格递增的非负整数序列 A1,A2,⋯ ,AnA_1, A_2, \cdots , A_n 和 B1,B2,⋯ ,BmB_1, B_2, \cdots , B_m，求解如下多项式：

∑i=1naixAi+∑i=1mbixBi\sum_{i = 1}^n a_i x^{A_i} + \sum_{i = 1}^m b_i x^{B_i}

# 输入格式

第一行一个正整数 tt（1≤t≤51 \le t \le 5），表示数据组数。

对于每组数据，第一行一个正整数 nn（1≤n≤1051 \le n \le 10^5），含义同题目描述。

第二行 nn 个整数 a1,a2,⋯ ,ana_1, a_2, \cdots , a_n（0<∣ai∣≤1090 < |a_i| \le 10^9），含义同题目描述。

第三行 nn 个非负整数 A1,A2,⋯ ,AnA_1, A_2, \cdots , A_n（0≤Ai≤1090 \le A_i \le 10^9），含义同题目描述。

第四行一个正整数 mm（1≤m≤1051 \le m \le 10^5），含义同题目描述。

第五行 mm 个整数 b1,b2,⋯ ,bmb_1, b_2, \cdots , b_m（0<∣bi∣≤1090 < |bi| \le 10^9），含义同题目描述。

第六行 mm 个非负整数 B1,B2,⋯ ,BmB_1, B_2, \cdots , B_m（0≤Bi≤1090 \le B_i \le 10^9），含义同题目描述。

保证 Ai>Ai−1A_i > A_{i − 1} 对 1<i≤n1 < i \le n 成立，Bi>Bi−1B_i > B_{i − 1} 对 1<i≤m1 < i \le m 成立，Ai=Bj⇒ai+bj≠0A_i = B_j \Rightarrow a_i + b_j \not = 0 对 1≤i≤n,1≤j≤m1 \le i \le n, 1 \le j \le m 成立。

# 输出格式

对于每组数据，输出三行：

第一行一个正整数 kk，表示所得多项式在合并同类项后有 kk 个系数非 00 项，并设所得多项式为：

∑i=1kcixCi\sum_{i = 1}^k c_i x^{C_i}

其中 Ci>Ci−1C_i > C_{i − 1} 对 1<i≤k1 < i \le k 成立。

第二行 kk 个整数 c1,c2,⋯ ,ckc_1, c_2, \cdots , c_k，含义同上式。

第三行 kk 个非负整数 C1,C2,⋯ ,CkC_1, C_2, \cdots , C_k，含义同上式。

# 输入样例

1
3
1 2 3
1 2 3
3
2 3 4
2 3 4

# 输出样例

4
1 4 6 4
1 2 3 4

# 题解：模拟

写一个仿照归并排序的模拟，就可以很容易地合并同类项。具体参考代码：

#include <stdio.h>
int n, m, cnt, a[100010], A[100010], b[100010], B[100010], c[200010], C[200010];
int main()
{
    // freopen("G.in", "r", stdin);
    // freopen("G.out", "w", stdout);
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        cnt = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++ i)
            scanf("%d", &a[i]);
        
        for (int i = 1; i <= n; ++ i)
            scanf("%d", &A[i]);
        scanf("%d", &m);
        for (int i = 1; i <= m; ++ i)
            scanf("%d", &b[i]);
        
        for (int i = 1; i <= m; ++ i)
            scanf("%d", &B[i]);
        
        int i = 1, j = 1;
        while (i <= n && j <= m)
        {
            if (A[i] < B[j])
            {
                c[ ++ cnt] = a[i];
                C[cnt] = A[i];
                ++ i;
            }
            else if (A[i] == B[j])
            {
                if (a[i] + b[j] != 0)
                {
                    c[ ++ cnt] = a[i] + b[j];
                    C[cnt] = A[i];
                }
                ++ i, ++ j;
            }
            else
            {
                c[ ++ cnt] = b[j];
                C[cnt] = B[j];
                ++ j;
            }
        }
        while (i <= n)
        {
            c[ ++ cnt] = a[i];
            C[cnt] = A[i];
            ++ i;
        }
        while (j <= m)
        {
            c[ ++ cnt] = b[j];
            C[cnt] = B[j];
            ++ j;
        }
        printf("%d\n", cnt);
        for (int i = 1; i <= cnt; ++ i)
            printf("%d ", c[i]);
        
        puts("");
        for (int i = 1; i <= cnt; ++ i)
            printf("%d ", C[i]);
        
        puts("");
    }
    return 0;
}