题面 题目描述 小 $T$ 打算在城市 $C$ 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的,小 $T$ 希望快餐店的地址选在离最远的顾客距离最近的地方。 快餐店的顾客分布在城市 C 的 $N$ 个建筑中,这 $N$ 个建筑通过恰好 $N$条双向道路连接起来,…
题面 题面描述 给定一个长度为$n$的序列$a_{1∼n}$。 $q$次询问,每次给出一个区间$[l,r]$,要求找出$[l,r]$的一个子区间$[l′,r′]$,满足它不包含$[l,r]$中所有种类的数,且它的长度$r′−l′+1$最大。你只需输出这个最大长度。 特别提醒,$[l′,r′]$可以是长度为$0$的空区间。 输入格式 第一行一个正整数…
前言 卧槽,距我上次更新博客已经整整1年了... 关于本人之前一直沉迷whk与fgo,久久未动OI和博客,眼看即将NOIP2021,所以我重新开始写博客记录一下我的康复训练之旅。 题目 题面描述 有一个$1∼n$的排列,其中有$m$个位置上的数缺失了。 已知这个排列的逆序对数恰好为$k$,求有多少种可能的排列。 输入格式 第一行两个正整数$n,k$…
题面 现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树,而希望知道这个图中有多少个不同的最小生成树。(如果两颗最小生成树中至少有一条边不同,则这两个最小生成树就是不同的)。由于不同的最小生成树可能很多,所以你只需要输出方案数对$31011$的模就可以了。(具有相同权值的边不会超过10条) 思路 这题有点ex啊,不知道矩阵树定理或者最小…
题面 给出 $n$个互不包含的字符串,要求你求出一个最短的字符串 $S$,使得这 $n$ 个字符串在 $S$ 中总共至少出现$m$次,问 $S$ 最短是多少。 思路 把题目转化一下,求出$F[i][j]$表示把$S[j]$接在$S[i]$后面的代价,这个用$substr…
题面 FJ的N(2 <= N <= 1,000,000)头奶牛选择了接力跑作为她们的日常锻炼项目。至于进行接力跑的地点 自然是在牧场中现有的T(2 <= T <= 100)条跑道上。 农场上的跑道有一些交汇点,每条跑道都连结了两个不同的交汇点 I1_i和I2_i(1 <= I1_i <= 1,000; 1 <…
题面 给定矩阵A,B和模数p,求最小的x满足 A^x = B (mod p) 思路 一眼看去就是BSGS,很显然这个结论在矩阵中也同样适用,那么把乘法替换成矩阵乘法然后矩阵HASH判重即可。(就这么简单) 代码 #include<bits/stdc++.h> #define LL long long #define Mod 998244353…
题面 $FOTILE$得到了一个长为$N$的序列$A$,为了拯救地球,他希望知道某些区间内的最大的连续$XOR$和。即对于一个询问,你需要求出$max(Ai xor Ai+1 xor Ai+2 ... xor Aj)$,其中$l<=i<=j<=r$。为了体现在线操作,对于一个询问$(x,y)$: $l = min ( ((x+la…
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…
题面 Welcome to ALO ( Arithmetic and Logistic Online)。这是一个 VR MMORPG, 如名字所见,到处充满了数学的谜题 现在你拥有 n 颗宝石,每颗宝石有一个能量密度,记为 ai,这些宝石的能量 密度两两不同。现在你可以选取连续的一些宝石(必须多于一个)进行融合,设 为 ai, ai+1, …, a…