比赛链接:http://codeforces.com/gym/100253
A了B,H,I,K,L 5题, 最后还是没攻下F题
其它题都很顺。
I题是O(n^2)的大水题,比赛时候想烦了
K题没想清楚,其实是个很水的贪心,K题代码在下面
K题code:
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int maxn = 3*1e5+100; int n; int a[maxn], b[maxn], c[maxn], d[maxn]; typedef pair<int, int> pii; vector <pii > ans; int main() { int i, j; scanf("%d", &n); for(i = 1; i <= n; i++) scanf("%d", &a[i]); for(i = 1; i <= n; i++) { j = b[i-1]+1; while(j <= n && a[j]-(j-i+1) >= 0) j++; b[i] = --j; } // for(i = 1; i <= n; i++) // printf("b[%d] = %d\n", i, b[i]); c[n+1] = n+1; for(i = n; i >= 1; i--) { c[i] = c[i+1]-1; while(j >=1 && a[j]-(i-j+1) >= 0) j--; c[i] = ++j; d[j] = max(d[j], i); } // for(i = 1; i <= n; i++) // printf("c[%d] = %d\n", i, c[i]); for(i = 2; i <= n; i++) d[i] = max(d[i-1], d[i]); for(i = 1; i <= n; i++) { if(d[i] > b[i]) { ans.push_back(make_pair(d[i], i)); i = d[i]; } else { ans.push_back(make_pair(i, b[i])); i = b[i]; } } printf("%d\n", ans.size()); for(i = 0; i < ans.size(); i++) printf("%d %d\n", ans[i].first, ans[i].second); return 0; } /* 8 3 4 1 1 3 2 1 3 */