补题链接

E. An Interesting Sequence

题意:

请构造一个总和最小，长度为n且首项为k，并且相邻两项的gcd = 1的数组，输出数组各项之和。

思路:

由唯一分解定理可知,与一个数互质的最小的数也一定是一个质数
由于第一个数是k,那么我们只用在质数中找到与他互质的第一个数
由于要使得最后的和最小,且两个质数一定是互质的,那么我们后面直接填2323这样的数即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>

using namespace std;
//#pragma GCC optimize(3)
const int N = 1e8 + 10;
typedef long long LL;
//#define int long long
#define endl "\n"
typedef pair<int,int>PII;
//#define x first
//#define y second
int primes[N],cnt;
bool st[N];

void init()
{
    for(int i = 2; i * i < N; i ++)
    {
        if(!st[i])primes[cnt ++] = i;
        else 
        {
            for(int j = 0; primes[j] * i < N; j ++)
            {
                st[primes[j] * i] = true;
                if(i % primes[j] == 0)break;
            }
        }
    }
}

int gcd(int a,int b)
{
    return b ? gcd(b,a % b) : a;
}

void solve()
{
    int n,k,t;cin >> n >> k;
    for(int i = 0; i < cnt; i ++)
    {
        if(gcd(primes[i],k) == 1)
        {
            t = primes[i];
            break;
        }
    }

    LL res = k + t;
    if(t == 2)
    {
        for(int i = 3; i <= n; i ++)
        {
            if(i & 1)res += 3;
            else res += 2;
        }
    }
    else 
    {
        for(int i = 3; i <= n; i ++)
        {
            if(i & 1)res += 2;
            else res += 3;
        }
    }

    cout << res << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    init();
    //cin >> T;
    while (T--) solve();
    return 0;
}

J. A Game about Increasing Sequences

题意:

有一个序列,Alice和Bob分别从两头取,且每次取的数要比上次大,不能操作的那个人输,问最后的赢家是谁?

思路:

假定我们的序列是$a[1-n]$,且$a[1]<a[n]$,另一种情况与之类似:
假设Alice选择了右侧的路,那么由于$a[1]<a[n]$,只能是一条路到头,这时候只用判断合法的数的奇偶性即可,奇数Alice赢,否则Bob赢.
对于Alice而言,如果右侧的路不为偶数,那么一定会选择左侧的路,不妨假设左侧的路是奇数,那么Alice一定不会去选择右侧的路,因为只要沿着当前路直走就能获胜,但是Bob可能会选择右侧的路,Alice此时跟进它即可,若Bob一致沿右侧的路走,那么一定会输,如果它中途换到左侧的路,注意此时Alice也换路跟进,但此时左侧路的奇偶性并没有改变,也就是说不会影响最终的胜负.
所以我们只用考虑分别沿左右两侧走的情况,若出现某一条路的长度为奇数,那么一定是Alice赢,否则是Bob赢

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>

using namespace std;
//#pragma GCC optimize(3)
const int N = 1e6 + 10;
typedef long long LL;
//#define int long long
#define endl "\n"
typedef pair<int,int>PII;
//#define x first
//#define y second
int a[N];
void solve()
{
    int n;cin >> n;
    for(int i = 1; i <= n; i ++)cin >> a[i];

    bool flag = false;
    int cnt1 = 0,cnt2 = 1;//确保第一个数都能被选上
    //从左侧选
    for(int i = 1; i <= n; i ++)
    {
        if(a[i] - a[i - 1] <= 0)break;
        cnt1 ++;
    }
    //从右侧选
    for(int i = n; i >= 1; i --)
    {
        if(a[i] - a[i - 1] >= 0)break;
        cnt2 ++;
    }
    if((cnt1 & 1) || (cnt2 & 1))cout << "Alice" << endl;
    else cout << "Bob" << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T--) solve();
    return 0;
}

F. Infinity Tree

题意:

给定一个参数k，最开始只有一个根节点1，每一秒钟，每个节点会长出k个子节点，给定结点u和v，求出u和v的lca。

思路:

找规律,假设k=2吧,第1s有1个结点,第2s有3个结点,第3秒有9个结点,依此类推,我们可以得到第t秒的结点数为(k+1) ^(t-1)个结点.
对于某个结点我们如何找到它的父节点呢?以$k=2$为例,当t=3的时候有$(10~27)$这18个结点,其中$(10,11)->1,(12,13)->2…$,换一种写法可以看到$(10-9,11-9)=(1,2)->1,(12-9,13-9)=(3,4)->2....$
所以对于结点x,假设它前一轮的结点数为xx,它的父节点就是$(x-xx)/k(上取整)$
最后如何求出xx呢?我们暴力跳即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>

using namespace std;
//#pragma GCC optimize(3)
const int N = 1e5 + 10;
typedef long long LL;
#define int long long
#define endl "\n"
typedef pair<int,int>PII;
//#define x first
//#define y second

void solve()
{
    int k,x,y;cin >> k >> x >> y;
    __int128 xx = 1,yy = 1;

    for(; xx <= x; xx *= (k + 1));
    for(; yy <= y; yy *= (k + 1));
    xx /= (k + 1);yy /= (k + 1);

    while(x != y)
    {
        if(x > y)//深的先跳
        {
            x = (x - xx + k - 1) / k;
            for(; xx <= x; xx *= (k + 1));
            xx /= (k + 1);
        }
        else 
        {
            y = (y - yy + k - 1) / k;
            for(; yy <= y; yy *= (k + 1));
            yy /= (k + 1);
        }
    }
    cout << x << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}

B.Non-decreasing Array

题意:

给定一个长度为n的单调上升的序列，每次可以选择删除一个数，然后再让一个另外一个数变成任意一个数但是不超过数组内的最大值和最小值。其中最大值和最小值不能删除，求第i次操作的$(a[i + 1] - a[i])^2$的总和的最大值。

思路:

DP:f[i][j]表示从前i个数中选,最多删除j个数的最大值。
我们只考虑状态转移,我们的状态是从前向后推得,我们只用考虑删连续的一段,这样我们最终的答案也是会包含所有不连续的部分.

int f[N][N]; // 第i位 删除j次 但是保留i位置 的最大值
int calc(int l, int r) {
    return (a[r] - a[l]) * (a[r] - a[l]);
}

signed main() {
    cin >> n;
    for(int i = 1; i <= n ; i ++ ) cin >> a[i];
    for(int i = 1 ; i <= n ; i ++ ) 
        for(int j = 0 ; j <= i - 2 ; j ++ ) 
            for(int k = 0 ; k <= j ; k ++ ) {
                int pos = i - k - 1; // 删除[pos + 1, i - 1]的区间:[i - k + 1, i - 1] // k是长度
                f[i][j] = max(f[i][j], f[pos][j - k] + calc(pos, i));
            }

    for(int i = 1 ; i <= n ; i ++ ) {
        if(i * 2 > n - 2) cout << f[n][n - 2] << endl;
        else cout << f[n][2 * i] << endl;
    }
    return 0;
}