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

Gym - 101986B Parallel Lines dfs暴力

链接:点击查看

题意:偶数个点,两点可连成一条线,求平行线最大对数

题解:当时想的时候傻逼了,想成了每次选两个点就是16*15/2  *  14*13/2 .....

其实不需要这样,因为每个点必须要匹配一个的,所以每次搜索,给一个点找其他点即可,复杂度15*13*11.....

斜率用mp记录一下即可  斜率为0 和 不存在的特殊标记

#include<bits/stdc++.h>
using namespace std;
map< int, map<int, int> > mp;
struct node{int x,y;
}a[20];
int n, vis[20];
int ans;
void dfs(int pos, int step, int sum)
{if(step==n/2+1){ans=max(ans, sum);return;}if(vis[pos]) dfs(pos+1, step, sum);else{vis[pos]=1;for(int i=pos+1;i<=n;i++){if(vis[i]) continue;vis[i]=1;int kx,ky;if(a[i].y==a[pos].y)kx=ky=0;else if(a[i].x==a[pos].x)kx=ky=100000;else{ky=a[i].y-a[pos].y;kx=a[i].x-a[pos].x;int d=__gcd(abs(kx),abs(ky));kx/=d;ky/=d;if(kx<0) kx=-kx,ky=-ky;}mp[kx][ky]++;dfs(pos+1, step+1, sum+mp[kx][ky]-1);mp[kx][ky]--;vis[i]=0;}vis[pos]=0;}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);dfs(1, 1, 0);printf("%d\n",ans);return 0;
}

 

相关文章:

划分树 K-th Number POJ - 2104

划分树&#xff0c;类似线段树&#xff0c;主要用于求解某个区间的第k 大元素&#xff08;时间复杂度log(n)&#xff09; 讲解&#xff1a;https://www.cnblogs.com/hchlqlz-oj-mrj/p/5744308.html 大致就是分治递归的思想&#xff1a; int tree[22][N]; //对应每层每个位置…...

POJ - 4044 Score Sequence 模拟+贪心

题目链接&#xff1a;点击查看 题意&#xff1a;给出两个班级的成绩&#xff0c;先按降序排序&#xff0c;去重。然后求连续的最长公共子序列。输出时&#xff0c;先输出最长公共子序列&#xff0c;然后按个位数字递增的顺序输出&#xff0c;若各位数字一样就按成绩递增。 题…...

JSON相关知识点

JSON是工作中经常会遇到的一种数据结构&#xff0c;下面来讲讲与他相关的一些知识点。 JSON简介&#xff1a; JSON: JavaScript Object Notation(JavaScript 对象表示法) JSON 是存储和交换文本信息的语法,类似 XML。 JSON 比 XML 更小、更快&#xff0c;更易解析。 JSONObj…...

TestNG使用总结

TestNG简介&#xff1a; TestNG是一个测试框架&#xff0c;其灵感来自JUnit和NUnit&#xff0c;但同时引入了一些新的功能&#xff0c;使其功能更强大&#xff0c;使用更方便。 TestNG相较于Junit的优点&#xff1a; 可指定执行顺序&#xff0c; dependsOnMethods 属性来应对…...

idea常用技巧收集

idea相比eclipse的优点我在这里就不赘述了&#xff0c;更多参考&#xff1a;idea官网,本文重点讲下自己在idea使用过程中常用的一些技巧&#xff0c;以后随时更新…… 主要分成三大块&#xff1a; 1. 系统设置 2. 快捷键 3. 其他设置 系统设置 主题风格设置&#xff1a;默…...

初识spring RestTemplate

《spring实战》读书笔记之初识spring RestTemplate。首先需要先了解下什么是REST。 REST&#xff1a;官方解释&#xff0c;表述性状态转移。 感觉还是不知所云&#xff0c;参考下怎样用通俗的语言解释REST&#xff0c;以及RESTful&#xff1f; 即URL定位资源&#xff0c;用H…...

ZOJ - 2112 Dynamic Rankings 动态主席树 主席树+树状数组

题目链接&#xff1a;https://vjudge.net/problem/ZOJ-2112 题意&#xff1a;能修改的查询第k大 学习博客&#xff1a;https://blog.csdn.net/WilliamSun0122/article/details/77885781 理解&#xff1a;修改pos位置x - >y的话&#xff0c;影响的是【pos&#xff0c;n】&…...

Gym - 101889I Imperial roads 树链剖分+最小生成树之必选一边

题目链接&#xff1a;https://vjudge.net/problem/Gym-101889I 题意&#xff1a;n个点&#xff0c;m条边&#xff0c;q次询问&#xff0c;每次必须选一边&#xff0c;求最小生成树的权值 题解&#xff1a;我们先跑一边最小生成树&#xff0c;然后按照最小边建树&#xff0c;必…...

CodeForces - 545D Queue 贪心 排序

题目链接&#xff1a;点击查看 Little girl Susie went shopping with her mom and she wondered how to improve service quality. There are n people in the queue. For each person we know time ti needed to serve him. A person will be disappointed if the time he …...

牛客网 Applese 走方格

题目链接&#xff1a;点击查看 题解&#xff1a;我们容易发现到当n,m都为奇数时&#xff0c;是回不到原点的&#xff0c;因为你无论哪个方向走一去一回就是两步&#xff0c;所以n和m必然有一个偶数&#xff0c;那至于我们怎么走呢&#xff0c;看下图&#xff0c;注意的是n1,m2…...

POJ - 2406 Power Strings next数组应用循环节

题目链接&#xff1a;点击查看 Language:Default Power Strings Time Limit: 3000MS Memory Limit: 65536KTotal Submissions: 61784 Accepted: 25534Description Given two strings a and b we define a*b to be their concatenation. For example, if a "abc" and…...

接口测试那些事儿

什么是接口&#xff1f; 首先&#xff0c;在讲接口测试之前&#xff0c;我们先要搞清楚接口类型的概念。 接口&#xff1a;可能是系统与系统&#xff08;包括服务与服务&#xff09;之间的调用&#xff0c;像A系统&#xff08;服务&#xff09;给B系统&#xff08;服务&#x…...

mysql重置Root密码

方法一: 在my.ini的[mysqld]字段加入&#xff1a; skip-grant-tables 重启mysql服务&#xff0c;这时的mysql不需要密码即可登录数据库 然后进入mysql mysql>use mysql; mysql>更新 user set passwordpassword(新密码) WHERE Userroot; mysql>flush privileges; 运…...

每天一个adb命令:wm命令详解

wm命令可以用于获取屏幕分辨率、像素密度等。 前提&#xff1a;Android4.3及以上 usage: wm [subcommand] [options]wm size [reset|WxH]wm density [reset|DENSITY]wm overscan [reset|LEFT,TOP,RIGHT,BOTTOM]wm size: return or override display size.wm density: overrid…...

idea插件开发入门

前言&#xff1a;最近想研究一款自动在idea中定位缺陷及发送JIRA的快捷工具&#xff0c;方便提升报自动化脚本的bug的效率。因为idea插件学习是必不可少了&#xff0c;沉淀小结如下。 idea插件开发入门插件用途工程创建配置文件Action实现开发语法常用对象常用方法运行效果打包…...

2017 ICPC Asia Urumqi I. A Possible Tree 带权并查集

题目链接&#xff1a;https://nanti.jisuanke.com/t/40520 题解&#xff1a;因为他们都是联通的且只有唯一路径&#xff0c;所以不用管之前怎么连的&#xff0c;直接按照他给的查询&#xff0c;带权并查集判断即可 #include <bits/stdc.h> using namespace std; const …...

基于数据驱动的接口自动化测试解决方案

总结一下我么项目中使用的基于数据驱动的接口自动化测试解决方案&#xff0c;仅供大家参考。1.接口框架设计结构 2.接口测试脚本设计原则 3.持续集成 这块用jenkins就可以了&#xff0c;就不介绍了&#xff0c;目前我们项目的集成规则介绍一下&#xff1a; 1.脚本job与应用对…...

C++设计模式

管理变化&#xff0c; 提高复用 两种手段&#xff1a;分解 抽象 八大原则&#xff1a;https://blog.csdn.net/mmk27_word/article/details/108521903 重构技法&#xff1a; 静态 -> 动态 早绑定 -> 晚绑定 继承 -> 组合 编译时依赖 -> 运行时依赖 紧耦合 ->…...

spring boot深入及启动原理探究

围绕spring boot 的优点&#xff0c;本文我们来探究一下spring boot具体是如何实现这些特性的。 自动配置&#xff1a;针对很多Spring应用程序和常见的应用功能&#xff0c;Spring boot能自动提供相关配置&#xff1b;起步依赖&#xff1a;告诉Spring boot需要什么功能,它就能引…...

JfreeChart柱状图饼图

JfreeChart画出柱状图饼图的代码片段及详细的注释&#xff0c;附件为JfreeChart中文API一览表&#xff0c;和生成的柱状图&#xff0c;饼图图片 import java.awt.Font; import java.io.FileOutputStream; import java.io.IOException; import org.jfree.chart.C…...

自动装配的底层实现

public void autowire(Object o, Map<String, String> map) throws Exception { // 获得map 所有key Set<String> keys map.keySet(); // 获得Object中所有属性 // 获得Class对象 Class c o.getClass(); // 获得…...

八大设计模式原则

1.依赖倒置原则 高层模块不依赖底层模块&#xff0c;二者都应该依赖抽象 抽象不依赖实现细节&#xff0c;实现细节应该依赖于抽象 这一原则与下面的针对接口编程而不是针对实现编程是一个道理&#xff0c;我们设计一个程序&#xff0c;我们应该先想好我们想要抽象什么&#x…...

每天一个adb命令:input 命令详解

input命令可以用于向键盘发送一些指令&#xff0c;先看看input的官方说明&#xff1a; Usage: input [<source>] <command> [<arg>...]The sources are:mousekeyboardjoysticktouchnavigationtouchpadtrackballstylusdpadtouchscreengamepadThe commands an…...

matlab图形功能

//...

Gym - 100589A Queries on the Tree 树状数组+分块

题目链接&#xff1a;https://vjudge.net/problem/Gym-100589A 题意&#xff1a;n个点&#xff0c;根节点为1的树&#xff0c;两种操作&#xff0c;1 L y 与根节点距离为L的节点权值全部加上y&#xff0c;2 x x子树的权值总和 题解&#xff1a;对于更新操作&#xff0c;因为更…...

webservice学习记录笔记(一)

一、先理解什么是服务 现在的应用程序变得越来越复杂&#xff0c;甚至只靠单一的应用程序无法完成全部的工作。更别说只使用一种语言了。 写应用程序查询数据库时&#xff0c;并没有考虑过为什么可以将查询结果返回给上层的应用程序&#xff0c;甚至认为&#xff0c;这就是数…...

flex获得指定时间段一共多少天

/** * 获得某个时间段 共有多少天 * param start 开始时间 * param end 结束时间 * return * */ public static function getTimeDays( start:Date , end:Date , type:int0):Number { var _re:int 0 ; if(start && end) { var _str:Numbe…...

互联网产品与需求二 评估需求

需求分析之评估需求 一.KANO模型 五个用户需求类型1.必备型需求必备型需求是用户认为产品“必须有”的属性或者功能当其特性不充足&#xff08;不满足用户需求&#xff09;时&#xff0c;用户很不满意当其特性充足&#xff08;满足用户需求&#xff09;时&#xff0c;无所谓满意…...

flex勾选,自动刷新

mxml: <s:CheckBox label"刷新" buttonMode"true" id "frc" selected "{model.autoFresh}" change "{model.startAutoQuery(frc.selected)}"/> <s:Label text"间隔"/> &…...

flex 下拉框验证组件

//继承验证 public class ObjectNullValidator extends Validator { public function ObjectNullValidator() { super(); requiredFieldError "必须填写" ; } private var _invalidCode:String "222"; public static function validateS…...

flex 事件机制详解

事件机制的工作流程 1&#xff1a;关于事件流 当一个事件发生&#xff0c;必然存在一个派发事件的对象&#xff0c;这里称之为目标对象。 当事件发生后flashPlayer生成一个携带数据的对象&#xff0c;然后检查目标对象是否处于显示层中&#xff0c;如果是则遍历从根容器一直到目…...

bzoj1568: [JSOI2008]Blue Mary开公司 李超线段树

题目链接&#xff1a;https://www.lydsy.com/JudgeOnline/problem.php?id1568 李超线段树&#xff1a; 问题&#xff1a; 现在要求你在线动态维护一个二维平面直角坐标系&#xff0c;支持插入一条线段&#xff0c;询问与直线xx0相交的所有线段中交点y的最大/最小值 更新&a…...

Appium-java API详解

目前appium-java最新版本是5.0.0-BETA3&#xff0c;因此就拿最新的说明&#xff0c;以Java为例&#xff0c;首先引入java client的依赖&#xff1a;<dependency><groupId>io.appium</groupId><artifactId>java-client</artifactId><version&g…...

问题 I: Monitoring Ski Paths 树链剖分+LCA+树状数组+贪心

问题 I: Monitoring Ski Paths 时间限制: 1 Sec 内存限制: 128 MB [提交] [状态] [命题人:admin] 题目描述 Fresh powder on a sunny day: it is a great time to ski! Hardcore skiers flock to a large mountain in the Rockies to enjoy these perfect conditions. The …...

2019ccpc网络赛 HDU - 6705 path 贪心跑第k小的路径长度

题目链接&#xff1a;https://vjudge.net/problem/HDU-6705 题解&#xff1a;建立源点 汇点 跑A*&#xff0c;到最后也一直超内存也真是菜到家了&#xff0c;A*时间空间怎么也得n^2&#xff0c;这个题原来是个贪心。。。。 官方题解&#xff1a; 先把每条边以 形式放进堆&am…...

HDU - 6153 A Secret 扩展kmp

题目链接&#xff1a;https://vjudge.net/problem/HDU-6153 题意&#xff1a;对于s2的每一个后缀&#xff0c;假设长度为l&#xff0c;在s1出现的次数为k&#xff0c;求l*k的和 题解&#xff1a;我们把两个串都倒过来&#xff0c;变为s1,s2&#xff0c;那么问题就变为&#x…...

log4j学习demo

log4j简介 Log4j是Apache的一个开放源代码项目&#xff0c;是项目中比较常用的日志记录组件。 引入log4j <dependency><groupId>log4j</groupId><artifactId>log4j</artifactId><version>1.2.14</version></dependency> log4…...

Appium学习遇到的坑

安装篇 Q1&#xff1a;安装时要求java运行环境为最低1.8&#xff0c;我原先的jdk1.7无法运行。 A1&#xff1a;升级jdk后解决。附appium安装教程 配置篇 Q2&#xff1a;运行提示error&#xff1a;Error: Android bootstrap socket crashed: Error: getaddrinfo ENOTFOUND lo…...

matlab数组运算与数组化编程

matlab中的运算和操作主要是以数组为对象的&#xff0c; 数组又包括&#xff1a;数值数组、字符数组、元胞数组等。 一、数值数组的建立&#xff1a; 1. 直接输入法&#xff1a; 逗号&#xff1a;用来分开数组中的行元素。&#xff08;可用空格代替&#xff09; 分号&#…...

初识matlab

简单的数学运算&#xff1a; 极限运算&#xff1a; limit(f,x,x0): 计算x→x0时函数f的极限。 举例&#xff1a; syms x y1(1x2*sin(x))^(2/x); y2((1x)^0.5-2)/(x^2-2*x-3); y3x^2*sin(1/x)/sqrt(2*x^2-1); f1limit(y1,0) f2limit(y2,3) f3limit(y3,inf…...

每天一个adb命令:pm 命令详解

介绍adb shell中一个很重要的命令——pm&#xff08;Package Manager&#xff09;&#xff0c;这个命令主要用于获取和安装在 Android 设备上的应用信息。 关于pm命令的用法解析。命令行下输入adb shell pm即可获得关于pm的用法帮助&#xff0c;如下所示&#xff1a; usage: …...

51nod 1571 最近等对 CQD分治

题目链接&#xff1a;https://www.51nod.com/Challenge/Problem.html#problemId1571 现在有一个序列 a1, a2, ..., ana1, a2, ..., an &#xff0c;还有m个查询 lj, rj (1 ≤ lj ≤ rj ≤ n)lj, rj (1 ≤ lj ≤ rj ≤ n) 。对于每一个查询&#xff0c;请找出距离最近的两个元素…...

HDU - 1890 Robotic Sort 伸展树

题目链接&#xff1a;https://cn.vjudge.net/problem/HDU-1890 题意&#xff1a;每次将第i个位置到第i大的数所在位置 之间的数进行翻转&#xff0c;输出的是第i大的数所在的位置 题解&#xff1a;按照1-n建树&#xff0c;原序列排序&#xff0c;每次把节点 a[i].id 放到顶部…...

matlab数值计算

第一节 多项式运算 一、多项式的表示、求值、求根 1. 表示&#xff1a; matlab中把多项式表达成一个行向量&#xff0c;该向量中的元素是按多项式降幂排列的。 p[2,3,-1,4,5]表示多项式&#xff1a; 显示多项式的数学形式&#xff1a; p1poly2str(p,x) 如&…...

VS2019在win10下配置boost库

第一步&#xff1a;官网下下载&#xff1a;https://www.boost.org/users/history/version_1_73_0.html win10选择boost_1_73_0.zip 第二步&#xff1a;解压 第三步&#xff1a;编译 打开VS命令行 选择 已压缩好的boost_1_73_0文件夹 运行 bootstrap.bat 成功之后运行 刚…...

http load介绍

前几天工作中要对项目的接口做简单压测&#xff0c;就使用了http load做了简单测试&#xff0c;下面介绍一下这款工具的使用说明。简介&#xff1a;http_load是基于linux平台的性能测试工具&#xff0c;它体积非常小&#xff0c;仅100KB。它以并行复用的方式运行&#xff0c;可…...

牛客 Fruit Ninja 随机大法

链接&#xff1a;https://ac.nowcoder.com/acm/contest/163/A 来源&#xff1a;牛客网 题目描述 Fruit Ninja is a juicy action game enjoyed by millions of players around the world, with squishy, splat and satisfying fruit carnage! Become the ultimate bringer of…...

matlab程序设计

一、自定义函数 格式&#xff1a;函数句柄 (自变量列表)函数表达式 例1 定义函数&#xff0c;并计算f(x)在点x-2,1,2.5,3,5.2的值。 f(x)x.^23*x5 x[-2,1,2.5,3,5.2] y1f(x) 二、 m-文件函数&#xff08;子程序&#xff09; 格式&#xff1a;function [y1,y2]ff(x1,x…...

inet_pton()和inet_ntop()函数

https://blog.csdn.net/zyy617532750/article/details/58595700 1.把ip地址转化为用于网络传输的二进制数值 int inet_aton(const char *cp, struct in_addr *inp); inet_aton() 转换网络主机地址ip(如192.168.1.10)为二进制数值&#xff0c;并存储在struct in_addr结构中&a…...

CodeForces - 500B New Year Permutation floyd+选择排序

User ainta has a permutation p1, p2, ..., pn. As the New Year is coming, he wants to make his permutation as pretty as possible. Permutation a1, a2, ..., an is prettier than permutation b1, b2, ..., bn, if and only if there exists an integer k (1…...