1103d3

本次比赛非常耻辱，只做了AB题，C题贪心失败，D题跳过去做E题，但是一直没调出来。补了CDEF1

AB

A题输出MAX+1-MIN即可。
B题顺序处理遇到1则将该位置和往后第k个位置转换，最后判断最后无法改变的k个位置有无1即可。

补题

C

An annual programmers fair is taking place on the main square of Omsk. You, as the main programmer of Omsk, decided to take part in this wonderful event and went there. At the entrance, a guard decided to check your skills and gave you a problem:

You are given three integers $a$, $b$, $x$. You want to make $a$ and $b$ equal. In order to do so, you can apply the following operations:

1. Choose one of the integers $a$ or $b$ and add $1$ to it.
2. Choose one of the integers $a$ or $b$ and divide it by $x$ with rounding down.

You need to find the minimum number of operations after which $a$ becomes equal to $b$. Can you prove your skills, or will you have to go back home?

分析

对于数p，除x和加1操作的顺序

• 若$x|(p+1)$，则$\lfloor\frac{p+1}{x}\rfloor=\lfloor\frac{p}{x}\rfloor +1$。（|为整除符号）
• 否则$\lfloor\frac{p+1}{x}\rfloor=\lfloor\frac{p}{x}\rfloor$，加一操作是无效的。

因此我们可以判断出，对于两个数a和b，一定是分别进行了若干次（可能0次）除x后，再通过加1操作达到相同值。

思路：

对于a和b一直除以x至0，记录所有的可能值以及代价，随后$O(N^2)$枚举两者，将代价增加两者差值后，取代价最小即可。

Code

void sol()
{
    int a,b,x;
    cin>>a>>b>>x;
    int ans=abs(a-b);
    vector<pair<int,int>>ma,mb;
    int cnt=0;
    ma.push_back({a,0});
    while(a)
    {
        ma.push_back({a/x,++cnt});
        a/=x;
    }
    ma.push_back({0,++cnt});

    mb.push_back({b,0});
    cnt=0;
    while(b)
    {
        mb.push_back({b/x,++cnt});
        b/=x;
    }
    mb.push_back({0,++cnt});
    for(auto [x,c1]:ma)
    {
        for(auto [y,c2]:mb)
        {
            ans=min(ans,abs(x-y)+c1+c2);
        }
    }
    cout<<ans<<'\n';
}

D

虽然本题不需要博弈论的知识，只需要逆向归纳即可，但是可以将本题扩展为求出所有必胜/必败点，作为一个组合博弈的入门题。

Dabir and Egor were not satisfied with the fame from the previous episode, so they decided to make another TV show: the guys play their favorite game on an array $a$ with their favorite integer $k$.

Dabir moves first. On the first move, any element from the array can be chosen and removed. Let the previous chosen element be equal to $x$. Then on the current move, except the very first one, a player must choose an element $y$ from the array such that $0 \leq y - x \leq k$ and remove it from the array. The player who cannot make a move loses.

But since this was not just a game, but a real show-match, Arseniy (aka MAKAN) — the main celebrity of Omsk was invited again. As a guest celebrity, Arseniy was given the opportunity to make the first move in this match, that is, to make the very first move in the game instead of Dabir. However, it turns out Arseniy is a fan of Egor, so he wants his first move to guarantee Egor a winning strategy against any response from Dabir.

Determine whether Arseniy can make the first move for Dabir so that, no matter how Dabir plays, Egor wins.

分析：

先说明逆向归纳法，桶排序并压缩空间。直接取最大值，由于取最大值后无法取其他值，若最大值为偶数，则胜，否则，看和第二大值之差是否不大于k，若不大于k，则胜。若大于k，则第二大值可以等价于最大值（因为无法向后取数），同样进行上述操作。如果最终都没有找到答案，则败。
复杂度：$O(N)$

以组合博弈的视角来看:
本题虽然看起来不能构成DAG（有向无环图），因为可以取相同的值，构成了自环，但是可以将相同的值聚合起来形成一个DAG。随后就是经典的组合博弈思路。

1. 找出所有终结态：无法取后续的值的点。
2. 若终结点对应值数量为偶数，则为必胜点N位置(Next Player Win)，否则为必败点P位置(Previous Player Win)。
3. 若某一点存在一条可以到达P位置的边，则该点位N位置。
4. 否则，若该点对应值数量为偶数，则可以让对手迈出这个点，这时该点仍然为N位置，否则为P位置。（这是转化为DAG需要额外判断的地方）

通过二分查找可以找到点i可以到达的最大位置x，随后用树状数组查询该区间内有没有N位置。
最后的答案统计，只需要判断有没有N位置即可。
复杂度：$O(N\log N)$

Code

inline int lb(int x)
{
    return -x&x;
}
inline void add(vector<int>&BIT,int x,int v=1)
{
    for(int i=x;i<BIT.size();i+=lb(i))
    {
        BIT[i]+=v;
    }
}
inline int search(const vector<int>&BIT,int x)
{
    int res=0;
    for(int i=x;i>0;i-=lb(i))
    {
        res+=BIT[i];
    }
    return res;
}

void sol()
{
    int n,k;
    cin>>n>>k;
    vector<int>a(n+1,0);
    vector<int>tr(n+1);
    vector<int>ct(n+1,0);
    vector<int>bt(1,0);
    int cnt=0;
    vector<int>dp(n+1,-1);//dp[i]means player del this cell and will win or fail
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a.begin()+1,a.end());
    int lst=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=lst)
        {
            lst=a[i];
            bt.push_back(a[i]);
            ct[++cnt]++;
        }
        else
        {
            ct[cnt]++;
        }
    }
    for(int i=cnt;i>=1;i--)
    {
        int j=upper_bound(bt.begin()+1,bt.end(),bt[i]+k)-bt.begin()-1;
        if(i==j)
        {
            if(ct[i]%2)
            {
                dp[i]=0;
            }
            else
            {
                dp[i]=1;
                add(tr,i);
            }
            continue;
        }
        if(search(tr,j)-search(tr,i)<j-i)//have P => N pos
        {
            dp[i]=1;
            add(tr,i);
        }
        else//not P
        {
            if(ct[i]%2)//odd => P
            {
                dp[i]=0;
            }
            else//even => N
            {
                dp[i]=1;
                add(tr,i);
            }
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        if(dp[i]==1)
        {
            cout<<"YES\n";
            return;
        }
    }
    cout<<"NO\n";
}
//1 2 3 4
//P N N P
//if I can move to P => the pos is N
//if I cant move to P,
    //if cnt is odd => the pos is P
    //if cnt is even => the pos still N
//choos y that x<= y <= x+k

E

Arseniy decided to make his friends Dabir and Egor happy. For this, he decided to give each of them an array of numbers of the same length. An array $b$ is called good if its elements can be rearranged so that for all $i \gt 1$ the condition $b_i - b_{i - 1} = 1$ holds.

Arseniy wants Dabir and Egor to be able to play with these arrays. For this, the following conditions must be satisfied:

1. Each of the given arrays is good.
2. If you write one array after the other (in other words, concatenate them), the resulting array is also good.

Arseniy already has an array $a$ of length $n$. He plans to cut both arrays from $a$, that is, to choose two non-overlapping subsegments of the same length. Help Arseniy determine the maximum possible length of the resulting arrays.

分析：

值域连续且不重复的序列被称为好序列，现在寻找等长度的一对好序列，两者拼起来仍然是个好序列，求出最大长度。

思路：

好序列的$O(N)$判断法，对于区间[l,r]，用vis判断是否有重复序列，并记录区间最大值和最小值，若无重复元素且$MAX-MIN=r-l$，则为好序列。由于有用信息可以只有MIN和区间长度L，我们用矩阵存储MIN和L的数据。
随后$O(N^2)$寻找答案，再矩阵中，定长度为L，的序列中，是否存在$MIN_i+L=MIN_j$，若存在，则答案更新为L。
取最大值即可。

Code

void sol()
{
    int n;
    cin>>n;
    vector<int>a(n+1,0);
    vector<vector<bool>>w(n+1,vector<bool>(n+1));
    vector<bool>vis(n+1,0);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int l=1;l<=n;l++)
    {
        int mi=a[l],ma=a[l];
        vis.assign(n+1,0);
        for(int r=l;r<=n;r++)
        {
            if(r-l+1>n/2)break;
            vis[a[r]]=vis[a[r]]^1;
            if(vis[a[r]]==0)break;
            mi=min(mi,a[r]);
            ma=max(ma,a[r]);
            if(r-l+1==ma-mi+1)
            {
                w[r-l+1][mi]=1;
            }
        }
    }
    int res=0;

    for(int len=1;len<=n/2;len++)
    {
        for(int i=1;i<=n;i++)
        {
            if(i+len>n)break;
            if(w[len][i]&&w[len][i+len])res=len;
        }
    }
    cout<<res<<'\n';
}

F

This is the easy version of the problem. The only difference is that $x = 1$

On the way home after buying his favorite soda “Zola Cero”, Egor saw that elections for the position of “Best Number” are taking place in Saransk.

There are $n$ people at the polling station. Each person brought a number $a_i$. When the $i$-th person enters the voting booth, they choose a candidate that is a divisor of the number $a_i$. Let the chosen candidate be $p_i$.

After everyone has voted, we get an array of votes $[p_1, p_2, \ldots, p_n]$.

Egor really likes the number $x$ and considers the voting ideal if $x \cdot {lcm}(p_1, p_2, \ldots, p_n)$$^{\text{∗}}$ = $p_1 \cdot p_2 \cdot \ldots \cdot p_n$. Help him find the number of different$^{\text{†}}$ arrays $p$ modulo $10^9 + 7$ that are ideal.

$^{\text{∗}}$$lcm$ — least common multiple.

$^{\text{†}}$Two arrays of votes are considered different if there exists an index $i$ where the two arrays have different elements.

分析：

${lcm}(p_1, p_2, \ldots, p_n)$ = $p_1 \cdot p_2 \cdot \ldots \cdot p_n$，实际上就是序列中数据互质。
对于一个数X，一定可以质因数分解为若干质数的幂的乘积，因此我们将所有的$a_i$质因数分解。
对于一个质数P，它如果是p序列中的某个因数$a_j$，它一定只出现在j这个位置，而其也有可能以k次幂的形式出现，因此质数P可以有1~k次幂k种情况出现在$p_j$中。对于每一个j均这样计算，最终可以得到质数P的贡献$D=1+\sum k$，这里的1是它不出现在任何$p_j$中。
最终的答案为所有质数贡献的乘积$ans=\prod D$。

Code

bitset<maxn>not_prime;
vector<int>p;
void prime()
{
    for(int i=2;i*i<=5e5;i++)
    {
        if(!not_prime[i])
        {
            p.push_back(i);
        }
        for(auto x:p)
        {
            if(x*i*x*i>5e5)break;
            not_prime[x*i]=1;
            if(i%x==0)break;
        }
    }
}

void sol()
{
    int n,x;
    cin>>n>>x;
    vector<int>a(n+1);
    map<int,int>mp;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        for(auto x:p)
        {
            if(a[i]%x)continue;
            while(a[i]%x==0)
            {
                mp[x]++;
                a[i]/=x;
            }
            if(a[i]==1)break;
        }
        if(a[i]>1)mp[a[i]]++;
    }
    int ans=1;
    for(auto [k,v]:mp)
    {
        ans=(ans*(v+1))%mod;
    }
    cout<<ans<<'\n';
}