A. Only Pluses

三个数越相近，乘积就越大。因此五次递增每次分别作用于当前三个数中最小的那个。

B. Angry Monk

除了当前最长的那一个片段之外，其他片段都必须要掰成一节节之后再拼上。这样总步数最小。

C. Gorilla and Permutation

定义的两个函数 $f(i)$ 表示数组前缀长度 $i$ 中所有大于 $k$ 的数字之和，$g(i)$ 表示数组前缀长度 $i$ 中所有小于 $m$ 的数字之和。要想最大化 $\sum_i(f(i)-g(i))$, 就必须要让 $f(i)$ 尽量大，$g(i)$ 尽量小。

所以构造的排列就是先是比 $k$ 大的数字降序排列，中间的无所谓，之后是比 $m$ 小的数字的升序排列。

D. Test of Love

题目大意

给出一个长度为 $n$ 的序列，其中包含水 W、鳄鱼 C 和浮木 L。如果在岸上或在浮木上，可以向前最多跳 m 格，可以跳到水里、浮木或岸上；如果当前在水里，则可以向前游一格，但整个过程中最多能游 k 格；无论如何都不能进入鳄鱼所在的格子。问：是否从起始位置到达彼岸。

解题思路

暴搜。因为游是有限制的，跳是无限制的，所以能跳则跳。

如果当前在岸上或在浮木上，向前搜索选择跳到最远的浮木。如果前面 m 格都没有浮木，选择能跳到最远的水里。
如果当前在水里，向前游一格。
如果游到鳄鱼格，则搜索失败。
如果游到或跳到彼岸，则搜索成功。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
//n length
//m jump
//k swim
string river;
bool BFS(int pos,int swim_remain){
    if(swim_remain<0)return false;
    if(pos>=n)return true;
    if(river[pos]=='C')return false;
    else if(river[pos]=='L'){
        for(int i=m;i>=1;i--){
            if(pos+i>=n)return true;
            else if(river[pos+i]=='L'){return BFS(pos+i,swim_remain);}
        }
        for(int i=m;i>=1;i--){
            if(pos+i>n)return true;
            else if(river[pos+i]=='W'){
                return BFS(pos+i,swim_remain);
            }
        }
        return false;
    }
    else if(river[pos]=='W'){
        return BFS(pos+1,swim_remain-1);
    }
}

void work(){
    cin>>n>>m>>k;
    cin>>river;
    for(int i=0;i<m;i++){
        if(BFS(i,k)){
            puts("YES");
            return;
        }
    }
    puts("NO");
    return;
}

int main(){
    int test_cases;
    cin>>test_cases;
    while(test_cases--)
    work();
    return 0;
}

E. Novice's Mistake

题目大意

给定 $n$，求所有的 $(a,b)$ 对，满足 $a\times n-b$ 的结果对应的（非空）字符串刚好和将 $n$ 对应字符串复制并拼接 $a$ 次，然后裁剪掉长度为 $b$ 的后缀得到的字符串一样。

解题思路

$a,b$ 的范围 $10^5$，因此不能用最直观的暴力 $O(n^2)$ 解法。

注意到 $a\times n$ 的范围，最多不会超过 $n\times 10^4$。又根据“字符串复制拼接”操作，得出 $a\times n-b$ 对应结果只有那么几种。比如 $n=34$ 时，$a\times n-b$ 可能取值只有 $3,34,343,3434,34343,343434$。针对这些值再暴力枚举 $a$ 即可。此方法的时间复杂度为 $O(n\log n)$。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n;
int ground_truth;
queue<int>res;
void verify(int X){
    for(int ai=1;ai<=10000;ai++){
        int b=ai*n-X;
        if(b<=0)continue;
        if(b>min(10000,ai*n))continue;
        string str_n=to_string(n);
        int len_an=ai*str_n.length();
        int len_X=to_string(X).length();
        if(len_an-b!=len_X)continue;
        if(b>=len_an)continue;
        res.push(ai);
        res.push(b);
    }
}
void work(){
    cin>>n;
    string str_n=to_string(n);
    int seg=str_n.length();
    //generate candidate
    str_n=str_n+str_n+str_n+str_n+str_n;
    while(str_n.length()>seg+4){
        str_n.erase(str_n.length()-1);
    }
    while(str_n.length()){
        verify(stoi(str_n));
        str_n.erase(str_n.length()-1);
    }
    cout<<res.size()/2<<endl;
    while(!res.empty()){
        int tmp=res.front();
        res.pop();
        cout<<tmp<<" ";
        tmp=res.front();
        res.pop();
        cout<<tmp<<endl;
    }
    return;
}
int main(){
    int test_cases;
    cin>>test_cases;
    while(test_cases--)
        work();
    return 0;
}

F. Valuable Cards

题目大意

给定一个数组和一个值 $x$。目标是将数组划分成最少的段数，使得每段中都不存在任何一个子集，其中所有元素的积为 $x$。

解题思路

贪心。一段一段地找，只要发现有几个元素相乘等于 $x$，就立马切开。具体实现可以使用 C++ STL 里高效的 set 来存储所有 $x$ 除以一些元素的商，一旦新扫描的值匹配上了，就立刻切开。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,x;
vector<int>a;
vector<int>temp;
set<int> divi;
void work(){
    a.clear();
    divi.clear();
    temp.clear();
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        int tmp;
        cin>>tmp;
        if(x%tmp==0)a.push_back(tmp);
    }
    if(a.size()==0){
        puts("1");
        return;
    }
    int res=1,left=0,ptr=0;
    divi.insert(x);
    divi.insert(x/a[ptr]);
    ptr++;
    while(ptr<a.size()){
        if(divi.find(a[ptr])!=divi.end()){
            res++;
            left=ptr;
            divi.clear();
            divi.insert(x);
            divi.insert(x/a[ptr]);
            ptr++;
            continue;
        }
        temp.clear();
        for(auto it:divi){
            if(it%a[ptr]==0){
                temp.push_back(it/a[ptr]);
            }
        }
        for(auto it:temp){
            divi.insert(it);
        }
        ptr++;
    }
    cout<<res<<endl;
    return;
    return;
}

int main(){
    int test_cases;
    cin>>test_cases;
    while(test_cases--)
        work();
    return 0;
}

G. Ultra-Meow

题目大意

定义 $MEX(a,b)$ 函数表示 $a$ 集合中未出现的第 $k$ 个正整数。求 $\{1,\cdots,n\}$ 的所有子集 $b$ 的 $MEX$ 值之和 $\sum_{b\subseteq a}MEX(b,|b|+1)$.

解题思路

对于 $n$，$MEX$ 函数的取值范围是 $1$ 到 $2n+1$。对于每个 $MEX$ 函数值，从 $0$ 到 $n$ 枚举子集的大小 $size$。

对于 $MEX$ 值为 $val$, 子集大小为 $size$ 而言，

$1,\cdots,val-1$ 位置上必须刚好有 $size$ 个位置不在子集里。那么刚好有 $a=(val-1)-size$ 个位置上的值在子集里。

（如果 $val$ 比 $n$ 大，$val-1$ 被进一步限制为 $n$）

情况的可能性有 $\left(\begin{array}{cc}\min\{val-1,n\}\\a\end{array}\right)$ 种。

如果 $val$ 比 $n$ 小，那么 $val+1,\cdots,n$ 位置上就刚好有 $size-a$ 个位置上的值在子集里。该情况的可能性有 $\left( \begin{array}{cc} n-val\\ size-a \end{array} \right)$ 种。

因此，$MEX$ 值为 $val$，子集大小为 $size$ 对应的子集个数为： $$ \left(\begin{array}{cc}\min{val-1,n}\ a \end{array}\right) \times \left( \begin{array}{cc} \max{0,n-val}\ size-a \end{array} \right) $$ 最终的结果就是对应的 $MEX$ 与之相乘再求和。

参考代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 5010;
ll C[maxn][maxn];
int n;
void prepare(){
    for(int i=1;i<maxn;i++){
        C[i-1][0]=1;
        for(int j=1;j<maxn;j++){
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
}
void work(){
    cin>>n;
    int res=0;
    for(int sz=0;sz<=n;sz++){
        for(int mex=1;mex<=2*n+1;mex++){
            int a=mex-sz-1,b=sz-a;
            //a represents # all chosen elements that is less than k
            //b represents # all chosen elements that is greater than k
            if(a>=0&&b>=0){
                res=(res+C[min(mex-1,n)][a]*C[max(0,n-mex)][b]%mod*mex)%mod;
            }
        }
    }
    cout<<res<<endl;
    return;
}

int main(){
    prepare();
    int test_cases;
    cin>>test_cases;
    while(test_cases--)
        work();
    return 0;
}