A
核心思路：就是一个简单的找规律大胆去猜结论就好了。
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
LL a[N];
void solve()
{
int n;
cin >> n;
LL mul = 1;
for (int i = 0;i < n;i++)
{
cin >> a[i];
mul *= a[i];
}
LL ans = (mul + n - 1) * 2022;
cout << ans<<endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}
B
核心思路：我们可以先模拟样例发现规律，我们可以发现其实像这种蛇皮走位是最快的，也就是就先向右走一步，再向下，再向右，在向下。但是我们可以发现那个数据范围实在是太大了，所以暴力肯定是不可以的。那我们就可以推导这个公式，也就是\(1+\sum_{i=1}^{n-1}i*(i+1)+(i+1)^2\),化简下就是\(\sum_{1}^{n}i^2+\sum_{1}^{n-1}i*(i+1)\),接下来使用平方和公式就好了。但是这里还有个数爆了精度，不知道为什么。以后再回来验证.
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+ 10;
int n,m;
vector<vector<int>> a;
LL mod=1e9+7;
LL qmi(LL a,LL b)
{
LL res=1;
while(b)
{
if(b&1)
res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
void solve()
{
int n;
cin>>n;
LL a=(n-1)*n%mod*(2*n%mod-1)%mod*qmi(3,mod-2)%mod;
LL b=3*n%mod*(n-1)%mod*qmi(2,mod-2)%mod;
LL ans=((a+b)%mod+mod)%mod;
LL res=(ans+n)%mod;
cout<<res*2022%mod<<endl;
}
int main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
C
核心思路：首先还是模拟样例发现一般结论，我们可以发现对于所有完全平方数都是不符合规则的。所以我们可以正难则反，先求出来所有方案，再减去不合法的方案就好了。
所以我们可以预处理出来所有的完全平方数和前缀异或和，然后使用完全平方数异或下前缀和就可以发现肯定不合法的方案。
总的方案数这里我们可以看成线段长度来表示序列，长度为n的序列很显然只有1个，为n-1的有两个，依次类推总的方案数就是\(n*(n+1)/2\).
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
const int N = 1e6 + 10;
int s[N], cnt[N];
vector<int> sqrts;
LL mod = 1e9 + 7;
void solve()
{
int n;
cin >> n;
LL ans = 1LL * n * (n + 1) / 2;
cnt[0]++;
for (int i = 1; i <= n; i++) {
cin >> s[i];
s[i] ^= s[i - 1];
for (auto x : sqrts)
ans -= cnt[s[i] ^ x];
cnt[s[i]]++;
}
cout << ans << '\n';
for (int i = 0; i <= n; i++) cnt[s[i]]--;
}
int main()
{
int T;
cin >> T;
for (int i = 0;i*i <= 500000;i++)
sqrts.push_back(i * i);
while (T--)
{
solve();
}
}
D
核心思路：我们可以先使用d数组表示大于mid的数，如果大于就是1，小于就是0.然后在联想二维数组的前缀和，这样我们就可以求出来任意一块面积为\(mid*mid\)的矩形是不是符合要求的。
因为如果是的话他的面积一定是等于\(mid*mid\)的。
然后mid表示的又是什么呢，他表示的是我们每次二分出来的答案。我们可以通过不断二分缩小范围最后拿到我们想要的答案。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+ 10;
int n,m;
vector<vector<int>> a;
int check(int mid)
{
int d[n+1][m+1],s[n+1][m+1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]>=mid)
d[i][j]=1;
else
d[i][j]=0;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]=d[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int x1=i;
int y1=j;
int x2=i+mid-1;
int y2=j+mid-1;
if(x2<=n&&y2<=m)
{
if(s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]==mid*mid)
return 1;
}
}
return 0;
}
void solve()
{
cin>>n>>m;
a.resize(n+1);
for(int i=1;i<=n;i++)
{
a[i].resize(m+1);
for(int j=1;j<=m;j++)
cin>>a[i][j];
}
int l=0;
int r=max(m,n);
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid))
l=mid;
else
r=mid-1;
}
cout<<r<<endl;
}
int main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}