1 条题解

  • 1
    @ 2026-3-24 18:32:34

    思路

    枚举每一对数列,再枚举每一个位子,计算一下相同的位数,如果是奇数就ans+1ans+1,如此简单的暴力。

    代码

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    const int N=2100;
    int a[N][N];
    signed main()
    {
    	int n,m;scanf("%lld%lld",&n,&m);
    	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%lld",&a[i][j]);
    	int ans=0;
    	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)
    	{
    		bool bk=0;
    		for(int k=1;k<=m;k++)bk^=(a[i][k]==a[j][k]);
    		ans+=bk;
    	}
    	printf("%lld\n",ans);
    	return 0;
    }
    

    如果你真的把这份暴力代码交上去了,我先批评你:为什么不好好看题解,为什么直接复制交了,为什么不思考一下?然后我再吐槽一下,O(N2M)O(N^2M)为什么能过?

    思路2

    仔细思考 (我并没有) 即可发现,在找寻每一位时会有重复运算,如果有某种神秘的方法把每一个数列的每一位只算一遍就好了。这时你想起古老的

    bitsetbitset

    注意到ai,j999a_{i,j}\le999,考虑把每一个数出现的位置存起来,细节详见代码 (其实是我解释不明白)

    代码2

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    const int N=2010;
    int a[N][N];
    bitset<N> l[N],e[1100];
    signed main()
    {
    	int n,m;scanf("%lld%lld",&n,&m);
    	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%lld",&a[i][j]);
    	for(int j=1;j<=m;j++)
    	{
    		for(int i=1;i<=n;i++)e[a[i][j]].set(i);
    		//这个数在j号位上在每一个数组中是否出现 
    		for(int i=1;i<=n;i++)
    		{
    			e[a[i][j]].reset(i);//自己不算 
    			l[i]^=e[a[i][j]];//这个数组与其他数组的相似性 
    		}
    		for(int i=1;i<=n;i++)e[a[i][j]].reset(i);//初始化好习惯 
    	}
    	int ans=0;
    	for(auto b:l)ans+=b.count();
    	printf("%lld\n",ans);
    	return 0;
    }
    
    • 1

    信息

    ID
    7721
    时间
    2000ms
    内存
    1024MiB
    难度
    10
    标签
    递交数
    8
    已通过
    3
    上传者