2022 PUZZLEUP

〇〇 · 发表于 2022-12-7 19:14

bron_kerbosch.py源代码居然是递归的
# Third Party
import numpy as np

######
# MAIN
######

def bron_kerbosch(adj_matrix : np.ndarray, pivot : bool = False) -> list:
maximal_cliques = []

def N(v):
      return {i for i, weight in enumerate(adj_matrix[v]) if weight}

def _bron_kerbosch(R, P, X):
      if not P and not X:
         maximal_cliques.append(R)
      else:
         if pivot:
            u = max(P | X, key=lambda i: len(N(i)))
            _P = P.copy() - N(u)
         else:
            _P = P.copy()

         for v in _P:
            _bron_kerbosch(R | {v}, P & N(v), X & N(v))
            P.remove(v)
            X.add(v)

R, P, X = set(), set(range(len(adj_matrix))), set()
_bron_kerbosch(R, P, X)

return maximal_cliques

〇〇 · 发表于 2022-12-7 20:44

newkid 发表于 2022-11-30 23:59
聪明的办法应该是反证法、抽屉原理之类的逻辑推理方法。笨办法是用图论。棋盘总共9行，每列看作一个二进制 ...

用你链接里的代码,算出来是6,但不知道符合条件的是哪几个数//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
const int a=9;
const int b=5;
const int maxn = 1+(1<<a);
bool mp[maxn][maxn];
int best, n, num[maxn];
bool dfs(int *adj, int total, int cnt)
{
int t[maxn], k;
if(total == 0)
{
if(cnt > best)
{
best = cnt;
return true;
}
return false;
}
for(int i = 0; i < total; ++i)
{
if(cnt+total-i <= best) return false;
if(cnt+num[adj[ i]] <= best) return false;
k = 0;
for(int j = i+1; j < total; ++j)
if(mp[adj[ i]][adj[j]]) t[k++] = adj[j];

if(dfs(t, k, cnt+1)) return true;
}
return false;
}
int MaximumClique()
{
int adj[maxn], k;
best = 0;
for(int i = n; i >= 1; --i)
{
k = 0;
for(int j = i+1; j <= n; ++j)
if(mp[ i][j]) adj[k++] = j;

dfs(adj, k, 1);
num[ i] = best;
}
return best;
}
int main()
{
      n=maxn-1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
{int cnt1=0;
for(int k=0;k<a;k++)if(((i-1)^(j-1))&(1<<k))cnt1++;
if(cnt1>=b)mp[ i][j] = 1;
}
cout << MaximumClique() << endl;
return 0;
}

〇〇 · 发表于 2022-12-7 21:07

FIVE-LETTER CODE

A five-letter code will be created using the letters A, B, C, D and E. If any two codes are required to be different in at least two places, how many codes can be generated at most?

五字母代码

将使用字母A、B、C、D和E创建五个字母的代码。如果要求任意两个代码在至少两个地方不同，最多可以生成多少个代码？

一些代码示例：

AAAAA，AABAB，EDEBC，EEABC…

〇〇 · 发表于 2022-12-7 21:37

像上一题的翻版，规模更大

〇〇 · 发表于 2022-12-7 22:05

五进制数异或不为0的位大于等于二

newkid · 发表于 2022-12-7 22:35

图太大了，硬算很困难，必须用推理方法大量剪枝才有可能算出来。

〇〇 · 发表于 2022-12-8 07:44

如果4位数，借用昨天的代码是126
int base=5;
int bj(int x,int y)
{

int r=0;
while(x | y)
{
r+=(x%base)!=(y%base);
x/=base;
y/=base;

}
return r;
}

〇〇 · 发表于 2022-12-8 07:52

3位数是26，猜5位数是626？

〇〇 · 发表于 2022-12-8 08:45

应该是625，刚才忘记-1，修改后：
n=maxn-1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
{int cnt1=bj(i-1,j-1);

if(cnt1>=b)mp[ i][j] = 1;
}

〇〇 · 发表于 2022-12-8 14:30

用4个4位4进制数,已经很多了,考虑上面c程序的结果，sql估计很难

D with a as(select i,[i/pow(4,4-x)::int%4 for x in range(1,5)] AS a from generate_series(0,254)t(i)),
> r as(select a.i n1,b.i n2,count(*)cnt from a,a b, generate_series(1,4)t(x) where a.i<b.i and a.a[x]<>b.a[x] group by a.i,b.i having count(*)>=2)
> select count(*) from r limit 10;
┌──────────────┐
│ count_star() │
│ int64    │
├──────────────┤
│       30861 │
└──────────────┘

with a as(select i,[i/pow(4,4-x)::int考虑%4 for x in range(1,5)] AS a from generate_series(0,254)t(i)),
r as(select a.i n1,b.i n2,count(*)cnt from a,a b, generate_series(1,4)t(x) where a.i<b.i and a.a[x]<>b.a[x] group by a.i,b.i having count(*)>=2)
select n1,count(*) from r group by n1 order by n1 limit 10 ;

┌───────┬──────────────┐
│  n1 │ count_star() │
│ int64 │ int64    │
├───────┼──────────────┤
│    0 │       242 │
│    1 │       242 │
│    2 │       242 │
│    3 │       242 │
│    4 │       239 │
│    5 │       239 │
│    6 │       239 │
│    7 │       239 │
│    8 │       236 │
│    9 │       236 │
├───────┴──────────────┤
│ 10 rows 2 columns │
└──────────────────────┘

[每日一题] 2022 PUZZLEUP