-1

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

这是我解决的问题

有两个整数 A 和 B。您需要计算位于 A 和 B 之间的所有自然数之间的按位与，均包括在内。

这是我的代码。

 #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;
    }
}
4

1 回答 1

3

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

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

和

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

两者之间的按位与可以计算为

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

ABA ^ B

0 0 0

0 1 0

1 0 0

1 1 1

我们观察到：

  • 所有位都可以单独计算，我们有尽可能多的等式
  • 在一系列逻辑语句中，其中 AND 是运算符，当且仅当任何项目为 0 时，结果才为 0

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

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

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

于 2020-10-07T17:17:24.353 回答