`

宏用的时候要想清楚!(宏不是那么好用的)

阅读更多
#define MAX(x,y) x>y?x:y
 

从昨天晚上到今天晚上,一直在调试一道线段树求最值的简单题,就是hdu的1754,一直TLE,无语,如此简单的题怎么会这样。搜索别人的代码,发现思路都一样,怎么会这样。

晚上重新写了一遍,结果AC了。然后就找原因,唯一不同的是一个用了

 

另一个AC的用了

 

int max(int x, int y)

{

      return x > y ? x : y;

}

 这下当我调用MAX对query的结果进行取最值的时候就出现了问题。重复计算了一次,导致了致命的超时!。

作为证据贴下自己的两个代码:

//超时的代码:
#include <stdio.h>
#define N 200010
#define MAX(x,y)  x>y?x:y
typedef struct{
    int left, right, mid;
    int score;   
}SegNode;
SegNode a[4 * N + 1];
int p[N + 1];

void build(int left, int right, int ind)
{
    int mid, tl, tr;
    a[ind].left = left;
    a[ind].right = right;
    
    if(left == right) 
    {
        a[ind].score = p[left];
        return ;
    }
    a[ind].mid = (left + right) / 2;
    build(left, a[ind].mid, ind * 2);
    build(a[ind].mid +1, right, ind * 2 + 1);
    a[ind].score = MAX( a[ind * 2].score, a[ind * 2 + 1].score ); // sum of the num 
}

int query(int left, int right, int ind)
{
    if(a[ind].left == left && right == a[ind].right)
        return a[ind].score;
    if(right <= a[ind].mid)
        return query(left, right, ind * 2);
    else if(left > a[ind].mid)
        return query(left, right, ind * 2 + 1);
    else
        return MAX(query(left, a[ind].mid, ind * 2) , query(a[ind].mid +1, right, ind * 2  + 1));
}

void modify(int site, int var, int ind)
{
    if(a[ind].left == a[ind].right)
    {
        a[ind].score = var;
        return;
    }
    if(site <= a[ind].mid)
        modify(site, var, ind * 2);
    else
        modify(site, var, ind * 2 + 1);
    a[ind].score = MAX(a[ind * 2].score , a[ind * 2 + 1].score);
}


int main()
{
    int t;
    int n;
    int i, j, k;
    int st, ed;
    char cmd[10];

        while(scanf("%d%d", &n, &k) == 2)
        {
            for(i = 1; i <= n; i++)
            {
                scanf("%d", &p[i]);    
            }    
            build(1, n, 1);
        
            while(k--)
            {
                getchar();
                scanf("%c%d%d", &cmd[0], &st, &ed);
                if(cmd[0] == 'Q')
                    printf("%d\n", query(st, ed, 1));
                else
                    modify(st, ed, 1);                                        
            }
        }
    return 0;    
}
 
//AC的代码:
#include <stdio.h>
#define N 200010

typedef struct{
    int l, r, mid;
    int mmax;
}NODE;

static inline int  MAX(int x, int y)
{
    return x>y?x:y;    
}

NODE node[N * 4 + 1];
int val[N];
void build_tree(int ll, int rr, int ind)
{
    node[ind].l = ll;
    node[ind].r = rr;
    if(ll == rr)
    {
            node[ind].mmax = val[ll];
            return ;
    }    
    node[ind].mid = (ll + rr) / 2;
    build_tree(ll, node[ind].mid, ind * 2);
    build_tree(node[ind].mid + 1 , rr, ind * 2 + 1);
    node[ind].mmax = MAX(node[ind * 2].mmax, node[ind * 2 + 1 ].mmax);    
}

int query(int ll, int rr, int ind)
{
   if(ll == node[ind].l && rr == node[ind].r)
        return node[ind].mmax;
   
   if(rr <= node[ind].mid) 
        return query(ll, rr, ind * 2);
   if(ll > node[ind].mid)
        return query(ll, rr, ind * 2 + 1);
    return MAX(query(ll, node[ind].mid, ind * 2), query(node[ind].mid + 1, rr, ind * 2 + 1));
}

void update(int site, int b, int ind)
{
    if(node[ind].l == node[ind].r)
    {
            node[ind].mmax = b;
            return ;
    }
    if(site <= node[ind].mid)
        update(site, b, ind * 2);
    else 
        update(site, b, ind * 2 + 1); 
    node[ind].mmax = MAX(node[ind * 2].mmax, node[ind * 2 + 1].mmax);   
}

int main()
{
    int n, k;
    int i;
    int a, b;
    char c;
    while(scanf("%d%d", &n, &k) != EOF)
    {
        for(i = 1; i <= n; i++)
        {
            scanf("%d", &val[i]);    
        } 
        //printf("yes\n");   
        build_tree(1, n, 1);
        //printf("over\n");
        while(k--)
        {
            getchar();
            scanf("%c%d%d", &c, &a, &b);
            //printf("%c %d %d\n", c, a, b);
            if(c == 'Q')
                printf("%d\n", query(a, b, 1));
            else
                update(a, b, 1);    
        }
    }
    return 0;    
}
 

 

分享到:
评论

相关推荐

    Word2021删除单个的宏和删除宏方案.docx

    5. 删除宏方案会影响所有使用该方案的文档,因此在执行此操作前请确保已考虑清楚。 宏的安全性和管理 在使用宏时,需要注意的是,不安全的宏可能携带病毒或恶意软件,因此在打开未知来源的文档时,应谨慎启用宏。...

    B类宏程序的应用

    首先,文章介绍了WHILE语句这一循环功能在椭圆宏程序中的使用。WHILE语句允许程序在满足特定条件时重复执行一段代码,直到条件不再满足。其基本结构为`WHILE [条件表达式] DO m;...END m;`。这里的m是一个程序标号,...

    WORD删除宏.docx

    4. 单击“删除”按钮,确认你想要删除选定的宏方案。 5. 完成删除后,记得点击“关闭”按钮来关闭宏方案管理器窗口。 删除宏需要注意的是,如果宏是与特定文档关联的,那么删除宏不会影响Word模板中的宏。如果宏是...

    c语言宏定义详解

    更加清楚明了得学懂c语言,明确宏定义在c中是怎样表示的,让大家少走弯路。

    嵌入式系统总是要用户对变量或寄存器进行位操作。给定一个整型变量a,写三个宏定义,第一个设置a的bit n,第二个清除a 的bit n,第三个取第n到n+4位的值。在以上操作中,要保持其它位不变。

    嵌入式系统总是要用户对变量或寄存器进行位操作。给定一个整型变量a,写三个宏定义,第一个设置a的bit n,第二个清除a 的bit n,第三个取第n到n+4位的值。在以上操作中,要保持其它位不变。

    JS宏和VBA条形码二维码生成插件

    Excel VBA 或者 WPS JS宏 要批量生成二维码或者条形码,一般通过网络请求的方式从网站上获取,对于不能联网的电脑非常麻烦。 另类的解决办法:利用bwip-js包,通过node.js环境搭建本地服务器 ,将其打包成exe可执行...

    Excel-VBA宏编程实例源代码-更改GetOpenFilaname方法的选项.zip

    2. **Title**:设置对话框的标题,使用户清楚知道他们要做什么。 3. **InitialDirectory**:指定对话框打开时的初始目录。 4. **AllowMultiSelect**:若设置为True,则允许用户选择多个文件;若为False,则只能选择...

    打印PPT工具 字迹清楚大小适中 一页八张

    1. **自定义布局**:宏可以帮助用户创建一个自定义的打印布局,使得每一页可以容纳八张幻灯片,而不是默认的布局。这可以通过调整幻灯片的缩放比例和排列方式来实现。 2. **自动调整大小**:宏可以智能地调整每张...

    ABB DCS500B 主从宏软件(1.1)手册.pdf

    通过以上知识点的总结和解释,用户可以更清楚地理解ABB DCS500B主从宏软件(版本1.1)的工作原理和使用方法,以及在使用该软件时需要注意的安全事项和系统配置要求。这不仅有利于用户更好地利用ABB的产品,也能够...

    excel进销存表格模板多仓库出入库管理 1个表格管理多个仓库+wps宏插件

    仓库管理中,有时需要同时记录多个仓库账目。比如分为材料科库、成品库等;也有按地区 分的,比如北京仓、上海仓等。此Exce1表格,能同时管理多个仓库账目,提高工作效率...注意使用前先安装好wps宏插件,压缩包中有。

    anaphorae:一小组照应宏

    (原始宏返回一个与传递给它们的第一个表单具有相同元数据的表单,这些宏不会复制这种行为) (要更清楚地描述他们的行为,请查看测试。)部分的一个不完全准备好的partial实现,额外支持在后面的参数应该传入的...

    宏国芯 T200 视频解决方案IC 入门教程手册

    在使用 T200 进行 GUI 设计时,需要对图资进行适当的预处理,以确保它们能够在各个图层上正确显示。图资处理主要包括以下几个步骤: 1. **确定 BOO 背景图**: - **过程**:首先需要确定一个合适的背景图像作为 ...

    JS异步宏队列与微队列原理区别详解

    JavaScript中的异步处理机制是...开发者需要清楚地知道哪些操作会触发微任务,哪些会触发宏任务,以便更好地控制代码的执行流程。在编写异步代码时,合理利用宏任务和微任务可以帮助提高程序性能并避免意外的并发问题。

    GCC预处理程序学习总结借鉴.pdf

    宏定义包含一行,若为表达清楚或表达式太长时,可将宏写成多行,并用连续符号反斜杠‘\’。宏定义按照顺序处理这些文本,而且只有在定义宏之后才会替换该宏。 例如,下面是一个多行宏定义: #define ran(low,high)...

    汇编教程 非常详细 说明的非常清楚 学汇编很好的教程

    汇编教程 非常详细 说明的非常清楚 学汇编很好的教程 课程介绍 第1章 预备知识  1.1 汇编语言的由来及其特点  1 机器语言  2 汇编语言  3 汇编程序  4 汇编语言的主要特点  5 汇编语言的使用领域  1.2 ...

    汇编程序的调试利器 白皮书

    对于其他寄存器,只要能够将它们的值转移到上述寄存器之一,也能够使用该宏显示其值。此外,该宏还支持显示负数值,并自动添加负号。 #### 实现原理 为了更好地理解`FG5H!HFG`宏的工作原理,我们可以通过分析提供...

    二级C语言 第八章 编译预处理.docx

    这些例子清楚地展示了宏定义如何帮助简化代码、提高可读性和复用性,并且可以用于解决特定问题,如数学计算、数据格式化和文本操作。通过熟练掌握这些编译预处理技术,C语言程序员能够编写出更加灵活和高效的代码。

    made4U ASM-MACRO 0.6

    要学或正在学计算机汇编的同学可能用的上哈,都是一些基础的宏和DEMO程序,初学者适用。 &lt;br&gt; 下面附上源程序以及DEMO程序,由于汇编程序受计算机环境影响较大,今天发现这些以前的DEMO程序运行效果和以前大不...

Global site tag (gtag.js) - Google Analytics