【2019浙江省赛 - B】Element Swapping（思维，数学）
题干：
DreamGrid has an integer sequence and he likes it very much. Unfortunately, his naughty roommate BaoBao swapped two elements and () in the sequence when DreamGrid wasn't at home. When DreamGrid comes back, he finds with dismay that his precious sequence has been changed into !
What's worse is that DreamGrid cannot remember his precious sequence. What he only remembers are the two values
Given the sequence after swapping and the two values DreamGrid remembers, please help DreamGrid count the number of possible element pairs BaoBao swaps.
Note that as DreamGrid is poor at memorizing numbers, the value of or might not match the sequence, and no possible element pair can be found in this situation.
Two element pairs () and () are considered different if or .
Input
There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case:
The first line contains three integers , and (), indicating the length of the sequence and the two values DreamGrid remembers.
The second line contains integers (), indicating the sequence after swapping. It's guaranteed that and .
It's guaranteed that the sum of of all test cases will not exceed .
Output
For each test case output one line containing one integer, indicating the number of possible element pairs BaoBao swaps.
Sample Input
2
6 61 237
1 1 4 5 1 4
3 20190429 92409102
1 2 3
Sample Output
2
0
Hint
For the first sample test case, it’s possible that BaoBao swaps the 2nd and the 3rd element, or the 5th and the 6th element.
解题报告：
两数作差不难发现，y的差除以x的差，就是a[i]+a[j]，，所以分情况讨论就行了。注意除数为0的情况和x相同y不相同的时候（好坑啊、、）
（%%%wjh大佬）
AC代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
//ll f[1000];
ll a[200000],b[200000];
map<ll,ll> mp;
map<ll,ll> ::iterator it;
int main()
{
int t;
cin>>t;
while(t--)
{
mp.clear();
ll n,x,y;
scanf("%lld%lld%lld",&n,&x,&y);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
mp[a[i]]++;
b[i]=a[i]*a[i];
}
ll x2=0,y2=0;
for(ll i=1;i<=n;i++)
{
x2+=a[i]*i;
y2+=b[i]*i;
}
if(x==x2)
{
if(y!=y2)
{
puts("0");
continue;
}
ll ans=0;
for(it=mp.begin();it!=mp.end();it++)
{
ll num=it->second;
ans+=num*(num-1)/2;
}
printf("%lld\n",ans);
continue;
}
ll ans=0;
if(abs(y-y2)%abs(x-x2)!=0)
{
puts("0");
continue;
}
ll tmp=(y-y2)/(x-x2);
ll dx=x-x2;
ll dy=y-y2;
for(int i=1;i<=n;i++)
{
ll aj=tmp-a[i];
ll dt=a[i]-aj;
ll dij;
if(dt==0)
{
continue;
}
if(abs(dx)%abs(dt)!=0)
continue;
dij=dx/dt;
ll wj=i+dij;
if(wj<=i) continue;
if(aj==a[wj]&&(x==(x2+wj*a[i]+i*a[wj]-i*a[i]-wj*a[wj]))&&(y==(y2-i*b[i]-wj*b[wj]+wj*b[i]+i*b[wj])))
ans++;
else
continue;
}
printf("%lld\n",ans);
}
return 0;
}
/*
8
6 61 237
1 1 4 5 1 4
3 20190429 92409102
1 2 3
*/
Momenta公司福利 594人发布