马蹄集第37周

1、最小子串覆盖

考点：双指针

代码：

def judge(s,t,l,r):
    m = [0] * (256)
    for i in t:
        m[ord(i)] += 1
    for i in range(l,r+1):
        if s[i] in t:
            m[ord(s[i])] -= 1
    for i in m:
        if i > 0:
            return False
    return True



def main():
    result = "No"
    s = input()
    t = input()
    l = r = 0   #定义一个滑动窗口
    num = 100000
    # print("字符串",len(s))
    while(r < len(s) and l<=r):
        if judge(s,t,l,r):
            # tmp = s[l:r + 1]
            # print("满足条件的字符串：",tmp)
            l += 1
            while judge(s,t,l,r):
                # tmp = s[l:r + 1]
                # print("滑动窗口缩小：",tmp)
                l+=1
            l -= 1
            if (r-l+1) < num:
                num = r-l+1
                result = s[l:r + 1]
        r += 1
    print(result)

if __name__ == '__main__':
    main();

2.方块桶

代码：

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    # print(n,a)
    l = 0
    r = n - 1
    maxl = a[0]
    maxr = a[n-1]
    ans = 0
    while l<r:
        if maxl <= maxr:
            l += 1
            maxl = max(maxl, a[l])
            ans += maxl - a[l]
        else:
            r -= 1
            maxr = max(maxr, a[r])
            ans += maxr - a[r]
    print(ans)

if __name__ == '__main__':
    main();

3.新材料

#include<bits/stdc++.h> 

using namespace std;
map<int,int> lst;
int n,k;

int main( )
{
    scanf("%d%d",&n,&k);
    int ans=0;
    for(int i=1;i<=n;i++){
        int cur;
        scanf("%d",&cur);
        if(!lst.count(cur)) lst[cur] = i;
        else if (lst[cur] == -1) continue;
        else if(i - lst[cur] > k) lst[cur] = i;
        else ans ^= cur,lst[cur] = -1;
    }
    cout << ans << endl;
}

4、与蝴蝶一起消散吧

解题思路：看不懂看不懂

直接抄答案

#include<bits/stdc++.h> 

using namespace std;
int n,k;
int main( )
{
    long long ans0 = 0,ans1 = 0;
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= n;i++){
        int a,m;
        scanf("%d%d",&a,&m);
        if(a>k){
            ans0 = ans1 = min(ans0 + k,ans1) + 1ll * (a-k) *m;
        }
        else{
            long long nxt0 = min(ans0 + 1ll * (m + 1)/2*a,ans1 + 1ll*m/2*a);
            long long nxt1 = min(ans0 + 1ll * (m + 2)/2*a,ans1 + 1ll*(m + 1)/2*a);
            ans0 = nxt0;
            ans1 = nxt1;
        }
    }
    cout << min(ans0,ans1)<<endl;
}

5、炼金术

这班实在是呆不下去了，这个题也太长了，答案都那么长，抄都不想抄

给大家一个链接吧，自己抄吧

【2023百度之星第三场题解】嘉宾：NOI、IOI金牌周航锐_哔哩哔哩_bilibili