The 2022 ICPC Asia Regionals Online Contest (II)ABEFJ
The 2022 ICPC Asia Regionals Online Contest (II)
A Yet Another Remainder
题意：给你一个正整数\(x\)，但是这个数被隐藏起来了。你问了电脑\(min(100,n)\)个问题，第\(i\)轮，的第\(j\)个问题：\(O(j,i\times \lfloor\dfrac{n-j}{i}\rfloor+j,i)\)，让\(l = j，r = i\times \lfloor \dfrac{n-j}{i}\rfloor + j\),你将得到\(a_l+a_{l+i}+a_{l+2_i}+...+a_r\)的值。之后有\(q\)个询问，给你一个质数\(p = 3,7\le p\le 97\)，你回答这个隐藏的整数\(x \mod p\)的值是多少？
思路：首先，看问题描述我们发现几个有趣的事情：
- 询问的\(p\)是\(100\)以内的质数，但唯独不包含\(2\)和\(5\)，是为什么？
- 题目中告诉你的都是每种步长的和，为什么要告诉我这个？和它的和有什么关系？
对于第一个事情，不包含\(2\)和\(5\)，说明询问的p是和\(10\)是互质的。
对于第二个事情，根据第一个想法，我们考虑，把一个数可以拆成以下形式：\(\sum_{i = 1}^{n} a[i]*10^{n-i}\)
举个例子：比如数\(998244353\),可以拆成：\(9*10^8+9*10^7+8*10^6+2*10^5+...+3*10^0\)
然后我们又发现，根据费马小定理知：如果\(a,p\)互质有：\(a^{p-1}≡1(\mod p)\)，所以每\(p-1\)是一个循环节。
比如以模数为\(7\)为例,因为\(10\)和\(7\)互质，所以有\(a^{p-1}≡1(\mod p)\)，即\(10^{p-1}≡1(\mod p)\),设\(p-1 = k\)，那么\(10^{tk} ≡ 1(\mod p)\)。也就是\(p-1\)是一个循环节，这里的话就是\(7-1 = 6\)。
\(10^0,10^6,10^{12}...\)在\(\mod 7\)的意义下都是等于\(1\)的，而\(10^1,10^7,10^{13}...\)在\(\mod 7\)的意义下都等于\(3\)....以此类推。
\((a[1]*10^0 + a[7]*10^6+a[13]*10^{12}+...)\mod 7 = 1*(a[1]+a[7]+a[13]+...)\)
\((a[2]*10^1 + a[8]*10^7+a[14]*10^{13}+...) \mod 7 = 3*(a[2]+a[8]+a[14]+...)\)
到这里，我们发现了，题目告诉我们每个步长个数的加和是为什么了。那么下面就是做法：对于模数\(p\),我们的答案在\(p-1\)行获取(因为步长是\(p-1\)，我们想要知道每隔\(p-1\)个的加和)。\(p-1\)行的第\(i\)列的加和就是\(10^i \mod p\)相等的值前面的系数了。用\(c[i][j]\)表示：\(10^j \mod i\)的值是多少(预处理),用\(b[i][j]\)表示：步长为\(i\)的第\(j\)组数的和(题目输入)。对于模数是\(p\)的答案就是：\(\sum_{i = 1}^{p-1}b[p-1][i]*c[p][(n-i)\bmod (p-1)]\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 110;
ll c[N][N],b[N][N];
void init()
{
for(int i = 1;i<=100;i++)
{
c[i][0] = 1;
for(int j = 1;j<=i;j++)
{
c[i][j] = c[i][j-1]*10%i;
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
init();
while(t--)
{
int n;
cin>>n;
for(int i = 1;i <= min(n,100);i++)
{
for(int j = 1;j<=i;j++)
{
cin>>b[i][j];
}
}
if(n<=100)
{
int q;
cin>>q;
while(q--)
{
int p;
cin>>p;
ll ans = 0;
for(int i = 1;i<=n;i++)
{
ans *= 10;
ans%=p;
ans += b[n][i];
ans %= p;
}
cout<<ans%p<<"\n";
}
}
else{
int q;
cin>>q;
while(q--)
{
int p;
cin>>p;
ll ans = 0;
for(int i = 1;i<=p-1;i++)
{
ans += b[p-1][i]%p*c[p][(n-i)%(p-1)];
ans%=p;
}
cout<<ans<<"\n";
}
}
}
return 0;
}
B Non-decreasing Array
题意：给你一个不降序列\(a_1,a_2,...,a_n\)，在一次操作：第一步你可以选择一个数删了或者什么也不做。第二步你可以选择一个数把它改成任意整数。
每次操作你都需要保证序列是单调不减的，你有\(k\)次操作\(1\le k\le n\)，当当前长度是\(m\)的时候，贡献是\(\sum_{i =2}^{m}(a_i-a_{i-1})^2\)。问操作\(k\)次的最大值。
思路：一次操作有\(2\)步：$1.删一个数(或者不删)\(2.改一个数。要保证一直是单调不减的，而且还要值最大，那么我们如果要变化一个数，最大的变化范围是\)a[1]\(到\)a[n]$。我们考虑如何使得值最大？
对于\(a->b\)，如果中间插入一个\(c\)，假设\(a->c\)贡献是\(x\)，\(c->b\)贡献是\(y\)。
那么对于\(a->b\)的贡献是\((x+y)^2\)，而\(a->c->b\)的贡献是\(x^2+y^2\)。显然前者贡献更大。那么我们得到了数越少越优。一开始我们考虑的策略是删中间某几个数，把两边的一遍往小缩小(缩小到它前一个一样)，一边往后放大(放大到它后一个一样)。其实换个角度考虑，如果按照以上策略，可以简化一下，因为缩小和放到都是变成和另一个别的什么数一样，那么这个数的贡献变成了\(0\)，和删了它效果一样。综上所述，我们要数尽量的少，那么考虑每次都删数，改数也理解为删数，那么题目变成了每次都删，一次删\(2\)个，第一个和最后一个是不删的，那么最后至少还有\(2\)个数。
对于数怎么删，考虑\(dp\)，设\(dp[i][j]\)表示：前\(i\)个数，删\(j\)个(保证这删的\(j\)个不包括第一个和最后一个）。接下来考虑转移：
\(for(i = 1;i<idx;i++)\)
\(cnt = j-((idx-1)-(i+1)+1);\)设这一次删的是\(i+1\)到\(idx-1\)
\(dp[idx][j] = \max(dp[idx][j],dp[i][cnt]+(a[idx]-a[i])*(a[idx]-a[i]));\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 110;
ll n;
ll a[N];
ll dp[N][N];
ll dfs(int idx,int k)
{
ll &res = dp[idx][k];
if(dp[idx][k]!=-1)return res;
res = 0;
for(int i = 1;i<idx;i++)
{
//i+1,idx-1
int cnt = k-((idx-1)-(i+1)+1);
if(cnt<0)continue;
res = max(res,dfs(i,cnt)+(a[idx]-a[i])*(a[idx]-a[i]));
}
return res;
}
int main()
{
cin>>n;
for(int i = 1;i <= n; i++)
cin>>a[i];
memset(dp,-1,sizeof(dp));
for(int i = 1;i <= n; i++)
{
int k = i*2;
if(n-k-2<=0)cout<<(a[n]-a[1])*(a[n]-a[1])<<"\n";
else cout<<dfs(n,k)<<"\n";
}
return 0;
}
/*
5
1 2 3 4 5
*/
E An Interesting Sequence
题意：给你一个\(a_1 = k\)，告诉你数列总长度是\(n\)，让你去构造，保证\(\gcd(a_{i-1},a_i)=1\)，求\(\sum_{i = 1}^{n}a_i\)的最小值。
思路：对于\(a_1\)是偶数(因为\(3\)不一定和偶数互质)，考虑找到与\(a_1\)互质的第一个奇数质数，然后后面构造\(2,3,2,3...\)
对于\(a_1\)是奇数，直接构造\(2,3,2,3,...\)即可（奇数一定和\(2\)互质）。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
const int N =1000010;
bool is_pri[N];
int pri[N];
int cnt;
void init(int n)
{
memset(is_pri, true, sizeof(is_pri));
is_pri[1] = false;
cnt = 0;
for (int i = 2; i <= n; i++)
{
if (is_pri[i])
pri[++cnt] = i;
for (int j = 1; j <= cnt && i * pri[j] <= n; j++)
{
is_pri[i * pri[j]] = false;
if (i % pri[j] == 0)break;
}
}
}
int main()
{
init(20);
cin>>n>>k;
ll ans = k;
if(k%2==0)
{
for(int i = 1;i<=cnt;i++)
{
if(pri[i]%2)
{
if(k%pri[i]!=0)
{
ans += pri[i];
break;
}
}
}
int m = n-2;
ans += m/2*5+(m%2)*2;
}
else
{
int m = n-1;
ans += m/2*5+(m%2)*2;
}
cout<<ans<<endl;
return 0;
}
F Infinity Tree
题意：一开始你有\(1\)个节点，每秒每个节点产生\(k\)个孩子。即第\(x\)秒的节点个数是\((k+1)^x\)个。
对于一个节点\(y\)，它产生的孩子是\([p+(y-1)\times k+1,p+y*k]\)。
给你两个节点\(x,y\)，问他们的\(lca\)是谁。
思路：考虑对于一个孩子\(x\)，它的父亲是谁？根据题目给的公式反推得到父亲\(y = (x-p)/k+((x-p)\mod k!=0)\)
那么我们先预处理出来每秒的节点个数，去找产生节点个数小于\(x\)的最后一个，那就是它父亲那一轮的节点个数，这样可以推出它的父亲。考虑\(x,y\)的\(lca\)怎么求？每次跳节点编号大的那个就行。注意，父亲不一定是孩子的上一秒产生的，所以不能单纯的用孩子的秒数-1得到，而是要重新去求。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
inline __int128 read(){__int128 x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
inline void write(__int128 x){if (x < 0){putchar('-');x = -x;}if (x > 9) write(x / 10);putchar(x % 10 + '0');}
typedef __int128 ll;
ll k,x,y;
ll p[N];
ll now;
ll pre_gx,pre_gy;
void init(ll x)
{
p[0] = 1;
now = 1;
if(x==1)return;
while(1)
{
p[now] = p[now-1]*(k+1);
if(p[now]>x)break;
now++;
}
}
ll lca(ll x,ll y)
{
while(x!=y)
{
if(x==1||y==1)return 1;
if(x>y)
{
x = (x-p[pre_gx])/k+((x-p[pre_gx])%k != 0);
ll t = pre_gx;
for(int i = t - 1;i>=0;i--)
if(p[i]<x){
pre_gx = i;
break;
}
}
else if(y>x)
{
y = (y-p[pre_gy])/k+((y-p[pre_gy])%k != 0);
ll t = pre_gy;
for(int i = t - 1;i>=0;i--)
if(p[i]<y){
pre_gy = i;
break;
}
}
}
return x;
}
int main()
{
int t;
cin>>t;
while(t--)
{
k = read(),x = read(),y = read();
init(max(x,y));
for(int i = 0;i<=now;i++)
if(p[i]>x)break;
else pre_gx = i;
for(int i = 0;i<=now;i++)
if(p[i]>y)break;
else pre_gy = i;
write(lca(x,y));
cout<<"\n";
}
return 0;
}
/*
1
2 100000000000000000 1000000000000000
*/
J A Game about Increasing Sequences
题意：\(A,B\)在玩游戏，每次每人选一个数，要求比上一个人选的大，而且只能从两端选取，第一个选不了了的人输。\(A\)是先手，\(B\)是后手，问谁赢。
思路：因为每次要选比上一个大的，那么选出来的数列一定是单增的。考虑能选多少次，如果前缀和后缀能选的次数都是偶数\(B\)赢，否则\(A\)。因为只要可下次数是奇数，那\(A\)必赢，反之\(B\)。可能你会有疑惑，那我如果某个人选了某一边而导致另一边不能选了的情况，会不会改变奇偶性呢？
举个实际的例子吧:\(1,2,3,5,7,7,5,4,3\)
可能你会疑惑第一次\(A\)选了左边和右边结果会不会不一样？
对应选法就是：(奇数个)\(ABABA\) \(BABA\)(偶数个)
因为都是最优策略，以\(A\)为例，如果\(A\)要自己赢，那么最后一步一定是\(A\)下的，是奇数步数。如果按照只下左边，那么肯定是奇数步，那如果\(B\)改了，他去下右边了，那也不会影响，右边是偶数个，左边下了奇数步，那总的还是奇数步，仍为\(A\)赢。
所以综上所述，只有两边都是偶数才是\(B\)赢。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int n,k;
int a[N];
int pre,suf;
int main()
{
cin>>n;
for(int i = 1;i<=n;i++)
cin>>a[i];
for(int i = 1;i<=n;i++)
{
if(a[i]>a[i-1])
pre++;
else break;
}
for(int i = n;i>=1;i--)
{
if(a[i]>a[i+1])
suf++;
else break;
}
if(pre%2==0&&suf%2==0)cout<<"Bob\n";
else cout<<"Alice\n";
return 0;
}