题目1

题目链接
题目大意：
给出n个整数的数组a，数组的元素可能是1或者2；
现在想要找到一个最小的位置k满足：
𝑎1⋅𝑎2⋅…⋅𝑎𝑘=𝑎𝑘+1⋅𝑎𝑘+2⋅…⋅𝑎𝑛

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100)
每个样例2行，第一行整数𝑛 (2≤𝑛≤1000）
第二行n个整数，𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤2).

输出：
每个样例一行，输出最小的位置k；如果不存在k，则输出-1；

Examples
input
3
6
2 2 1 2 1 2
3
1 2 1
4
1 1 1 1

output
2
-1
1

题目解析：
由于题目数字取值范围只有1和2，1不影响乘积，那么只需要考虑2；
如果数组中有偶数个整数，那么题目有解；
注意如果是0个数字2，那么答案是1；

class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            vector<int> pos;
            for (int i = 1; i <= n; ++i) {
                int tmp;
                cin >> tmp;
                if (tmp == 2) pos.push_back(i);
            }
            int ans = 1;
            if (pos.size() % 2) ans = -1;
            else if (pos.size() > 0) ans = pos[pos.size() / 2 - 1];
            
            cout << ans << endl;
        }
    }
}

题目2

题目链接
题目大意：
给出一个整数n，将整数n拆成两个整数A和B，要求满足：
A+B=n；
A和B的数字和最多相差1；

数字和的意思就是将整数A的各个位置数字相加，比如说198就是1+9+8=18，208就是2+0+8=10；

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例1行，第一行整数𝑛 (2≤𝑛≤1e9）

输出：
每个样例一行，输出A和B，题目保证结果存在；

Examples
input
5
1
161
67
1206
19
output
1 0
67 94
60 7
1138 68
14 5

题目解析：
当n是偶数的时候，A=B=n/2，必然满足要求；
当n是奇数时，我们可以令A=n/2, B=n - n/2，这样有A和B必然满足A+B=n情况，接下来讨论AB数字和相差1的的情况：
1、当A的个位数小于9时，A和B必然数字和只差1，比如说81和82，78和79；
2、当A的个位数等于9时，由于B会进位，最终A和B的数字和会产生一个差值，比如说9和10，39和40，99和100；
由此我们可以产生一个朴素的做法：令A--，B++，最终肯定能够找到符合要求的数字；

但是这么做的话，会出现超时（TLE）的情况，我们来分析下复杂度。
当数字为999和1000时，数字和相差(9+9+9) - 1 = 26的情况，那么要A的数字和-13，B的数字和+13；
我们知道获得数字和13最快的情况是十位数4+个位数9，那么结果为A=999-49=950，B=1000+49=1049；
如果采用枚举的复杂度，需要枚举49次；

最坏的情况，数字n为199999999，A=99999999，B=100000000，A和B的数字和相差(9 * 8) - 1=71，也就是说A需要减去数字和35，B需要加上数字和36；
最终数字A为 99999999 - 8999 = 99991000，数字和是72-35=37；
最终数字B为100000000 + 8999 = 1000089999，数字和是1+36=37；
枚举的复杂度是10000左右，加上每次计算数字和的复杂度 和 样例数量，最终复杂度为10000 * 10 * 10000 = 1e9，复杂度偏高；

优化方式1：每次在计算A--和B++的时候，直接按照数字和一半进行操作，比如说数字和一半是37，那么A-=37，B+=37，这样效率能加快一些；因为最终数字和会逐步收敛，结果保证是正确的；

优化方式2：直接按照数字和之差，从个位数开始往高位填9，直到数字和小于9，则在当前位数填下剩余数字，比如说37就得到8999，13就得到49；这样可以O(1)得到最优解。

class Solution {
    static const int N = 201010;
    int digSum(int x) {
        int ret = 0;
        while (x) {
            ret += x % 10;
            x /= 10;
        }
        return ret;
    }
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            int x = n / 2, y = n - x;
            while (abs(digSum(x) - digSum(y)) > 1) {
                int dif = abs(digSum(x) - digSum(y)) / 2;
                x -= dif;
                y += dif;
            }
            cout << x << " " << y << endl;
        }
    }
}

题目3

题目链接
题目大意：
给出n个整数的数组，从数组中选择两个数字a[i]和a[j]，要求满足：
i和j不相同；
| a[i] - a[j] |的值，等于数组中最大值与最小值的差；
问，最多能选出多少个组合。

输入：
第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤100)
每个样例2行，第一行整数 𝑛 (2≤𝑛≤1e5)
第二行整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e5)

输出：
每个样例一行，输出满足要求的组合数。

Examples
input
2
5
6 2 3 8 1
6
7 2 8 3 2 10
output
2
4

样例解释：
样例1，满足要求的有[1, 8]和[8, 1]；
样例1，满足要求的有[2, 10]和[10, 2]，其中2可以为第2个数字、第5个数字；

题目解析：
因为选出来的数字要满足差的绝对值最大，那么必然是最大值和最小值的组合。
假设最小值x，最大值y，首先看x和y是否相同。
如果x==y，则看x的总数，答案就是A(n, 2)，即是从n个整数中选择2个数字的组合排列数；
如果x!=y，那么结果就是x的数量与y的数量的乘积。

trick：
两个情况都可能超int32。

class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            for (int i = 0; i < n; ++i) {
                cin >> a[i];
            }
            sort(a, a + n);
            if (a[0] == a[n - 1]) cout << n * 1LL * (n - 1) << endl;
            else {
                int x = 0, y = 0;
                while (a[x] == a[0]) {
                    ++x;
                }
                while (a[n - 1 - y] == a[n - 1]) {
                    ++y;
                }
                cout << x * 1LL * y * 2 << endl;
            }
        }
    }
}

题目4

题目链接
题目大意：
给出1到n的n个整数的数组，现在需要从数组里面选择新的数组，但是已知有m对整数是不能共存：
比如说整数2和4不能共存，则新的数组里面不能同时存在2和4，比如说整数数组[1,2,3,4,5]，其中[2,3]和[3,4]都是合法的，[2,3,4]是不合法的；
现在想知道，能选出多少个子数组，里面不存在不合法的整数对。

输入：
第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤2⋅1e4),
每个样例第一行整数 𝑛 and 𝑚 (2≤𝑛≤1e5, 0≤𝑚≤1e5)
接下来m行整数 𝑥𝑖 and 𝑦𝑖 (1≤𝑥𝑖,𝑦𝑖≤𝑛, 𝑥𝑖≠𝑦𝑖)，表示两个不能相互相处的整数。

输出：
每个样例一行，输出满足要求的组合数。

Examples
input
2
3 2
1 3
2 3
4 2
1 2
2 3
output
4
5
样例解释：
样例1，满足要求的有整数[1],[2],[3],[1,2]；
样例2，满足要求的有整数[1],[2],[3],[4],[3,4]；

题目解析：
对于子数组[x, y]，我们可以枚举做区间x，再考虑y的取值；
首先y要满足x <= y，考虑所有y的取值，只要包括一个不能相处整数对，那么后续的整数就不用考虑，比如说样例2：
x=1，我们考虑y=1,2,3,4的情况，当我们发现整数1和2是不能相处的，那么2以及2后面的整数就不用考虑；
也即是说，我们只需要向右遍历到第一个出现的最小不能相处整数对的右区间y，[x, x]到[x, y-1]的区间都是合法的；

现在的问题变成了，对于选定整数x，如何快速得到右边区间最小的整数对；
假设我们把所有不合法整数对都按照左区间归类，然后从右到左遍历整数数组。
比如说遍历到整数i，那么对于所有做左区间≥i的整数对，都是在i的右边；

class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        int tmp = 0;
        while (t--) {
            ++tmp;
            int n, m;
            map<int, vector<int> > mp;
            cin >> n >> m;
            while (m--) {
                int x, y;
                cin >> x >> y;
                if (x < y) {
                    mp[x].push_back(y);
                }
                else {
                    mp[y].push_back(x);
                }
            }
            lld sum = 0;
            int leftMin = n + 1;
            for (int i = n; i > 0; --i) {
                if (mp[i].size()) {
                    sort(mp[i].begin(), mp[i].end());
                    leftMin = min(leftMin, mp[i][0]);
                }
                sum += leftMin - i;
            }
            cout << sum << endl;
        }
    }
}

题目5

题目链接
题目大意：
给出n个整数，询问是否存在两个整数，最大公约数不是1；
如果存在则输出YES，如果不存在则输出NO；

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1e5)；
每个样例第一行整数 𝑛 (2≤𝑛≤1e5).
接下来n个整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9).

输出：
每个样例一行，输出是否满足要求。

Examples
input
2
3
32 48 7
3
14 5 9
output
YES
NO

题目解析：
先不考虑复杂度，最直接的做法，就是求出每个整数的因子，复杂度是O(M)，M是整数的大小的根，10^9需要遍历1w+次；
然后用map管理每个整数的因子，遍历每一个整数求是否有相同的因子，整体复杂度在O(NM)左右，map的复杂度可以暂时忽略；
总的复杂度会到达10^5 * 10^5 = 10^10量级，时间上是不允许的。

分析这个里面的优化空间，每个整数的因子最终都可以拆分为若干素数，这样就可以大幅度减少因子数量；
先预处理1-sqrt(10^9)的素数，再用这个素数去筛选n个整数，这样速度会更加快。

trick：这个如果遇到两个相同数字，就会出现异常。
另外在拆解的时候，一定要拆解数字到x = a * b * c这样的形式。

class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int m = sqrt(1e9) + 1;
        vector<int> vec;
        
        for (int i = 2; i<= sqrt(m); ++i) {
            if (!a[i]) {
                int tmp = i;
                while (tmp <= m) {
                    tmp += i;
                    a[tmp] = 1;
                }
            }
        }
        for (int i = 2; i <= m; ++i) {
            if (!a[i]) {
                vec.push_back(i);
//                cout << i << " ";
            }
        }
        
        int t;
        cin >> t;
        while (t--) {
            int n;
            map<int, int> mp;
            cin >> n;
            bool ok = 0;
            for (int i = 0; i < n; ++i) {
                int k;
                cin >> k;
                vector<int> tmp;
                for (int j = 0; j < vec.size(); ++j) {
                    if (k % vec[j] == 0) {
                        tmp.push_back(vec[j]);
                        while (k % vec[j] == 0) k /= vec[j];
                    }
                }
                if (k != 1) {
                    tmp.push_back(k);
                }
                
                for (int j = 0; j < tmp.size(); ++j) {
                    if (mp[tmp[j]]) ok = 1;
                    mp[tmp[j]] = 1;
                }
            }
            cout << (ok ? "YES" : "NO") << endl;
        }
    }
}