目录
问题概述
原题参考:D. Divisible Pairs
给出整数n、x、y和长度为n的数组,要求求出数组中满足以下关系的数对
- x|ai+aj
- y|ai-aj
- i < j
思路分析
刚开始看到这个题的时候觉得没思路,坐牢卡半天发现感觉是对的(裂开)。
题解给的是map的做法,看完之后又恍然大悟,实在是妙啊。这个题给我的思路是什么呢,是对于数组中求解数对的特殊关系的总和数
这类问题的解法的思路,这种题往往n2的时间复杂度是爆掉的(好吧,说了句废话,好像很多题n2都要爆)。这个好像总是给人无从下手的感觉,好吧,我真的是很讨厌数组里,发现最近写的数组连续性、数组公式求和...,估计是杠上了,首先是推出给出的公式的作用
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中
标签:Pairs,const,Divisible,ll,cf,long,int,数组,define From: https://www.cnblogs.com/notalking569/p/18015787