我留下了关于我的逻辑是什么的评论。它的工作方式应该是,例如,如果我们有K=3
和S={1,7,2,4}
,那么每对的和不除以K
的最大子集是{1,7,4}
。
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
static void Main(String[] args)
{
int k = Int32.Parse(Console.ReadLine().Split(' ')[1]);
var S = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
// first get all pairs in S whose sum doesn't divide k,
// each pair in their own subset set of S
var subsets = from i in S
from j in S
where i < j && ((i + j) % k != 0)
select new HashSet<int>() { i, j };
// for each subset, for each number in the original set
// not already in the subset, if the number summed with
// every numer in the subset doesn't divide k, add the
// number to the subset
foreach(var ss in subsets)
foreach(int n in S.Where(q => !ss.Contains(q)))
if(ss.All(m => (m + n) % k != 0))
ss.Add(n);
// get the size of the largest subset, print to console
int max = subsets.Select(ss => ss.Count).Max();
Console.WriteLine(max);
}
}
您对问题的算法可能是错误的,但意外的行为是由于代码中的错误造成的。(但即使你修复了它,我认为它对在线法官来说太慢了,而且你可能会错过一些棘手的案件,你可以尝试提交它)。
HashSet
对象subsets
不会更新,因为当您调用Add
时,整数会添加到另一个HashSet
的副本中。
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
public class Test
{
public static void Main(String[] args)
{
...
foreach(var ss in cnt){
foreach(int n in S.Where(q => !ss.Contains(q)))
if(ss.All(m => (m + n) % k != 0)){
ss.Add(n);
}
// Log here, you will see the size is updated to 3
Console.WriteLine(ss.Count);
}
// Log here, it is still printing 2 !
foreach(var ss in cnt)
Console.WriteLine(ss.Count);
// get the size of the largest subset, print to console
int max = ...
Console.WriteLine(max);
}
}
一个简单的修复方法是首先新建一个全局哈希集列表,并更新该列表
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
public class Test
{
public static void Main(String[] args)
{
int k = Int32.Parse(Console.ReadLine().Split(' ')[1]);
var S = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
List<HashSet<int>> cnt = new List<HashSet<int>>();
// first get all pairs in S whose sum doesn't divide k,
// each pair in their own subset set of S
cnt = (from i in S
from j in S
where i < j && ((i + j) % k != 0)
select new HashSet<int>() { i, j }).ToList();
// for each subset, for each number in the original set
// not already in the subset, if the number summed with
// every numer in the subset doesn't divide k, add the
// number to the subset
foreach(var ss in cnt){
foreach(int n in S.Where(q => !ss.Contains(q)))
if(ss.All(m => (m + n) % k != 0)){
ss.Add(n);
}
}
// get the size of the largest subset, print to console
int max = cnt.Max(ss => ss.Count);
Console.WriteLine(max);
}
}
然而,这个问题在O(k)
(如果不计算I/O时间,即O(N)
)中可以很容易地解决
这是我在C++中接受的代码
#include<bits/stdc++.h>
using namespace std;
int n,k,a,c[105] = {0},ans=0;
int main() {
cin >> n >> k;
for(int i=0; i<n;i++) cin >> a, c[a%k]++;
for(int i=1; i<=k/2; i++){
if(k%2 == 0 && i==k/2 && c[i]) ans++;
else ans += max(c[i], c[k-i]);
}
if(c[0] && ans) ans++;
if(!ans) ans++;
cout << ans << endl;
return 0;
}
这背后的概念是模块化算法:
(a+b)%k = 0 is equavalent to (a%k + b%k)%k = 0
所以实际上,我们只计算模k等于0,1,2…k-1的元素数量,将它们存储在c[0], c[1]...c[k-1]
中
那么逻辑上对于c[1]
&c[k-1]
不能一起选择,所以我们选择计数较大的一个。类似地,c[2] & c[k-2]
不能一起选择,等等。
不过也有一些特殊情况,您可以看到我的代码并查看它。
注意这个问题的一个更棘手的地方是(我认为这是一个糟糕的问题语句),如果结果集大小为1,那么它总是一个有效集,即使唯一的元素可以被k整除。(即,ans永远不会是0)
在第二个循环中,当您编写ss.Add(n);
时您将'n'添加到哈希集ss的副本中。
因此在foreach部分之后,subsets
与之前的集合保持在一起。
您可以手动计算foreach内部的最大值作为快速解决方案
使用您的方法,您将计算出所有数字都满足条件的子集,但您不会将数字的子集添加到您的整体subsets
中。因此,当你在寻找最大的子集时,你不会找到正确的子集。
foreach(var ss in subsets)
{
foreach(int n in S.Where(q => !ss.Contains(q)))
{
if(ss.All(m => (m + n) % k != 0))
ss.Add(n);
}
//Add the subset ss to subsets or replace it
}