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创作,保留所有版权权利,如需转载,请在评论区中说明。

CCC 2018 解题报告以及心得体会

2018年3月8日,北京,清华大学,与滕老师、一群可爱的小伙伴们还有他们的家长一起参加了 CCC 2018 清华赛区的比赛。废话不多说,下方是我对各个题目的想法以及最后的总结。

Editor

题目解析

提供两个字符串,要求比较大小规则。首先需要对两个字符串的所有字符转换为小写字母,然后对两个字符串从左到右逐位比较,如果遇到一个位置上a字符串比b字符串在字典的位置靠前,输出该字符串;如果遇到一个字符串遇到结尾,输出该字符串。

算法设计

按照题目解析的方式进行模拟。

Tags: simulation

失误分析

最开始在写的时候,偷懒使用了全文翻译,结果没有完全理解题目的含义。

为了算法效率的优化,在每一次比较的时候进行小写转换,导致在第一次输出的时候出现了问题(后面的字符串还是大写,不过后来改正了)。

另外如果错了,那估计就是没有充足的测试?

得分预估

最高:100

Equation

题目解析

题目提供一个形如 p[]q=r 的算式,其中算式的操作符号可能是 + – *;其中 p q r 的部分数字被大写字母替换;如果一个字母是在 p q 或者是 r 的最高位,则该字母不能为 0 ;另外每一个字母所对应的数字不能相同。

算法设计

初步想法,从0-9枚举每一字母对应的数字并且带回验证,算法最坏复杂度为O(10^9)

考虑到每一个字母的对应的数字不能相同,可以对字母产生0-9的全排列,然后替换算式中相应的位置,带回验证。算法最坏复杂度为O(10!)

Tags: enumerate

失误分析

由于之前没有怎么接触过枚举(或者说暴力)的题目,或者说上次szr讲的那道暴力最终也没找时间写,对这种题目一下子就懵住了,尤其是对于字母的枚举,完全不知道如何下手。

过高的估计算法复杂度,认为10s的程序一定过不去,后来也就没有心情去做这道题了。

得分预估

最高:0

Count Path

题目解析

提供一个带有 n 个点的图,对于点 i ,有一个权值 ai ,对于 i j 两点;如果 i < j 则有 wij 条有向边从 i 指向 j ,求问从点 1 到点 n 总共有多少条路径。另外,最终结果需要mod一个数。

另外,定义有一个函数为 lcs(i, j) ,返回 i j 转换为二进制后从右看起共用1,比如 3 = (11)2 , 5 = (101)2 则两者lcs后的结果为 1 = (1)2。

wij = (ai + lcs(ai, aj)) * (aj + lcs(ai, aj)) (印象里,这里应该是对 ai aj lcs)

算法设计

动态规划题目,定义 si 为为 i 到 n 的道路数,那么 si = s(i + 1) * wi(i + 1) + s(i + 2) * wi(i + 2) + … + sn * win,其中 sn = 1。

Tags: bit_operation dp

失误分析

被数据范围给吓到了

lcs的时候提供的操作数错误(印象里是提供ai,aj而不是i,j)

忘记mod数了。

得分预估

最高:50

第四题

看不懂。

第五题

看不懂。

总结

失误分析

由于耍了些小聪明,用了全文翻译,结果机翻的结果搭配着图片版本因为bug最终没有显示的公式,实际上读题效率还不如查字典来的快。

对IDE的依赖性太强了,依靠着IDE的符号自动补全,没有自动补全后,写代码越写越烦躁。

对算法复杂度的估算(包括数据范围的分析)能力不行,心理承受能力太差。

由于被第二道题卡住,花费了过量的时间去看那些我并看不懂的4 5题,另外,搭配上考试前的睡眠不足,最后,心态爆炸。

还是要多写题啊。

总分预估

150左右浮动。

另附一幅合影,我才不会说在这么远照相是因为近的地方被一对夫妻拍婚纱照了呢

合影