1 C202044zxy

尚未进行身份认证

暂无相关简介

等级
TA的排名 1w+

[HNOI2009]梦幻布丁

一、题目点此看题二、解法可以把颜色的修改看做合并,那么我们用启发式合并即可,用链表维护,时间复杂度O(nlog⁡n)O(n\log n)O(nlogn)#include <cstdio>#include <iostream>using namespace std;const int M = 1000005;int read(){ int num=0,flag=1;char c; while((c=getchar())<'0'||c>'9'

2020-05-29 12:20:29

Treediff

一、题目题目描述nnn个点的树,有mmm个叶子结点,只有叶子结点有权值,问每一个非叶节点的子树内选两个不同的叶子的最小差,如果不存在输出231−12^{31}-1231−1数据范围1≤m<n≤500001\leq m<n\leq 500001≤m<n≤50000二、解法启发式合并的版题,随便取一个子树的setsetset,然后启发式合并,把小的并到大的那里去,随便算答案就行了。证明一下这样做的复杂度,每次合并后的数量一定是小的集合大小的两倍,最开始的大小都为111,合并ttt

2020-05-29 11:36:57

[NOI Online #3 提高组]优秀子序列

一、题目点此看题二、解法首先有一个朴素dpdpdp,因为每个数位都只会最多出现111次,而且出现数位相同的不同情况最后也可以一起算答案(和一定),那么我们只需要统计出方案数,dp[i]dp[i]dp[i]为二进制位出现的装压为iii,转移枚举包含iii的状态jjj,设a[i]a[i]a[i]为值iii出现次数,000需要单独考虑,转移为:dp[j]=dp[j⊕i]×a[i]dp[j]=dp[j\oplus i]\times a[i]dp[j]=dp[j⊕i]×a[i]这样做O(min⁡(a,n)a)

2020-05-28 15:49:53

[NOI Online 3 提高组]魔法值

一、题目点此看题二、解法首先要理解这个aaa天,一个f0f_0f0​有贡献的话一定是111和这个点有一条路径,那么我们只需要考虑这个长度为aaa的路径个数奇偶就行了,奇数的话计入贡献。现在就不难想到矩阵快速幂,求出邻接矩阵的aaa次方即可。这样做的时间复杂度是O(n3qlog⁡a)O(n^3q\log a)O(n3qloga),就算用bitsetbitsetbitset优化也要T\text{T}T,考虑我们只需要知道111到各个点的情况,那么我们预处理邻接矩阵的222幂次次方,每次用第一行去乘,相当

2020-05-27 15:56:42

[模板] 扩展BSGS

一、题目点此看题二、解法求解关于xxx的方程:yx=zmod  py^x=z\mod pyx=zmodp主要就是处理yyy和ppp不互质的情况,我们把这个方程重写形式:yx+bp=zy^x+bp=zyx+bp=z此时我们把方程全部同时除以d=gcd⁡(y,p)d=\gcd(y,p)d=gcd(y,p):ydyx−1+bpd=zd\frac{y}{d}y^{x-1}+b\frac{p}{d}=\frac{z}{d}dy​yx−1+bdp​=dz​前面的就可以当做系数了,如果ddd除不尽zzz就无解

2020-05-27 15:49:44

[SDOI2015]寻宝游戏

一、题目点此看题二、解法本题其实是问一个极小联通子图总权值的222倍,有一个关键结论,如果我们把给定的关键点aaa按dfndfndfn排序,那么答案就是:dis(a1,a2)+dis(a2,a3)....+dis(an,a1)dis(a_1,a_2)+dis(a_2,a_3)....+dis(a_n,a_1)dis(a1​,a2​)+dis(a2​,a3​)....+dis(an​,a1​)这个结论也不难证明,主要利用了dfndfndfn相近的两点距离就较近(可以理解为一个贪心),那么我们就可以按d

2020-05-23 21:22:04

[NOI2017]蔬菜

一、题目点此看题二、解法每个水果是逐渐变质的,我们可以想到不守交规这道贪心题,也就是我们先按权值从大到小排序,然后从变质的最后时间往前填充就行了,至于sss的额外收益,新建一个水果就行了。虽然变质是分阶段的,但是我们不需要把水果拆开,填充的时候逐渐增加水果的质量即可。我们还要用并查集优化填充的过程,填满mmm就不再填了。还有一个问题,我们只能针对一个固定的天数做这些操作,但是多组天数怎么办呢?我们可以先跑出一个极大天数填入的物品方案,对于一个较小的天数这些物品都是可以随便取的,iii天我们就取权值

2020-05-23 21:06:32

[学习笔记] Pell方程

感谢这两位巨佬,部分思路和图片来源于他们的启发:IBN5100The-Pines-of-Star是什么?Pell\text{Pell}Pell方程主要用来解决下面形式的方程:x2−dy2=1x^2-dy^2=1x2−dy2=1其中ddd是正数且不是完全平方数,若x,yx,yx,y都为整数的解称为这个方程的解,其中x+ydx+y\sqrt dx+yd​最小的那组解就称为Pell\text{Pell}Pell方程的基本解,我们要解决两个问题:求出基本解和用它扩展出所有解。基本解?本文结论大多不给出

2020-05-22 11:13:15

CF830C Bamboo Partition

一、题目点此看题二、解法首先有一个等价变化:(ai−1)%d+1=ai−ai−1d×d(a_i-1)\% d+1=a_i-\frac{a_i-1}{d}\times d(ai​−1)%d+1=ai​−dai​−1​×d我们再来重写一下题目表达式:∑d−ai+ai−1d×d≤k\sum d-a_i+\frac{a_i-1}{d}\times d\leq k∑d−ai​+dai​−1​×d≤kd(n+∑ai−1d)≤k+∑aid(n+\sum \frac{a_i-1}{d})\leq k+\sum a

2020-05-21 16:04:19

HDU 6395 Sequence

一、题目点此看题二、解法最难处理的是pn\frac{p}{n}np​,由于这个最多只有根号个取值,我们可以数论分块,对于每个块内都跑一边矩阵加速。#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int mod = 1e9+7;int read(){ int x=0,flag=1;char c; while((c=getchar())&l

2020-05-21 15:27:11

HDU 2620 Ice Rain

一、题目点此看题二、解法首先有一个对于模数的等价替换:k%i=k−ki×ik\%i=k-\frac{k}{i}\times ik%i=k−ik​×i那么原问题就变成了:∑k−ki×i\sum k-\frac{k}{i}\times i∑k−ik​×i如果你学过数论分块的话应该就可以秒了。#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int

2020-05-21 15:23:49

可持久化并查集

一、题目点此看题

2020-05-21 14:11:56

数学上来先打表

一、题目点此看题二、解法如果是222操作直接连向前面的点,否则连向上一个点,这样dfsdfsdfs就可以得到一个顺序,问题就变成了只需要加入单条边和回退这条加入的边,用启发式合并的并查集就可以了。为了询问我们需要值域分块,合并和回退的时候就维护一下这个块,询问的时候挨个扫值域,确定到一个值域中,然后我们就可以暴力地访问这个值域里的值,看他和当前点是不是同根,如果是的话减排名就行了。#include <cstdio>#include <vector>#include &l

2020-05-20 21:57:13

[POJ 2912]Rochambeau

一、题目点此看题题目描述n个小伙伴进行猜拳游戏,除了一个比较聪明的家伙以外,其他人只会出单一的一种,给出m种猜拳的结果,要求找出那个比较聪明的小伙伴序号,并且输出在第几次猜拳可以确定。数据范围1≤n≤500,0≤m≤20001\leq n\leq 500,0\leq m\leq 20001≤n≤500,0≤m≤2000二、解法首先可以枚举聪明的人,跟聪明人有关的猜拳直接忽略,然后看剩下的猜拳会不会冲突,这里可以用带权并查集,我们先将查询的结果赋权值,===当做000,>>>当

2020-05-19 21:07:05

HDU 3047 Zjnu Stadium

一、题目点此看题题目描述nnn个人,mmm个关系,每个关系描述为AAA和BBB顺时针距离为ddd,每个询问由前面的关系为判定依据,如果错误则后面无视这个关系,问最后会有多少个错误的关系。二、解法带权并查集好题,我们先规定一个合并方向,也就是把BBB合并到AAA的上面,每个节点维护一个disdisdis,表示到根的顺时针距离,我们现在考虑把BBB并到AAA上面的时候如何修改disdisdis,请看下图。容易发现yyy到rxrxrx的距离应该是dx+mdx+mdx+m,已经有了一个dydydy,所

2020-05-19 16:40:26

[FJOI2015]火星商店问题

一、题目点此看题二、解法外层就是一个线段树,所有节点上保存一个tiretiretire树,我们完全可以把所有tiretiretire树压在一起,写一个可持久化tiretiretire树,把这个可持久化理解成前缀和,lower_boundlower\_boundlower_bound找出一个答案产生的后缀,差分之后询问就行了。#include <cstdio>#include <vector>#include <iostream>using namespace

2020-05-18 22:13:47

CF576E Painting Edges

一、题目点此看题二、解法这道题很特殊,我们在做线段树分治需要边询问边插入,具体来说就是把询问搞到线段上,如果一个询问lll成功的话那么我们就把[l+1,nxt−1][l+1,nxt-1][l+1,nxt−1]之间都插入这个边,其他就是正常线段树分治了。一开始初始化的时候nnn没有赋值就锅了,还是需要写一个初始化函数。#include <cstdio>#include <vector>#include <iostream>using namespace st

2020-05-18 16:09:17

[CTSC2016]时空旅行

一、题目点此看题二、解法可以看出这些平行时空呈树形结构,每个星球都会出现在一段连续的dfndfndfn序中,而我们正是要对每个时空的星球中找最小值,那么可以把星球打在dfndfndfn的线段树上,使用线段树分治。考虑怎么从若干个点中选取最优解,首先y,zy,zy,z没有卵用,发现是平方的柿子,考虑斜率优化,x[j]>x[k]x[j]>x[k]x[j]>x[k]且jjj更优的条件:(X−xj)2+cj<(X−xk)2+ck(X-x_j)^2+c_j<(X-x_k)^2+

2020-05-15 11:46:36

CF1140F Extending Set of Points

一、题目点此看题二、解法我们考虑把每个点拆成两个点,然后每个点对就是这个二分图里面的边。考虑一个连通的二分图(用给出的点对连接)的所有边都会存在,这里给出归纳法的证明。一开始都是单个点,所以满足,如果加入一条(x1,y1)(x_1,y_1)(x1​,y1​)的边,那么和x1x_1x1​相连的yyy,和y1y_1y1​相连的xxx都会连接,原来是一个完全二分图的话现在还会是一个完全二分图。可以用启发式合并并查集来维护这个二分图,回退就记录一下就行了,维护一下xxx区域的点和yyy区域的点,贡献就是乘

2020-05-15 10:12:17

CF813F Bipartite Checking

一、题目点此看题二、解法把每条边出现时间段打到线段树上面,然后跑一遍线段树。问题在于维护一个树的结构,如果一条边连接的两点暂时还不连通,我们就连接一波。否则我们看这条非树边构成的环是不是奇环,如果是的话直接不符合条件,否则没有影响(这里你需要考虑两条非树边构成的环)可以用启发式合并的并查集,可以算一个点到根的距离的奇偶disdisdis,合并(u,v)(u,v)(u,v)需要连接一条dis(u)⊕dis(v)⊕1dis(u)\oplus dis(v)\oplus 1dis(u)⊕dis(v)⊕1,

2020-05-14 21:26:47

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。