为啥本地跑飞快,交上去就T捏

DGL__DGL_AFO @ 2024-04-20 16:26:12

#include<bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;
int a,b;
int res;
int ans;
int main()
{
    cin>>a>>b;
    //a=1;b=2;
    srand(time(0));
    while(res<=100000000)
    {
        res++;
        ans=rand();
        if(ans-a==b)
        {
            cout<<ans;
            return 0;
        }
    }

    return 0;
}

3
--------------------------------
Process exited after 0.1829 seconds with return value 0
请按任意键继续. . .

by 小粉兔 @ 2024-04-20 16:49:13

@DGL__DGL

Windows 平台上的 RAND_MAX 多是 32767，而洛谷评测机是 Linux，RAND_MAX 多是 2147483647

所以，在你本地，如果答案在 [0, 32767] 内，期望随机 32768 次就能猜到答案。所以可以在 1s 内跑出结果。（并且如果答案超出了 32767 则永远也跑不出来）

在洛谷上就没那么幸运了，因为期望要随机 2147483648 次。而且由于调用 rand() 的开销是比一般语句大的，调用 10^8 次 rand() 消耗的时间明显大于 1s，所以会 TLE。

by DGL__DGL_AFO @ 2024-04-20 16:49:38

@hexuchen

能看力,谢谢

by cmaths @ 2024-04-20 16:53:53

@GoodLuckCat 有没有可能在洛谷和 CCF 的 linux 环境下 rand() 的范围是 [0,2^{31}-1]

by Enoch2013 @ 2024-04-20 16:54:08

ac代码：

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int a,b;
    cin >> a >> b;
    cout << a+b << endl;
    return 0;
}

这不很简单吗？

by DGL__DGL_AFO @ 2024-04-20 17:06:44

@小粉兔

感谢%%%

已关

by DGL__DGL_AFO @ 2024-04-20 17:08:08

@cmaths

确实

by DGL__DGL_AFO @ 2024-04-20 17:11:06

洛谷实测:

当 res<=8e7时,用时约1.13s,会超时

当 res<=7e7时,用时约993ms,不会超时

所以正确概率约为0.175(还挺高的)

by zhouzihang1 @ 2024-04-20 17:18:08

事实上这题正解是二分吧……

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b;
int main()
{
    scanf("%lld%lld",&a,&b);
    ll l=-10000000000,r=10000000000,mid,ans;
    while(l<=r)
    {
        mid=l+r>>1;
        if(mid<a+b) l=mid+1;
        else if(mid>a+b) r=mid-1;
        else{ans=mid;break;}
    }
    printf("%lld",ans);
    return 0;
}

by litjohn @ 2024-04-20 17:24:13

@zhouzihang1 正解是splay/LCT！详见题解区的大佬们

by sapo1o @ 2024-04-20 18:20:44

@DGL__DGL 我记得rand超级慢