当前位置: 首页 > news >正文

G. The Morning Star

Problem - G - 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时后两个直线重复,但是在算贡献是一定不会同时添加

// 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

Problem - G - Codeforces 思路&#xff1a;想了挺长时间的&#xff0c;一直没想到一个简便的方法在瞎搞。我们发现对于某个点来说&#xff0c;其他的点如果能够跟他匹配&#xff0c;那么一定在这8个方向上&#xff0c;而同时这8个方向其实对应这4条直线&#xff0c;假设点为(x…...

电池的健康状态 SOH 估计

电池的健康状态 SOH 估计 SOH&#xff08;State of Health&#xff09;估计通常用于描述电池的健康状态&#xff0c;即电池当前容量与初始容量的比值。 一种常见的SOH估计方法是基于经验的电池寿命预测方法&#xff0c;包括循环周期数法、安时法与加权安时法、面向事件的老化…...

Web 安全之 Permissions Policy(权限策略)详解

什么是 Permissions Policy&#xff08;权限策略&#xff09;&#xff1f; Permissions Policy 为 web 开发人员提供了明确声明哪些功能可以在网站上使用&#xff0c;哪些功能不能在网站上使用的机制。可以设置一组策略&#xff0c;用于限制站点代码可以访问的 API 或者修改浏…...

【黄啊码】nginx如何设置php运行的

禁止访问 PHP 脚本可以通过 Nginx 服务器配置中的多种方式来实现。以下是其中的一些常见方法&#xff0c;您可以根据实际需求选择合适的方式&#xff1a; 1 禁用 PHP 解析&#xff1a; 在 Nginx 配置中&#xff0c;确保 PHP 脚本无法被解析&#xff0c;从而禁止 PHP 执行。 lo…...

无涯教程-JavaScript - ISPMT函数

描述 ISPMT函数计算在特定投资期间支付的利息。提供此功能是为了与Lotus 1-2-3兼容。 语法 ISPMT (rate, per, nper, pv)争论 Argument描述Required/OptionalRateThe interest rate for the investment.RequiredPerThe period for which you want to find the interest, an…...

LeetCode 面试题 03.05. 栈排序

文章目录 一、题目二、C# 题解 一、题目 栈排序。 编写程序&#xff0c;对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据&#xff0c;但不得将元素复制到别的数据结构&#xff08;如数组&#xff09;中。该栈支持如下操作&#xff1a;push、pop、peek 和…...

构建微服务项目时启动网关服务失败的解决方案

启动网关服务时报“Unable to create the temporary folder: C:\WINDOWS\TEMP\/nio-file-upload”错误。 代码与之前没有任何变化&#xff0c;但就是启动不了&#xff0c;观察错误意思大概是不能创建临时文件夹&#xff1a;C盘下的WINDOWS下的TEMP目录下的nio-file-upload这个东…...

零基础教程:使用yolov8训练无人机VisDrone数据集

1.准备数据集 1.先给出VisDrone2019数据集的下载地址&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1e2Q0NgNT-H-Acb2H0Cx8sg 提取码&#xff1a;31dl 2.将数据集VisDrone放在datasets目录下面 2.数据集转换程序 1.在根目录下面新建一个.py文件&#xff0c;取名叫…...

【Mysql专题】使用Mysql做排行榜,线上实例

背景 我们这里有个需求&#xff0c;对存量用户的余额做排行处理&#xff0c;这个实现方式很多&#xff0c;这边介绍的是&#xff0c;通过Mysql直接实现&#xff0c;将排名也直接返回出来。 我知道大家在网上能找到一大把这种实例&#xff0c;我在这里可不是【重复造轮子】。我…...

matlab数据处理: cell table array+datetime

原数据文件.csv matlab xlsread(filename{i},B2:T2881) 会同于Excel最多1048576行 舍弃 a{1,i} xlsread(filename{i},‘B2:T2881’);%读取excel文件,选定区域’B2:G2881’ readcell(filename{i},Range,E2:M2881) 会全部读取 优选 对于日期 yyyy-MM-dd HH:mm:ss.000 matlab cel…...

如何应用运营商大数据精准营销?

如何应用运营商大数据精准营销&#xff1f; 越来越多的企业逐渐觉察到运营商大数据所带来的商业价值&#xff0c;精准营销也被他们用的越来越娴熟。那么&#xff0c;企业的大数据精准营销该如何应用呢&#xff1f;想必是很多资源有限的中小型公司最想了解的。 一 数据驱动运营…...

AJAX学习笔记5同步与异步理解

AJAX学习笔记4解决乱码问题_biubiubiu0706的博客-CSDN博客 示例 前端代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>演示AJAX同步和异步</title> </head> <body> <script…...

911面试

WebPack分包 webpack分包 ts泛型 ts泛型 优化if-else和switch 优化if-else 左侧固定&#xff0c;右侧自适应 左侧固定&#xff0c;右侧自适应...

【Java基础篇 | 面向对象】—— 继承

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【JavaSE_primary】 本专栏旨在分享学习JavaSE的一点学习心得&#xff0c;欢迎大家在评论区讨论&#x1f48c; 继承允许一个类继承另一个…...

DELL precision上安装nvidia A4000驱动 cuda cudnn

一、安装驱动 参考这篇文章进行安装Ubuntu安装Nvidia显卡驱动_Kevin__47的博客-CSDN博客 【出现问题】 禁用nouveau后出现黑屏&#xff0c;有几行代码&#xff0c;断线一直在闪 【解决方法】 1、参考这篇文章Ubuntu20.04安装nvidia显卡驱动并解决重启后黑屏问题_ubuntu安装…...

数据结构算法刷题(29)动态规划

思路一&#xff1a;回溯&#xff1a;按照选和不选的判断方式&#xff0c;使用回溯来解决这个问题。 class Solution: def rob(self, nums: List[int]) -> int: n len(nums) #数组的长度 def dfs(i): if i<0: #到达边界条件后 return 0 #返回最大金额是0 res max(dfs(i…...

W11下CMake MinGW配置OpenCV和Qt

&#x1f482; 个人主页:风间琉璃&#x1f91f; 版权: 本文由【风间琉璃】原创、在CSDN首发、需要转载请联系博主&#x1f4ac; 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦 前言 前几天将cuda版本的opencv给编译成功了&#xff0c;当时用的VS的MSVC&…...

反转字符串 反转字符串 || 反转字符串 |||

思想总结&#xff1a;首先将字符串转变为字符数组&#xff0c;再进行遍历并反转字符。 1.反转字符串 代码&#xff1a; class Solution {public void reverseString(char[] s) {reverse(s,0,s.length); //左闭右开}public static void reverse(char[] ch,int i,int j) { 翻转函…...

XML解析 不允许有匹配 _[xX][mM][lL]_ 的处理指令目标

以上错误是在解析xml参数时候报出的。 我这里错误的原因在于&#xff0c;<?xml version\"1.0\" encoding\"UTF-8\"?>少了个空格&#xff0c;参考下图&#xff1a; 下面一行才是对的。...

【C++进阶(五)】STL大法--list模拟实现以及list和vector的对比

&#x1f493;博主CSDN主页:杭电码农-NEO&#x1f493;   ⏩专栏分类:C从入门到精通⏪   &#x1f69a;代码仓库:NEO的学习日记&#x1f69a;   &#x1f339;关注我&#x1faf5;带你学习C   &#x1f51d;&#x1f51d; list模拟实现 1. 前言2. list类的大致框架与结构…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...