竞码编程-蓝桥杯模拟赛4（大学生组&青少年组）个人题解

试题A：可爱的倍数

很容易想到尽量从大往小贪心，如果可以取一个数，就往余下的数的集合中删除其因子，求出取出的数的个数，做出来答案是 $100$ 。另一个角度想想，我们把所可以 $101\sim 200$ 放入集合，而剩余的数字，再放进去显然都会是矛盾的。又因为假设可以有超过100个数，在 $a\sim 2a$ 这100个抽屉中，必然会出现一个抽屉放两个元素，也就是存在倍数。所以，不可能超过100了。

试题B：可爱的志数

典型的类似于筛法的约数计数。

当然作为填空题 $n\sqrt n$ 的暴力也是可接受的。

n=200328
#n=20
cnt=[0]*(n+1)
ans=0
for i in range(1,n+1):
    for j in range(i,n+1,i):
        cnt[j]+=1
    if cnt[i]<=3:
        ans+=1

print(ans)
#print(cnt)

试题C：斐波那契数列

斐波那契数列的模数列实际上是存在循环节的，这个循环节长甚至有公式。当然一般人不知道，所以可以打出前面一百项找找规律。看出了循环节是 $60$ 。最后答案为 $9$ 。

f=[0]*100
f[1]=1
f[2]=1
for i in range(3,100):
    f[i]=f[i-1]+f[i-2]
print([i%10 for i in f])

n=2002003281331
print(f[(n-1)%60+1]%10)

试题D：路径配对

很显然，如果给每一个小三角形编号 $0\sim 15$ ，那么题中总的路径数不会超过 $2^{16}=65536$ 条（每个三角形有选与不选两种可能），实际上用dfs搜索，或者二进制枚举出来的路径数远远要小于这个数，因此，最后我们暴力用 $cnt^2$ 的效率枚举不相交路径即可。

三角形按层编号。因为三角形不大，这里采用手动连边的方式。枚举起点dfs，dfs中用vis数组来标记路径已经覆盖的三角形有哪些，再把路径的信息扔进字典s中。这里一定要用字典，因为不同顺序可以出来同样的vis。

最后不要忘了ans要除以2，这是因为两条路径是无序的。

实现中有很多细节需要小心。为了防止出错，可以先备好一个小三角形做数据，进行检查。

E=[[] for i in range(16)]
val=[1,3,2,2,4,2,4,4,7,3,5,6,3,1,5,2]

def add(a,b):
    E[a].append(b)
    E[b].append(a)

add(0,2);add(1,5);add(3,7);add(4,10);add(6,12);add(8,14)

add(1,2);add(4,5);add(9,10);add(11,12);add(6,7);add(13,14)

add(2,3);add(5,6);add(7,8);add(10,11);add(12,13);add(14,15)

vis=[False]*16
s=dict()

def dfs(x):
    s[tuple(vis)]=sum([val[i] for i in range(16) if vis[i]])
    for i in E[x]:
        if not vis[i]:
            vis[i]=True
            dfs(i)
            vis[i]=False

for i in range(16):
    vis[i]=True
    dfs(i)
    vis[i]=False

ans=0
for i in s:
    for j in s:
        if not [x for x in range(16) if i[x] and j[x]] and s[i]==s[j]:
            ans+=1

print(ans//2)

试题E：解决NPC问题

我们尝试找到符合条件的哪些年份在求出相应的日期。这里依旧是采用了datetime模块来方便实现。

from datetime import *

for y in range(2,3000):
    a=date(y,1,1)+timedelta(299)
    b=date(y+1,1,1)+timedelta(199)
    if a.weekday()==2 and b.weekday()==2:
        c=date(y-1,1,1)+timedelta(99)
        print(c.weekday())

发现符合条件的年份很多，但答案都是周四。事实上可以从逻辑上来推导出本年必然是闰年，再以此求出星期数。

试题F：友好数字

水题。

s=set()
for i in range(10):
    a=int(input())%42
    for j in str(a):
        s.add(j)

print(len(s))

试题G：友好序列

水题。

n=int(input())
s=input()

g=[0,0]
h=[0,0]

for i in range(n>>1):
    if s[i]=='R':
        g[0]+=1
    else:
        g[1]+=1

for i in range(n>>1,n):
    if s[i]=='R':
        g[1]+=1
    else:
        g[0]+=1

for i in range(0,n,2):
    if s[i]=='R':
        h[0]+=1
    else:
        h[1]+=1

for i in range(1,n,2):
    if s[i]=='R':
        h[1]+=1
    else:
        h[0]+=1

print(min(g[0],g[1],h[0],h[1]))

试题H：友好组合

注意题目中要求字典序最小，那么实际上从小到大贪心，能放就放，当然可以满足字典序最小。

n,m,k=map(int,input().split())

a=[]

for i in range(n):
    f=True
    for j in a:
        if str(bin(i^j))[2:].count('1')<k:
            f=False
            break
    if f:
        a.append(i)
        if len(a)==m:
            break

print(" ".join(list(map(str,a))))

试题I：同桌的你

手动模拟一下发现，我们从原序列 $A$ 取走数字放到另一个位置的最小次数，得到符合条件的某个序列 $B$ ，实际上意味着， $A$ 取走相应数字，剩下的序列需要和 $B$ 取走相应数字剩下的序列一致——因为取走的数字，顺序可以随意放，放到该放的位置即可。如果我们已知 $B$ ，只需要求和 $A$ 的最长公共子序列即可。

$B$ 有很多种，因为相邻两元素可以任意。实际上正因为此，我们完全可以将相邻的两个元素，重新编号为同一种。例如 $1,n*2$ 都应该编成 $0$ ， $2,n*2-1$ 都应该编码成 $1$ ...这样我们对新的 $A'$ 和 $B'$ 求一次最长公共子序列，就可以覆盖所有答案了。

最长公共子序列是一道经典的 $dp$ 题。这里已经可以有 $O(n^2)$ 解法了。

注意到，序列 $A$ 和序列 $B$ 的元素集是一致的，比较特殊，另外 $B=00112233...$ 。公共序列和不下降序列，出现了一致性。那么意识到这实际上也可以是一个对于 $A$ 的最长上升（不下降）子序列问题。而最长上升（不下降）子序列问题是有 $O(n\log n)$ 解法的，可拿满分。

这里可以写线段树。也可以采用更普遍的“三行二分优化”的方式。

from bisect import *

n=int(input())
a=list(map(int,input().split()))
b=sorted(a)

for i in range(len(a)):
    a[i]=bisect_left(b,a[i])
    if a[i]>=n:
        a[i]=(n<<1)-1-a[i]

n<<=1
g=[1<<31]*(n+1)
dp=[0]*n

for i in range(n):
    k=bisect_right(g,a[i],1,n+1)
    dp[i]=k
    g[k]=a[i]

print(n-max(dp))

试题J：奇怪的回路

首先我们手动模拟一下，发现这个图是左右对称的，另外很容易看出，如果 $n$ 是奇数，一定没有答案。但 $n$ 是偶数如何找答案是一个大问题。

题解的做法像是一个魔改过后的fleury算法。现在也没有理解。因此先贴上我12分的暴力搜索。以后再研究

n=int(input())
vis=[False]*n
ans=[0]

if n&1:
    print(-1 if n>1 else "0 0")
    exit(0)

def dfs(x):
    if len(ans)==n:
        if ans[-1]*2%n==0:
            print(" ".join(map(str,ans))+" 0")
            exit(0)
        return 
    p=x*2%n
    q=(x*2+1)%n
    if not vis[p]:
        vis[p]=True
        ans.append(p)
        dfs(p)
        ans.pop()
        vis[p]=False
    if not vis[q]:
        vis[q]=True
        ans.append(q)
        dfs(q)
        ans.pop()
        vis[q]=False

vis[0]=True
dfs(0)