观察这个式子 x + ⌈ d x + 1 ⌉ x + \lceil{\frac{d}{x+1}}\rceil x+⌈x+1d⌉
让其最小化，长得很像基本不等式，变形一下， min ( x + 1 + ⌈ d x + 1 ⌉ ) − 1 ≤ n \min ( {x + 1 + \lceil \frac{d}{x + 1}}\rceil) - 1 \leq n min(x+1+⌈x+1d⌉)−1≤n
观察一下，左边的最小值会是， ⌈ 2 × d ⌉ \lceil \sqrt{2 \times d}\rceil ⌈2×d ⌉
之后就直接判断就可
a × b + a + b = c o n c ( a , b ) a \times b + a + b = conc(a, b) a×b+a+b=conc(a,b)
而其中， c o n c ( a , b ) = a × 1 0 k + b conc(a, b) = a\times 10^k + b conc(a,b)=a×10k+b （ k k k 为某一确定的数）
由此可知， b = 1 0 k − 1 b = 10^k - 1 b=10k−1 ，而对于 a a a 没有限制
所以，只需统计满足上述条件的 b b b 即可
这 题 有 优 秀 得 多 的 做 法 ， 参 考 洛 谷 大 佬 \sout{这题有优秀得多的做法，参考洛谷大佬} 这题有优秀得多的做法，参考洛谷大佬
设 f i , j , k f_{i,j,k} fi,j,k 为当前构造到第 i i i 位，序列 a , b a,b a,b 的最后一位分别为 j , k j,k j,k
由于序列 a a a 单调不降，序列 b b b 单调不升，这个状态转移非常好写，同时由于单调性， f i , j , k f_{i,j,k} fi,j,k 和 f i , j + 1 , k f_{i,j+1,k} fi,j+1,k 的转移有很大一部分是相同的，所以只需要在转移全部的 k k k 时，对于每一个 j , k j,k j,k 考虑在 j − 1 , k j - 1,k j−1,k 中没有出现的部分，然后就是 f i , j − 1 , k f_{i,j-1,k} fi,j−1,k 再加上没有出现的部分即可
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <queue> #include <string> #include <map> #include <vector> #include <unordered_map> #include <set> #include <cmath> using std :: vector; using std :: swap; using std :: queue; using std :: set; using std :: map; using std :: string; using std :: unordered_map; using std :: priority_queue; template <typename Tp>Tp Max(const Tp &a, const Tp &b) {return a > b ? a : b;} template <typename Tp>Tp Min(const Tp &a, const Tp &b) {return a < b ? a : b;} template <typename Tp>Tp Abs(const Tp &a) {return a > 0 ? a : -a;} template <typename Tp>void Read(Tp &x) { Tp in = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9') {in = in * 10 + ch - '0'; ch = getchar();} x = in * f; } const int SN = 1000 + 10; const int SM = 10 + 2; const int MOD = 1000000007; typedef long long LL; LL f[SM][SN][SN]; LL g[SN], h[SN]; int n, m; int main(int argc, const char * argv[]) { Read(n), Read(m); for (int j = 1; j <= n; j++) for (int k = j; k <= n; k++) f[1][j][k] = 1; for (int i = 2; i <= m; i++) { for (int j = 1; j <= n; j++) { for (int k = j; k <= n; k++) g[k] = f[i - 1][j][k]; for (int k = n - 1; k >= j; k--) g[k] = (g[k] + g[k + 1]) % MOD; for (int k = j; k <= n; k++) { f[i][j][k] = (f[i][j - 1][k] + g[k]) % MOD; } } } LL ans = 0; for (int j = 1; j <= n; j++) { for (int k = j; k <= n; k++) ans = (ans + f[m][j][k]) % MOD; } printf ("%lld\n", ans); return 0; }对于求最小值最大的问题，上来先二分
于是问题转化为，对于当前的数字矩阵，是否存在两行，其对应位置上的 max ( a x , j , ( a y , j ) ) ≥ k \max (a_{x,j}, (a_{y,j})) \geq k max(ax,j,(ay,j))≥k，
如果 a x , j ≥ k a_{x,j} \geq k ax,j≥k 令 b x , j = 1 , o t h e r w i s e b x , j = 0 b_{x,j} = 1, otherwise \;b_{x,j}=0 bx,j=1,otherwisebx,j=0
于是问题转化为 是否存在两行，其 b x ∣ b y = 2 m − 1 b_{x} \,|\, b_{y} = 2^m - 1 bx∣by=2m−1
利用二进制压位，同时做一个高位前缀和即可
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <queue> #include <string> #include <map> #include <vector> #include <unordered_map> #include <set> #include <cmath> using std :: vector; using std :: swap; using std :: queue; using std :: set; using std :: map; using std :: string; using std :: unordered_map; using std :: priority_queue; template <typename Tp>Tp Max(const Tp &a, const Tp &b) {return a > b ? a : b;} template <typename Tp>Tp Min(const Tp &a, const Tp &b) {return a < b ? a : b;} template <typename Tp>Tp Abs(const Tp &a) {return a > 0 ? a : -a;} template <typename Tp>void Read(Tp &x) { Tp in = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9') {in = in * 10 + ch - '0'; ch = getchar();} x = in * f; } const int SN = 300000 + 10; const int SM = 8 + 2; int a[SN][SM]; int vis[1 << 9]; int n, m, ansx, ansy; bool check(int k) { memset(vis, 0, sizeof vis); int std = (1 << m) - 1; for (int i = 1; i <= n; i++) { int now = 0; for (int j = 0; j < m; j++) if (a[i][j] >= k) now |= (1 << j); vis[now] = i; } for (int sta = std; sta >= 0; sta--) { if (!vis[sta]) continue ; for (int j = 0; j < m; j++) if ((sta & (1 << j)) && (!vis[sta ^ (1 << j)])) vis[sta ^ (1 << j)] = vis[sta]; } for (int i = 1; i <= n; i++) { int now = 0; for (int j = 0; j < m; j++) if (a[i][j] >= k) now |= (1 << j); if (vis[std ^ now]) { ansx = i, ansy = vis[std ^ now]; return true; } } return false; } int main(int argc, const char * argv[]) { Read(n), Read(m); for (int i = 1; i <= n; i++) for (int j = 0; j < m; j++) Read(a[i][j]); int l = 0, r = 1000000000, ans = 0; while (l <= r) { int mid = (l + r) >> 1; if (check(mid)) ans = mid, l = mid + 1; else r = mid - 1; } printf("%d %d\n", ansx, ansy); return 0; }考虑某个元素 x x x，对于位置最小值，发现如果 x x x 一直没有被弹到最开始，则最小值就是其初始位置，否则被弹到开头就是 1 1 1 （因为一直不被弹，别的元素就会被弹到开头， x x x 的位置就至少会大于等于其初始位置）
现在解决最大值，我们发现对于被操作的数 x x x 其可能的位置最大值一定是在被某次操作之前（可能操作很多次，这里是讨论每一次），因为没有被操作时， x x x 的位置关于时间是不降的，所以我们就只需要对每次操作前的位置取 m a x max max 即可
而对于没有被操作的数，只需要在所有操作完成后，类似上面那样即可
于是，我们需要实现，在某个位置上删除一个数，添加一个数，查询某个区间有多少个数，这里直接用线段树实现
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <queue> #include <string> #include <map> #include <vector> #include <unordered_map> #include <set> #include <cmath> using std :: vector; using std :: swap; using std :: queue; using std :: set; using std :: map; using std :: string; using std :: unordered_map; using std :: priority_queue; template <typename Tp>Tp Max(const Tp &a, const Tp &b) {return a > b ? a : b;} template <typename Tp>Tp Min(const Tp &a, const Tp &b) {return a < b ? a : b;} template <typename Tp>Tp Abs(const Tp &a) {return a > 0 ? a : -a;} template <typename Tp>void Read(Tp &x) { Tp in = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9') {in = in * 10 + ch - '0'; ch = getchar();} x = in * f; } const int SN = 300000 + 10; const int SM = SN << 1; int sum[SM << 2]; int pre[SN], next[SN], a[SN], pos[SN]; bool vis[SN]; int n, m; void Modify(int x, int C, int l, int r, int rt) { if (l == r) { sum[rt] += C; return ; } int mid = (l + r) >> 1; if (x <= mid) Modify(x, C, l, mid, rt << 1); else Modify(x, C, mid + 1, r, rt << 1 | 1); sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } int Query(int QL, int QR, int l, int r, int rt) { if (QL <= l && QR >= r) return sum[rt]; int mid = (l + r) >> 1, ans = 0; if (QL <= mid) ans += Query(QL, QR, l, mid, rt << 1); if (QR > mid) ans += Query(QL, QR, mid + 1, r, rt << 1 | 1); return ans; } int main(int argc, const char * argv[]) { Read(n), Read(m); for (int i = 1; i <= m; i++) Read(a[i]), vis[a[i]] = 1; for (int i = 1; i <= n; i++) if (vis[i]) pre[i] = 1, next[i] = i; else pre[i] = i, next[i] = i; for (int i = 1; i <= n; i++) Modify(i + m, 1, 1, n + m, 1), pos[i] = i + m; for (int i = 1; i <= m; i++) { int now = a[i]; next[now] = Max(next[now], n - Query(pos[now] + 1, n + m, 1, n + m, 1)); Modify(pos[now], -1, 1, n + m, 1); pos[now] = m - i + 1; Modify(pos[now], 1, 1, n + m, 1); } for (int i = 1; i <= n; i++) next[i] = Max(next[i], n - Query(pos[i] + 1, n + m, 1, n + m, 1)); for (int i = 1; i <= n; i++) printf("%d %d\n", pre[i], next[i]); return 0; }