分类: 题解

21 篇文章

BZOJ1016 [JSOI2008]最小生成树计数
题面 现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树,而希望知道这个图中有多少个不同的最小生成树。(如果两颗最小生成树中至少有一条边不同,则这两个最小生成树就是不同的)。由于不同的最小生成树可能很多,所以你只需要输出方案数对$31011$的模就可以了。(具有相同权值的边不会超过10条) 思路 这题有点ex啊,不知道矩阵树定理或者最小…
BZOJ2085 [Poi2010]Hamsters
题面 给出 $n$个互不包含的字符串,要求你求出一个最短的字符串 $S$,使得这 $n$ 个字符串在 $S$ 中总共至少出现$m$次,问 $S$ 最短是多少。 思路 把题目转化一下,求出$F[i][j]$表示把$S[j]$接在$S[i]$后面的代价,这个用$substr…
BZOJ1706 [usaco2007 Nov]relays 奶牛接力跑
题面 FJ的N(2 <= N <= 1,000,000)头奶牛选择了接力跑作为她们的日常锻炼项目。至于进行接力跑的地点 自然是在牧场中现有的T(2 <= T <= 100)条跑道上。 农场上的跑道有一些交汇点,每条跑道都连结了两个不同的交汇点 I1_i和I2_i(1 <= I1_i <= 1,000; 1 <…
BZOJ4128 Matrix矩阵BSGS模板题
题面 给定矩阵A,B和模数p,求最小的x满足 A^x = B (mod p) 思路 一眼看去就是BSGS,很显然这个结论在矩阵中也同样适用,那么把乘法替换成矩阵乘法然后矩阵HASH判重即可。(就这么简单) 代码 #include<bits/stdc++.h> #define LL long long #define Mod 998244353…
BZOJ2741【FOTILE模拟赛】L
题面 $FOTILE$得到了一个长为$N$的序列$A$,为了拯救地球,他希望知道某些区间内的最大的连续$XOR$和。即对于一个询问,你需要求出$max(Ai xor Ai+1 xor Ai+2 ... xor Aj)$,其中$l<=i<=j<=r$。为了体现在线操作,对于一个询问$(x,y)$: $l = min ( ((x+la…
NOI Online #3提高组题解
T1水壶 和名字一样水,双指针移动或者前缀和爆草就行。 #include<bits/stdc++.h> #define LL long long using namespace std; inline void read(LL &x) { LL f=1;x=0;char ch=getchar(); while (!isdigit(ch…
BZOJ3166 [HEOI2013]ALO
题面 Welcome to ALO ( Arithmetic and Logistic Online)。这是一个 VR MMORPG, 如名字所见,到处充满了数学的谜题 现在你拥有 n 颗宝石,每颗宝石有一个能量密度,记为 ai,这些宝石的能量 密度两两不同。现在你可以选取连续的一些宝石(必须多于一个)进行融合,设 为 ai, ai+1, …, a…
BZOJ3261 最大异或和
题面 给定一个非负整数序列$a$,初始长度为$n$。 有 $m$ 个操作,有以下两种操作类型: A x:添加操作,表示在序列末尾添加一个数 $x$,序列的长度 $n+1$。Q l r x:询问操作,你需要找到一个位置 $p$,满足$l \leq p \leq r$,使得: $a[p] \o…
BZOJ2115 [Wc2011] Xor
题面 样例输入 第一行包含两个整数$N$和 $M$, 表示该无向图中点的数目与边的数目。 接下来$M$ 行描述 $M$ 条边,每行三个整数$S_i$,$T_i$ ,$D_i$,表示 $S_i$ 与$T_i$之间存在 一条权值为 $D_i$的无向边。 图中可能有重边或自环。 样例输出 仅包含一个整数,表示最大的XOR和(十进制结果),注意输出后加换行…
BZOJ3248 [ioi2013]robots
题目描述 $Marita$ 的弟弟把玩具扔在客厅地板上,乱七八糟。庆幸的是,$Marita$ 设计了一种特殊的机器人可以收拾玩具。 不过,她需要确定哪个机器人去拣起哪个玩具。 一共有$T$个玩具,整数$W[i]$表示这个玩具的重量,整数$S[i]$表示这个玩具的体积。机器人有两种,分别是:弱机器人和小机器人。 有 $A$ 个弱机…