题目描述

dd最近比较喜欢二进制数，她认为对于任意两个正整数x,y（x<=y），当且仅当x,yx,y的二进制非前导零部分最大连续重合位数≥k时，x,y是匹配的，比如175的二进制形式为(10101111),472的二进制形式为(111011000),因此175175和472472最大连续重合部分为(1011)，故这两个数的最大连续重合位数为4。 现在给定一个正整数n(n≤2000)和一个k，求对于所有x,y(且1≤x＜y≤n)x,y(且1≤x＜y≤n),满足条件的匹配数

输入样例

6 2

输出样例

7

算法1

(暴力枚举) $O(n^2)O(n^2)$

题目的意思显而易见，其实这一题挺简单的就是先预处理出来1-n的二进制表示之后每长度为k的子串一存之后对于1-n中不同的两个数两两check一下就可以了 really简单但是当时看没啥人做出了我就放弃了，，，/(ㄒoㄒ)/~~

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_set>

using namespace std;

const int N=2020;
string s[N];
unordered_set<string> S[N];
bool st[N][N];

void init(int n)
{
    for(int x=0;x<=n;x++)
    {
        string str;
        for(int i=10;i>=0;i--)
        {
            if(x>>i&1) str+='1';
            else str+='0';
        }
//         cout<<str<<endl;
        int i=0;
        while(i<str.size()-1&&str[i]=='0') i++;
        str=str.substr(i);
        s[x]=str;
//         cout<<str<<endl;
    }
}

int main()
{
    int n,k;
    cin>>n>>k;
    init(n);
    int ans=0;
    for(int i=0;i<=n;i++)
    {
//         cout<<"i = "<<i<<endl;
        if(s[i].size()<k)continue;
        int len=s[i].size();
        for(int j=0;j+k-1<len;j++)
        {
            string tmp=s[i].substr(j,k);
//             cout<<"i = "<<i<<" tmp = "<<tmp<<endl;
            S[i].insert(tmp);
        }
    }
    for(int i=0;i<=n;i++)
    {
        if(s[i].size()<k)continue;
        for(int j=i+1;j<=n;j++)
        {
            for(auto t:S[i])
            {
                if(S[j].count(t)&&!st[i][j]) 
                {
//                     cout<<"i = "<<i<<" j = "<<j<<" t = "<<t<<endl;
                    ans++;
                    st[i][j]=st[j][i]=true;
                }
            }
        }
    }
    cout<<ans<<endl;
}