如何摆脱 "Time Limit Exceeded"

Question

我尝试解决在线网站中的一些问题。我用简单的 C++ 解决了一个问题，它运行良好，但有时会抛出“超出时间限制”错误。如何摆脱这个？

这是我解决的问题

There are two integers A and B. You are required to compute the bitwise AND amongst all natural numbers lying between A and B, both inclusive.

这是我的代码。

 #include<iostream>
using namespace std;
int main()
{
    int t,a,b;
    long ans;
    cin>>t;
    while(t--)
    {
        cin>>a>>b;
        ans=a;
        for(int i=a+1; i<=b; i++)
        {
            ans=ans&i;
        }
        cout<<ans<<endl;
    }
}

Answer 1

如果你有两个数字，X 和 Y，它们由有限的位集表示：

X = Bx(1), ..., Bx(n)

和

Y = By(1), ..., By(n)

两者按位与可以计算为

X ^ Y = (Bx(1) ^ By(1)), ..., (Bx(n) ^ By(n))

A B A ^ B

0 0 0

0 1 0

1 0 0

1 1 1

我们观察到：

所有的位都可以单独计算，我们有多少位就有多少方程
在一系列逻辑语句中，其中 AND 是运算符，当且仅当任何一项为 0 时，结果为 0

因此，如果任何数字都是对，则最后一位为 0。否则，最后一位将为 1。如果任何数字的倒数第二位为 0，则该位的结果将为 0 .否则就是1.

作为一般规则，基于狄利克雷提出的pigeonhole principle，如果给定位的连续（元素）足够多，那么该位的结果将为0。例如，对于最后一位你有两个变化，因此，如果你的连续集合中至少有两个数字，那么最后一位将为 0。如果我们取下一位，那么你有四个变化：00、01、10和 11。因此，如果您的连续集合中至少有 3 个数字，则该位为 0。对于下一位，您有 8 个变体：000、001、010、011、100、101、110、111。所以, 如果你的连续集合中至少有 5 个数字，则此位为 0.

现在，由于我们有一个简单的规则来确定大多数位（如果有很多项目），您最终会得到一些位，其变化数量超过了我上面描述的规则。对于这些位，您可以检查第一个和最后一个数字。如果它们对该位具有相同的值，则该值将是结果，无论是 0 还是 1。

如何摆脱 "Time Limit Exceeded"

How to get rid of "Time Limit Exceeded"

c++

runtime-error

time-limiting