codeforces 777C 题目解答:给你 n 行 m 列的矩阵;然后给你 k 个询问 [l,r]; 问你在第 l 到第 r 行, 是否存在一个列, 这一列的第 l 到第 r 行是升序的; 是输出 YES,否则输出 NO。
【题解】
- /* 对于每一列; 从小到大枚举行; 对于第i行; 看看从第i个元素能有序多长,dp[i]; 然后对于j (j∈[i..i+dp[i]-1]),dp[j] = dp[i]-(i-j); 然后i = i+dp[i]; 记录下第i行,dp[i][1..m]中的最大值; 对于每一个询问; if (l+dp[l]-1>=r) 则yes,否则no;*/
【完整代码】
- #include using namespace std;#define lson l,
- m,
- rt << 1#define rson m + 1,
- r,
- rt << 1 | 1#define LL long long#define rep1(i, a, b) for (int i = a; i <= b; i++)#define rep2(i, a, b) for (int i = a; i >= b; i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d", &x)#define rel(x) scanf("%lld", &x) typedef pair pii;
- typedef pair pll;
- const int dx[9] = {
- 0,
- 1,
- -1,
- 0,
- 0,
- -1,
- -1,
- 1,
- 1
- };
- const int dy[9] = {
- 0,
- 0,
- 0,
- -1,
- 1,
- -1,
- 1,
- -1,
- 1
- };
- const double pi = acos( - 1.0);
- const int N = 1e5 + 100;
- vector a[N];
- int n,
- m,
- k;
- int tdp[N],
- dp[N];
- int main() { //freopen("F:\\rush.txt", "r", stdin); rei(n), rei(m); rep1(i, 1, n) { a[i].pb(-1); int x; rep1(j, 1, m) { rei(x); a[i].pb(x); } } rep1(j, 1, m) { rep1(i, 1, n) { int t = i; while (t + 1 <= n && a[t][j] <= a[t + 1][j]) t++; tdp[i] = t - i + 1; rep1(j, i + 1, t) tdp[j] = tdp[i] - (j - i); i = t; } rep1(i, 1, n) dp[i] = max(dp[i], tdp[i]); } rei(k); int l, r; rep1(i, 1, k) { rei(l), rei(r); if (l + dp[l] - 1 >= r) puts("Yes"); else puts("No"); } return 0;}
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/02-25/17598209.html