問題概述

原題參考：D. Divisible Pairs
給出整數n、x、y和長度為n的數組，要求求出數組中滿足以下關系的數對

• x|ai+aj
• y|ai-aj
• i < j

思路分析

剛開始看到這個題的時候覺得沒思路，坐牢卡半天發現感覺是對的(裂開)。
題解給的是map的做法，看完之后又恍然大悟，實在是妙啊。這個題給我的思路是什么呢，是對于數組中求解數對的特殊關系的總和數這類問題的解法的思路，這種題往往n²的時間復雜度是爆掉的(好吧，說了句廢話，好像很多題n²都要爆)。這個好像總是給人無從下手的感覺，好吧，我真的是很討厭數組里，發現最近寫的數組連續性、數組公式求和...，估計是杠上了，首先是推出給出的公式的作用

x|ai+aj  -->  x%(ai%x + aj%x) == 0
y|ai-aj  -->  ai%y == aj%y

這個不就是映射關系嘛，首先是求出和ai同余y的數，放到一起，然后再在這些數里面找出和ai“互補”的aj，注意還有一個i<j的條件，所以遍歷只能一方進行，也就是說，當前數只能當aj，不能當ai，說起來抽象，但是我在補題的時候想起來一個遠古題目，放在這里互補一下A-B數對，這里就不一樣了，這里的話就沒有限制，所以當前數既可以當A，也可以當B，具體參考代碼

參考代碼

• D. Divisible Pairs

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 2e5+7;
int n, x, y, a[N];
map<int, map<int, int>> w;
void solve() {
	ll ans = 0;
	cin >> n >> x >> y;
	for(int i=1; i<=n; i++) cin >> a[i];
	w.clear();
	for(int i=1; i<=n; i++) {
        //其實這里<j, i>也是可以的，所以假如沒有第三個條件的話，這里是*2
		ans += w[a[i]%y][(x-(a[i]%x))%x];
		w[a[i]%y][a[i]%x] ++;
	}
	cout << ans << endl;
}
int main() {
#ifdef xrl
	freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
	FAST_IO;
	int t = 1;
	cin >> t;
	while(t --) solve();
#ifdef xrl
	cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
	return 0;
}

• A-B數對

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 2e5+7;
map<int, int> w;
int n, a[N], c;
void solve() {
    ll ans = 0;
    cin >> n >> c;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) {
        //這里就是分別求作為b、a的情況
        ans += w[a[i]-c];
        ans += w[a[i]+c];
        w[a[i]] ++;
    }
    cout << ans << endl;
}
int main() {
#ifdef xrl
    freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
    FAST_IO;
    int t = 1;
    //cin >> t;
    while(t --) solve();
#ifdef xrl
    cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
    return 0;
}

做題反思

當數組求解特殊關系的數對數時，尋找他們之間的映射關系，將其放入到map中