Topcoder SRM 640 Div2 T3 TwoNumberGroupsEasy 题解

文章目录

• Translation
• Examples
• Original
• Analysis
• Code

Topcoder Single Round Match 640 DIv2 T3 TwoNumberGroupsEasy 题解

（TC SRM 从 640 到 616 持续施工～）
（倒着开车，最为致命）（国庆之前怕是完不成了）

Translation

给你两个 Multiset，你可以把这两个 Multiset 里的元素都模某个大于 1 的数 $m$，使得模完之后它们的距离最小。你要输出最小距离。
两个 Multiset 的距离定义为：要使得两个 Multiset 完全相同，需要删去的最少元素数量 $x$。
题目里给出数据的方式是：给你一个不多于 10 个元素的 vector A，然后给你一个和 A 一样大的 vector numA，numA[i] 表示 A[i] 这个元素在第一个 Multiset 中有几个。B 同理。

• A and B will each contain between 1 and 10 elements, inclusive.
• All elements of A will be distinct.
• All elements of B will be distinct.
• The number of elements in numA will be the same as the number of elements in A.
• The number of elements in numB will be the same as the number of elements in B.
• All elements of A and B will be between 1 and 1,000,000,000, inclusive.
• All elements of numA and numB will be between 1 and 100,000, inclusive.
• Time limit (s): 2.000
• Memory limit (MB): 256

数据范围是：$A_i,B_i \leqslant 10^9,numA_i,numB_i \leqslant 10^5$。注意时限是 2s。

Examples

样例零：

{1,2,3,4}
{2,1,1,1}
{5,6,7,8}
{1,1,1,2}

Returns: 2

不难看出，A 是 {1,1,2,3,4} 而 B 是 {5,6,7,8,8}。当 M=2 时，所有数字模 2，则 (A modulo M) = {0,0,1,1,1} ，(B modulo M) = {0,0,0,1,1}，“距离”为 2。这已经是最小距离了。

This input describes the multisets A = {1,1,2,3,4} and B = {5,6,7,8,8}. For M=2, we have (A modulo M) = {0,0,1,1,1} and (B modulo M) = {0,0,0,1,1}. The distance between these two multisets is 2, and that is the best we can get.

样例一：

{5,7}
{1,1}
{12,14}
{1,1}

Returns: 0

A 集合是 {5,7}，而 B 集合是 {12,14}，显然 M=7 时两个集合相同。

The optimal solution is obtained for M = 7.

Original

A multiset is the same thing as a set, with the difference that a multiset can contain multiple copies of the same element. For example, {1,1,1,2,3} is a multiset that contains three 1s, one 2, and one 3.
The distance between two multisets is the smallest total number of elements we need to erase from them in order to make them equal. For example, the distance between {1,1,2,2,3} and {1,2,2,4} is 3. Note that we can compute distance as follows: For each value, we count its occurrences in the first multiset, we count its occurrences in the second multiset, and we write down the difference between those two counts. The distance is then equal to the sum of all values we wrote down.
If S is a multiset, then (S modulo M) is the multiset of all values (x modulo M) where x belongs to S. For example, if S = {11,12,13,21,22} and M = 10, then (S modulo M) = {1,2,3,1,2} = {1,1,2,2,3}.
You have two multisets called A and B. The first multiset is described by the vector s A and numA. For each valid i, the multiset contains numA[i] copies of the value A[i]. The second multiset is described by the vector s B and numB in the same way.
We are now looking for a positive integer M with the following properties: M must be greater than 1, and the distance between (A modulo M) and (B modulo M) must be as small as possible. Compute and return the smallest possible distance.

Analysis

看到这题最暴力的想法就是：暴力枚举 $m$ 从 2 到 MaxNumber，每次都处理出距离，取最小。显然超时。
仔细思考可以发现：其实很多枚举到的 m 是“显然没有用的”，我们理想中的 $m$ 必须使得 A 与 B 中至少一对元素模 $m$ 后相同了。也就是说：

A_i\equiv B_j  \pmod m \iff A_i-B_j \equiv 0 \pmod m

显然 $m$ 是 $A_i-B_j$ 的因子。这告诉我们，只需要暴力枚举 $A_i,B_j$，然后将 $|A_i-B_j|$ 的因子作为 $m$ 暴力尝试，找最优解就可以了。因为我们枚举到的 $m$ 都是“有贡献”的（至少也是做了一点微小的贡献的），没有贡献的我们就都不用枚举了。
小于等于 $10^9$ 的数字的最大因子个数好像是 1000 左右（反正不会超过 2000），所以这样的做法不会超时。

Code

#include <bits/stdc++.h>
using namespace std;
vector<int> vec;
map<int,int> cnt;
map<int,int>::iterator it;
class TwoNumberGroupsEasy {
public:
    int solve( vector <int> A, vector <int> numA, vector <int> B, vector <int> numB );
};
inline int MyAbs(int x){return x>0?x:-x;}
int TwoNumberGroupsEasy::solve(vector <int> A, vector <int> numA, vector <int> B, vector <int> numB) {
    vec.clear();
    for (int i=0;i<A.size();i++)
    for (int j=0;j<B.size();j++){
        int now=MyAbs(A[i]-B[j]);
        for (int k=2;k<=sqrt(now);k++) if (now%k==0){
            vec.push_back(k);
            if (now/k!=now) vec.push_back(now/k);
        }
        vec.push_back(now);
    }
    vec.push_back(1<<30);
    int ret=1<<30;
    for (int i=0;i<vec.size();i++){
        int m=vec[i];
        cnt.clear();
        if (m==0||m==1) continue;
        int now=0;
        for (int j=0;j<A.size();j++) cnt[A[j]%m]+=numA[j];
        for (int j=0;j<B.size();j++) cnt[B[j]%m]-=numB[j];
        for (it=cnt.begin();it!=cnt.end();it++) now+=MyAbs(it->second);
        if (now<ret) ret=now;
    }
    return ret;
}