The 2022 ICPC Asia Regionals Online Contest (II)

一直没补，把之前的粘贴过来

E An Interesting Sequence

 为使数组和小，并且gcd=1，我们添加2,3,，找到第一个不整除k的质数，然后后面放2,3，判断先放2还是3

J A Game about Increasing Sequences

Alice and Bob like playing games.

The game is played on a sequence of length n. Alice and Bob take turns performing the operation, with Alice going first.

In each operation, the player can remove an element from the beginning or the end of the sequence.

If this operation is not the first operation of the game, the removed element must be strictly greater than all the previously removed elements.

The player who cannot perform the operation loses.

Please determine who will win the game if both Alice and Bob play the game optimally.

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int l=1;
    for(int i=2;i<=n;i++){
        if(a[i]>a[i-1])l++;
        else break;
    }
    int r=1;
    for(int i=n-1;i>=1;i--){
        if(a[i]>a[i+1])r++;
        else break;
    }
    if(l%2==0&&r%2==0)puts("Bob");
    else puts("Alice");
}

F Infinity Tree

#include<bits/stdc++.h> 
using namespace std;
typedef long long int LL;
vector<LL> xx,yy; 
void find1(LL x,LL k){
    LL d=k+1; LL idex=1; LL lx=1; LL pre; 
    for(int i=1;idex<=1e18/d;i++){ 
        pre=idex; idex*=d; 
        if(idex>=x){ 
            lx=pre; break;
        } 
        pre=idex;
    } 
    lx=pre; LL fa;
    if((x-lx)%k==0)fa=(x-lx)/k;
    else fa=(x-lx)/k+1; xx.push_back(fa); //cout<<fa<<endl; 
    if(fa==1)return ;
    else find1(fa,k);
}
void find2(LL x,LL k){
    LL d=k+1; LL idex=1;
    LL lx=1; LL pre; 
    for(int i=1;idex<=1e18/d;i++){ 
        pre=idex; 
        idex*=d; 
        if(idex>=x){ 
            lx=pre; break;
        } pre=idex;
    }
    lx=pre; LL fa; 
    if((x-lx)%k==0)fa=(x-lx)/k;
    else fa=(x-lx)/k+1;
    yy.push_back(fa); //cout<<fa<<endl;
    if(fa==1)return ; 
    else find2(fa,k); 
}
LL ans; 
void solve(){
    LL k,x,y;
    cin>>k>>x>>y;
    xx.clear();yy.clear();
    xx.push_back(x); 
    yy.push_back(y); 
    find1(x,k); 
    find2(y,k);
    for(int i=0;i<xx.size();i++){ 
        for(int j=0;j<yy.size();j++){ 
            if(xx[i]==yy[j]){
                ans=xx[i];
                return ; 
            }
        }
    }
}
int main(){ 
    int t;
    cin>>t; 
    while(t--){ 
        solve();
        cout<<ans<<endl;
    }
}

A Yet Another Remainder

#include<bits/stdc++.h>

using namespace std;
const int N=100+10;
int a[N][N];
int ph[N];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=min(n,100);i++){
           for(int j=1;j<=i;j++){
             cin>>a[i][j];
           }
        }
        
        int q;
        cin>>q;
        while(q--){
            int p;
            cin>>p;
            ph[0]=1;
        for(int i=1;i<=100;i++){
            ph[i]=ph[i-1]*10%p;
        }
            int k=p-1;
            if(n<=100){
                long long res=0;
                for(int i=1;i<=n;i++){
                    res=(res*10+a[n][i])%p;
                }
                cout<<res<<endl;
            }
            else{
                long long ans=0;
                for(int i=1;i<=k;i++){
                    ans=(ans+a[k][i]*ph[(n-i)%k])%p;
                }
                cout<<ans<<endl;
            }
        }
    }
}

 B Non-decreasing Array

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 110;

int n,a[N];
int f[N][N];

signed main(){
    cin >> n;
    for(int i = 1; i <= n ; ++i)cin >>a[i];

    for(int i = 2; i <= n; ++i){
        for(int j = 2; j <= n;++j){
            for(int k = j - 1; k < i; ++k){
                f[i][j] = max(f[i][j],f[k][j - 1] + (a[i] - a[k])*(a[i] - a[k]));
            }
        }
    }

    int b = (a[n] - a[1])*(a[n] - a[1]);

    int cnt = 0;
    for(int i = n - 2; i >= 2; i -= 2){
        if(f[n][i] == b)break;
        cout<<f[n][i]<<endl;
        cnt ++ ;
    }
    for(int i = cnt; i < n; ++i)cout<<b<<endl;
    return 0;
}