题目大意:给定一个多项式各校的系数和次幂,输出化简后的非零项数目。

排序,将次幂相同的排在一起;合并同类型,次幂相同累加系数,非零则统计。

(次幂非常大,不能用桶排序;需要哈希或者使用map;排序去重统计更方便。)

#include <bits/stdc++.h>
using namespace std;
int n, m, t, i, j, k, ans;
struct AB{
    int a, b;
    bool operator < (const AB &A) const{
        return a < A.a;
    }
} d[100005];
int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(i=1; i<=n; i++){
            scanf("%d%d", &d[i].a, &d[i].b);
        }
        sort(d+1, d+n+1);
        ans = m = 0, d[++n].a = 2e9;
        for(i=1; i<=n; i++){
            if(d[i].a != d[i-1].a){
                if(m) ans++;
                m = d[i].b;
            }
            else m += d[i].b;
        }
        printf("%d\n", ans);
    }
    return 0;
}