2 C202044zxy

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 1w+

[NOI2018] 归程

一、题目点此看题二、解法先弄清楚本题要求什么,实际上那个到111的距离就是个摆设,因为我们可以直接求dijkstra\tt dijkstradijkstra,那么问题就变成了 保留水位线大于ppp的边,uuu所在块连通性是怎样的,我们只需要把这个维护出来就行了。第一种显然的思路是可持久化并查集,太麻烦了。kruskall\tt kruskallkruskall重构树可以很好的解决这个问题,想象我们需要的边只可能是最大生成树上的边,如果我们在跑生成树的时候构建重构树,那么就具有下列性质:点代表的是

2020-10-27 21:11:39

[BJOI2018] 治疗之雨

一、题目点此看题二、解法状态定义很显然,设dp[i]dp[i]dp[i]为从生命iii减少到000的期望轮数,转移:dp[i]=1+∑j=1i+1dp[j]×Qi,jdp[i]=1+\sum_{j=1}^{i+1} dp[j]\times Q_{i,j}dp[i]=1+j=1∑i+1​dp[j]×Qi,j​其中Qi,jQ_{i,j}Qi,j​表示生命值一次从iii转移到jjj的概率,先考虑如何算它,题目限制较多,最宜分类讨论(下面表达式的系数是讨论增加生命值那次的概率):Qi,j={0i=n,j=

2020-10-25 16:35:44

「LibreOJ β Round #5」最小倍数

一、题目点此看题二、解法这题肯定是勒让德定理的题了,对于每个质数我们可以算出来一个满足条件的nnn,因为质数之间是独立的,然后答案就是这些nnn中的最大值了(注意至少是111)对于某一个质数ppp怎么求他的nnn呢?我们可以先二分这个nnn,然后用勒让德定理求解(求出的是有多少个因子ppp)。但是这样做是O(nlog⁡2n)O(n\log^2n)O(nlog2n)的,无法通过此题。考虑勒让德定理的本质,其实就是把数转成ppp进制然后算贡献,举个栗子,比如对于三进制下的100001000010000

2020-10-25 11:28:16

[JSOI2016]独特的树叶

一、题目点此看题二、解法其实就是判断树同构,然后自然联想到了树hashhashhash简单介绍一下树哈希的方法,我们先求出子树的hashhashhash值g[i]g[i]g[i],我用的是质数+++自然溢出的方式,设p[i]p[i]p[i]为第iii个质数,那么转移:g[u]=1+∑g[v]×p[siz[v]]g[u]=1+\sum g[v]\times p[siz[v]]g[u]=1+∑g[v]×p[siz[v]]那么对于uuu点为根的哈希值hs[u]hs[u]hs[u],就可以再跑一遍dfs

2020-10-25 09:52:09

[SGU 183] Painting the balls

一、题目来源不详,好像是个外国网站。peterpeterpeter 把 nnn 个白球排成一列,他想把一些白球刷为黑色,且任意连续 mmm 个球中至少要有 222 个黑球,peterpeterpeter 知道他需要 CiC_iCi​ 的燃料刷第 iii个球,你的任务是找出 peterpeterpeter 所需的最少的燃料达到目标。2≤n≤104,2≤m≤100,m≤n2\leq n\leq10^4,2\leq m\leq 100,m\leq n2≤n≤104,2≤m≤100,m≤n二、解法数据范围

2020-10-24 16:19:29

[nowcoder 2020] 牛半仙的魔塔(增强版)

一、题目点此看题二、解法值得一说的是本题的数据范围,你看他构造得这么恶心,就知道是为了避免某些情况。人的攻击力一定比怪高,那么人一定打的掉血。怪物的伤害很高,人无论如何都会掉血。这告诉我们只用求减免的伤害最多就行了,也不用多么麻烦的判无解(还没有无解的数据呢!)不妨从贪心的角度思考,俗话说的好:十个贪心九个排。想要知道最优的选取顺序,可以排序!推理排序规则的方法就是我们看最好的排列方法满足什么条件,然后按照这个条件排就可以了,现在我带着你们来推一推,假设i,ji,ji,j是两个相邻的怪物(iii先被

2020-10-24 15:22:15

[nowcoder 2020] 牛半仙的妹子Tree

一、题目点此看题二、解法这题是个套路题,两种方法都是套路(我都见过但是不会应用,该反思!)0x01 树链剖分

2020-10-23 21:09:26

[nowcoder 2020] 牛半仙的妹子数

一、题目点此看题二、解法考试时候先打了个表,首先我们可以确定A+B+CA+B+CA+B+C是一个定值,一开始我想去维护AAA和BBB然后去算CCC,但是这样会很难算,AAA和BBB的变化是极不规律的,我们不妨去研究CCC在重复一遍,p=A+B+Cp=A+B+Cp=A+B+C是定值,打表如下(数据是大样例):好像CCC是断续乘222的,结合我们唯一的一个性质,开动我们的想象力,猜CCC的变化是×2mod  p\times2\mod p×2modp的,然后带回去验证一下。知道结论之后,证明就非常简单

2020-10-23 19:09:24

[nowcoder 2020] 牛牛的凑数游戏

一、题目点此看题

2020-10-21 17:43:16

[APIO 2018] 新家

一、题目点此看题二、解法不难发现答案具有单调性,所以对于每个询问都可以二分答案。具体来说对于位置xxx,如果答案≥m\geq m≥m,那么等价于存在一种店在(x−m,x+m)(x-m,x+m)(x−m,x+m)不存在店,但是区间并不好维护,可以使用前驱来判断存在与否,那么等价于在[x+m,inf)[x+m,inf)[x+m,inf)存在店的前驱≤x−m\leq x-m≤x−m,那么我们只需要判断[x+m,inf)[x+m,inf)[x+m,inf)前驱的最小值mn≤x−mmn\leq x-mmn≤x

2020-10-21 17:01:23

[nowcoder 2020] 移动

一、题目点此看题二、解法首先请明确两点:可以往回走!dpdpdp贪心死活想不出来的时候可以考虑下图论,思路要打开!其实这道题如果用最短路的话就比较好想,我们的目的是让每个点向相邻的点转移(这样可以兼顾回退、等待、前进),但是我们要知道时间,怎么办?我们知道时间的目的是为了确定闸门的关闭,既然不能知道具体的时间,我们就通过闸门的关闭时间段来划分时间段,夹在两个之间的就当做一个可通行的状态,通过最短路可求出到达这个状态的最小时间,状态的编号就用夹住它的前面关闭时间段的编号,状态数是O(n+m)O(n+m

2020-10-21 16:23:07

小 Y 的背包计数问题

一、题目https://loj.ac/problem/6089

2020-10-20 22:14:37

CF1394D Boboniu and Jianghu

一、题目点此看题二、解法我们把边定向,如果a[u]>a[v]a[u]>a[v]a[u]>a[v],那么我们就把边定向成v−>uv->uv−>u知道了这一点后考虑dpdpdp,我们需要解决的情况是a[u]=a[v]a[u]=a[v]a[u]=a[v]就不能直接定向,设dp[u][0/1]dp[u][0/1]dp[u][0/1]为uuu到父亲的边连入///连出...

2020-10-16 20:53:43

CF1408E Avoid Rainbow Cycles

一、题目点此看题本题的翻译似乎叫彩虹圈,好浪漫呀qwqqwqqwq二、解法给边染色然后找环特别不好做,而且边数都会炸。考虑把集合里面的所有点接在这个集合上,这个集合就可以代表颜色,用边的话可以通过到这个新建点中转完成,仔细考虑这样建出来是一个二分图。考虑这个图的性质,如果这个图存在环,那么原图也存在环,因为可以用点到集合的边等效代换原图中点到点的边。问题变成了保留权值最大的边使得这个图不存在环,直接最大生成树。#include <cstdio>#include <algori

2020-10-11 16:47:22

CF1416D Graph and Queries

一、题目点此看题二、解法删边有一个经典的套路就是变成加边离线,但是操作111必须要按照时间顺序来,蛋疼。这时候就要介绍一下kruskal\tt kruskalkruskal重构树(以前我还不知道有这个东西),在合并来个联通块的时候我们新建一个点连接这两个合并点的根,就建成了重构树。离线的时候可以建出我们的重构树,因为重构树一个重要的性质就是新建点的子树代表了某个时刻这些点是连在一起的。询问的时候我们找到代表当时联通性的这个祖先,怎么找呢?我们把联通的时间放在这个祖先上,满足联通时间≥\geq≥当前

2020-10-11 16:16:44

CF1389G Directing Edges

一、题目点此看题二、解法这个图很不舒服,如果想把它转化成舒服的结构-----树,那么我们就要考虑缩点。这个图的性质能不能缩点呢?怎么缩点呢?考虑缩成边双联通分量,我们就可以把这个部分设置成互相可到达的有向图,利用的性质就是边双任意两点之间有两条经过边完全不同的路径。转化成树之后,对于这种规划问题我们考虑树形dpdpdp,设f[i]f[i]f[i]为iii子树内所有所有特殊点到iii的最大收益,如果我们把某一条边加上,那么可以获得f[v]f[v]f[v]的贡献,初始可以获得当前点上的收益a[u]a[

2020-10-11 14:47:30

[HDU 5304] Eastest Magical Day Seep Group‘s Summer

https://vjudge.net/contest/397200#status/C202044zxy/C/0/

2020-10-07 19:43:11

小 Y 和恐怖的奴隶主

https://www.luogu.com.cn/problem/P4007

2020-10-07 19:16:44

[POJ 1220] NUMBER BASE CONVERSION

一、题目点此看题二、解法本篇题解将详细介绍如何进行大数进制转化(实现非常简单,不用高精度)我们考虑从高位到低位的转化过程,如下图:然后从小到大地去修改bbb数组就行了,每个值都乘上aaa,再维护一个余数(一开始是mmm),进个位就行了。#include <cstdio>#include <cstring>const int M = 1005;int read(){ int num=0,flag=1;char c; while((c=getchar

2020-10-07 18:50:18

[USACO18OPEN]Out of Sorts P

一、题目点此看题二、解法这道题真的考思维。有一个常见的问题转化,求冒泡的区间长度其实等价于求每个点被冒泡的次数。那么这个次数好不好求呢?我们需要考虑分割点的含义,如果一个序列全是分割点那么它就是有序的,然后对于一个位置如果两边都是分割点那么它就在正确的位置上。如果求出了分割点出现的时间就知道了每个点冒泡的次数,因为他取决与两边分割点出现的最大时间。时间怎么求?我们把iii和i+1i+1i+1的分割点放在iii上,位置iii对应的应出现值是iii,如果后面有比iii小的就必须要移到iii前面,他们的

2020-10-07 17:09:32

查看更多

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