2025.11.7 月考游记

前一节体育课十二分钟跑跑寄了遂在自己笔记本上打的比赛。

一种等价类划分问题

模拟。可以使用字典完成。
注意审题，范围不包括m和n，以及要按数字和大小顺序输出。一开始还没注意输入输出格式。T1再次连交两发WA.
以后做题一上来一定不能急，仔细审题，确保签到题一次性对。

from collections import defaultdict  
m,n,k=map(int,input().split(','))  
a=defaultdict(list)  
keys=set()  
for i in range(m+1,n):  
    t=str(i)  
    s=0  
    for j in range(len(t)):  
        s+=int(t[j])  
    if(s%k==0):  
        a[s].append(i)  
        keys.add(s)  
keys=list(keys)  
keys.sort()  
for i in keys:  
    print(",".join(map(str,a[i])))

dance

贪心。相邻两人组一组，差一定是最小的。

n,d=map(int,input().split())  
a=list(map(int,input().split()))  
flag=1  
a.sort()  
for i in range(0,2*n-1,2):  
    if(a[i+1]-a[i]>d):  
        flag=0  
        break  
if(flag==1):  
    print("Yes")  
else:  
    print("No")

洋葱

直接考虑每个方块的数字之和，周围一圈的和就是大方块减小方块。

n=int(input())  
a=[]  
for i in range(n):  
    t=list(map(int,input().split()))  
    a.append(t)  
i=0  
j=n-1  
res=[]  
while(i<=j):  
    temp=0  
    for p in range(i,j+1):  
        for q in range(i,j+1):  
            temp+=a[p][q]  
    res.append(temp)  
    i+=1  
    j-=1  
res.append(0)  
ans=[]  
for i in range(len(res)-1):  
    ans.append(res[i]-res[i+1])  
print(max(ans))

数的划分

dfs需要剪枝。为保证不重不漏，考虑从小到大搜，因此每次搜索的数不小于前一个数，同时不大于剩余所有数的平均数。
dp状态定义为i个数分为j组的方案数。由于每组均为正整数，考虑先每组置1，再将剩余的数分1-j组。
状态转移方程：\(dp[i][j]=\sum_{k=1}^j dp[i-j][k]\)
注意到\(dp[i][j]=\sum_{k=1}^{j-1} dp[i-j][k]\)
因此\(dp[i][j]=dp[i-1][j-1]+dp[i-j][j]\)
或者考虑选1或不选1.选1即为dp[i-1][j-1],不选1则可以把每组减1，依然符合条件，即为dp[i-j][j].

n,k=map(int,input().split())  
ans=0  
def dfs(step,cur,s):  
    global ans  
    if(s<0):  
        return  
    if(s==0 and step<k):  
        return  
    if(step==k):  
        if(s==0):  
            ans+=1  
        return  
    for i in range(cur,s//(k-step)+1):  
        dfs(step+1,i,s-i)  
dfs(0,1,n)  
print(ans)

n,k=map(int,input().split())  
dp=[[0 for _ in range(k+1)]for _ in range(n+1)]#把i划分为j组的方案数  
for i in range(1,n+1):  
    dp[i][1]=1  
for i in range(1,n+1):  
    for j in range(2,k+1):  
        if(i==j):  
            dp[i][j]=1  
        elif(i>j):  
            dp[i][j]=dp[i-1][j-1]+dp[i-j][j]  
print(dp[n][k])

购物

好难的贪心。
考虑相同硬币数能够最多能够组成1-m的面值。下一次需要选取小于等于m+1面值的硬币，这样可以完全覆盖。一直选到能够覆盖到x面值。

x,n=map(int,input().split())  
a=list(map(int,input().split()))  
a.sort()  
ans=1  
if(n==0):  
    print(-1)  
elif(a[0]!=1):  
    print(-1)  
else:  
    cur=1  
    while(cur<x):  
        for i in range(n-1,-1,-1):  
            if(a[i]<=cur+1):  
                ans+=1  
                cur+=a[i]  
                break  
    print(ans)

排队

谁懂打开比赛题目列表发现T是一道之前老师布置的难题且没有尝试的救赎感。
没get到为什么标签是贪心。感觉更像升级版冒泡排序。
如果一个数与前面所有数的最大值与最小值都相差d以内，那么它一定可以到开头去。每一次都这么操作，把能够放到开头的元素存到缓存数组中并排序，如果没有就只放开头，并把当前数组加到答案数组末端。

根据你对题目的分析和代码实现，这道题 25353: 排队 的核心思想是：

利用“相邻且身高差 ≤ D 可交换”的规则，推导出可交换的连通块（等价类）；
在每个连通块内部可以任意重排（因为交换具有传递性）；
为了得到字典序最小的序列，对每个连通块内部进行升序排序；
连通块的划分不是显式建图，而是通过贪心扫描 + 极值维护的方式动态确定。
因此，合适的算法标签应包括：
✅ Greedy（贪心）
核心策略：从左到右尽可能早地形成一个合法的“可重排块”，并在块内排序以保证字典序最小。
每轮贪心地扩展当前块，只要加入新元素后仍满足 max - min <= D（等价于所有元素两两之间可通过一系列合法交换连通）。
✅ Sorting（排序）
每个连通块内部需排序（升序）以获得字典序最小结果。
✅ Two Pointers / Sliding Window（滑动窗口思想）
虽然代码用的是多轮扫描，但本质是在动态维护一个“当前可合并区间”，类似滑动窗口或分组策略。
更准确地说，是 Iterative Grouping with Range Constraint，但归入滑动窗口或双指针思想也合理。
✅ Connected Components（连通分量）（可选，偏图论视角）
如果从图论角度理解：若 |h[i] - h[j]| <= D 且 i, j 在同一连通段中（通过相邻合法交换可达），则属于同一分量。
但本题并未显式建图或使用 DFS/BFS，所以这个标签可加但非必需；若平台支持“隐式连通分量”类标签，可考虑。

闫宏飞 , 11月12日 19:44

n,d=map(int,input().split())  
a=[]  
for i in range(n):  
    t=int(input())  
    a.append(t)  
check=[1]*n  
ans=[]  
maxm=a[0]  
minm=a[0]  
while(sum(check)!=0):  
    i=0  
    qaq=[]  
    maxm=0  
    minm=0  
    while(i<n):  
        if(check[i]==1):  
            if(len(qaq)==0):  
                check[i]=0  
                qaq.append(a[i])  
                maxm=a[i]  
                minm=a[i]  
            else:  
                if(a[i]>=maxm):  
                    maxm=a[i]  
                elif(a[i]<=minm):  
                    minm=a[i]  
                if(a[i]>=maxm-d and a[i]<=minm+d):  
                    qaq.append(a[i])  
                    check[i]=0  
        i+=1  
    qaq.sort()  
    ans.extend(qaq)  
for i in ans:  
    print(i)