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;
} 

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左右浮动。

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

合影