# 离散化

Acwing255 第k小数

原题链接:Acwing255

题目描述:给定长度为 N 的整数序列 A,下标为 1 ∼ N。

现在要执行 M 次操作,其中第 i 次操作为给出三个整数 $l_i,r_i,k_i$,求 $A[l_i],A[l_i+1],…,A[r_i]$ (即 $A$ 的下标区间 $[l_i,r_i]$)中第 $k_i$ 小的数是多少。

……

READ MORE

Acwing345 牛站

原题链接:Acwing345

题目大意:给定一张由T条边构成的无向图,点的编号为1~1000之间的整数。

求从起点 S 到终点 E 恰好经过 N 条边(可以重复经过)的最短路。

……

READ MORE

Acwing239 奇偶游戏

原题链接:Acwing239

题目大意:小A和小B在玩一个游戏。

首先,小A写了一个由0和1组成的序列S,长度为N。

然后,小B向小A提出了M个问题。

在每个问题中,小B指定两个数 l 和 r,小A回答 S[l~r] 中有奇数个1还是偶数个1。

机智的小B发现小A有可能在撒谎。

例如,小A曾经回答过 S[1~3] 中有奇数个1, S[4~6] 中有偶数个1,现在又回答 S[1~6] 中有偶数个1,显然这是自相矛盾的。

请你帮助小B检查这M个答案,并指出在至少多少个回答之后可以确定小A一定在撒谎。

即求出一个最小的k,使得01序列S满足第1~k个回答,但不满足第1~k+1个回答。

……

READ MORE

Acwing237 程序自动分析

原题链接:Acwing237

题目大意:考虑一个约束满足问题的简化版本:假设$x_1,x_2,x_3,…$代表程序中出现的变量,给定$n$个形如$x_i=x_j$或$x_i≠x_j$的变量相等/不等的约束条件,判定上述所有约束条件是否能同时被满足。

现在给出一些约束满足问题,请分别对它们进行判定。

……

READ MORE

Recents
Categories
Tags
Links