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 w23c3c3 @ 2020-12-16 20:36:20
@aldol_reaction 就这个吧(希望你看得懂) https://oi-wiki.org/misc/complexity/
by expect @ 2020-12-16 20:36:47
简单来讲时间复杂度大概就是关于输入数据的一个多项式,每个数都只保留最高次,忽略常数因子
定义不太严谨,大概是这么一个东西
by aldol_reaction @ 2020-12-16 20:40:06
@千反田 好的我去学一下复杂度nm的做法。不过我看题解好多人都是n2m做法,没想到这是错解。
and您的意思是洛谷的机子是5e7稳过,1e8可以冲吗?
by aldol_reaction @ 2020-12-16 20:41:39
去世@w23c3c3
蒟蒻尝试去学习一下,谢谢dalao的帮助。已关注
by AsunderSquall @ 2020-12-16 20:42:03
@千反田
时间复杂度挺简单的
快来分析吉司机线段树的复杂度!
by expect @ 2020-12-16 20:43:00
@aldol_reaction 这个大概是ccf少爷机的速度
洛谷稍微慢一点,不过也没差太多
by w23c3c3 @ 2020-12-16 20:43:09
@aldol_reaction luogu机子是1e8稳过,5e8能冲吧(大雾
by expect @ 2020-12-16 20:43:36
@我知道了王子 大佬别d我我指的是简单的复杂度不带势能分析的orz
by AsunderSquall @ 2020-12-16 20:43:56
@千反田 或者构造可以卡到两只
by expect @ 2020-12-16 20:44:23
@w23c3c3 那得是常数极小的像dp之类的吧(