一个奇葩的问题

P1439 【模板】最长公共子序列

WanderingTrader @ 2020-05-04 16:48:55

RT

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int pos1[N],pos2[N],seq[N],n;
int find_(const int goal,const int left,const int right){
    int l = left,r = right,mid,ans ;
    if(l == r)return l - 1;
    while(l < r){
        mid = (l + r) / 2;
        if(seq[mid] > goal)
            r = mid;
        else { l = mid + 1 ; ans = mid;}
    }
    return ans;
}
int solve()             //二分求LCS 
{
    int l = 1;
    seq[1] = pos2[1];
    for(int i = 2;i <= n;i ++)
    {
        if(pos2[i] >= seq[l])
            seq[++ l] = pos2[i];
        else 
            seq[find_(pos2[i],1,l) + 1] = pos2[i];  //插入 
//      for(int j = 1;j <= l;j ++)
//          cout << seq[j] << " ";
        printf("\t%d\n",l);
    }
    return l;
}
int main(){
    scanf("%d",&n);
    for(int i = 1,u;i <= n;i ++)
    {
        scanf("%d",&u); 
        pos1[u] = i;    
    }
    for(int i = 1,u;i <= n;i ++)
    {
        scanf("%d",&u);
        pos2[i] = pos1[u];
    }
    cout << solve() << endl;
    for(int i = 1;i <= n;i ++)
        cout << pos2[i] << " ";
    return 0;
}

中间代码块里的两行注释是有什么特异功能吗

| 50 |

| 12 1 3 22 39 13 35 25 21 50 33 27 42 36 6 11 46 20 48 8 4 5 30 29 17 15 34 45 38 16 41 32 47 9 44 26 37 19 2 7 49 31 40 14 10 43 24 23 18 28 |

| 9 16 8 38 7 22 13 6 24 28 29 1 44 48 25 26 50 46 40 10 14 23 37 43 47 42 3 30 35 15 2 11 41 45 18 20 19 32 21 4 34 39 31 36 33 12 27 49 5 17 |

这组数据,答案是10,中间两行注释打开就输出10,没打开就输出11,什么操作……

大佬可以解答一下吗,谢谢


by Suuon_Kanderu @ 2020-05-04 17:05:45

玄学?


by Suuon_Kanderu @ 2020-05-04 17:07:48


by infinities @ 2020-05-04 17:10:08

我谔谔,中间那个只是个输出语句,对变量没有任何影响为啥会影响答案,难道是编译器sb了?


by 谁是鸽王 @ 2020-05-04 17:10:20

一般玄学问题就是


by 谁是鸽王 @ 2020-05-04 17:10:54

而且最有可能是负数下标


by 谁是鸽王 @ 2020-05-04 17:11:02

而且最有可能是负数下标


by zhjxaoini @ 2020-05-04 17:23:14

@zycany 在 i=12 的时候,find_ 中没有执行给 ans 赋值的语句,所以返回值就是 ans 原先的值。不写中间的输出语句时,ans 所在的内存位置为 3,所以返回值为 3;写了中间的输出语句时,ans 所在的内存位置被写为了 0,所以返回值为 0。


by zhjxaoini @ 2020-05-04 17:25:31

那么就应该是二分写的有问题。


by WanderingTrader @ 2020-05-04 19:18:40

@zhaojinxi 额,好吧,那我还是不作死用lower_bound函数吧,谢谢大佬解答


|