数字匹配

NC228076. 数字匹配

描述

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

输入描述

读入共一行，包括两个正整数n,k(n≤2000,k≤10)

输出描述

输出共一行，表示匹配数

示例1

输入:

6 2

输出:

说明:

2(10)和4(100)
2(10)和5(101)
2(10)和6(110)
3(11)和6(110)
4(100)和5(101)
4(100)和6(110)

5(101)和6(110)

共7对

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 44ms, 内存消耗: 16856K, 提交时间: 2021-11-05 22:11:15

#include <bits/stdc++.h>
using namespace std;
#define b(x) (1<<((x)-1))
int i,j,n,m,t,res,f[2050][2050],msk;
int dfs(int x,int y){
	if(b(m)>x||b(m)>y)return 0;
	if(~f[x][y])return f[x][y];
	return f[x][y]=((x&msk)==(y&msk))?1:(dfs(x>>1,y)|dfs(x,y>>1));
}
int main() {
	memset(f,-1,sizeof(f));
	cin>>n>>m;
	msk=b(m+1)-1;
	for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)res+=dfs(i,j);
	cout<<res;
}

上一题

下一题

详情