ZROI2018.8.1 吴瑾昭的忠告

ZROI2018.8.1 骗分赛

Pww0Mt.png

题面
A
B
C
D

来自吴奆奆的教诲

打 OI 赛,不是看你能 AC 多少道,而是看你能不挂多少道。

A. 说好的一起富起来呢贺爸你怎么不等我

Subtask3

只考虑一维,O(n) 求出最长的 O 段再乘上 m 即可。

Subtask1

m<=3
要么 1,2 挨在一起,要么 1,3 要么 2,3,要么 1,2,3。四种情况 O(n) 判断即可。

正解

记 h[i][j] 为从第 i 行第 j 列向上延伸的最多 0 的数量。枚举矩形宽度 w,对 h 排序(同样的最大子矩形),结合 w 更新答案,复杂度 O(n^2logn)。

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
char qp[3005][3003];
char qp2[100005][10];
int h[3005][3003];
bool cmp(int a,int b){return a>b;}
int main(){scanf("%d%d",&n,&m);
    if(n>3000){//Subtask3
        for(int i=1;i<=n;i++)scanf("%s",qp2[i]+1);
        int t=0,mxt=0;
        for(int i=1;i<=n;i++)
            if(qp2[i][1]=='0')t++,mxt=max(mxt,t);
            else t=0;
        printf("%d",mxt*m);
        return 0;
    }
    for(int i=1;i<=n;i++)scanf("%s",qp[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(qp[i][j]=='0')h[i][j]=h[i-1][j]+1;
    for(int i=1;i<=n;i++){sort(h[i]+1,h[i]+m+1,cmp);
        for(int w=1;w<=m;w++)ans=max(ans,h[i][w]*w);
    }
    printf("%d",ans);
    return 0;
}

B. 仅有两千单词量的汪同学开始加紧学习英语

C. 丁同学从小就养成了自觉学习的习惯

s2

f[n,l,r] 放了 n 个最大的,左边 l 个,右边 r 个。
DP,O(n^3).

优化,l+r<=n+1.

D. 蔡老师最近发现了有同学打游戏


 上一篇
ZROI2018.7.27% 你赛 ZROI2018.7.27% 你赛
提高组模拟赛题面 A. 小 T 的 GCD分两个问题求解 Task1考虑到在你找到符合要求的序列后后,在其左右两边增加数字,并不会对结果有影响(多多益善)。所以直接计算整个序列的 gcd,判断是否为 1 即可。 Task2 lcm(a1.
2018.10.01
下一篇 
ZROI 提高组 Day4 ZROI 提高组 Day4
A. 天将 n 个数拆成左右两列, 左边表示买, 右边表示卖, 从左向右连边即表示买入和卖出。 考虑第 天是否卖出, 一定是在左边列的前 个中找一个还未配对的最小值和其配对进行买卖获益最大, 如果最小值
2018.10.01
  目录