test

难度预测（从左到右难度升序）:

easy: F A D

easy-mid: E C

mid: B I G

hard: K H

very hard: J

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

## F.迎接终结的寂灭

知识点：无

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

参考代码（PHP语言）：

```php

42

```

## A.不断减损的时间

知识点：贪心

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

参考代码：

```c++

#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变成奇数，仍然到必输的状态。因此奇数先手必输，偶数先手必胜。

```c++

#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)$和向量$(-y,x)$的夹角为90度（因为点乘为0）。

那么我们假设$AB$向量为$(x,y)$，那么我们从$A$点为起点加上向量$(-y,x)$得到$C$点，那么$BC$的中点即为所求。只需要判一下是否是整数即可。（由于只有求中点时除2，所以只需要判奇偶）。

当然本题还可以通过求$AB$中垂线和以$AB$为直径的圆的交点来求，不过这个做法码量巨大，不是很推荐。如果比赛中萌新实在想不出第一个做法可以尝试用第二个做法。

参考代码：

```c++

#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=4k$形式的情况：[3,4,1,2,7,8,5,6]等。

之后我们可以尝试构造$n=5$和$n=6$的情况，发现有[4,5,1,2,3]和[4,5,6,1,2,3]，那么可以构造出$n=4k+5$、$n=4k+6$、$n=4k+5+6$的情况，以上分别对应$n$模4等于1、2、3的情况，加上之前的$n=4k$，那么就覆盖了几乎所有正整数（需要特判$n=7$和$n<4$时是无解的）。

例如$n=13$，我们发现13=4*2+5，那么可以构造成：[3,4,1,2,7,8,5,6,12,13,9,10,11]，即13=4+4+5的情况。

参考代码：

```c++

#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)。

拼边长为$len$正方形的策略是：先用$1* \lceil \frac{n}{2} \rceil $的矩形（共$len+(len-\lceil \frac{n}{2} \rceil)$个），还剩一个边长为$len-\lceil \frac{n}{2} \rceil$的正方形，使用$1*(len-\lceil \frac{n}{2} \rceil)$的矩形即可。（可以证明，最终$len$一定是在$[n/2,n]$）之间。

另外，本题需要特判$n=2$的无解情况。

~~由于出题人的良心，直接把该情况放进样例里，使大家没有被这个特判wa到死去活来，但却遭到了小沙的反对。某沙语录：

~~

参考代码：

```c++

#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.灵魂碎片的收集

知识点：数论、构造

注意看输入中隐含的一个提示：若$x$是偶数，保证$x−1$、$x−3$中至少有一个是素数。

当$x-1$是素数时，即$x$可以写成$1+p$的形式。显然$p^2$只包含$1,p,p^2$这三个因子，得解。

当$x-3$是素数时，即$x$可以写成$1+2+p$的形式。显然$p*2$只包含$1,2,p,p*2$这四个因子，得解。

当$x$是奇数时，根据哥德巴赫猜想的结论，我们可以很容易找到两个素数$p$和$q$满足$1+p+q=x$，由于$p*q$只包含$1,p,q,p*q$这四个因子，得解。

需要注意，当$x\leq 7$时，部分情况需要特判。

参考代码：

```c++

#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$个三进制数就能表示所有的情况了。对于每种情况进行判断运算式是否合法。

参考代码（状压枚举）：

```c++

#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.永恒守候的爱恋

知识点：数论，数学

前置知识：若$n$的质因数分解形式为$n=p_1^{a_1}*p_2^{a_2}*...*p_k^{a_k}$，那么$n$的因子数量为$(a_1+1)*(a_2+1)*...*(a_k+1)$。

证明如下，对于每个素因子$p_i$而言，可以取0个、取1个……取${a_i}$个，共有$a_i+1$种取法。根据乘法原理，总方案数为$\sum_{i=1}^k(a_i+1)$

根据这个性质，我们可以想出这样的策略：首先每个素数第一次出现依次排下来，然后还有次数的素数的第二次依次排下来……以此类推。这样一定是最优的。因为当素数的出现次数从$i$次变成$i+1$次的时候，带来的贡献为$\frac{i+2}{i+1}$；（之前是乘以$i+1$，现在是乘以$i+2$）。所以每次优先选择“目前已选择的出现次数最少的素数”是更优的。

这样当我们选择出现次数为i的素数时，前缀因子数量从此时开始即为一个公比为$\frac{i+2}{i+1}$的等比数列；我们可以通过等比数列求和公式快速算出这一段的和。这样总复杂度即为$O(nlogn)$，其中log是逆元部分的复杂度。

参考代码：

```c++

#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个串，最终会有$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,k$满足上述条件的red子串的数量。这样可以分别根据三种操作进行分类讨论来递推了。

参考代码：

```c++

#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”次数】这两种情况下才可以进行。

```c++

#include<bits/stdc++.h>

using namespace std;

struct node{

    long long val,cnt;

    bool operator< (const node &x)const{

        if(this->val!=x.val)

            return this->val<x.val;

        return this->cnt<x.cnt;

    }

};

long long a[202020];

multiset<node>s,temps;

int main(){

    int n,k,i;

    cin>>n>>k;

    multiset<long long>vals,ss;

    long long ma=0,mi=1e9;

    for(i=1;i<=n;i++){

        cin>>a[i];

        ma=max(ma,a[i]);

        mi=min(mi,a[i]);

        ss.insert(a[i]);

        s.insert({a[i],0});

        vals.insert(a[i]);

    }

     long long res=prev(s.end())->val-s.begin()->val;

    for(i=0;i<k;i++){

        long long temp=*prev(vals.end());

        vals.erase(prev(vals.end()));

        vals.insert(temp/2);

        res=min(res,*prev(vals.end())-*vals.begin());

    }

    for(i=0;i<k;i++){

        auto temp=*s.begin();

        s.erase(s.begin());

        temp.cnt++;

        temp.val*=2;

        s.insert(temp);

        res=min(res,prev(s.end())->val-s.begin()->val);

    }

    vals.clear();

    for(auto i:s){

        if(i.cnt)

            temps.insert(i);

        else vals.insert(i.val);

    }

    int t=0;

    for(i=0;i<k;i++){

        if(temps.empty())break;

        auto temp=*prev(temps.end());

        int mx=temp.val;

        while(!temps.empty()&&prev(temps.end())->val==mx){

            auto er=*prev(temps.end());

            temps.erase(temps.find(er));

            er.cnt--;

            er.val/=2;

            if(er.cnt)temps.insert(er);

            else vals.insert(er.val);

            t++;

            long long ma,mi;

            if(!vals.empty()) ma=*prev(vals.end()),mi=*vals.begin();

            if(!temps.empty())ma=max(ma,prev(temps.end())->val),mi=min(mi,temps.begin()->val);

            res=min(res,ma-mi);

        }

        while(t>0){

            if(vals.empty())break;

            if(!temps.empty()&&*prev(vals.end())<(prev(temps.end())->val))break;

            long long tempval=*prev(vals.end());

            vals.erase(vals.find(tempval));

            vals.insert(tempval/2);

            long long ma,mi;

            if(!vals.empty()) ma=*prev(vals.end()),mi=*vals.begin();

            if(!temps.empty())ma=max(ma,prev(temps.end())->val),mi=min(mi,temps.begin()->val);

            res=min(res,ma-mi);

            t--;

        }

    }

    cout<<(long long)res;

}

```