2 gongyuandaye

尚未进行身份认证

我要认证

不要再问我会不会写可持久化非确定状态AC自动分块维护线段平衡仙人掌优化最小费用最大流预处理混合图上莫比乌斯反演莫队带花舞蹈链并查集树状数组套主席树预处理动态DP分治FFT求多项式逆元对数函数的指数函数用可持久化并查集合并最小费用循环流上插头DP了。

等级
TA的排名 3w+

Gym 101911C Bacteria (最小堆)

题意:n个元素,每次选两个相同元素出来,若没有,则新增一个,然后将两数之和放回原序列,问最后能否只剩一个元素,且新增多少个。题解:最小堆模拟取的过程即可。#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<queue>#

2020-10-06 20:16:53

POJ 2763 Housewife Wind (树链剖分+边权化点权)

题意:给定一棵含n个结点的生成树,共有q次操作,分为两种:0 c:求从位置s到c的距离,然后s变成c1 a b:把第a条边的权值变为b题解:树链剖分0操作就是树上区间查询。由于该题是边权且为生成树,树链剖分只能解决点权,那我们化成点权即可。即对于边<u, v>,将离根节点远的那个点的权值赋为边权。这样在进行树剖的时候,减去lca的点权即可。这样1操作就是单点更新了。#define _CRT_SECURE_NO_WARNINGS#include<iostream>#

2020-10-03 18:38:05

POJ 3728 The merchant (在线查询+倍增lca)

题意:给出N个点,和每个点物品的售价,现在有一个商人,要从u点到v点,他想在路上多赚点钱。他可以从一个城市买物品,然后再卖到另一个城市,但买卖只允许一次,且不能回头走,问最多能赚多少。题解:在线查询+倍增lcan个点的生成树,路径有且只有一条,所以考虑lca路径。接下来考虑如何获取利润的最大值。从u到v,差值只可能出现在u到lca、u到v、lca到v这三种路径上。对于u到lca路径,用up数组记录最大利润。对于lca到v路径,用down数组记录最大路径。对于u到v路径,需要记录左路径的最小值M

2020-10-03 16:31:06

POJ 3417 Network (lca+树上差分)

题意:n个点的生成树,还有m条附加边,删去一条生成树的边和一条附加边,使得变成两个连通分量,有几种方案。题解:lca+树上差分对于每一条附加边<x, y>,将x到y的lca路径上的边标记,即对于该路径上的任意边删去,再删去附加边即可满足要求,但此做法前提是该路径上的边只被覆盖一次。这是第一种情况,ans++。第二种情况就是边没有被覆盖,则删去该边即可分为两个连通块,所以任意删除一条附加边即可,ans += m。对于如何进行覆盖,用树上边差分即可。vector建图会t,用链式前向星存,常

2020-09-29 00:23:00

POJ 1330 Nearest Common Ancestors (lca)

题意:带环lca。题解:lca从入度为0的点开始dfs。注意是有向边。#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<queue>#include<stack>#include<cmath&gt

2020-09-28 22:14:43

HDU 3078 Network (lca+排序)

题意:一棵无向树,输入点数和操作数,下面一行n个值代表每个点的权。下面n-1行是树边。操作分为 0 x w ,表示把点x的权改为w; k a b , 求出从a到b的路径中,第k大的点权。题解:lca+排序居然直接暴力就可以过了,每次询问将lca路径中的点权排序即可。#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<string>#include<cstri

2020-09-28 21:04:53

HDU 2874 Connections between cities (并查集+lca倍增法)

题意:由于战争期间大部分道路已被完全摧毁,两个城市之间可能没有路径,也没有环存在。现在,告诉您道路状况后,我们想知道任何两个城市之间是否存在路径。如果答案是肯定的,则输出它们之间的最短路径。题解:并查集+lca倍增法先用并查集缩点,不在同一集合必然不存在路径,然后dfs预处理每一个集合。这里用倍增法求lca。#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<strin

2020-09-27 22:10:14

HDU 2586 How far away ? (lca倍增法)

题意:给出一棵有边权的树,q次询问,求u、v之间的路径长度。题解:lca倍增法。#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<queue>#include<stack>#include<cmat

2020-09-27 21:37:17

HDU 1914 The Stable Marriage Problem (稳定婚姻匹配)

题意:稳定婚姻匹配问题,板子题。题解:稳定婚姻匹配注意按字典序输出,还有输出格式,最后个样例不输出空行。#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<queue>#include<stack>#inc

2020-09-27 20:07:59

HDU 1522 Marriage is Stable (稳定婚姻匹配)

题意:稳定婚姻匹配问题,板子题。题解:稳定婚姻匹配还好做了这题,之前的板子有点问题,1435数据太弱了。#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<queue>#include<stack>#inc

2020-09-26 23:55:54

HDU 3585 maximum shortest distance (二分+最大团)

题意:有n个点。选取k个点(k> = 2),并在这k点中最近的两个点距离最远。题解:二分+最大团最近的最远,往二分上面靠。由于最近的两个点所连的边是k点构成完全图中边权最小的,那么其他的边必然大于等于该值,那么我们二分这个答案即可。对于二分的mid,每次将大于等于mid的边连上,然后跑最大团(点点直接相连才能保证最短边权,若不是完全图则必然存在小于mid的边),若最大团的结点数大于等于k,则最大团存在结点数等于k,且最小边权大于等于mid的子图。#define _CRT_SECURE_NO_

2020-09-26 16:56:36

HDU 1435 Stable Match (稳定婚姻匹配)

题意:建立一个匹配表,使得一个发射点对应一个接收点,对于某一个发射点来说,它的接收点离它越近那么就会更稳定,同样对于接收点也是一样的情况。匹配的目标是使得整个网络变得稳定。对于某2个匹配,比如,( a ---- 1) ,(b----2) ,如果发射点a 离接收点2 比 1要近,而且2 也离 发射点a要比 b 近,那么 a 就很有可能把信号发到 2中,我们就说这个搭配是不稳定的。而且每个点都有一个容量值,如果对于一个发射点到2个接收点的距离一样的话,它将首先选择容量大的那个。题解:稳定婚姻匹配让发射

2020-09-26 15:38:58

HDU 1530 Maximum Clique (最大团)

题意:给出无向图,求最大团的结点数。题解:最大团团:若图是一个团,则该图是无向图。极大团:不是其他团的子集。最大团:结点数最多的团。#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<queue>#include&l

2020-09-25 11:06:26

HDU 3666 THE MATRIX PROBLEM (差分约束+栈优化spfa判负环)

题意:给出一个N∗M的矩阵C,要求构造两个序列a1,a2,…,an和b1,b2,…,bm, 矩阵的第i行元素乘上 ai,矩阵的第j列元素除以bj,最终矩阵的每个元素Cij∈[L,U]。若可以构造成功,则输出YES,否则输出NO。题解:差分约束+栈优化spfa可得约束方程:L<=c∗ai/bj<=UL <= c * ai / bj <= UL<=c∗ai/bj<=U习惯最长路,于是可以转换为:ai/bj>=L/cai/bj>=L/cai/bj>=L

2020-09-24 22:02:48

HDU 3592 World Exhibition (差分约束)

题意:n个人按顺序1-n排队,可并列排,给出x对关系,两两距离不超过D;给出y对关系,两两距离不小于D,求1到n的最远距离。题解:差分约束求最远,跑spfa最短路。按题意建立差分约束方程即可。由于并列排,所以相邻两人距离限制条件是≤0。注意inf输出-2。#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<string>#include<cstring

2020-09-24 14:38:08

Visual Studio 2019 新建OpenGL项目无需重新配置环境

(1)原文件为GLFWOpenGL,直接复制该项目至同一目录下,改名为Texture。(2)打开Texture,点击.sln文件即可,无需重新引进依赖项,ok完成。

2020-09-24 08:50:31

HDU 3440 House Man (差分约束)

题意:有N个在一条直线上的房子, 每个房子有着不同的高度,超人可以将这些房子左右移动,但不能改变房子之间的相对位置。超人要从最矮的房子跳到刚好比他高的房子上面, 且每次跳的房子都要比当前房子要高,他要跳N-1次。那么最后超人肯定会跳到最高的房子上面,现在给出超人一次能够跳的最远距离D,求如何摆放这些房子, 使得超人能够经过所有的房子跳到最高的房子, 又要使最矮的房子和最高的房子之间的距离最远,输出最远距离。题解:差分约束求最远距离,跑最短路即可。我们用d[i]d[i]d[i]表示离起点的距离。由于不改

2020-09-23 17:52:54

HDU 1534 Schedule Problem(差分约束)

题意:一个项目可以分为几个部分。 每个部分都应连续完成。 这意味着如果一个零件需要3天,我们应该连续3天完成它。 这些部分中有四种约束,分别是FAS,FAF,SAF和SAS。 如果第一个零件应该在第二个零件开始之后完成,则零件之间的约束就是FAS。FAF完成后完成。 SAF完成后启动,SAS启动后启动。 假设有足够的人参与项目,这意味着我们可以同时进行任何数量的部分。 编写一个程序给出项目的时间表,该时间表最短。题解:差分约束用d[i]d[i]d[i]表示第iii个部分开始的时间,依据题意建立约束即可,

2020-09-22 22:34:27

HDU 1531 King (差分约束)

题意:给出序列a的长度n,以及m个连续子序列的起始点及长度,对于每个连续子序列,给出其和与整数 ki 的大小关系,问是否存在序列a。题解:差分约束简单的差分约束问题,按照题目输入建立约束方程即可,然后跑spfa最长路。由于我们用d[i]d[i]d[i]表示序列a前iii个元素和,那么就有包含0的n+1个点,所以负环的判断条件是>n+1。还有就是我们把n+1个点全部push即可。#define _CRT_SECURE_NO_WARNINGS#include<iostream>#i

2020-09-22 21:42:29

HDU 1529 Cashier Employment (差分约束)

题意:德黑兰的某国营商店需要聘用一批员工,不同的时间有不同的人员需求,能够雇佣到的人数也不同。然而你一旦聘用了一个人,他就会跟着你干8个小时。输入24个时间点的需求与劳动力人数,输出满足需求最少需要的人数,不行就输出no solution。题解:差分约束设d[i]d[i]d[i]表示从0点到i−1i-1i−1点(包括i−1i-1i−1)雇佣的人数。答案就是d[24]d[24]d[24]。每个点iii的需求和供应人数分别用r[i]r[i]r[i]和a[i]a[i]a[i]表示。可得约束方程:d[i+

2020-09-22 17:55:07

查看更多

勋章 我的勋章
  • GitHub
    GitHub
    绑定GitHub第三方账户获取
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。
  • 原力探索 · S
    原力探索 · S
    在《原力计划【第二季】》打卡挑战活动中,发布 12 篇原创文章参与活动的博主,即可获得此勋章。(本次活动结束后统一统计发放)