A. Joey Takes Money

思路：

累乘在加上n-1即可

Code:

#include
#include
#include
#include
#include
typedef long long LL;
using namespace std;
void solve()
{int n;cin>>n;LL res=1;for(int i=1;i<=n;i++){int x;cin>>x;res*=x;}cout<<2022*(res+n-1)<<'\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int test;cin>>test;while(test--) solve();
}

B. Kill Demodogs

思路：

贪心：靠中心走。

求和化简得n*(n+1)*(2n+1)/3-n*(n+1)/2

Code:

#include
#include
#include
#include
#include
typedef long long ll;
using namespace std;
const long long mod=1e9+7;
ll ksm(ll a,ll b)
{ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b/=2;}return res;
}
void solve()
{ll n;cin>>n;ll a,b,c;a=n%mod;b=(n+1)%mod;c=(2*n+1)%mod;ll res=a*b%mod*c%mod*ksm(3,mod-2)%mod;ll tmp=a*b%mod*ksm(2,mod-2)%mod;res=((res-tmp)%mod+mod)%mod*2022%mod;//注意相减可能为负cout<>test;while(test--) solve();
}

C. Even Subarrays 

思路：

维护前缀异或和数组s[]

区间[l,r]异或和为s[r]^s[l-1]

暴力枚举区间O(n^2)必超时

 因子个数为奇数的一定是平方数，可以枚举所有x，x^s[r]为平方数。考虑到ai的范围，平方数的大小不会超过512*512。

具体做法：枚举右端点，t[]数组维护前i-1个s[]值的个数,减去平方的即可。

Code:

#include
#include
#include
#include
#include
typedef long long ll;
using namespace std;
const int N=4e6+10;
int a[N],s[N],t[N];
void solve()
{int n,mx=0;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]^a[i];mx=max(mx,a[i]);}for(int i=0;i<=10*mx;i++) t[i]=0;ll res=0;t[0]=1;for(int r=1;r<=n;r++){int cnt=0;for(int i=0;i<=513;i++){int tmp=s[r]^(i*i);cnt+=t[tmp];}t[s[r]]++;res+=(ll)r-cnt;}cout<>test;while(test--) solve();
}

 D. Valiant's New Map

思路：

边长具有单调性，考虑二分边长

如何判断矩形满足条件

暴力判断O(mid*mid)

考虑判断矩形大于mid的个数，维护数组b。如果a[i]>=mid b[i]=1,否则b[i]=0.

在维护前缀和prefix，即为数组中大于mid的个数，就可以O(1)判断矩形是否满足条件

时间复杂度(n*m*log(n))

Code:

#pragma GCC optimize(2)
#include
#include
#include
#include
#include
#include
#define endl "\n"
typedef long long LL;
using namespace std;
int n,m;
bool check(int mid,vector> a)
{vector> sum(n+1,vector(m+1));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(a[i][j]>=mid) a[i][j]=1;else a[i][j]=0; sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(i+mid-1>n||j+mid-1>m) continue;int tmp=sum[i-1][j-1]+sum[i+mid-1][j+mid-1]-sum[i-1][j+mid-1]-sum[i+mid-1][j-1];if(tmp>=mid*mid) return true;}return false;
}
void solve()
{cin>>n>>m;vector> a(n+1,vector(m+1));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];int l=0,r=min(n,m)+1;while(l+1>test;while(test--) solve();
}

tips:

一开始我把计算矩阵和写为函数cal(int x1,int y1,int x2,int y2,vector> sum)

时间超限了。

我猜是因为以数组为形参会把数组的数都遍历一遍，就和暴力的复杂度一样了