A. Joey Takes Money
--------------------------题解------------------------------------
选取x和y替换掉a[i],a[j]，前提是两者乘积相同，最后要求和数组最大，其实很简单，我们只需要不对另x=1 y=a[j]*a[x]就行，从左到右遍历整个数组队a[i]和a[i+1]进行此操作，就可以得到我们想要的值了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll a[N];
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n;
ll sum=0;
cin>>n;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
}
for(ll i=1;i<=n-1;i++)
{
ll q=a[i]*a[i+1];
a[i]=1;
a[i+1]=q;
sum+=a[i];
}
sum+=a[n];
sum=sum*2022;
cout<<sum<<'\n';
}
}
B. Kill Demodogs
-----------------------------------------题解-----------------------------------
这题我们要求i和j乘积的和的最大值，根据中学我们学的基本不等式可以知道当i==j的时候是一定范围内的乘积最大值，因此我们要走的就是对角线我们按照(1,1)(1,2)(2,2)(2,3)....这样的方法的走我们可以得到11+...nn加上12+23+34...(n-1)n。我故意这么写就是为了把这两步分开来计算 要分别求出两个公式来，公式推导过程我就不贴了，请自己去查询两个公式求和公式分别是
n(n+1)(2*n+1)/6
((n-1)n))(n+1)/6
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll qmi(ll a,ll b,ll q)
{
ll res=1;
while(b)
{
if(b&1)res=res*a%q;
a=a*a%q;
b=b/2;
}
return res;
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll sum=0;
ll q1=(((n*(n+1))%mod)*(2*n+1)%mod)%mod;
ll q2=((((n-1)*n)%mod)*(n+1)%mod)%mod;
sum+=q1*qmi(6,mod-2,mod)%mod*2022%mod;
sum+=q2*qmi(6,mod-2,mod)%mod*2022*2%mod;
//sum=sum*2022;
sum=sum%mod;
//if(sum==999584486)sum=999589541;
cout<<sum<<'\n';
}
}
C. Even Subarrays
-----------------------------题解----------------------------
这题用到了一个理论，只有完全平方数的因子个数才是奇数个，其他的全是偶数个。总子数组的个数是(n*n+1)/2个，我们用总子数组的个数减去区间异或和为完全平方数的个数就行了
然后我们用异或前缀和的另a[i]^a[i-1]这样出来的一个新数组 如果我们想求 a[i]a[i+1]....a[j]的值只需要用整个新数组的b[i]^b[j]就好了
这么处理完之后我们对于数组中每个值，我们设一个数为x 如果x^b[i]=jj（完全平方数） 那么jj^b[i]=x,由此可知，我们需要找出所有x就需要对每一个b[i]枚举j*j
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N];
int b[N];
signed main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
b[0]=0;
int ans=0;
int x=1;
while(x<=n) x=x<<1;
vector<int> c(x, 0);
c[0]=1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i]^b[i-1];
for(int j=0;j*j<x;j++)
{
ans+=c[(j*j)^b[i]];
}
c[b[i]]++;
}
cout<<n*(n+1)/2-ans<<'\n';
}
}
D. Valiant's New Map
d很简单，二分+二位前缀和检验，直接贴代码了，icpc比赛中做过很多了
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3;
int n, m;
int a[N][N];
int check(int x){
vector<vector<int>> g(n + 1, vector<int>(m + 1, 0));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
g[i][j] = (a[i][j] >= x);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
for(int i = 1; i + x - 1 <= n; i++)
for(int j = 1; j + x - 1 <= m; j++)
if(g[i + x - 1][j + x - 1] - g[i + x - 1][j - 1] - g[i - 1][j + x - 1] + g[i - 1][j - 1] == x * x)
return true;
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--){
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> a[i][j];
int l = 0, r = n + 1;
while(l + 1 < r){
int mid = l + r >> 1;
if(check(mid)) l = mid;
else r = mid;
}
cout << l << "\n";
}
return 0;
}