- 博客(77)
- 收藏
- 关注
RSS订阅原创 Codeforces Round #561 (Div. 2)
A. Silent ClassroomA题就不多说了，统计一下开头字母的出现次数，平均分到两边，每次统计时取C（num,2）即可#include<bits/stdc++.h>#define exp 1e-8#define mian main#define pii pair<int,int>#define pll pair<ll,ll>#def...
2019-05-19 20:43:29
294
转载 KM算法详解+模板
原文地址：http://www.cnblogs.com/wenruo/p/5264235.htmlKM算法用来求二分图最大权完美匹配。本文没有给出KM算法的原理，只是模拟了一遍算法的过程。另，博主水平较差，发现问题欢迎指出，谢谢！！！！现在有N男N女，有些男生和女生之间互相有好感，我们将其好感程度定义为好感度，我们希望把他们两两配对，并且最后希望好感度和最大。怎么...
2019-05-16 21:54:33
1245
原创 二分图专题
Fire Nethdu1045题意：在一个最多4×4的方格中，类似于求棋盘问题，只是有些点变成了“墙”，对于同一行或同一列如果有墙，墙两边的点是没有影响的。思路：对于普通的棋盘问题，只需要把每一行或每一列当成一个点建图就可以了，但这个因为有墙的存在显然不行了，可以想到对于普通的棋盘问题在没有墙的时候对于每一行每一列正好是一行一个点，一列一个点，所以也就是连续的 “.” 当成一个点，所...
2019-05-15 17:21:45
349
原创 2019第十届山东ACM省赛部分题解
B、Flipping Game比赛时一直以为是个组合数找规律的题，今天一想应该要用dp，推了一节毛概课，到晚上终于给A了。dp[i][j]表示当第i轮有j个不同的时的方案数，那么可以得到初始条件dp[0][num]=1(num表示一开始有多少个灯状态不同，因为接下来递推要用乘法所以初始化为1，这里只需知道dp[0][num]是初始条件即可）那么dp[i][j]可以怎么得到呢?首先肯...
2019-05-14 09:58:09
1231
2
原创 spoj Favorite Dice（概率dp+期望）
favorite dice题意：给你一个N面的骰子，问n个面都扔到的期望是多少？概率dp和其他的dp有些不同，区别是其他的dp通常是顺着推，而概率dp有的时候需要逆推，具体要看给的条件，例如这个题，很明显用dp[i]表示已经扔到了i个面，还需要扔的期望次数，而可以得出dp[n]=0，所以这个题就需要逆推求解时考虑dp[i]是怎么来的，有可能是扔到了已经扔过的面或者是扔到了没有扔到过...
2019-05-10 15:53:16
391
原创 hznu 校赛 Little Sub and Johann
Little Sub and Johann这个题打个SG函数表找个规律就可以了，先跑了前100个sg函数的值，#include<bits/stdc++.h>#define exp 1e-8#define mian main#define pii pair<int,int>#define pll pair<ll,ll>#define ll ...
2019-05-06 19:25:29
313
2
原创 SG函数
一、必败点和必胜点必败点：P点，处于这一点时在双方操作均正确的前提下必败必胜点：N点，处于这一点时双方操作均正确的前提下必胜。有关的性质:1、所有终结点都是必败点2、必败点P无论怎么操作只能进入必胜点N3、至少有一种操作使可以从必胜点N到达必败点PSprague-Grundy定理（SG定理）： 游戏和的SG函数等于各个游戏SG函数的Nim和。Bouto...
2019-05-06 19:09:56
1167
原创 浙江省赛部分题解
Sequence in the PocketDreamGrid has just found an integer sequencein his right pocket. As DreamGrid is bored, he decides to play with the sequence. He can perform the following operation any numbe...
2019-04-28 10:00:24
364
1
原创 Codeforces Round #554 (Div. 2)
A. Neko Finds Grapestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputOn a random day, Neko foundnntreasure chests andmmkeys. ...
2019-04-25 09:28:31
524
原创 欧拉降幂
一、欧拉降幂先贴一个欧拉定理在数论中，欧拉定理,（也称费马-欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互质，则:平常做题时应该都遇到过要求 A^BmodC的情况吧，而当B很大时该怎么做呢。这时候要用到欧拉降幂什么是欧拉降幂？ 就是这个公式了。条件是B>=phi(C),phi表示欧拉函数或者当B与C互质时，A^B%C=A^(...
2019-04-24 20:34:49
829
原创 欧拉函数
一、欧拉函数贴一下百度百科在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。此函数以其首名研究者欧拉命名(Euler's totient function)，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。所以通过欧拉函数可以很方便快捷的找出小于n的与n互质的数的个数i...
2019-04-24 19:55:52
174
原创 稳定婚配问题
一、稳定婚配问题通过问题的名字可以看出这是一个类似匹配的问题，有男女各n人，每个人对其他人都有好感度，问如何匹配可以使每个人都能找到自己心仪的对象？很显然，二分图匈牙利算法即可，这里不过多叙述。现在加上稳定两个字，即当前假设1号男生的对象是1号女生，2号男生的对象是2号女生，但如果1号男生对2号女生的好感度大于对1号女生的好感度，并且二号女生对1号男生的好感度也大于对2号男生的好感...
2019-04-23 21:44:47
1634
原创 次短路
一、次短路听名字也能知道，次短路就是求的第二短的路径，这里有两种解法1、A*，上一篇博客写的就是关于A*的，A*用来求第k短的路径，当k==2时，即为次短路。这里就不多叙述2、其实就是在最短路上稍微修改一点点就好啦......即将dis数组改为二维，dis[i][0]表示到i点的最短路，dis[i][1]表示到i点的次短路，然后每次比较更新每个点的两个值即可二、这里用p...
2019-04-22 19:53:40
1352
原创 K短路 A*
一、k短路什么是k短路？最短路就是第一短路，那么第k短的就是k短路。二、求k短路首先可以想到在BFS中，从起点开始走，把每个点放入队列中时，以当前走过的距离加上当前点到终点的最短距离的和（即我们假设可以预知走哪个点到终点的距离最短）作为比较条件从小到大排序，当第一个到达终点时，走过的路径长度即为最短路，那么第k次到达终点的长度显然就是k短路。那么接下来就是问题的核心了，如何判断...
2019-04-20 09:55:14
941
4
原创 二分图最大匹配
先上定义：一、二分图二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图也就是一个图被划分成了两个不相交的集合，集合内部没有边相连。二、匹配1、匹配在一个二分图G中，它的一个子集...
2019-04-11 21:59:38
2851
1
原创 中石油第五场补
E: Election of Evil题目描述Dylan is a corrupt politician trying to steal an election. He has already used a mind-control technique toenslave some set U of government representatives. However, the re...
2019-04-11 16:16:01
320
原创 20190402训练赛
Problem A Patches1 s, 256 MB【Description】Carlos is very concerned with the environment. Whenever possible, he tries to use less pollutingmeans of transport. He recently got a job close to home a...
2019-04-04 16:40:38
402
原创 逆元
一、逆元是什么 当我们平常做题遇到需要求类似于（a/b）%p的时候，显然这个时候不能像做加法和减法一样展开成((a%p)/(b%p))%p。这个时候就要用到逆元了。假设c是b的逆元，那么就可以得到b*c1（mod p）,那么上式就可以写成(a/b)*1 %p=(a/b)*b*c%p=(a*c)%p这样我们就把除法取模问题转化成乘法取模问题了。二、求逆元1、费马小定理...
2019-04-01 20:35:51
207
原创 分块
学莫队之前先看了看分块，，总结一下的话感觉还是一个暴力的算法一、什么时候可以用到分块呢？如果问，一个数列，给定m次询问，每次问一个区间内的和是多少? 很明显可以用前缀和来解决那么如果问还要对随机一个区间进行加或减之类的修改呢？ 很容易想到树状数组和线段树来解决再问，如果在加上问一个区间大于等于k的数有几个呢？这个时候就需要这个‘暴力’的方法出场了，我们可...
2019-03-27 18:37:23
186
原创 树上的最小支配集、最小点覆盖、最大独立集（贪心解决）
首先来看一下这三个知识点的概念一、最小支配集对于图G=(V,E)来说，最小支配集指的是从V中取尽量少的点组成一个集合，使得对于V中剩余的点都与取出来的点有边相连。也就是说，设V‘是图G的一个支配集，则对于图中的任意一个顶点u，要么属于集合V’，要么与V‘中的顶点相邻。在V’中出去任何元素后V‘不再是支配集，则支配集是极小支配集。称G的所有支配集中顶点个数最少的支配集为最小支配集，最小支配集...
2019-03-16 16:31:55
2379
原创 训练赛20190310
B - GliderA plane is flying at a constant height ofhhmeters above the ground surface. Let's consider that it is flying from the point(−109,h)(−109,h)to the point(109,h)(109,h)parallel with...
2019-03-10 20:26:11
530
原创 训练赛20190304
D - Balanced LineupFor the daily milking, Farmer John'sNcows (1 ≤N≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the ...
2019-03-05 19:31:47
240
原创 寒假牛客第六场
A-出题题目描述小B准备出模拟赛。她把题目按难度分为四等，分值分别为6,7,8,9。已知小B共出了m道题，共n分。求小B最少出了多少道6分题。 输入描述:两个正整数n,m输出描述:一个数，表示答案。若无解，输出"jgzjgzjgz"。示例1输入复制34 5输出复制1示例2输入复制32 5输出复...
2019-02-02 19:40:15
250
原创 寒假牛客第五场
A-炫酷双截棍 题目描述小希现在手里有一个连着的两块木条，长度分别为l1l1,l2l2，木条之间有一个无摩擦的连接点，木条之间可以相互转动，小希将其称之为双截棍。现在小希把长为l1l1的木条的一端放在原点(0,0)，任意转动这两根木条，小希想知道，是否有可能通过一种转动方式使得双截棍的另一端到达指定点呢? 如果不能，请输出所有能到达的点中离目标点最近的距离。输入描述:...
2019-02-01 12:43:16
450
转载 C++ STL之unique函数
类属性算法unique的作用是从输入序列中“删除”所有相邻的重复元素。该算法删除相邻的重复元素，然后重新排列输入范围内的元素，并且返回一个迭代器（容器的长度没变，只是元素顺序改变了），表示无重复的值范围得结束。在STL中unique函数是一个去重函数， unique的功能是去除相邻的重复元素(只保留一个),其实它并不真正把重复的元素删除，是把重复的元素移到后面去了，然后依然保存到了原数组中...
2019-02-01 10:48:19
172
原创 寒假牛客第四场
E-Applese 涂颜色题目描述 精通程序设计的 Applese 叕写了一个游戏。在这个游戏中，有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定左右相邻两格的颜色不能相同。请你帮它统计一下有多少种涂色的方法。由于答案很大，你需要将答案对 109+7取模。输入描述:仅一行两个正整数 n, m，表示方阵的大小。输出描述:输出一个正整数，表示...
2019-01-30 20:57:10
265
转载 Java大数运算
因为之前做到了大数的题目，但不想自己写关于java大数的模板了，所以这里转一下元哥的模板原文地址描述import java.util.*;import java.math.*;public class Main{ public static void main(String [] args){ Scanner in = new Scanner(Syste...
2019-01-25 23:02:13
694
原创 寒假牛客第二场部分题解
A-处女座的签到题平面上有n个点，问：平面上所有三角形面积第k大的三角形的面积是多少?输入描述:第一行T，表示样例的个数。对于每一组样例，第一行两个整数n和k，接下来n行，每行两个整数x,y表示点的坐标T<=803<=n<=100-109<=x,y<=109对于每一组样例，保证任意两点不重合，且能构成的三角形的个数不小于k输出描述...
2019-01-25 22:51:38
276
原创 STL—nth_element（）
nth_element函数的作用是在一个未排序的数组中，寻找如果这个数组按从小到大的顺序排序，第n个位置上应该是哪一个数，在<algorithm>头文件中具体的使用方法是 nth_element(a+start,a+k,a+end)就是在a数组的start位置到end范围内从小到大排序应该在第k个位置上的数是哪一个并且这个函数只是找到了第k个位置上的数，其他的位置并不是有...
2019-01-25 20:43:26
246
原创 QLU—寒假第二次训练
A - Generous Kefa One day Kefa found n baloons. For convenience, we denote color of i-th baloon as si— lowercase letter of the Latin alphabet. Also Kefa has k friends. Friend will be upset, If he ...
2019-01-19 16:42:46
518
原创 QLU—寒假第一次训练
A - Classy Numbers（数位dp）Let's call some positive integer classy if its decimal representation contains no more than 33 non-zero digits. For example, numbers 44, 200000200000, 1020310203 are classy a...
2019-01-17 17:16:10
355
原创 QLU-第九次训练
因为期末复习半个月没更博客了，，中间还有一次训练没打。。可上周明明第二天就要六级，，却打了一场训练赛（我也不知道自己怎么想的......）A - Paper Airplanes 传送门To make a paper airplane, one has to use a rectangular piece of paper. From a sheet of standard size...
2018-12-17 19:25:01
377
原创 QLU-第七次训练
A coinsYou have unlimited number of coins with values 1,2,…,n1,2,…,n. You want to select some set of coins having the total value of SS.It is allowed to have multiple coins with the same value i...
2018-12-01 22:04:21
339
原创 QLU-第六次训练
B 数列传送门题目描述给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是： 1，3，4，9，10，12，13，… （该序列实际上就是：30，31，30+31，32，30+32，31+32，30+31+32，…） 请你求出这个序列的第N项的值（用10进制数表示）。 例如，对于k=3，N=100...
2018-11-23 21:31:00
270
原创 QLU-第五次训练
A 无线网路发射器选址传送门题目描述随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共 场所覆盖无线网。假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格 状，并且相邻的平行街道之间的距离都是恒定值 1。东西向街道从北到南依次编号为 0,1,2…128,南北向街道从西到东依次编号为 0,1,2…128。东西向街道和南北向街...
2018-11-17 11:16:15
520
原创 poj 3264Balanced Lineup(RMQ算法）
传送门DescriptionFor the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cow...
2018-11-14 20:10:54
167
原创 RMQ (Range Minimum/Maximum Query)算法
RMQ算法是一种查找一个区间最值的算法，当然是有Q次询问，如果只询问一次，当然直接遍历就好了，如果是询问很多次，这时就需要RMQ算法了。RMQ算法RMQ算法用的是DP求解， 预处理是nlogn的，查询是O(1)。A[i]表示要查询的数列，F[i,j]表示从i开始2^j个数中最大的那一个。例如： 3 ,4 ,5,23,1,12,7F[1,0]就表示从3开...
2018-11-14 20:07:50
292
转载 C++对数函数log()用法
原文地址：https://blog.csdn.net/qq_40788630/article/details/79673539首先要知道exp（）函数exp（n）值为e^n次方；另外log函数包括两种函数 一种以e为低的log（）函数另一种为以10为底的log 10（）函数；具体用法见下面这个小程序#include<iostream> #include...
2018-11-13 21:10:33
30362
原创 QLU-第四次训练
A 生活大爆炸版 石头剪刀布题目描述石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。如果两个人出拳一 样，则不分胜负。在《生活大爆炸》第二季第 8 集中出现了一种石头剪刀布的升级版游戏。 升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势： 斯波克：《星际迷航》主角之一。 蜥蜴人：《星际迷航》中的反面角色。 这五种手势的胜负关系如表一所示，表中列出的是甲对乙的游戏结果。...
2018-11-10 17:09:10
298
原创 poj 2135 Farm Tour(费用流）
传送门：http://poj.org/problem?id=2135 Farm TourTime Limit: 1000MS Memory Limit: 65536K Total Submissions: 20591 ...
2018-11-08 20:10:16
124
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人