11

#include<bits/stdc++.h> using namespace std; const int N=805; #define son(x) (rt*4-2+x) #define ll long long struct node{ int mn; int mx; void reset(){ mx=INT_MIN; mn=INT_MAX; } }tree[(N<<2)*(N<<2)]; void build(int rt, int xl, int xr, int yl, int yr)...

利用叉积，如果点在三角形内部的话，则顺序处理全部边的话，这个点都在边的同一侧，直接用叉积判断 double det(double x1,double y1,double x2,double y2){ return x1*y2-x2*y1; } //x0,y0为需要的检查点，其他点顺时针顺序 bool check(double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3){ if(det(x0-x1,y0-y1,x2-x1,y2-y1)>=0&&d...

比赛链接 http://https://codeforces.com/gym/102220 题目链接 https://codeforces.com/gym/102220/problem/C 题目大意： 给n组二维坐标点，每一组两个点，组成一条直线。问有多少对直线存在公共点。 解题思路 1.如何保存直线信息。 用直线形式y=kx+b，维护k，b两个信息，虽然有一定精度损失，但是这个题也可以过。也可以考虑用两个的坐标gcd维护斜率信息，求出gcd之后标准化向量，如何维护b值。（斜率不存在单独考虑） 2.如何优化，不用O（nn)的复杂度。 首先对维护的直线排序，可以把斜率相同的直线排在...

题意：   一个数论题，要求满足如下等式的x有多少个。      思路：   当时比赛是，队伍看到这个题，也没有做太多的思考，就是无从下手，几乎放弃。但是看到学校另外两支队伍都过了这个题，感觉自己还是好菜。   打表可以发现，当a为奇数的时候答案为1。当a为偶数的时候，x一定也是偶数，这个还是比较明显的。   对左边进行推导，因为a为偶数，设a=2*t，所以a^x=2^x*t^x,所以当x大于p时，这个求余之后一定为0。由于p很小，可以直接暴力求解，所以对于右边直接考虑x^a求余之后为0的x的情况。由于x为偶数。我们再次对x分解，设x=2^k*t,就是把x写成一个2的 次幂和t的乘...

题意：   初始有n个灯泡，灯泡状态是0和1,。现在有k***作，每次改变且仅改变m个的灯的状态，给定n盏灯的初始状态的最终状态，求有多少种解决改变灯的方案满足可以满足题目条件。 思路：   开始写的时候以为是组合计数和容斥原理什么鬼的，后来发现n，m，k的值都比较小，觉得应该是三维dp了，当然是瞎想，最后看题解还是一个二维dp可以解决的问题，只不过是三重循环。给队友lrr说了一下题解的状态定义，他也较快就写出来了。其实对于灯的状态，每次改变一次之后，现在的问题和之前的问题形式一样，只是k值和目标灯的状态不同的个数变了。   状态如下定义dp【i】【j】表示操作到第 i 轮，与目标的灯...

题意： 给定平面内若干点，要求求出这些点组成的三角形中锐角三角形的个数。 思路： 锐角三角形，即这个三角形中不存在直角或者钝角。所以现在的思路是不断枚举三个点，看他们之间组成的角度在什么范围内，这样的复杂O（n*n*n），时限内肯定不能通过。对于二维平面的向量，用点积和叉积可以较为方便的判断他们之间的角度。 由于 锐角三角形个数=三角形个数-直角个数-顿角个数 可以考虑枚举每一个点，以这个点为参考点，对这个点和其他点组成的向量进行极角排序，这个在一个相对有序的向量之间，判断两两之间的角度就可以优化了，存在二分的two point两种优化方法，two point较为好写。如何尺取呢？由...

这里我们说的极角排序，指的是对于二维坐标中的点，当然也可以说是向量。极角排序的用途一般是预处理二维平面中的点，使之变得相对有序，接下来在有序的条件小用O（n）或者O（nlogn）处理，而不是无序条件下的O（n*n）的枚举。 应用链接  https://www.cnblogs.com/gzr2018/p/10873518.html 极角排序：根据数学知识，在极坐标的情况下，有一个原地，一个参考方向（x轴正方向），现在对于其他点，对于原点，即存在一个极坐标（r，thata），对于极角排序。 关于叉积：叉积=0是指两向量平行（重合）；叉积>0，则向量a在向量b的顺时针方向（粗略的理解为在...

//对多边形没有要求，但要求点按照顺时针或者逆时针的顺序1 for (int i = 0; i < x; i++) 2 scanf("%lf%lf", &a[i][0], &a[i][1]); 3 a[x][0] = a[0][0]; 4 a[x][1] = a[0][1]; 5 double sum = 0; 6 for (int i = 0; i < x; i++) 7 sum += (a[i][0] * a[i + 1][1] - a[i + 1][0] * a[i][1]); 8 sum = sum / 2; 9 if (...

问题描述 小龙同学最近为了完成毕业设计头痛不已。巨大的精神压力导致他经常做 噩梦。这天他又做了一个史诗般的噩梦。他梦见自己被困在一个密室中，密室 的门上有一个谜题，只有解开谜题才能打开此门，逃出这个密室，否则就会永 远地被困在密室中，更可怕的是他还会永远的困在梦境中，无法完成毕设，从 而面临毕业危机。 谜题是这样的，给定一个连续的正整数序列 n, n+1, n+2, ..., m，要求通过 调整序列中数字的顺序，将其变成一个“k 度芝麻开门序列”。 一个简单的“2 度芝麻开门序列”可以理解为重新调整一个连续整数序列 的顺序，使得每对相邻两个数之和是一个合数（非质数）。同样的，一个“k 度 芝麻...

二分图匹配： 知识点：交替路，增广路，匈牙利树，匈牙利算法求最大匹配数，bfs染色法判断是否是二分图（不存在奇数回路） 例题：hud2063 匈牙利算法 1 #include <iostream> 2 #include<bits/stdc++.h> 3 //二分图匹配，在find函数理解。 4 //找增广路，增广路的定义是从为匹配的节点出发，终止与未匹配的节点，中间是交替路。 5 //find函数的递归不是一层一层的，而是直接dfs一个节点的匹配的节点 6 //然后沿着增广路修改相互匹配的节点，在寻找过程中，用vis标记节点是否在增广路中，可以保...

POJ 2342链接 树形dp入门题，对于几乎没有接触树形dp的同学来说，是不错的练习题。 题目大意： 一棵有向树中，节点带权值 ，选择其中一些节点使得选择的总的节点权值最大，选择的规则是不能同时选择一个节点和他的直接父亲节点。 解题思路： 无疑是一个多决策问题，在多步决策中得到最优的答案。考虑dp，树形结构，树形dp 。 设计状态： dp[i][0]表示没有选择该节点的最大价值和 dp[i][1]表示选择该节点的最大价值和 ，输入的时候就可以初始化 dp[i][0]=sigma(max(dp[son][0] ,dp[son][1])) dp[i][1]=sigma(dp[son][...

蓝桥杯真题-小计算器 链接 小计算器 题目描述 模拟程序型计算器，依次输入指令，可能包含的指令有   1. 数字：'NUM X'，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数   2. 运算指令：'ADD','SUB','MUL','DIV','MOD'，分别表示加减乘，除法取商，除法取余   3. 进制转换指令：'CHANGE K'，将当前进制转换为K进制(2≤K≤36)   4. 输出指令：'EQUAL'，以当前进制输出结果   5. 重置指令：'CLEAR'，清除当前数字   指令按照以下规则给出：   数字，运算指令不会连续给出，进制转换指令，输出指令，重置指...

2017年蓝桥杯试题解析 不得不说自己还是太菜了，2017年蓝桥杯填空题自己就措手不及了。。 t1标题：迷宫 X星球的一处迷宫游乐场建在某个小山坡上。 它是由10x10相互连通的小房间组成的。 房间的地板上写着一个很大的字母。 我们假设玩家是面朝上坡的方向站立，则： L表示走到左边的房间，R表示走到右边的房间， U表示走到上坡方向的房间，D表示走到下坡方向的房间。 X星球的居民有点懒，不愿意费力思考。 他们更喜欢玩运气类的游戏。这个游戏也是如此！ 开始的时候，直升机把100名玩家放入一个个小房间内。 玩家一定要按照地上的字母移动。 迷宫地图如下： UDDLUULRUL UURLLLRRR...