RainAir
My OI Blog
RainAir

题解
文章归档

「CF623E」 Transforming Sequence

题目链接 没想到非 Chinese Round 也会出这么毒瘤的题目...... 题目大意:对于正整数序列 $A$,定义序列 $B$: $B_1=A_1,B_i=B_{i-1}\ or\ A_i,i\in[2,n]B $ 其中 or 为位或运算。 每一个序列合法,满足对于$ \forall i\in[1,n]$,有 $A_i\in[1,2^k])$ 而且对于 $\fo…

   45   2019-03-14 去围观

构造杂题

占坑,有时间补。 (如果咕咕咕的时间超过半个月了回来叫我)

   61   2019-03-09 去围观

「BZOJ5415」「NOI2018」归程

题目链接 题解 首先我们尝试把不能被车经过的边删掉,得到了一张新图。这个新图上每一个连通块的答案都相同。 所以 Dijkstra 是首先要跑的。然后我们发现如果可以离线的话我们可以把边和询问放在一起排序,用普通的并查集维护一下每个连通块到 $1$ 节点的最短距离就…

   157   2019-02-07 去围观

「BZOJ4906」「BJOI2017」喷式水战改

题目链接 题目大意是对于每种物品被划分到不同的组里会产生不同的贡献,求一种最大的划分(这里的划分是连续一段划分到一起),并且要动态维护这个东西。 我们首先考虑静态如何做这个东西,显然我们可以设出一个极为暴力的状态:$f(l,r,i,j)$ 表示燃料 $[l,r]$ 使用…

   171   2019-02-01 去围观

「BZOJ2002」「HNOI2010」弹飞绵羊

题目描述 题目链接 某天,Lostmonkey 发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置,每个装置设定初始弹力系数 $k_i$,当绵羊达到第 $i$ 个装置时,它会往后弹 $k_i$ …

   137   2019-01-29 去围观

「CF487E」Tourists

题目链接 题目描述 给定 $n$ 个点 $m$ 条边的连通点权无向图。 有 $q$ 个操作,要么修改一个点的点权,要么询问两点间经过一条从 $s$ 到 $t$ 的简单路径,路径上最小点权最小值是多少。 $ n,m,q \leq 10^5 $. 题解 问的是所有可能路径上的最小点权的最小值,那我们…

   186   2019-01-23 去围观

「BZOJ 3669」「NOI2014」魔法森林

题目链接 题目简述 给定 $N$ 个点 $M$ 条边的无向图,每条边有两个权值 $a$ 与 $b$ 。求一条 $1$ 到 $n$ 的路径使得路径经过边的最大 $a$ 与最大 $b$ 的和最小。无法到达输出 $-1$。 $ n \leq 50000,m \leq 100000$。 解题报告 乱入:这个题目只需要枚举 a 然后动…

   239   2019-01-06 去围观

「POJ1966」Cable TV Network

题目链接 题目描述 给定一张无向图,求让这张无向图不连通应删去的点的最小个数。 解题报告 首先发现这很像割的定义,只不过由边转化为了点。 那我们不妨拆点来对边进行限制:其中对于每个点 $v$ 拆成 $v$ 和 $v'$ ,然后我们在这两个点之间连一条容量为 $1$ 的边…

   153   2018-12-24 去围观

「BZOJ 1280」Emmy卖猪pigs

题目链接 题目描述 Emmy 在一个养猪场工作。这个养猪场有M个锁着的猪圈,但 Emmy 并没有钥匙。顾客会到养猪场来买猪,一个接着一个。每一位顾客都会有一些猪圈的钥匙,他们会将这些猪圈打开并买走固定数目的猪。 所有顾客有的钥匙和他们需要买猪的数量在事先都告诉了…

   100   2018-12-14 去围观

密码保护:「19省选1」题解

这篇文章受密码保护,输入密码才能看哦

   234   2018-12-05 去围观
加载更多
文章归档