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;
}