求助qwq,AC后想问问dalao们关于此题时间复杂度的问题

P1983 [NOIP2013 普及组] 车站分级

aldol_reaction @ 2020-12-16 19:48:50

蒟蒻建图的AC代码片段在最后面。 我没开O2,用的vector存边,827msAC。但是此题复杂度是O(nnm),1e9是怎么卡过1s的?我记得1s时间复杂度两千万是可以过的。

还有个问题是,常数优化的数量级范围是多少呢。

还有想问一下我一直不懂的地方

for(int j = start; j <= endd; ++j) {
    if(stand_bool[j]) {
        for(int k = start; k <= endd; ++k) {
            if(!stand_bool[k] && !exit_edge[j][k]) {
                ++in[j], ++out[k];
                e[k].push_back(j);
                exit_edge[j][k] = 1;
            }

这个AC代码片段.n个点至多n/2个停下来,n/2不停下来,这样乘起来时间复杂度最大。变成O(nnm/4)。但是每一次循环我都需要在if判断,这个if判断算不算在时间复杂度里面呢...算的话不就是O(nnm)了吗。(好蒟蒻的问题QAQ) 完整建图部分的AC代码


void inp() {
    cin >> n >> m;

    for(int i = 1; i <= m; ++i) {
        int s = 0;
        scanf("%d", &s);
        memset(stand_bool, 0, sizeof(stand_bool));

        for(int j = 1; j <= s; ++j) {
            scanf("%d", &stand_num);
            stand_bool[stand_num] = 1;

            if(j == 1) {
                start = stand_num;
                if(final_start > start) final_start = start;
            }
            if(j == s) {
                endd = stand_num;
                if(final_endd < endd) final_endd = endd;
            }
        }

        for(int j = start; j <= endd; ++j) {
            if(stand_bool[j]) {
                for(int k = start; k <= endd; ++k) {
                    if(!stand_bool[k] && !exit_edge[j][k]) {
                        ++in[j], ++out[k];
                        e[k].push_back(j);
                        exit_edge[j][k] = 1;
                    }
                }
            }
        }
    }
}

by AsunderSquall @ 2020-12-16 20:47:17

@千反田 常数小的不应该是树状数组和树剖吗 (还有吉司机线段树)


by aldol_reaction @ 2020-12-16 20:47:53

认真的吗@w23c3c3 我太蒟蒻了,分不清您是开玩笑的还是认真的


by expect @ 2020-12-16 20:52:04

@我知道了王子 朴素dp也挺小啊(

不过我很多时候直接把树状数组看成近似O(1)的


by aldol_reaction @ 2020-12-16 21:04:45

@千反田 不知道洛谷的机子是他说的范围还是您说的范围?就做一般题而言


by AsunderSquall @ 2020-12-16 21:27:02

@千反田 dp 常数不小啊, dp 是跑满的啊。
上述两个是跑不满所以常数小啊


上一页 |