我真的我要被我自己给猪死了md T1让输出边长我输出面积硬生生掉了100分 气死
这道题我之前在讲单调栈的时候是讲过的 对于每一个位置 维护一个他的$up$表示以这里为起点只走$1$向上走的高度
然后对于每一行都跑一边求最大矩形的单调栈即可 维护一个单增的 每次弹栈的时候求出以弹栈元素为矩形边长的最大矩形面积 不过这道题是求最大正方形
就改成边长取$min$再取$max$即可
代码
#include <bits/stdc++.h> #define il inline #define rg register #define oo 1e9 using namespace std; const int N = 2000 + 5; int up[N][N], a[N][N], stk[N], n, m, top; il int read( ) { int t = 1, ans = 0; char x; x = getchar( ); while(x < '0' || x > '9') { if(x == '-') t = -1; x = getchar( ); } while(x >= '0' && x <= '9') { ans = ans * 10 + x - '0'; x = getchar( ); } return ans * t; } il void Init( ) { n = read( ), m = read( ); for(rg int i = 1;i <= n;i ++) { for(rg int j = 1;j <= m;j ++) { a[i][j] = read( ); if(a[i][j] == 1) up[i][j] = up[i - 1][j] + 1; else up[i][j] = 0; } up[i][m + 1] = -oo; } } il void Solve( ) { int ans = 0; for(rg int i = 1;i <= n;i ++) { top = 0; for(rg int j = 1;j <= m + 1;j ++) { while(top && up[i][stk[top]] > up[i][j]) { ans = max(ans, min(up[i][stk[top]], j - 1 - stk[top - 1])); top --; } stk[++ top] = j; } } printf("%d ", ans); } int main( ) { freopen("inspect.in", "r", stdin); freopen("inspect.out", "w", stdout); Init( ); Solve( ); }
这道题其实是一道裸裸的而粪土二分图匹配
就对于每本书拆点 如果$a$能够摞到$b$上 就连接$a -> b$ 然后求一个最大匹配$cnt$即可 答案为$n - cnt$
因为每匹配一次相当于节省一个书架 注意判重 也就是如果两本书一模一样 就只需要连一条就够了 否则会减多
代码
#include <bits/stdc++.h> #define il inline #define rg register #define oo 1e9 using namespace std; const int N = 300 + 5; int src, sink, x[N], y[N], tot, head[2 * N]; int nex[N * N], tov[N * N], n; int cx[2 * N], cy[2 * N], ans = 0; bool vis[2 * N]; il int read( ) { int t = 1, ans = 0; char x; x = getchar( ); while(x < '0' || x > '9') { if(x == '-') t = -1; x = getchar( ); } while(x >= '0' && x <= '9') { ans = ans * 10 + x - '0'; x = getchar( ); } return ans * t; } il void add(int u, int v) { tot ++; nex[tot] = head[u]; tov[tot] = v; head[u] = tot; } il void Add_Edge( ) { n = read( ); for(rg int i = 1;i <= n;i ++) x[i] = read( ), y[i] = read( ); for(rg int i = 1;i <= n;i ++) { for(rg int j = 1;j <= n;j ++) { if(i == j) continue; if(x[j] == x[i] && y[j] == y[i]) { if(i < j) add(i, j + n); continue; } if(x[j] >= x[i] && y[j] >= y[i]) add(i, j + n); } } } il int dfs(int u) { for(rg int i = head[u];i;i = nex[i]) { int v = tov[i]; if(vis[v]) continue; vis[v] = true; if(! cy[v] || dfs(cy[v])) { cy[v] = u; cx[u] = v; return 1; } } return 0; } int main( ) { freopen("militarytraining.in", "r", stdin); freopen("militarytraining.out", "w", stdout); Add_Edge( ); for(int i = 1;i <= n;i ++) if(! cx[i]) { memset(vis, 0, sizeof(vis)); ans += dfs(i); } printf("%d ", n - ans); }
这道题我暴力莫队70分hhh
正解是将询问离线 按照左端点排序 然后要做的事情是在从后往前扫的过程中 求出每个数产生贡献的区间 用前缀和查分对于以当前点为左端点的区间的答案
维护一个数组$t,t[i]$ 表示如果询问区间包含了点$i$ 答案会增加$t[i]$（可能为负）
初始情况下$t$全为$0$，$i$从$n$枚举到$1$
对某个$i$ 考虑$a[i]$这个数在$i$位置及其以后是否出现过$a[i]$次及以上 假设$a[i]$在位置$x$出现了第$a[i]$次 在位置y出现了第$a[i]+1$次
即表示对于左端点为$i$的询问区间 当右端点在$[x,y)$时 $a[i]$会贡献$1$的答案 否则贡献$0$的答案 此时设$t[x]=1$且$t[y] = -1$即可
用一个树状数组维护$t$数组，可以很容易的统计前缀和。
复杂度为$O(nlogn+qlogn+qlogq)$
代码
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; int c[N], t[N], cnt[N], n, q, a[N], ans[N]; vector<int>pos[N]; struct ques { int id, l, r; }Q[N]; bool cmp(const ques & a, const ques & b) { return a.l < b.l; } int read( ) { int t = 1, ans = 0; char x; x = getchar( ); while(x < '0' || x > '9') { if(x == '-') t = -1; x = getchar( ); } while(x >= '0' && x <= '9') { ans = ans * 10 + x - '0'; x = getchar( ); } return ans * t; } void Init( ) { n = read( ), q = read( ); for(int i = 1;i <= n;i ++) a[i] = read( ); for(int i = 1;i <= q;i ++) { Q[i].l = read( ), Q[i].r = read( ); Q[i].id = i; } sort(Q + 1, Q + q + 1, cmp); } int lowbit(int x) { return x & (-x); } int query(int pos) { int ans = 0; while(pos >= 1) { ans += c[pos]; pos -= lowbit(pos); } return ans; } void modify(int pos, int del) { while(pos < N) { c[pos] += del; pos += lowbit(pos); } } void update(int x) { t[a[x]] ++; pos[a[x]].push_back(x); if(t[a[x]] == a[x]) modify(pos[a[x]][0], 1); else if(t[a[x]] == a[x] + 1) { modify(pos[a[x]][0], -1); int pos1 = pos[a[x]][cnt[a[x]] ++], pos2 = pos[a[x]][cnt[a[x]]]; modify(pos1, -1);int cc = query(N); modify(pos2, 1); } else if(t[a[x]] > a[x] + 1) { int pos1 = pos[a[x]][cnt[a[x]] - 1], pos2 = pos[a[x]][cnt[a[x]] ++], pos3 = pos[a[x]][cnt[a[x]]]; modify(pos1, 1); modify(pos2, -2); modify(pos3, 1); } } void Solve( ) { int now = q; for(int i = n;i >= 1;i --) { update(i); int cc = query(14); while(Q[now].l == i) { ans[Q[now].id] = query(Q[now].r); now --; } } for(int i = 1;i <= q;i ++) printf("%d ", ans[i]); } int main( ) { freopen("count.in", "r", stdin); freopen("count.out", "w", stdout); Init( ); Solve( ); }