3 条题解
-
1
根据题意很容易想到用函数的方式来解决。
共分为 种情况:
- 东北西南方向:
- 东南西北方向:
- 东西方向:
- 南北
绿豆方向:
于是就可以获得一份极品代码:
#include<bits/stdc++.h> #define int long long using namespace std; constexpr int N=110,INF=11111; int n,ans; map<pair<int,int>,int>mp; signed main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int T; cin>>T; while(T--){ ans=0; mp.clear(); cin>>n; for(int i=1;i<=n;i++){ int x,y; cin>>x>>y; ans+=mp[{1,y-x}]++*2;//y=x+b ans+=mp[{-1,y+x}]++*2;//y=-x+b ans+=mp[{0,y}]++*2;//y=b ans+=mp[{INF,-x*INF}]++*2;//y=∞x+b } cout<<ans<<"\n"; } } -
0
题解构造巧妙,我来解释一下
题意

是很好理解的,有一个指南针和一颗星星,再给你 n 个点,每次可以放两个点,一个在中心,一个在八个方向的任意一个方向。求有多少种放置方法。
第一步
首先把所有相互满足条件的点的个数求出来,题目中有8种情况,但是我们可以把它化成4种情况,因为如果有两个点满足条件,那就会产生两个相反方向的答案,所以可以把8个方向看成4条直线
第二步
回到图中,顺着第一步的思路,就是说N&S两个方向为一条直线,同理,W&E,NW&SE,NE&SW就是另外三条直线
这时,如果我们将每一个点看成原点,那别的点想要满足条件就有四种情况:
1: 与这个点的坐标相同,就是在N&S这条直线上
2: 与这个点的坐标相同,就是在W&E这条直线上
3: 与这个点形成的直线斜率为,就是在NW&SE这条直线上,此时它们的的值是一样的
4: 与这个点形成的直线斜率为,就是在NE&SW这条直线上,此时它们的值是一样的
第三步
我们就可以开四个映射表,代表四条直线映射四种情况,设映射表中有个数,那就是这个映射表的总情况数,最后四个答案加起来即可
构造十分巧妙,仔细理解,回味无穷......
#include<bits/stdc++.h> using namespace std; #define ll long long int main() { ll t,n;scanf("%lld",&t); while(t--) { ll ans=0;map<ll,ll>up,down,xie1,xie2; scanf("%lld",&n); for(ll i=1,x,y;i<=n;i++) { scanf("%lld%lld",&x,&y); up[x]++;down[y]++;xie1[x+y]++;xie2[x-y]++; } for(auto i:up)ans+=i.second*(i.second-1); for(auto i:down)ans+=i.second*(i.second-1); for(auto i:xie1)ans+=i.second*(i.second-1); for(auto i:xie2)ans+=i.second*(i.second-1); printf("%lld\n",ans); } return 0; } -
0
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=2e5+10; int main(){ int T; scanf("%d", &T); while(T--){ int n; LL ans=0; scanf("%d", &n); map<int, int> up, down, x1, x2; for(int i=1, x, y; i<=n; i++){ scanf("%d%d", &x, &y); up[x]++; down[y]++; x1[x+y]++; x2[x-y]++; } for(auto i: up) ans+=(LL)i.second*(i.second-1); for(auto i: down) ans+=(LL)i.second*(i.second-1); for(auto i: x1) ans+=(LL)i.second*(i.second-1); for(auto i: x2) ans+=(LL)i.second*(i.second-1); printf("%lld\n", ans); } return 0; }
- 1
信息
- ID
- 40
- 时间
- 2000ms
- 内存
- 128MiB
- 难度
- 4
- 标签
- 递交数
- 160
- 已通过
- 70
- 上传者