G. The Morning Star

这篇具有很好参考价值的文章主要介绍了G. The Morning Star。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Problem - G - Codeforces

G. The Morning Star,codeforces,算法G. The Morning Star,codeforces,算法

思路:想了挺长时间的,一直没想到一个简便的方法在瞎搞。我们发现对于某个点来说,其他的点如果能够跟他匹配,那么一定在这8个方向上,而同时这8个方向其实对应这4条直线,假设点为(x1,y1),那么直线为x=x1,y=y1,y=x+y1-x1,y=-x+x1+y1,那么在求能够跟当前点匹配的点时,只需要看一下在这四条直线上的点的数量,假设为a,b,c,d,那么产生的贡献就是a-1+b-1+c-1+d-1,同时我们还需要考虑会不会重复,就是一个点会不会跟一个点匹配两次,因为保证了没有重复点,所以前两条直线是不会重复的,那么后两条直线也是不会重复的,只有当x1=0,y1=0时后两个直线重复,但是在算贡献是一定不会同时添加文章来源地址https://www.toymoban.com/news/detail-701522.html

// Problem: G. The Morning Star
// Contest: Codeforces - Codeforces Round 886 (Div. 4)
// URL: https://codeforces.com/contest/1850/problem/G
// Memory Limit: 256 MB
// Time Limit: 2000 ms

#include<bits/stdc++.h>
#include<sstream>
#include<cassert>
#define fi first
#define se second
#define i128 __int128
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
const double eps=1e-7;
const int N=5e5+7 ,M=5e5+7, INF=0x3f3f3f3f,mod=1e9+7,mod1=998244353;
const long long int llINF=0x3f3f3f3f3f3f3f3f;
inline ll read() {ll x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=(ll)x*10+c-'0';c=getchar();} return x*f;}
inline void write(ll x) {if(x < 0) {putchar('-'); x = -x;}if(x >= 10) write(x / 10);putchar(x % 10 + '0');}
inline void write(ll x,char ch) {write(x);putchar(ch);}
void stin() {freopen("in_put.txt","r",stdin);freopen("my_out_put.txt","w",stdout);}
bool cmp0(int a,int b) {return a>b;}
template<typename T> T gcd(T a,T b) {return b==0?a:gcd(b,a%b);}
template<typename T> T lcm(T a,T b) {return a*b/gcd(a,b);}
void hack() {printf("\n----------------------------------\n");}

int T,hackT;
int n,m,k;
PII w[N];

void solve() {
	n=read();
	
	for(int i=1;i<=n;i++) w[i].fi=read(),w[i].se=read();
	
	ll res=0;
	map<int,int> a,b,c,d;
	for(int i=1;i<=n;i++) {
		a[w[i].fi]++;
		b[w[i].se]++;
		c[w[i].fi+w[i].se]++;
		d[w[i].se-w[i].fi]++;
	}
	
	for(int i=1;i<=n;i++) {
		a[w[i].fi]--;
		b[w[i].se]--;
		c[w[i].fi+w[i].se]--;
		d[w[i].se-w[i].fi]--;
		
		res+=a[w[i].fi]+b[w[i].se]+c[w[i].fi+w[i].se]+d[w[i].se-w[i].fi];
	}
	
	printf("%lld\n",res*2);
}   

int main() {
    // init();
    // stin();
	// ios::sync_with_stdio(false); 

    scanf("%d",&T);
    // T=1; 
    while(T--) hackT++,solve();
    
    return 0;       
}          

到了这里,关于G. The Morning Star的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 每周一算法:A*(A Star)算法

    在 3 × 3 3times 3 3 × 3 的棋盘上,摆有八个棋子,每个棋子上标有 1 1 1 至 8 8 8 的某一数字。棋盘中留有一个空格,空格用 0 0 0 来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为 123804765 12

    2024年03月15日
    浏览(57)
  • C. Salyg1n and the MEX Game Codeforces Round 897 (Div. 2)

    Problem - C - Codeforces 题目大意:有一个所有数互不相同的长度为n的数组n,A先手,可以向数组中假如一个没有的数x,B可以从数组中移除一个x的数,目标是使数组最终的MEX最小,扮演A进行操作,使数组最终的MEX最大 1=n=1e5;最大回合数为n 思路:我们要让当前数组的MEX增大,必

    2024年02月07日
    浏览(33)
  • 混合A*算法---Hybrid A Star

    考虑机器人运动模型下的路径规划中说道,不管是离散控制空间还是状态空间,生成的图形都是Lattice Graph。 但是,加入在离散的过程当中,发现因为当时份数选择的更多,就会导致离散时候彼此连接的很近,所以可以进行剪枝的操作。 那如何进行剪枝?最有效的是使用栅格

    2023年04月14日
    浏览(33)
  • 路径规划A*(A-Star)算法

    A*(A-Star)算法是一种常用的寻路算法,用于图形表达的环境中找到起点到目标点的最短路径。 代价函数𝑓(𝑛)由两部分组成:起点沿着已生成的路径到达当前节点的开销𝑔(𝑛)和当前节点到终点的预估开销ℎ(𝑛)。公式表示: 𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛) A*算法的详细原理

    2024年02月04日
    浏览(25)
  • 快速入门 Codeforces 算法比赛/练习 网站

    Codeforces是一家为计算机编程爱好者提供在线评测系统的俄罗斯网站。同时也是广大ACM编程爱好者所喜爱,被使用的网站之一,但是有很多编程小白刚接触此类算法网站,不太熟悉如何使用,这里博主给出快速入门Codeforces的图文教程。 Codeforces官网: Codeforces 我们刚进入网站会

    2024年02月22日
    浏览(45)
  • 51k+ Star!动画图解、一键运行的数据结构与算法教程!

    大家好,我是 Java陈序员 。 我们都知道,《数据结构与算法》 —— 是程序员的必修课。 无论是使用什么编程语音,亦或者是前后端开发,都需要修好《数据结构与算法》这门课! 在各个互联网大产的面试中,对数据结构和算法的考核乐此不疲。往往《数据结构与算法》学

    2024年02月05日
    浏览(39)
  • 路径优化算法 | 基于A_Star算法实现复杂地形下无人机威胁概率地图最短路径避障三维航迹规划

    A* (A-Star) 算法是一种广泛使用的路径搜索和图形遍历算法,用于在给定起点和终点的情况下找到最短路径。对于无人机在复杂地形下的三维航迹规划,A* 算法可以与其他技术结合,例如威胁概率地图(Threat Probability Map),以实现避障和最短路径规划。 以下是一个基于 A* 算法

    2024年04月08日
    浏览(83)
  • 【多机器人】基于A_Star算法实现多机器人路径规划附Matlab代码

     ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进, 代码获取、论文复现及科研仿真合作可私信。 🍎个人主页:Matlab科研工作室 🍊个人信条:格物致知。 更多Matlab完整代码及仿真定制内容点击👇 智能优化算法       神经网络预测       雷达通信    

    2024年02月04日
    浏览(53)
  • 【路径规】基于A_star算法实现多机器人避障路径规划附Matlab代码

    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进, 代码获取、论文复现及科研仿真合作可私信。 🍎个人主页:Matlab科研工作室 🍊个人信条:格物致知。 更多Matlab完整代码及仿真定制内容点击👇 智能优化算法       神经网络预测       雷达通信    

    2024年02月03日
    浏览(47)
  • 【路径规划】 A_star算法机器人动静态避障路径规划【含Matlab源码 371期】

    获取代码方式1: 完整代码已上传我的资源:【路径规划】基于matlab A_star算法机器人动静态避障路径规划【含Matlab源码 371期】 获取代码方式2: 付费专栏Matlab路径规划(初级版) 备注: 点击上面蓝色字体付费专栏Matlab路径规划(初级版),扫描上面二维码,付费29.9元订阅海

    2024年01月17日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包