• 等级
  • 20387 访问
  • 209 原创
  • 0 转发
  • 27049 排名
  • 43 评论
  • 16 获赞

差分约束系统

一般用来求解在MMM个不等式的限制下,是否存在解,最大解,最小解。判断存在解:spfa判负环最大解:最短路(三角不等式)最小解:最长路(三角不等式)POJ3169最大距离:最短路#include<map>#include<set>#include<cmath>#include<queue>#include<v...

2019-04-24 15:28:00

POJ 1932 XYZZY (查分约束+传递闭包)

题目链接题意有NNN个屋子,走进每个屋子血量都会发生改变,开始生命值100100100。问是否可以从111号屋子走到NNN号屋子中间血量保持大于000思路按照给定的顺序建图,因为要让血量尽可能的高所以求最长路,如果走到NNN的最长路的血量小于0那么就无解。最长路可能存在正环,当存在正环而且111到NNN联通,那么一定有解个人认为标程应该是spfaspfaspfa判正环+传递闭包判联通...

2019-04-24 15:07:29

ICPC China Nanchang National Invitational - I. Max answer(线段树+ST)

题目链接N个数字求一个区间使得∑i=li=ra[i]×∑i=li=rmin(a[i])\sum_{i=l}^{i=r}a[i]×\sum_{i=l}^{i=r}min(a[i])∑i=li=r​a[i]×∑i=li=r​min(a[i])最大思路枚举区间的最小值为a[i]a[i]a[i],根据ST表二分找到它最左LLL和最右RRR端点,这是保证区间[L,R][L,R][L,...

2019-04-21 00:29:02

NEUQ 2015: Bitmap(二维hash)

题目链接题意给一个N×NN×NN×N的矩阵问包含多少个M×MM×MM×M的子矩阵,子矩阵不一定完全相同,同时加上某个数相同也算思路首先差分,这样就可以直接找匹配的矩阵。二维hash+容斥判断矩阵是否相同冲突是不可避免的,我们要最小化冲突,可以对矩阵进行左右和上下两次差分,进行计算可以用unsignedlonglong,也可以取模。一直wa的原因是:差分之后矩阵的大小搞错了...

2019-04-16 18:00:47

zzuli 2520: 大小接近的点对

题目链接题意给你一棵树,每个节点有一个权值。询问每个节点有多少个点对,满足以该节点为根节点uuu与它的所有子节点vvv,并且∣val[u]−val[v]∣≤K\left|val[u]-val[v]\right|\leqK∣val[u]−val[v]∣≤K思路比赛的时候想到一个思路:就是每次从叶子节点向根节点返回,每次把经过的点加入集合,并满足根节点的数量。没时间写了,回来实现一下...

2019-04-15 20:56:52

zzuli 2525: 咕咕的搜索序列

题目链接题意给一个长度为MMM的序列,问它是否能作为给定的一棵树的dfs序的一部分思路比赛的时候和队友在写假算法,本来以为会TLETLETLE或者MLEMLEMLE,但是一直WAWAWA。回来问了学长才过的。按照给定序列的顺序从下到上打上同一个标记,遇到打过标记的点就returnreturnreturn,然后按照标记从小到大dfsdfsdfs得到一个dfsdfsdfs序,最后查找序列是...

2019-04-15 20:38:03

Codeforce 1042 D. Petya and Array(树状数组、前缀和)

题目链接省赛选拔学长说是CF的原题,赛后得知学长是用树状数组写的,补了一个树状数组的代码。题意NNN个数,问一共有多少个连续区间满足区间和小于MMM思路记录每个数的前缀和sortsortsort之后,枚举区间的起始位置找到前缀和小于M+preM+preM+pre的个数(设当前区间起始为i,满足条件的区间==Lastpre−Nowpre<MLastpre-Nowp...

2019-04-06 21:21:27

第九届河南理工大学算法程序设计大赛 正式赛(ABCDEFGHJKL)

A.Asia区域赛读题目输出奖牌之和就行,我把冠亚军也记成奖牌了。。ACcode#include<bits/stdc++.h>#defineLLlonglong#definePpair<int,int>#include<time.h>#definelowbit(x)(x&-x)#definemem(a,b...

2019-03-31 18:31:31

行列式

行列式性质互换行列式的两行(列),行列式变号。如果行列式有两行(列)完全相同,则此行列式为零。把行列式的某一列(行)的各元素乘以同一数然后加到另一列(行)对应的元素上去,行列式不变行列式有一行或者一列的所有元素都是0,行列式的值等于0根据性质求行列式LLdet(intn){LLtmp=1;for(inti=1;i<=n;++i)...

2019-03-27 13:18:00

Matrix-Tree (生成树计数)

生成数计数对于一个无向简单图,nnn个点和n−1n-1n−1条边构成一个生成树,生成树计数就是求这个无向图中一共有几种不同的生成树(任意两边不同)度矩阵n×nn×nn×n的矩阵,统计每个点的度数,只有i=ji=ji=j时矩阵才有正值,其余为零。邻接矩阵n×nn×nn×n的矩阵,如果(u,v)(u,v)(u,v)存在边,对应矩阵g[u][v]=g[v][u]=1g[u][v...

2019-03-27 13:13:18

Codeforces Round #547 (Div. 3)

E.SuperheroBattle题意有一个血量,N次循环攻击,每次可以加血见血。问第几次可以把血量减到0思路如果存在解,必定是N次攻击中的一次终结,所以可以枚举终结点的情况,取一个最小值`#include<bits/stdc++.h>#defineLLlonglong#definePpair<int,int>#include<ti...

2019-03-21 19:57:39

2-SAT

2-Satisfiability2可满足性,2-SAT或仅2SAT是将值赋值给变量的计算问题,每个变量具有两个可能的值,以满足变量对的约束系统。这是一般布尔可满足性问题的一个特例,它可能涉及对两个以上变量的约束,以及约束满足问题,这可以允许对每个变量的值进行两次以上的选择。但与NP完全的那些更一般的问题形成对比,可以在多项式时间内求解2-可满足性。个人理解多个约束条件每个约束有两个限制,判断...

2019-03-19 21:53:47

hihoCoder #1468 : 2-SAT·hihoCoder新春晚会(2-SAT 输出字典序最小的方案)

描述hihoCoder新春晚会正在紧张地筹备中。晚会分为上半场和下半场,总导演小Hi现在要为N个节目安排演出时间(上半场或下半场)。为了描述方便,我们将第i个节目对应两个编号2i-1和2i,分别表示把第i个节目安排在上半场和下半场。由于演员、道具和布景的限制。有些安排之间存在冲突,比如编号1的安排和编号4的安排有冲突,意味着"把第1个节目安排在上半场"同"把第2个节目安排在下半场"有冲突。现...

2019-03-19 21:39:47

HDU-6470 Count (构造矩阵+矩阵快速幂)

ProblemDescriptionFarmerJohn有n头奶牛.某天奶牛想要数一数有多少头奶牛,以一种特殊的方式:第一头奶牛为1号,第二头奶牛为2号,第三头奶牛之后,假如当前奶牛是第n头,那么他的编号就是2倍的第n-2头奶牛的编号加上第n-1头奶牛的编号再加上自己当前的n的三次方为自己的编号.现在FarmerJohn想知道,第n头奶牛的编号是多少,估计答案会很大,你只要输出答案对...

2019-03-17 16:55:36

hihoCoder #1467 : 2-SAT·hihoCoder音乐节

题目链接描述hihoCoder音乐节由hihoCoder赞助商大力主办,邀请了众多嘉宾和知名乐队参与演出。音乐会分为上午、下午两场进行,主办方指定了n首歌让乐队进行演唱。每首歌只会被演唱一次,要么在上午要么在下午。参加音乐会的嘉宾们对于歌曲的演唱时间有一些要求。具体来说,每位嘉宾会指定两首歌曲的演唱时间(上午或者下午)。如果最后实际的演出安排中,两首歌都没有达到嘉宾的要求,那么嘉宾就会对音...

2019-03-15 14:22:25

HDU 4685 Prince and Princess(二分匹配加点建图+强连通分量)

题目链接ProblemDescriptionTherearenprincesandmprincesses.Princesscanmarryanyprince.ButprincecanonlymarrytheprincesstheyDOlove.Forallprinces,givealltheprincessesthattheylov...

2019-03-14 19:49:40

POJ 1904 King's Quest(强连通分量)

题目链接DescriptionOnceuponatimetherelivedakingandhehadNsons.AndtherewereNbeautifulgirlsinthekingdomandthekingknewabouteachofhissonswhichofthosegirlshedidlike.Thes...

2019-03-13 20:38:30

Tarjan 强连通分量

强连通分量图中找到一个最大的子图,使得子图中任意两个节点相互到达。一个点也是一个强连通分量Tarjan构成强连通分量是必定是dfs树的一棵子树,在对树进行dfs的时候记录访问时间dfn和以该节点为根节点的子树的最小编号low,将节点加入栈中并递归它的子节点,子节点在栈中更新根节点的low,子节点没有访问过就继续递归下去。在回溯的时候,当dfn==low表示改点可以通过栈中的节点...

2019-03-13 19:58:40

hihoCoder #1457 : 后缀自动机四·重复旋律7

题目链接描述小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。神奇的是小Hi发现了一部名字叫《十进制进行曲大全》的作品集,顾名思义,这部作品集里有许多作品,但是所有的作品有一个共同特征:只用了十个音符,所有的音符都表示成0-9的数字。现在小Hi想知道这部作品中所有不同的旋律的“和”(也就是把串看成数字,在十进制下的求和,允许有前导0)。答案有可能很大,...

2019-03-12 14:05:34

hihoCoder #1445 : 后缀自动机二·重复旋律5

描述小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。现在小Hi想知道一部作品中出现了多少不同的旋律?输入共一行,包含一个由小写字母构成的字符串。字符串长度不超过1000000。输出一行一个整数,表示答案。样例输入aab样例输出5思路后缀自动机板子子串的种类数=∑maxlen−minlen{\summaxlen-minlen...

2019-03-11 10:19:14

henuyh

关注
  • 学生
  • 中国 河南省 郑州市
奖章
  • 持之以恒
  • 勤写标兵Lv1