The 2022 ICPC Asia Regionals Online Contest (II)

E An Interesting Sequence

232323232323

323232323232

#include<bits/stdc++.h>


using namespace std;

typedef long long ll;

void solve()
{
	ll n, k;	cin>>n>>k;
	ll res = k;
	ll t = 0;
	for(int i = 2; i <= k + 1; i++)
		if(__gcd(1ll * i, k) == 1)
		{
			t = i;
			break;
		}


	if(__gcd(t, 2ll) == 1)
	{
		res = k + t;
		n -= 2;
		res += (n / 2) * 5 + (n % 2) * 2;
	}
	else if(__gcd(t, 3ll) == 1)
	{
		res = k + t;
		n -= 2;
		res += (n / 2) * 5 + (n % 2) * 3;		
	}
	cout<<res<<'\n';

}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);	cout.tie(nullptr);

	solve();
	return 0;
}

J A Game about Increasing Sequences

能拿的区间奇偶性判断

#include<bits/stdc++.h>


using namespace std;

typedef long long ll;


const int N = 2e5 + 10;
int n, a[N], cnt1 = 0, cnt2 = 0;
void solve()
{
	cin>>n;
	for(int i = 1; i <= n; i++)
		cin>>a[i];
	cnt1 = 1;
	while(cnt1 + 1 <= n && a[cnt1 + 1] > a[cnt1])
		cnt1++;
	int j = n;
	while(j - 1 >= 1 && a[j - 1] > a[j])
		j--;
	cnt2 = n - j + 1;
	if(cnt1 % 2 == 0 && cnt2 % 2 == 0)
		cout<<"Bob\n";
	else if(cnt1 % 2 == 1 || cnt2 % 2 == 1)
		cout<<"Alice\n";
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);	cout.tie(nullptr);

	solve();
	return 0;
}

F Infinity Tree

记录每一轮产生儿子的上一轮数量，

记录产生 \(u\) 是第 \(tu\) 轮，\(v\) 同理

对 \(u\) ， \(v\) 做一个 LCA, LCA 过程：

结点最大的数 \(u\)，上一轮数量 \(y\), 其 \(u\) 父亲是的 \(\dfrac{u - y}{k} + [u \% k != 0]\) ，并更新 \(tu\)

__int128 a[N];

void lca(__int128 u, __int128 v, __int128 tu, __int128 tv, __int128 &k)
{
    int cnt = 0;
    while(u != v)
    {
        ++cnt;
        //if(cnt == 10)   break;
        // write(u); cout<<"    "; write(v);   cout<<'\n';
        // write(u); cout<<"    ";     write(a[tu]); 
        // cout<<"    "; cout<<"    ";
        // write(v);  cout<<"    ";    write(a[tv]);
        // cout<<'\n';


        //write(u);   cout<<"    "; write(v);
        if(u > v)
        {
            __int128 t = u - a[tu];
           // write(a[tu]);    cout<<'\n';
            t = t / k + (t % k != 0);
            u = t;
           // write(t);   cout<<"new u\n";
            while(u <= a[tu])    tu--;
        }
        else if(u < v)
        {
            __int128 t = v - a[tv];
           // write(a[tv]);    cout<<'\n';
            t = t / k + (t % k != 0);
            v = t;
            //write(t);   cout<<"new v\n";
            while(v <= a[tv])    tv--;
        }
        // write(u); cout<<"    "; write(v);   cout<<'\n';
        //  cout<<'\n'; cout<<'\n';

    }
    write(u);
    puts("");
}
/*
1
2 6 7
*/
/*
3
2 6 7
2 4 5
3 20 2

1
2 100000000000000000 1000000000000000
*/
void solve()
{
    __int128 k, u, v;
    __int128 p, tu, tv, times;
    k = read(), u = read(), v = read();
    if(u == 1 || v == 1)
    {
        __int128 res = 1;
        write(res);
        cout<<'\n';
        return;
    }
    tu = tv = 0, p = 1, times = 0;
    while(tu == 0 || tv == 0)
    {
        times++;
        a[times] = p;
        __int128 l = p + 1, r = (k + 1) * p;
        p = r;
        // write(l); cout<<"    "; write(r);   cout<<'\n';
        if(l <= u && u <= r)    tu = times;
        if(l <= v && v <= r)    tv = times;
    }
    // cout<<'\n';
    // cout<<'\n';
    // write(tu); cout<<"  ";  write(tv);
    // cout<<'\n';
    // cout<<'\n';

    lca(u, v, tu, tv, k);
}

B Non-decreasing Array

对于两个操作都可以认为是删掉一个元素

直接dp即可

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e2 + 10;
ll n, a[N], f[N][N], b[N];
void solve()
{
	cin>>n;
	for(int i = 1; i <= n; i++)
		cin>>a[i];
	for(int i = 1; i <= n; i++)
	{
		int k = i * 2;
		ll res = 0;
		if(n - 2 - 2 * i <= 0)
		{
			cout<<(a[n] - a[1]) * (a[n] - a[1])<<'\n';
			continue;
		}
		memset(f, 0, sizeof f);
		for(int p1 = 1; p1 <= n; p1++)
			for(int q = 0; q <= k; q++)
				for(int p2 = p1 + 1; p2 - p1 - 1 + q <= k && p2 <= n; p2++)
					f[p2][p2 - p1 - 1 + q] = max(f[p1][q]  + (a[p2] - a[p1]) * (a[p2] - a[p1]),
						f[p2][p2 - p1 - 1 + q]);
					//cout<<p1 <<" "<<q<<" "<<p2<<" "<<p2 - p1 - 1 + q <<" "<<f[p2][p2 - p1 - 1 + q]<<'\n';
					//res = max(f[p2][p2 - p1 - 1 + q], res);
		for(int q = 0; q <= k; q++)
			res = max(f[n][q], res);
		cout<<res<<'\n';
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);	cout.tie(nullptr);

	solve();
	return 0;
}