NOIP 2018 游记

变化,这是我对今年 NOIP 的概括,从天津赛区的选址变为新校区,到 CCF 更新那个被无数选手诟病已久的“老爷机”,可以看出来 NOIP 的不断完善以及受重视程度不断提高。废话不多说,谈谈本次考试的想法吧。

Day 1

第一题铺设道路,一道简单的贪心,随便打个树状数组 30min A 掉切下一题(其实时间要比 30 分钟长)。

看到了第二题,艹,数学题,还是去年小凯的疑惑加强版。不过简单的分析一下可以发现如果一个数能被其他数表示,那么这个数字一定是没用的,否则是一定是有用的(“显然”),手玩了几组样例,发现思路正确,然后打了一个筛,1h A 掉完事切下一道题。这里的筛有一个坑,就像欧拉筛一样,必须做一个标记,否则复杂度无法保证那就妥妥的 T 了。

然后去厕所呼吸一下新鲜空气,大概 2.5h 过去了。

看第三题,读了两遍题发现是树形动态规划,可惜我的树形动态规划是上周学的,敲掉暴力,写个对拍,弄几组测试数据测试一下,交卷。

今年 Day 1 的题目看网上的说法是都撞题了,不过可惜我都没做过(zg dalao 两个月 A 掉 300 道题目 %%% 啊)。

Day 2

读了一遍题,发现第一题的数据特别神奇,是一个单环树,考虑断环上边然后枚举去做,这样复杂度已经 O(n^2) 了,可是还要求最小,所以考场上的想法就是每次都排一遍序,O(n^2logn) ,考虑到今年 CCF 换评测机,外加由于每次排序改变的东西并不会非常多,所以就这样了,没有细想。好在命大,最后拜托了我“优秀”的卡常技巧,居然卡过去了。具体来讲用 vector 存边的都 T 了…

第二题,艹,又是数学题,不过由于心太高,所以在这道题上犯了一个考场上一定不能犯的错误,就是硬抗,事实证明,要不是我福大命大,最后 30 分钟 T3 调出来了,否则就凉凉了,这道题目浪费了我足足 1 个小时,不过最后还是果断换题了,减少损失,最后一道题目敲出来了以后回来发现有几组白痴数据,手敲了一个表,交了上去,最后在基础的暴力分上只扣了 5 分,感谢 CCF 弱数据…

第三题,这是 NOI Plus 吧…不会,敲了一个暴力交了上去。

总结

总体来讲体验还算可以,但是之前犯的错,这次又犯了,时间规划真的非常非常非常重要啊!

另外感觉这次比赛自己的码风非常吃亏,因为我一直坚持的代码可读性原则导致我的代码普遍比别人长 2 倍以上,这个可能要改一下了,毕竟打的是竞争性的比赛,而不是长久维护的工程。

394,近 400 分的成绩对的起我一年的付出,我已经非常满意了。

NOI 2019 我们明年见!

图为 NOIP 2018 天津考场,天津大学北洋园校区。

奋斗!

午后,阳光射进自习室,温暖而不刺眼。与那些进队的物理化学同学们坐在一个地方,一同为这自己的目标奋斗,这大概是人生最好的时刻了吧。

但是,我跟他们不一样,我只有这一次机会了。成还是败,就在这一举了。

我不是一个普通的孩子,我一定会做出自己的事业。这是我一直告诉我自己的,过去是,现在是,将来更是。

加油,抓紧每一分时间,奋斗!

理想与现实

一堆课文没背,一堆事情没办,今天过的又很让人沮丧。

其实,你们知道吗,我知道为什么吾得这个项目为什么4年了到现在都没有什么特别大的进展了。大概是我过于理想化了,我给吾得打上了太多的标签,就像父亲对孩子,有过多的想法,我没有找到重点,这样导致我没办法实现。其实这也有一部分是我的行动力的问题,我错在全在想而不是在做,一直都是TODO而不是Do。

吾得是我对有一定成就的愿望的寄托,或者说是,我希望成为一个像一些名人一样受人尊重,敬仰,但是我错了。我一直在说的是人权,保护个人隐私,但是如果我忽然有了权力,有了地位了,我还会这么想吗?我在保护我个人的隐私的同时,我在干什么,我爬了别人的成绩窥探了他人的隐私。我的呼吁是没有力度的。更令人无语的是,我希望他人去跟从我的想法而我却不愿意承认他人的爱好。这是一种病态的思维方式。

话又说回来,为什么我今天心情又不好了?人类是一个很神奇的动物,总是会对一些东西抱有不切实际的期望。其实我已经很不错了,但是我在想变得更好,但是我却不想为此付出代价,这很可笑对吧,但是的确是我的现状,我需要去改变。

我需要改变,但是我也迷茫,我该改变成什么样子,下一步,我该何去,又该何从?希望几年后的我看到这些文字的时候不会是一个颓丧的样子。Fighting!

保持探索,好奇心万岁!

这是 lookas2001 写作计划的第一篇,同时也是 lookas2001 尝试系列中的一部分。

在 lookas2001 尝试系列中,我会了解并且学习各种我之前没有或者不敢尝试的能力,尽力的拓宽我的知识面,锻炼我的认知能力,并且为这个庞大的世界作出一些微小但也可能很伟大的改变。

6月1日,国际儿童节。这是我的第17次儿童节,对于我来说,这可能是我在成年以前过的倒数第二次儿童节了。很显然,我不再是当年那个清纯可爱的我了,但是我在想,为什么我不是了,有哪些变化,以及我得到了什么亦或是失去了什么。为了纪念我已经度过的童年并且即将逝去的青春,以及作为这个系列的开篇,为之后的探索提供一个方向。在这里,我写下这篇文章。

首先,回答开头提出的问题,我认为,最大的变化是:我失去了我一直引以为傲的好奇心。没错,不是其他,虽然我知道这个世界仍然很大,但是,慢慢的,我越来越懒得去探索世界,不再愿意迈出步子,走出我的 comfort zone。越来越固化的学习及生活,日复一日的面对着电脑,令人头疼的社交,这种事情令我感觉越来越无趣,正因如此,我的时间度过的时间变得越来越快,恍惚间,时间就过去了。这就如同一个会直立行走的僵尸,没有好奇的生活会变得令人生厌,疯狂。哦,我的上帝,这真的是一件令人可怕的事情。

如果说事物的发展是拜人类的智慧所赐,那么人类的智慧正是由好奇所赐。早在19世纪,马克思创造的马克思主义哲学中有这么一句话:“事物内部的矛盾是事物发展的源泉和动力。”现在看来,仍然有着很强大的参考意义,人正因为不了解自己不清楚的事物,才去进行的探索。作为世界发展的新生力量,好奇永远都是最重要的。如果需要为人类的能力排个序,那好奇绝对可以排入第一批次。正如维基上所说的那样:“好奇和人类各层面的发展都高度相关,有好奇才会引发学习的过程,以及想要了解知识及技能的欲望。”她强烈的推动着人类的发展,人类的发展离不开好奇。

我们耳熟能详的各位为人类科学事业在自然以及人文学科奉献出巨大贡献的大师们,没有不拥有着强大的好奇心的。举世界名校MIT的例子,这里的孩子们热爱恶作剧,其校方甚至为其恶作剧特意制作了一个恶作剧博物馆,这让常年接受要做一个乖宝宝的教育的我们无法理解这个恶作剧文化,但是与此同时,我们应该想到,这些制作恶作剧的孩子们为了制作一个吸引眼球的,创意奇特的恶作剧,挖空了多少心思,这正是好奇给他们提供的推动力。这些人成长为成人的结果就是为美国的持续的繁盛提供了不懈的动力,使美国至今为止仍然是世界上最强大的国家。

就像枯木、硬石一般,一个人失去了好奇意味着他失去了探索改变自身以及世界的能力,一个国家或者民族失去了好奇更会是一个国家政权更替或者是民族没落的标志。历史上有何其多的将军因为固化思维吃了败仗的亏,有多少国家因为不考虑新想法结果强盛没能持续几年就没落了,现在社会中又有多少人失去了探索的能力,碌碌无为,搬砖搬了半个辈子,到了人生的末尾的追悔莫及的。

在最后也祝愿每一个人能保持住自己探索世界的本能,持续不断的好奇,并且不放弃改变世界的努力。当然我也希望能阅读到这里的读者们,时刻反思,是否停下了发现的步伐,是否安于现状并且不愿改变,是否放弃了思考的能力。

儿童节快乐!

好奇心万岁!

Man Down 解题报告(hdu3016 动态规划 线段树 排序)

http://acm.hdu.edu.cn/showproblem.php?pid=3016

算法设计

拿到题二话不说,先把这些木板按照其高从小到大排个序,然后我们给木板从下到上从1开始递增编号(我们认为最下面的地板编号为0),通过这样的一个步骤,显然,越高的木板序号越大。

根据题意,如果人在一个木板上,他只可以从这个木板的左端或者右端垂直下落。我们定义 d[i] 为当这个人到达第 i 个板的时候最大生命值。如果我们知道 d[i] 的值,我们就可以推出其左端或者右端下落到的板子相应的值。(d[j] = d[i] + 跳到 j 板上生命值的变化量)。这样,我们可以从上往下递推的求解。

但是我们如何知道这个人他在左端或者右端下落会落到哪里呢?我们可以对 x 轴根据点建立一棵线段树,然后从下往上根据木板对这个 x 轴“染色”(即对木板所覆盖的地方标记上自己的序号),这样的话,在往上推进的过程中,很方便就能求出一个木板左右端跳下去会跳到哪个板上。

示例代码

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 110000, L = 110000, INF = 0x7fffffff;

int n;

struct a_d {
    int h, l, r, v;
    int ld, rd; // left down to 
} a[N];

inline bool cmp(a_d a, a_d b) {
    return a.h < b.h;
}

struct node {
    int l, r;
    int f;
    node *lc, *rc;
} mem[2 * L];
node *memp;
node *root;

node *init(int l, int r) {
    node *p = memp++;
    p->l = l;
    p->r = r;
    p->f = 0;
    if (l == r) {
        p->lc = p->rc = NULL;
    } else {
        int mid = (l + r) >> 1; 
        p->lc = init(l, mid);
        p->rc = init(mid + 1, r);
    }
    return p;
}

inline void push_down(node *p) {
    if (p->f) {
        p->lc->f = p->f;
        p->rc->f = p->f;
        p->f = 0;
    }
}

void change(node *p, int l, int r, int f) {
    if (l <= p->l && p->r <= r) {
        p->f = f;
        return;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (l <= mid) change(p->lc, l, r, f);
    if (mid < r) change(p->rc, l, r, f);
}

int query(node *p, int i) {
    if (i == p->l && p->r == i) {
        return p->f;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (i <= mid) return query(p->lc, i);
    return query(p->rc, i);
}

int d[N]; 

inline int max(int a, int b) {
    if (a > b) return a; else return b;
}

int main() {
//  freopen("input.txt", "r", stdin);

    while(scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) scanf("%d%d%d%d", &a[i].h, &a[i].l, &a[i].r, &a[i].v);
        a[0].v = 0;

        std::sort(a + 1, a + n + 1, cmp);
//      
//      for (int i = 1; i <= n; ++i) printf("%d %d %d\n", i, a[i].l, a[i].r); printf("\n");

        memp = mem;
        root = init(0, 100010);
        for (int i = 1; i <= n; ++i) { 
//          printf("%d %d %d\n", i, a[i].l, a[i].r);
            a[i].ld = query(root, a[i].l); // 注意这里不 +1 -1
            a[i].rd = query(root, a[i].r);
            change(root, a[i].l, a[i].r, i);
        }
//      
//      for (int i = 1; i <= n; ++i) printf("%d %d %d\n", i, a[i].ld, a[i].rd);

        for (int i = 0; i <= n; ++i) d[i] = -INF;
        d[n] = 100 + a[n].v;
        for (int i = n; i; --i) {
            if (d[i] <= 0) continue;
            d[a[i].ld] = max(d[a[i].ld], d[i] + a[a[i].ld].v);
            d[a[i].rd] = max(d[a[i].rd], d[i] + a[a[i].rd].v);
        }

        if (d[0] > 0) printf("%d\n", d[0]); else printf("-1\n");
    }

    return 0;
}

HH 的项链 解题报告(SDOI 2009 线段树 排序 离线处理)

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此他的项链变得越来越长。

有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?

这个问题很难回答。。。因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。

输入

第一行:一个整数N,表示项链的长度。

第二行:N个整数,表示依次表示项链中贝壳的编号(编号为0到1000000之间的整数)。

第三行:一个整数M,表示HH询问的个数。

接下来M行:每行两个整数,L和R(1 ≤ L ≤ R ≤ N),表示询问的区间。

N ≤ 50000,M ≤ 200000。

输出

M行,每行一个整数,依次表示询问对应的答案。

样例输入

6
1 2 3 4 3 5
3
1 2
3 5
2 6

样例输出

2
2
4

来源

SDOI 2009

在线评测

lydsy

vjudge

算法设计

看到题目,首先想了想所学的数据结构,当前还没有如此高级的数据结构可以求任意的一个区间内有多少种数字。那么我们试试能不能在确定一个端点的前提下,通过简单的数据结构得到结果。

这道题目我们需要离线处理,将所有的查询根据右节点从小到大排序,使其变得有序后进行操作。

我们定义一个变量 k 为当前推进(或者说枚举)到的右节点,定义一棵线段树,第 j 个节点的含义为 j-k 内不同的数字个数

我们定义一个数组 last 数组,第 i 个元素为 第 i 个贝壳序号 在 贝壳序列中 上一次出现的位置。

我们可以发现,如果我们推进到了一个新的 k,很明显 1 ~ last[k] 到 k 这些段中一定是存在 第 k 个贝壳序号,而在 last[k] + 1 ~ k 到 k 这些段中是不存在的。那反映到线段树中 last[i] + 1 ~ k 所有节点都应该 + 1。

没听懂?没关系,可以看看下面的代码。

示例代码

#include <cstdio>
#include <cstring>
#include <algorithm>

//using namespace std;

const int N = 55000, M = 220000, MAX = 1100000;

int n, m, a[N];

int last[N];
int idx[MAX]; // 本来是 index 但是与头文件中的函数冲突了 

struct q_d {
    int l, r, id;
} q[M];

int result[M];

inline bool cmp(q_d a, q_d b) {
    return a.r < b.r;
}

struct node {
    int l, r;
    int f;
    node *lc, *rc;
} mem[2 * N];
node *memp;
node *root;

inline void push_down(node *p) {
    if (p->f) {
        p->lc->f += p->f;
        p->rc->f += p->f;
        p->f = 0;
    }
}

node *init(int l, int r) {
    node *p = memp++;
    p->l = l;
    p->r = r;
    p->f = 0;
    if (l == r) {
        p->lc = p->rc = NULL;
    } else {
        int mid = (l + r) >> 1;
        p->lc = init(l, mid);
        p->rc = init(mid + 1, r); 
    }

    return p;
}

void change(node *p, int l, int r) {
    if (l <= p->l && p->r <= r) {
        ++p->f;
        return;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (l <= mid) change(p->lc, l, r);
    if (mid < r) change(p->rc, l, r);
} 

int query(node *p, int i) {
    if (p->l == p->r) {
        return p->f;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (i <= mid) return query(p->lc, i);
    return query(p->rc, i);
}

int main() {
//  freopen("input.txt", "r", stdin);

    scanf("%d", &n);
    memset(idx, 0, sizeof idx);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        last[i] = idx[a[i]];
        idx[a[i]] = i;
    }

    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    std::sort(q + 1, q + m + 1, cmp);
//  
//  for (int i = 1; i <= m; ++i) printf("%d %d\n", q[i].l, q[i].r);

    int j = 1;
    memp = mem;
    root = init(1, n);
    for (int i = 1; i <= n; ++i) {
        change(root, last[i] + 1, i); 
        for (; q[j].r == i && j <= m; ++j) {
            result[q[j].id] = query(root, q[j].l);
        }
    }

    for(int i = 1; i <= m; ++i) printf("%d\n", result[i]);

    return 0;
}

The Bakery 解题报告(cf833b dp 带优化的dp 线段树)

http://codeforces.com/contest/833/problem/B

NOTICE

推荐在写这道题前看看 HH 的项链 解题报告(SDOI 2009 线段树 排序 离线处理)

算法设计

拿到题,3分钟,这是一道动态规划。写码,调试,提交,一气呵成,最后发现在第4个点超时。转过头来看,发现在处理每一个状态的时候套着一个循环,导致整体算法复杂度 O(n ^ 3) 遂放弃。

最近学习了线段树,然后再看这道题,发现了这道题在求不同数字的个数的时候进行了很多不必要的重复运算,可以用线段树解决。

由于本人的描述实在不行,具体解决方案请直接看下面代码以及其注释,先粗略看一遍全局变量的定义,然后再看一下main函数。

配合这张图食用更佳。

示例代码

#include <cstdio>
#include <cstring>

const int N = 38500; // 35000 * 1.1 

int n, k, a[N]; // 题目中提供的数据 

int last[N]; // 记录该位置的数上一次出现的位置,last[i] 代表 a[i] 位置上的数在 a 数组中上一次出现的位置,如果没有出现过,则为 0 
int index[N]; // 用于辅助建立 last 数组 

int d[N]; // 动态规划中用于保留结果的数组, d[i] 代表在一次切割中(阶段),最后一个切割点(或者说是最后一个箱子装的最后一个蛋糕的坐标)的结果 

struct node {
    int l, r;
    int f;
    int max;
    node *lc, *rc;
} mem[2 * N];
node *memp;
node *root; // 线段树中第 i 个位置的数 为 上一个阶段 d[i] 以及 i + 1 ~ j 中不同数字的个数 的和,其中 j 为当前推进到的位置,详见下方解释 

inline void push_down(node *p) {
    if (p->f) {
        p->lc->max += p->f;
        p->lc->f += p->f; // mistake: 就像傻子一般,线段树这里给写错了 
        p->rc->max += p->f;
        p->rc->f += p->f;
        p->f = 0;
    }
}

inline void pull_up(node *p) {
    if (p->lc->max > p->rc->max) p->max = p->lc->max; else p->max = p->rc->max;
}

node *init(int a[], int l, int r) {
    node *p = memp++;
    p->l = l;
    p->r = r;
    p->f = 0;
    if (l == r) {
        p->lc = p->rc = NULL;
        p->max = a[l];
    } else {
        int mid = (l + r) >> 1;
//      printf("%d %d %d\n", l, mid, r);
        p->lc = init(a, l, mid);
        p->rc = init(a, mid + 1, r);
        pull_up(p);
    }
    return p;
}

void change(node *p, int l, int r) {
    if (l <= p->l && p->r <= r) {
        ++p->max;
        ++p->f;
        return;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (l <= mid) change(p->lc, l, r);
    if (mid < r) change(p->rc, l, r);
    pull_up(p);
}

int query(node *p, int l, int r) {
    if (l <= p->l && p->r <= r) {
        return p->max;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    int max = 0, tmp;
    if (l <= mid) {
        max = query(p->lc, l, r);
    }
    if (mid < r) {
        tmp = query(p->rc, l, r);
        if (tmp > max) max = tmp;
    }
    pull_up(p); // mistake:这里的pull_up是不可或缺的 

    return max;
}
//
//void debug2() {
//  for (int i = 1; i <= n; ++i) printf("%d ", last[i]);
//  printf("\n\n");
//}
//
//void debug1() {
//  for (int i = 0; i <= n; ++i) printf("%d ", d[i]);
//  printf("\n");
//} 

int main() {
//  freopen("input.txt", "r", stdin);

    scanf("%d%d", &n, &k);
    memset(index, 0, sizeof index);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        last[i] = index[a[i]]; // 读取输入的过程中同时填充一下 last 数组,last 数组的含义见上定义 
        index[a[i]] = i;
    }
//  
//  debug2();

    // 动态规划,为了能够对动态规划中的一个阶段中的不同状态下的求解能够快速进行,我们使用了递推,这样求解的顺序可以利用线段树进行优化 
    memset(d, 0, sizeof d); // 不难发现最开始的结果都是 0 的 
    for (int i = 1; i <= k; ++i) { // 阶段,即切割或者说是箱子的个数 
        memp = mem;
        root = init(d, 0, n); // 线段树是可以从 0 开始建立的,详见下方解释 
        for (int j = i; j <= n; ++j) { // 枚举当前阶段切割点的位置 
            // 诚然,我们对于每一个切割点而言,我们都可以跑一次如下的循环 
            /* 
            int max = 0, tmp;
            for (int k = i - 1; k <= j - 1; ++k) { // 很明显 i - 1 之前的是不可能满足题意的 
                tmp = last_d[k] + different_num_between(k, j);
                if (tmp > max) max = tmp;
            }
            */
            // 但是这样太慢了,我们发现,计算从 k 到 j 的有多少个不同的数字这个函数被调用了很多遍,并且发现貌似每次都进行了许多无用的计算
            // 我们建立一棵线段树,定义为当推进到 j 位置的时候,线段树中第 k 个数为从 k + 1(加一是为了初始化方便) 到 j 中不同数字的个数
            // 我们可以发现,last[j] + 1 到 j 中间是没有 a[j] 这个数的(一句废话)
            // 那也就是说,如果我们的进度推进到了 j 的话,对于所有的 在 last[j] + 1 ~ j 中的位置到 j 的不同数字种类应该会多出一个 j ,反映到数量上,就是个数 +1 
            // 映射到线段树的时候别忘了位置 -1 
            //  
            // 我们还可以发现,如果说按照上述定义,求最大值仍然需要扫描整个线段树,因为在原始的线段树上我们还需要增加上一个阶段的结果
            // 那么我们索性就在线段初始化的时候,将 d 数组作为线段树最开始的初始化用数组,这样求最大值就可以用线段树舒服的求出来了(当然线段树写错了当我没说) 
            // 
            // 被绕晕了?可以翻上去看看定义那里的注释,并且根据代码理解一下 
            change(root, last[j] + 1 - 1, j - 1); 
            d[j] = query(root, i - 1, j - 1); // mistake: 请注意,这里必须是 i - 1 而不是 i 
        }
//      debug1();
    }
//  
//  // 哦,我的老伙计,这一坨被注释的代码是彻头彻底的错误 
//  int max = 0;
//  for (int i = 1; i <= n; ++i) if (d[i] > max) max = d[i];
//  printf("%d", max);
//  for (int i = 1; i <= n; ++i) printf("%d ", d[i]);
//  printf("%d", d[n]); 

    printf("%d", d[n]);

    return 0;
}

Load Balancing 解题报告(USACO 2016 February Contest, Silver. Problem 2. 排序 树状数组 离散化)

USACO(W) (滑稽

题目解析

题目在线详情(提交地址):http://www.usaco.org/index.php?page=viewproblem2&cpid=619

题目意思其实很简单,给定一个二维矩阵(农场),其中放置着许多点(牛),求在一个恰当的地方切水平竖直两刀,使得所切的四个区域中点最多的那个区域中的点最少。(啥,还没看懂?回到题目详情继续啃英文)

算法设计

且不考虑什么 k-d tree 这种特别高级的算法,我们先想一想暴力怎么做?枚举每一个切割点(水平竖直切割线的交点)!但是,我们可以发现,由于x,y都特别大,这样会导致程序最后时间非常慢…

Wait!为啥点才1000多个?对,我们可以简单的在大脑中想,这么一个大矩阵,一大堆空间都是0,也就是说我们枚举了很多没用的位置点,我们可以对x,y单独(想一想为什么单独做是可以的)做一次离散化,这样可以迅速让枚举范围减小。离成功进了一步!

但是,依然很慢 O(n^3) ,原因其实蛮简单的,因为统计区域内的点非常的慢,每一次统计我们都统计了上次统计过的点。那为什么我们不想想办法解决这个问题呢?首先,我们可以让这些牛 有序 (其实这是我最开始的想法,比离散化的想法还要早一些),我们按行往下推进,然后我们对水平切割线的上下分别建立一个树状数组。(其实最开始我的想法是对每一行都建立一棵线段树的,但是发现其实没有必要每一行都建立一棵的),然后枚举每一个垂直切割线,这样我们的复杂度降低到了 O(n ^ 2 * logn)

实例代码

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 1100;

int n;
struct cd {
    int x, y;
} c[N];

bool cmp(cd a, cd b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

int *d[N];

bool cmp_d(int *a, int *b) {
    return *a < *b;
}

int t[N], b[N]; // 水平轴切开的上下两部分,top bottom 

void change(int t[], int k, int x) {
    while (k <= n) {
        t[k] += x;
        k += k & (-k); 
    }
}

int sum(int t[], int k) {
    int x = 0;
    while (k > 0) {
        x += t[k];
        k -= k & (-k);
    }
    return x;
}

int main() {
//  freopen("input.txt", "r", stdin);
    freopen("balancing.in", "r", stdin);
    freopen("balancing.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &c[i].x, &c[i].y);

    // 对x进行排序,便于下方移动水平轴 
    std::sort(c + 1, c + n + 1, cmp); 
//  for (int i = 1; i <= n; i++) printf("%d %d\n", c[i].x, c[i].y); printf("\n");

    // 对y进行离散化,便于下方移动垂直轴
    for (int i = 1; i <= n; i++) d[i] = &c[i].y;
    std::sort(d + 1, d + n + 1, cmp_d); 
    int last = 0, count = 0;
    for (int i = 1; i <= n; i++) {
        if (*d[i] != last) {
            count++;
            last = *d[i];
        }
        *d[i] = count;
    }
//  for (int i = 1; i <= n; i++) printf("%d %d\n", c[i].x, c[i].y); printf("\n");

    // 移动水平轴,并且枚举垂直轴 
    memset(t, 0, sizeof t);
    memset(b, 0, sizeof b);
    for (int i = 1; i <= n; i++) change(b, c[i].y, 1); // 先填充水平轴下方的内容
    int ans = 0x7fffffff;
    int i = 1;
    while (i <= n) {
        int row = c[i].x; 
        // 从水平轴下方删除,并且添加到水平轴上方
        while (i <= n && c[i].x == row) {
            change(t, c[i].y, 1);
            change(b, c[i].y, -1);
            i++;
        }

        for (int j = 1; j <= n; j++) { 
            int tmp, stage_ans = 0;
            tmp = sum(t, j); // 上左 
            if (tmp > stage_ans) stage_ans = tmp;
            tmp = sum(t, n) - tmp; // 上右 
            if (tmp > stage_ans) stage_ans = tmp;
            tmp = sum(b, j); // 下左 
            if (tmp > stage_ans) stage_ans = tmp;
            tmp = sum(b, n) - tmp; // 下右 
            if (tmp > stage_ans) stage_ans = tmp;
            if (stage_ans < ans) ans = stage_ans; 
        }
    }
    printf("%d", ans); 

    return 0;
} 

Gourmet Grazers 解题报告(poj3622 treap 平衡树 sort)

大家好,我是…咳咳,废话不说直接上分析。

题目解析

现有n头牛,m种草。对于每一头牛,吃的草价值不能小于ai并且吃的草绿色值不得小于bi;对于每一种草,都有草价值ci以及草的绿色值ci。要求,每一头牛有且仅有一种草与之对应且每一种草有且仅有一头牛与之对应。求满足条件的牛草搭配方式中,花费最少多少?

算法设计

初步想法,枚举暴力

然后,我寻思着,求花费最少,首先我们需要先让我们的搭配满足条件。因为bi小的牛一定能吃bi大的牛所能吃的草,反之却不可以,另外,我们需要使得花费最少,如果优先处理bi小的牛很有可能会导致bi大的牛无法找到方案。所以我想着,可以对绿色值从大到小将牛与草排个序,先处理bi大的牛,然后再处理bi小的牛。

与此同时,就绿色值而言,可供牛选择的草会越来越多,在每一次处理牛之前,我们先把这些草加入到一个集合中。然后,我们在这个不断增加的集合中找到价格最少的草提供给牛吃,计入到最终的结果中。这个过程,维持这个有序集合我们使用平衡树来进行,下面的示例代码我使用了treap来实现。

错误分析

  • 最开始总是WA,分析数据范围后发现,最终结果可能会非常大,所以我们需要用long long。
  • 另外,如果使用treap,请一定要保证写的代码是准确的,否则会导致非常隐蔽的错误,比如在这里,我的treap的merge方法递归中传递的参数顺序错了,结果导致最终的集合无法保证顺序。
  • sort的结束位置是不会计入排序的。
  • 一些很智障的访问越界可以使用Dev C++的debug来查,别忘了编译模式为debug而不是release,另外貌似win10下如果编译成64位会导致无法跟踪代码。(更新:其实并不是,切断点啥的都是可以的,但是如果程序中某个位置函数调用栈过大可能就显示不出来的)

示例代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

const int N = 110000;

int n, m;

struct cow_grass_d {
    int price, greenness;
} cow[N], grass[N];

struct node {
    int val, w;
    node *lc, *rc;
//  node *debug_self;
} mem[N];
node *mem_p;
node *root;

bool cmp(cow_grass_d a, cow_grass_d b) {
    return a.greenness > b.greenness; 
}

void split(node *root, int key, node *&left, node *&right) {
    if (!root) {
        left = NULL;
        right = NULL;
        return;
    }
    if (root->val < key) {
        left = root;
        split(root->rc, key, left->rc, right);
    } else {
        right = root;
        split(root->lc, key, left, right->lc);
    }
}

void merge(node *left, node *right, node *&root) {
    if (!left) {
        root = right;
        return;
    }
    if (!right) {
        root = left;
        return;
    }
    if (left->w < right->w) {
        root = left;
        merge(left->rc, right, root->rc);
    } else {
        root = right;
        merge(left, right->lc, root->lc);
    } 
}

//int lay = 0;
//void debug_print(node *p) {
//  if (!p) return;
//  lay++;
//  for (int i = 1; i < lay; i++) printf(" ");
//  printf("%p %p %p %d %d\n", p, p->lc, p->rc, p->val, p->w);
//  debug_print(p->lc);
//  debug_print(p->rc);
//  lay--;
//}

int main() {
//  freopen("input.txt", "r", stdin);

    scanf("%d%d", &n, &m);
    memset(cow, 0, sizeof cow);
    memset(grass, 0, sizeof grass);
    for (int i = 1; i <= n; i++) scanf("%d%d", &cow[i].price, &cow[i].greenness);
    for (int i = 1; i <= m; i++) scanf("%d%d", &grass[i].price, &grass[i].greenness);
    std::sort(cow + 1, cow + n + 1, cmp);
    std::sort(grass + 1, grass + m + 1, cmp);
//  for (int i = 1; i <= n; i++) printf("%d %d\n", cow[i].price, cow[i].greenness); printf("\n");
//  for (int i = 1; i <= m; i++) printf("%d %d\n", grass[i].price, grass[i].greenness); printf("\n");

    memset(mem, 0, sizeof mem);
    mem_p = mem;
    root = NULL;
    long long ans = 0;
    int j = 1;
    for (int i = 1; i <= n; i++) {
        for (; grass[j].greenness >= cow[i].greenness && j <= m; j++) {
            node *l, *r, *p;
            p = mem_p++; 
            p->val = grass[j].price;
            p->w = rand();
            p->lc = p->rc = NULL;
//          p->debug_self = p;
            split(root, p->val, l, r);
            merge(l, p, l);
            merge(l, r, root);
//          printf("%d ", p->val);
        }
//      printf("\n");
//      debug_print(root);

        node *l, *r, *m, *p;
        split(root, cow[i].price, l, r);
        p = r;
        if (!p) {
            printf("-1");
            return 0;
        } 
        while (p->lc) p = p->lc;
        ans += p->val;
//      printf("%d\n\n", p->val);
        merge(l, r, root);
        split(root, p->val, l, r);
        split(r, p->val + 1, m, r);
        merge(l, m->lc, l);
        merge(m->rc, r, r);
        merge(l, r, root); // 丢弃了m 
    }
    printf("%lld", ans); // TIP 别忘了用long long哟 

    return 0;
} 

使用CamStream配合OBS低成本实现功能强大的现场直播

你是否经常去户外直播?你是否苦恼各大直播平台的直播软件不够强大?你是否在犹豫是否购买价格高昂的直播设备?

来试试CamStream+OBS直播方案,低成本,功能强大!

请注意,技术更新非常迅速,本文章可能在发布后一段时间后不再可用。

需要

在下面的教程中,我们需要:

  • 一台手机(Android系统)
  • 一台笔记本电脑(MacOS系统或者其他)
  • 50元人民币(银行卡,不是现金)
  • 不限制流量的流量卡(日租也可以,土豪无视)
  • 合理的梯子(由于相关法律法规,部分asdfasdfasdfadsfsafads)
  • 以及一个愿意折腾的心(其实不是特别麻烦啦)

配置网络

打开你的手机,设置你的手机上网卡为直播用的流量卡。

打开你的手机热点,设置连接密码,并且取消对流量的限制,以及没有连接一段时间后自动关闭的功能,保证你的直播网络稳定性。

配置自动待机

打开你的手机、电脑,找到自动待机的设置,全部取消,保证直播稳定性

安装 CamStream

CamStream 是本篇文章的主角,其开发商同时也开发了另外一个广受好评的应用 Screen Stream Mirroring 推荐有需要的朋友们可以去play上搜索购买。

过梯子,访问 https://play.google.com/store/apps/details?id=com.mobzapp.camstream ,下载,安装。

配置 CamStream

CamStream的功能非常丰富,建议各位有时间可以去看看配置选项,自己调整成为自己最喜欢的选项

点击左上角菜单,点击购买专业版,去除广告以及最长直播时间限制(间隔一段时间自动停止直播),等待应用重启。

点击左上角菜单,选择串流到VLC播放器/OBS

横过来屏幕(别忘了解除屏幕锁定),记住串流地址。

安装 OBS

建议用梯子,访问 https://obsproject.com/ ,下载,安装。如果很早之前已经安装过OBS,这里仍然推荐安装一下新版。

配置 OBS

OBS也有非常丰富的功能,也欢迎各位自行发掘。

首次打开后,同意一下GPL协议。

跳过首次配置向导。

找到场景的位置,点击左下角或者右键空白,添加场景。

点击你所需要的场景,点击左下角或者右键空白,添加来源

找到媒体源,点击。

起个好听的名字。

取消选择本地文件,然后在输入那里填入之前所找到的串流地址,输入格式填入HLC。

后面,如果需要修改该来源的属性,点击相应来源后点击下方齿轮即可修改。

前往设置,找到配置串流的地方,把在直播平台上看到的串流地址以及串流参数复制到相应位置。

返回主界面,点击开始推流。

如果想同时录制直播,可以点击开始录制,文件会保存到设置里所填写的位置,一般为“家”目录下的影片(影视)目录。

如果想要录制原始素材,可以使用VLC直接录制信号,不过这里又是坑(比如录制完没有声音啦,视频格式有问题啥的),故不再多述。

对于音频的混音方式,OBS的行为会比较怪异,另外还有码率的高低以及分辨率会导致效果变化很大,建议各位用另外一台手机或者电脑实时监控直播网站上的直播画面。

另外,OBS的坑很大,所以建议各位在正式直播前先预先直播一下。

如果发现了文章错误或者有些地方文章介绍不够完整,欢迎各位在下方评论区跟我留言互动。欢迎关注我的b站直播间:https://live.bilibili.com/71261,我的新浪微博:https://weibo.com/lookas2001,另外,都翻墙了,关注下Twitter以及Facebook也不是难事嘛:https://twitter.com/lookas20011 https://www.facebook.com/lookas2001

本文章由lookas2001创作,保留所有版权权利,如需转载,请在评论区中说明。