难度预测（从左到右难度升序）: easy: F A D easy-mid: E C mid: B I G hard: K H very hard: J

实际难度：I mid->hard。其余和预期相符。

F.迎接终结的寂灭

知识点：无

签到题。输出42即可通过本题。

参考代码（PHP语言）：

42

A.不断减损的时间

知识点：贪心

对所有的正整数能操作就操作（显然操作后会变小），而0和负数则不操作。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int a[202020];
int main(){
    int n,i,x;
    cin>>n;
    long long sum=0;
    for(i=0;i<n;i++){
        cin>>x;
        while(x>0&&x%2==0)x/=2;
        sum+=x;
    }
    cout<<sum;
}

D.宿命之间的对决

知识点：博弈

显然1是先手必输。我们证明所有奇数都是先手必输：由于奇数只包含奇数的因子，那么只能取一个奇数变成偶数（或者变成0直接输掉），然后对方就可以直接取1变成奇数，仍然到必输的状态。因此奇数先手必输，偶数先手必胜。

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n;
    cin>>n;
    if(n&1)cout<<"yukari";
    else cout<<"kou";
}

E.公平守望的灯塔

知识点：计算几何

首先需要知道一个计算几何的常用知识：向量$(x,y)(x,y)$和向量$(-y,x)(-y,x)$的夹角为90度（因为点乘为0）。 那么我们假设$ABAB$向量为$(x,y)(x,y)$，那么我们从$AA$点为起点加上向量$(-y,x)(-y,x)$得到$CC$点，那么$BCBC$的中点即为所求。只需要判一下是否是整数即可。（由于只有求中点时除2，所以只需要判奇偶）。 当然本题还可以通过求$ABAB$中垂线和以$ABAB$为直径的圆的交点来求，不过这个做法码量巨大，不是很推荐。如果比赛中萌新实在想不出第一个做法可以尝试用第二个做法。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long ax,ay,bx,by;
    cin>>ax>>ay>>bx>>by;
    long long x=bx-ax,y=by-ay;
    if(x+y&1)return cout<<"No Answer!",0;
    long long cx=ax-y,cy=ay+x;
    cout<<(cx+bx>>1)<<" "<<(cy+by>>1)<<'\n';
}

C.忽远忽近的距离

知识点：构造

我们从样例可以发现，[3,4,1,2]是一组合法解，那么可以以此构造出所有$n=4kn=4k$形式的情况：[3,4,1,2,7,8,5,6]等。 之后我们可以尝试构造$n=5n=5$和$n=6n=6$的情况，发现有[4,5,1,2,3]和[4,5,6,1,2,3]，那么可以构造出$n=4k+5n=4k+5$、$n=4k+6n=4k+6$、$n=4k+5+6n=4k+5+6$的情况，以上分别对应$nn$模4等于1、2、3的情况，加上之前的$n=4kn=4k$，那么就覆盖了几乎所有正整数（需要特判$n=7n=7$和时是无解的）。 例如$n=13n=13$，我们发现13=4*2+5，那么可以构造成：[3,4,1,2,7,8,5,6,12,13,9,10,11]，即13=4+4+5的情况。

参考代码：

#include<bits/stdc++.h>
using namespace std;
void out(int n,int x){
    for(int i=n+x/2;i<n+x;i++)cout<<i<<" ";
    for(int i=n;i<n+x/2;i++)cout<<i<<" ";
}
int main(){
    int n,i=1;
    cin>>n;
    if(n<4||n==7)return cout<<-1,0;
    for(i=1;i<=n-11;i+=4){
        out(i,4);
    }
    if(n-i==10){
        out(i,5);
        out(i+5,6);
        return 0;
    }
    if(i<=n-7)out(i,4),i+=4;
    out(i,n-i+1);
}

B.勉强拼凑的记忆

知识点：二分

显然本题满足可以二分答案，并且在给定了正方形边长时，可以O(1)判定能否拼成。总复杂度为O(logn)。 拼边长为$lenlen$正方形的策略是：先用$1\ast \lceil \frac{n}{2}\rceil 1*\; \backslash lceil\; \backslash frac\{n\}\{2\}\; \backslash rceil$的矩形（共$len+(len-\lceil \frac{n}{2}\rceil )len+(len-\backslash lceil\; \backslash frac\{n\}\{2\}\; \backslash rceil)$个），还剩一个边长为$len-\lceil \frac{n}{2}\rceil len-\backslash lceil\; \backslash frac\{n\}\{2\}\; \backslash rceil$的正方形，使用$1\ast (len-\lceil \frac{n}{2}\rceil )1*(len-\backslash lceil\; \backslash frac\{n\}\{2\}\; \backslash rceil)$的矩形即可。（可以证明，最终$lenlen$一定是在$[n\mathrm{/}2,n][n/2,n]$）之间。 另外，本题需要特判$n=2n=2$的无解情况。 由于出题人的良心，直接把该情况放进样例里，使大家没有被这个特判wa到死去活来，但却遭到了小沙的反对。某沙语录：

参考代码：

#include<bits/stdc++.h>
using namespace std;
long long bs(long long l,long long r,long long n){
    if(l==r)return l;
    long long mid=l+r>>1;
    long long bc=n/2+n%2;
    long long chu=mid/bc,yu=mid%bc;
    long long cnt=chu*(mid+yu)+yu;
    if(cnt>n)return bs(l,mid,n);
    return bs(mid+1,r,n);
}
int main(){
    int _;
    cin>>_;
    while(_--){
        long long n;
        cin>>n;
        if(n==1){cout<<1<<'\n';continue;}
        if(n==2){cout<<-1<<'\n';continue;}
        cout<<bs(n/2,n,n)-1<<'\n';
    }
}

I.灵魂碎片的收集

知识点：数论、构造

注意看输入中隐含的一个提示：若$xx$是偶数，保证$x\mathrm{-}1x-1$、$x\mathrm{-}3x-3$中至少有一个是素数。 当$x-1x-1$是素数时，即$xx$可以写成$1+p1+p$的形式。显然$p^{2}p^2$只包含$1,p,p^{2}1,p,p^2$这三个因子，得解。 当$x-3x-3$是素数时，即$xx$可以写成$1+2+p1+2+p$的形式。显然$p\ast 2p*2$只包含$1,2,p,p\ast 21,2,p,p*2$这四个因子，得解。 当$xx$是奇数时，根据哥德巴赫猜想的结论，我们可以很容易找到两个素数$pp$和$qq$满足$1+p+q=x1+p+q=x$，由于$p\ast qp*q$只包含$1,p,q,p\ast q1,p,q,p*q$这四个因子，得解。 需要注意，当$x\le 7x\backslash leq\; 7$时，部分情况需要特判。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int f(long long x){
    int i;
    for(i=2;i*i<=x;i++){
        if(x%i==0)return 0;
    }
    return 1;
}
int main(){
    int _;
    cin>>_;
    while(_--){
        long long n,i;
        cin>>n;
        if(n&1){
            if(n==1)cout<<3<<'\n';
            else if(n==5)cout<<-1<<'\n';
            else if(n==3)cout<<4<<'\n';
            else if(n==7)cout<<8<<'\n';
            else{
                for(i=3;i<(n-1)/2;i++){
                    if(f(i)&&f(n-1-i))break;
                }
                cout<<1ll*i*(n-1-i)<<'\n';
            }
        }
        else{
            if(f(n-1))cout<<(n-1)*(n-1)<<'\n';
            else if(f(n-3))cout<<2*(n-3)<<'\n';
        }
    }
}

G.严肃古板的秩序

知识点：枚举/dfs

本题为纯码力题，暴力搜索所有情况即可。可以用三进制状压枚举或者dfs完成本题。 需要注意的两点： 1.算出0或者负数时若下一步是#运算应直接终止。 2.当爆int时，快速幂应将底数取模，指数不应取模。 三进制状压枚举介绍： 我们假设'+'用0数位，'-'用1数位，'#'用2数位，那么由三进制的000……到222……这$3^{n}3^n$个三进制数就能表示所有的情况了。对于每种情况进行判断运算式是否合法。

参考代码（状压枚举）：

#include<bits/stdc++.h>
using namespace std;
vector<long long>v;
long long ans;
int b[202];
long long power(long long a,long long b,long long mod){
    long long res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
int main(){
    string s;
    cin>>s;
    int i,temp=0,j;
    for(i=0;i<s.length();i++){
        if(s[i]=='?'||s[i]=='=')v.push_back(temp),temp=0;
        else temp*=10,temp+=s[i]-'0';
    }
    ans=temp;
    while(!b[v.size()]){
        long long temp=v[0];
        for(j=1;j<v.size();j++){
            if(b[j]==0)temp=temp+v[j];
            if(b[j]==1)temp=temp-v[j];
            if(b[j]==2){
                if(temp<=0){temp=-1;break;}
                temp=power(temp%v[j],temp,v[j]);
            }
        }
        if(temp==ans){
            cout<<v[0];
            for(j=1;j<v.size();j++){
                if(b[j]==0)cout<<'+';
                if(b[j]==1)cout<<'-';
                if(b[j]==2)cout<<'#';
                cout<<v[j];
            }
            cout<<"="<<ans;
            break;
        }
        b[1]++;
        for(j=1;j<v.size();j++){
            b[j+1]+=b[j]/3;
            b[j]%=3;
        }
    }
    if(b[v.size()])cout<<-1;
}

K.永恒守候的爱恋

知识点：数论，数学

前置知识：若$nn$的质因数分解形式为$n=p_1^{a_1}\ast p_2^{a_2}\ast \mathrm{.}\mathrm{.}\mathrm{.}\ast p_k^{a_k}n=p\_1^\{a\_1\}*p\_2^\{a\_2\}*...*p\_k^\{a\_k\}$，那么$nn$的因子数量为$(a_1+1)\ast (a_2+1)\ast \mathrm{.}\mathrm{.}\mathrm{.}\ast (a_k+1)(a\_1+1)*(a\_2+1)*...*(a\_k+1)$。 证明如下，对于每个素因子$p_{i}p\_i$而言，可以取0个、取1个……取$a_i\{a\_i\}$个，共有$a_i+1a\_i+1$种取法。根据乘法原理，总方案数为${\sum }_{i=1}^k(a_i+1)\backslash sum\_\{i=1\}^k(a\_i+1)$ 根据这个性质，我们可以想出这样的策略：首先每个素数第一次出现依次排下来，然后还有次数的素数的第二次依次排下来……以此类推。这样一定是最优的。因为当素数的出现次数从$ii$次变成$i+1i+1$次的时候，带来的贡献为$\frac{i+2}{i+1}\backslash frac\{i+2\}\{i+1\}$；（之前是乘以$i+1i+1$，现在是乘以$i+2i+2$）。所以每次优先选择“目前已选择的出现次数最少的素数”是更优的。 这样当我们选择出现次数为i的素数时，前缀因子数量从此时开始即为一个公比为$\frac{i+2}{i+1}\backslash frac\{i+2\}\{i+1\}$的等比数列；我们可以通过等比数列求和公式快速算出这一段的和。这样总复杂度即为$O(nlogn)O(nlogn)$，其中log是逆元部分的复杂度。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod=1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){
    return power(x,mod-2);
}
long long a[202020];
int main(){
    int n,i;
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    int j=1;
    long long temp=1;
    long long s=0;
    for(i=1;i<=2e5;i++){
        while(j<=n&&a[j]<i)j++;
        if(j>n)break;
        int cnt=n-j+1;
        s+=temp*(power(i+1,n-j+1)*inv(power(i,n-j+1))%mod-1)%mod*i%mod;
        temp=temp*power(i+1,n-j+1)%mod*inv(power(i,n-j+1))%mod;
        s%=mod; 
    }
    cout<<((s+temp-1)%mod+mod)%mod<<'\n';
}

H.穿越万年的轮回

知识点：动态规划，期望

由于每次三种操作的概率相等，因此最终的期望乘以$3^{k}3^k$后等于下面问题的答案：每次操作会将一个串分别用三种操作生成3个串，最终会有$3^{k}3^k$个串，求所有串的"red"子串数量之和。

这个问题可以直接用dp求解。 设dp[i][j][k]的含义如下：i代表操作次数，j=k=0代表字符串为空，j=1代表前缀是"red"，j=2代表前缀是"edr"，k=1代表后缀是"red"，k=2代表后缀是"edr"。然后dp数组代表$i,j,ki,j,k$满足上述条件的red子串的数量。这样可以分别根据三种操作进行分类讨论来递推了。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int mod=1e9+7;
long long power(long long a,long long b){
    long long res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
long long inv(int x){
    return power(x,mod-2);
}
long long dp[200010][3][3],cnt[201010][3][3];     //cnt代表字符串数量，dp代表red子串数量
int main(){
    dp[1][1][1]=1;
    cnt[1][0][0]=1;
    cnt[1][1][1]=1;
    cnt[1][2][2]=1;
    int n,i,j,k;
    cin>>n;
    for(i=2;i<=n;i++){
        cnt[i][0][0]+=cnt[i-1][0][0];
        cnt[i][1][1]+=cnt[i-1][0][0];
        cnt[i][2][2]+=cnt[i-1][0][0];
        for(j=1;j<=2;j++){
            cnt[i][j][1]+=cnt[i-1][j][1]*2+cnt[i-1][j][0]+cnt[i-1][j][2];
            cnt[i][j][2]+=cnt[i-1][j][2]*2+cnt[i-1][j][0]+cnt[i-1][j][1];
            cnt[i][j][0]+=cnt[i-1][j][0];
            dp[i][j][1]+=dp[i-1][j][1]+cnt[i-1][j][1]+dp[i-1][j][0]+cnt[i-1][j][0]+dp[i-1][j][2]+cnt[i-1][j][2];
            dp[i][j][2]+= dp[i-1][j][1]+dp[i-1][j][0]+dp[i-1][j][2]+cnt[i-1][j][2];
            dp[i][j][1]+=dp[i-1][j][1]*10;
            dp[i][j][2]+=dp[i-1][j][2]*10;
            dp[i][j][0]+=dp[i-1][j][0]*10;
            for(k=0;k<3;k++)dp[i][j][k]%=mod,cnt[i][j][k]%=mod;
        }
        dp[i][1][1]+=cnt[i-1][0][0];
        dp[i][2][2]+=cnt[i-1][2][2]*9;
        dp[i][1][1]%=mod;
        dp[i][2][2]%=mod;
    }
    long long res=0;
    
    for(i=0;i<3;i++){
        for(j=0;j<3;j++){
            res+=dp[n][i][j];
        }
    }
    cout<<res%mod*power(inv(3),n)%mod;
}

J.无法磨灭的悔恨

知识点：贪心,双指针

我们采用反悔贪心的策略。先假设所有操作均为“乘2”，然后当回撤这种操作的时候，每回撤一次就可以返还一个操作次数，然后维护这个操作过程中的max和min即可。需要注意的是，由于一个数不可能既乘2又除2，所以我们需要开两个multiset分别维护两种数：“未回撤完毕的数”和“已经回撤完毕的数”，其中未被乘2过的也属于第二种。当我们回撤时，只对第一种数的进行操作，回撤后的“除2”操作第二种数进行操作。 操作过程中，我们采取贪心策略：最开始的乘2只对最小值进行操作；后面的除2仅当同时满足【第二种数的最大值大于第一种数的最大值】以及【目前还存在由于反悔导致拥有了“除2”次数】这两种情况下才可以进行。

#include<bits/stdc++.h>
using namespace std;
multiset<pair<long long,int>>s;
multiset<long long>s2;
long long res=1e18;
void update(){
    long long ma=0,mi=1e18;
    if(!s.empty())ma=max(ma,s.rbegin()->first),mi=min(mi,s.begin()->first);
    if(!s2.empty())ma=max(ma,*s2.rbegin()),mi=min(mi,*s2.begin());
    res=min(res,ma-mi);
}
int main(){
    int n,k,i,x,cnt;
    cin>>n>>k;
    cnt=k;
    for(i=0;i<n;i++){
        cin>>x;
        s.insert({x,0});
    }
    for(i=0;i<k;i++){        //乘2操作
        pair<long long,int>temp=*s.begin();
        if(temp.first>1e9)break;
        s.erase(s.begin());
        s.insert({temp.first*2,temp.second+1});
        cnt--;
    }
    update();
    vector<pair<long long,int>>v;
    for(auto i:s)v.push_back(i);
    s.clear();
    for(auto i:v){
        if(i.second)s.insert(i);
        else s2.insert(i.first);
    }
    while(cnt>0||!s.empty()){
        pair<long long ,int>temp;
        long long temp2;
        if(!s2.empty())temp2=*s2.rbegin();
        if(!s.empty())temp=*s.rbegin();
        if(!s2.empty()&&(s.empty()||temp2>temp.first)&&cnt>0){  //除2
            s2.erase(s2.find(temp2));
            s2.insert(temp2/2);
            cnt--;
        }
        else{              //对之前的乘2进行反悔
            s.erase(s.find(temp));
            if(temp.second==1){
                s2.insert(temp.first/2);
            }
            else{
                s.insert({temp.first/2,temp.second-1});
            }
            cnt++;
        }
        update();
    }
    cout<<res;
}