个人网站建设策划书,微商城网站建设讯息,长沙网络公司app,wordpress去index.phpcf1557D. Ezzat and Grid
题意#xff1a;
有n行#xff0c;每行有10910^9109列#xff0c;仅仅由0和1构成 现在给你1的存在位置#xff0c;(i,l,r)表示第i行的第l列到第r列全为1 你可以删除任意一行i#xff0c;删除后#xff0c;第i-1行和第i1行为相邻 现在我们要求求…cf1557D. Ezzat and Grid
题意
有n行每行有10910^9109列仅仅由0和1构成 现在给你1的存在位置(i,l,r)表示第i行的第l列到第r列全为1 你可以删除任意一行i删除后第i-1行和第i1行为相邻 现在我们要求求最多的行数使得每个相邻两行最少有一列都是1(可以理解成上下相邻1)并输出删除了哪些行
题解
对于i行我们考虑前i-1行个是与i行满足要求的(即存在相邻1)。我们用线段树维护一个pairint,intsum sum.first表示以id为结尾所保留的最大行数 sum.secondid:表示以id为结尾的情况 因为1的出现都是连续的我们想查找与第i行满足情况的行数就在第i行出现1的区间例如[l,r],我们就查看所有[l,r]区间内的值取最大值得到sum(相当于取之前的最大值接着当前的i)。sum为与第i行满足情况且保留行数最多的某一行。查询完后要将第i行的情况插入到线段树中在区间[l,r]中插入我们的ans(ans.secondi,ans.firstsum.first1) 为了方便输出我们用一个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 pairint, 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;
vectorPII 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();
}
