cf1557D. Ezzat and Grid

題意：

有n行，每行有$10^9$列，僅僅由0和1構成
現在給你1的存在位置，(i,l,r)表示第i行的第l列到第r列全為1
你可以刪除任意一行i，刪除后，第i-1行和第i+1行為相鄰
現在我們要求求最多的行數，使得每個相鄰兩行最少有一列都是1(可以理解成上下相鄰1)，并輸出刪除了哪些行

題解：

對于i行，我們考慮前i-1行個是與i行滿足要求的(即存在相鄰1)。我們用線段樹維護一個pair<int,int>sum
sum.first表示以id為結尾所保留的最大行數
sum.second=id:表示以id為結尾的情況
因為1的出現都是連續的，我們想查找與第i行滿足情況的行數，就在第i行出現1的區間（例如[l,r]）,我們就查看所有[l,r]區間內的值，取最大值得到sum(相當于取之前的最大值接著當前的i)。sum為與第i行滿足情況且保留行數最多的某一行。查詢完后，要將第i行的情況插入到線段樹中，在區間[l,r]中插入我們的ans(ans.second=i,ans.first=sum.first+1)
為了方便輸出，我們用一個path來實現記錄路徑
講的可以不是很明白，詳細可以看看代碼

代碼：

改了一個多小時，終于改出來了

// Problem: D. Ezzat and Grid // Contest: Codeforces - Codeforces Round #737 (Div. 2) // URL: https://codeforces.com/contest/1557/problem/D // Memory Limit: 256 MB // Time Limit: 2500 ms // Data:2021-08-23 15:24:28 // By Jozky#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef LOCALstartTime= clock();freopen("in.txt", "r", stdin); #endif } void Time_test() { #ifdef LOCALendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn= 1e6 + 9; vector<PII> vec[maxn]; int num[maxn]; int tot= 0; struct tree {int l, r;int lazy= 0;PII maxx; } tr[maxn << 2]; void pushup(int rt) {tr[rt].maxx= max(tr[rt << 1].maxx, tr[rt << 1 | 1].maxx); } void solve(int rt, PII val) {tr[rt].maxx= val;tr[rt].lazy= 1; } void pushdown(int rt) {if (tr[rt].lazy == 0)return;solve(rt << 1, tr[rt].maxx);solve(rt << 1 | 1, tr[rt].maxx);tr[rt].lazy= 0; } void build(int rt, int l, int r) {tr[rt].l= l;tr[rt].r= r;tr[rt].lazy= 0;tr[rt].maxx= {0, -1};if (l == r) {return;}int mid= (l + r) >> 1;build(rt << 1, l, mid);build(rt << 1 | 1, mid + 1, r);pushup(rt); } void update(int rt, int l, int r, PII x) {if (tr[rt].r < l || tr[rt].l > r)return;if (tr[rt].l >= l && tr[rt].r <= r) {solve(rt, x);return;}//if (tr[rt].lazy)pushdown(rt);int mid= (tr[rt].l + tr[rt].r) >> 1;update(rt << 1, l, r, x);update(rt << 1 | 1, l, r, x);pushup(rt); } PII query(int rt, int l, int r) {if (tr[rt].r < l || tr[rt].l > r)return {0, -1};if (tr[rt].l >= l && tr[rt].r <= r) {return tr[rt].maxx;}//if (tr[rt].lazy)pushdown(rt);int mid= (tr[rt].l + tr[rt].r) >> 1;PII maxx= {0, -1};maxx= max(maxx, max(query(rt << 1, l, r), query(rt << 1 | 1, l, r)));return maxx; } int path[maxn]; int ans[maxn]; int main() {//rd_test();int n, m;read(n, m);for (int i= 1; i <= m; i++) {int id, l, r;read(id, l, r);vec[id].push_back({l, r});num[++tot]= l;num[++tot]= r;}sort(num + 1, num + 1 + tot);int cnt= unique(num + 1, num + 1 + tot) - num - 1;// cout << "cnt=" << cnt << endl;for (int i= 1; i <= n; i++) {for (int j= 0; j < vec[i].size(); j++) {// printf("vec[i][j]=%d \n", vec[i][j]);vec[i][j].first= lower_bound(num + 1, num + 1 + cnt, vec[i][j].first) - num;vec[i][j].second= lower_bound(num + 1, num + 1 + cnt, vec[i][j].second) - num;// printf("處理后vec[i][j]=%d\n ", vec[i][j]);}}build(1, 1, cnt);//cout << "--" << endl;PII maxx;for (int i= 1; i <= n; i++) {maxx= {0, -1};//保存的數量 編號for (auto it : vec[i]) {// printf("l=%d r=%d\n", it.first, it.second);maxx= max(maxx, query(1, it.first, it.second));}path[i]= maxx.second;PII ans= {maxx.first + 1, i};for (auto it : vec[i]) {// printf("l=%d r=%d\n", it.first, it.second);update(1, it.first, it.second, ans);}}maxx= query(1, 1, cnt);printf("%d\n", n - maxx.first);int now= maxx.second;while (now != -1) {ans[now]= 1;now= path[now];}for (int i= 1; i <= n; i++) {if (!ans[i])printf("%d ", i);}return 0;//Time_test(); }

總結

以上是生活随笔為你收集整理的cf1557D. Ezzat and Grid的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。