http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4101
题意:数组a通过交换一对数字,得到了b数组,给出x=和y=和b数组,问有多少对l,r(l<=r)能满足条件
C++版本一
题解:规律+数学
1、;
2、;
3、,则;
4、,则不合法数据;
5、,,则不合法数据;
6、,,对于某一个位置i,可以推出应该交换的位置,其中,不一定在范围内,不一定在范围内;
7、对于每个再完成上述操作后,放进vector;
8、可以查询vector是否操作 ,当然直接询问;
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r;
ll x,y;
ll ans,cnt,flag,temp,X,Y;
ll b[N];
vector<int>v[M];
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
scanf("%d",&t);
while(t--){
scanf("%d%lld%lld",&n,&x,&y);
X=Y=0;
for(int i=1;i<=100000;i++)
v[i].clear();
for(int i=1;i<=n;i++){
scanf("%lld",&b[i]);
X+=i*b[i];
Y+=i*b[i]*b[i];
}
//cout<<X<<" "<<Y<<endl;
ll needx=x-X,needy=y-Y;
ans=0;
if(needx==0&&needy==0){//needx==0&&needy==0时,任意两个相同的元素都可以交换
for(int i=1;i<=n;i++){
ans+=v[b[i]].size();
v[b[i]].push_back(i);
}
}else if(needx==0){
ans=0;
}else if(needy%needx==0){//needx和needy必须倍数关系
//cout<<needx<<" "<<needy<<endl;
ll need=needy/needx;
//cout<<need<<endl;
for(int i=1;i<=n;i++){
if(need-2*b[i]&&1<=need-b[i]&&need-b[i]<=100000){
int j=i-needx/(need-2*b[i]);
vector<int>::iterator it=lower_bound(v[need-b[i]].begin(),v[need-b[i]].end(),j);
//cout<<need-b[i]<<" "<<i-needx/(need-2*b[i])<<endl;
if(it!=v[need-b[i]].end()&&*it==j){//it不能是end(),不然会段错误
ans++;
}
}
v[b[i]].push_back(i);
}
}
cout<<ans<<endl;
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
题解:
#include<bits/stdc++.h>
#define ll long long
#define Map map<ll,ll>::iterator
#define MAXN 100005
#define se second
using namespace std;
map<ll,ll>cnt;
ll X1,Y1,X2,Y2,a[MAXN];
int T,n;
int main(){
cin>>T;
while(T--){
cnt.clear();
scanf("%d%lld%lld",&n,&X1,&Y1);
X2=Y2=0;
for(ll i=1;i<=n;i++){
scanf("%lld",&a[i]);
cnt[a[i]]++;
X2+=a[i]*i;Y2+=a[i]*a[i]*i;
}
ll dx=X2-X1,dy=Y2-Y1;
if(dx==0){
if(dy!=0){
puts("0");continue;
}
ll ans=0;
for(Map it=cnt.begin();it!=cnt.end();it++){
ans+=((it->se)-1)*(it->se)/2;
}
printf("%lld\n",ans);
continue;
}
if(dy%dx){
puts("0");continue;
}
//cout<<dx<<" "<<dy<<endl;
ll dt=dy/dx,ans=0;
//cout<<dt<<endl;
for(ll i=1;i<=n;i++){
ll Aj=dt-a[i];
if((Aj-a[i])==0)continue;
ll j=(dx+(Aj-a[i])*i)/(Aj-a[i]);
if(j<=i||j>n)continue;
if(a[j]==Aj)ans++;
}
printf("%lld\n",ans);
}
}