A

显然最后保留的是一段连续的长为 $n-k$ 的数组，直接前缀和预处理+遍历长度为 $k$ 的数组即可

void solve()
{
    int n,k; cin>>n>>k; k = n-k;
    vector<ll> pre(n+1);
    ll res = 0;
    for(int i=1; i<=n; ++i) {
        cin>>pre[i];
        pre[i] += pre[i-1];
        if(i>=k) res = std::max(res, pre[i]-pre[i-k]);
    }
    cout<<res<<endl;
}

B

由于 $fc$ 和 $tb$ 不会重复，显然每次能删就删。对于删除，我们可以使用栈来维护

void solve()
{
    int n; cin>>n;
    std::string S; cin>>S;
    std::stack<char> st;
    for(auto &ch:S) {
        if(!st.empty()) {
            if(st.top()=='f' && ch=='c'){ st.pop(); continue; }
            if(st.top()=='t' && ch=='b'){ st.pop(); continue; }
        }
        st.emplace(ch);
    }
    cout<<st.size()<<endl;
}

C

手玩一会，不难发现：我们无法通过传送门到达 $[n-1, n]$ 和 $[n,n]$ 。

考虑 gcd 性质， $gcd(a,b) = gcd(a,a-b)$ ，因此想到找到最接近 $[n,n]$ 的一个位置，即 $[2k-2, 2k]$ 。因此最近的走法就是从 $[1,1]$ 走到 $[2,2]$ ，然后跳到 $[2k-2, 2k]$ 。再加上几个 $n$ 比较小的时候的特判即可

void solve()
{
    int n; cin>>n;
    if(n==1){ cout<<0<<endl; return; }
    if(n==2){ cout<<2<<endl; return; }
    if(n==3){ cout<<4<<endl; return; }

    if(n&1) cout<<6<<endl;
    else cout<<4<<endl;
}

D

感觉比 C 题简单

假设 $[L,R]$ 是满足题意的区间，那么这段区间对答案的贡献就是 $[L,R]$ 上的所有答案 $1$

由于 $n$ 比较小，直接 $O(n^2)$ 遍历所有区间，考虑贡献即可

计算的实现多种多样，包括但不限于差分树状数组、线段树、差分。我的代码中用的是差分树状数组

template <class T>
class FenwickTree {
private:
    int n;
    std::vector<T> a;
    constexpr int lowbit(int x){ return x&-x; }
public:
    FenwickTree(size_t _n): n(_n), a(_n+1) {}
    void add(int pos, T v){ for(int i=pos; i<=n; i+=lowbit(i)) a[i] = a[i]+v; }
    void init(size_t n, T val=T{}) {
        this->n = n;
        a.assign(n+1, val);
    }
    T sum(int x) {
        T ans{};
        for(int i=x; i>0; i-=lowbit(i)) ans = ans+a[i];
        return ans;
    }
    T rangeSum(int l, int r){ return l<=r? sum(r)-sum(l-1):0; }
};

constexpr bool check(const int x) {
    int t = sqrt(x);
    return t*t==x;
}

void solve()
{
    int n,q; cin>>n>>q;
    vector<int> pre(n+1);
    for(int i=1; i<=n; ++i) {
        cin>>pre[i];
        pre[i] += pre[i-1];
    }
    
    FenwickTree<ll> FT(n);
    for(int L=1; L<=n; ++L) for(int R=L; R<=n; ++R) {
        if(check(pre[R]-pre[L-1])) {
            FT.add(L, 1);
            if(R<n) FT.add(R+1, -1);
        }
    }
    while(q--) {
        int x; cin>>x;
        cout<<FT.sum(x)<<endl;
    }
}

E

对于一个数字 $x$ 若是好的，那么他的所有因数都要出现在 $A$ 中。手玩得出一下结论：

若 $x$ 为好，那么 $x\in A$

若 $x$ 为坏，那么 $\forall y=kx(k \in \mathbb{N}), y \notin A$

由此我们可以使用类似于埃氏筛的做法，得到所有的好数字，埃氏筛时间复杂度为 $O(n\log (n))$ ，所有此代码复杂度 $O(1e6 \log(1e6))$

void solve()
{
    int n; cin>>n;
    std::set<int> st;
    while(n--) {
        int tt; cin>>tt;
        st.emplace(tt);
    }

    int m = *st.rbegin();
    vector<bool> good(m+1, true);
    int res = 0;
    for(int i=1; i<=m; ++i) {
        if(good[i]==false) continue;
        if(auto it=st.find(i); it==st.end()) {
            for(int j=i; j<=m; j+=i) 
                good[j] = false;
        }
        if(good[i]) ++res;
    }
    cout<<res<<endl;
}

F

题目有点诈骗。

手玩发现：对于任何一个 $B_i$ ，当且仅当 $pos[B_i] \gt i m$ 时无解，其他情况都可以有解

如果 $B_i$ 在 $A$ 中没有出现过，那么同理 $B_i$ 可以出现在 $\le i m$ 的任何地方，于是我们使用类似于前缀和的方式，cnt[i] 记录有多少个数字可以放在位置 i 上。又由于假设前面已经放了 suf 个数字，那么当前位置就有 suf 个数字已经不能放了，所以答案于 cnt[i]-suf 相乘

// 这里的 Z 使用的是 jiangly 的自动取模模板，太长了就不放出来了
void solve()
{
    int n,w; cin>>n>>w;
    vector<int> aa(n+1), bb(n+1);
    for(int i=1; i<=n; ++i) cin>>aa[i];
    for(int i=1; i<=n; ++i) cin>>bb[i];
    
    vector<int> pos(n+1);
    for(int i=1; i<=n; ++i) if(~aa[i]) pos[aa[i]] = i;
    
    vector<int> cnt(n+1);
    for(int i=n; i; --i) {
        int R = std::min(n, i+w);
        if(pos[bb[i]] && pos[bb[i]]>R) {
            cout<<0<<endl; return;
        }
        if(!pos[bb[i]]) ++cnt[R];
    }
    
    Z res = 1;
    int suf = 0;
    for(int i=n; i; --i) {
        cnt[i-1] += cnt[i];
        if(~aa[i]) continue;
        res *= cnt[i]-suf;
        ++suf;
    }
    cout<<res<<endl;
}

题解 | #tb的区间问题#

A

B

C

D

E

F