Codeforces Round#841(Div.2) and Divide by Zero 2022
题解A~D(后续可能会更EF)
A题
题目描述
给定一个数组a,每次操作(次数无限制)选择两个下标 i , j。可以让元素a[i],a[j]重新赋值为x,y当且仅当a[i]*a[j]=x*y; 问数组最后的和可能最大为多少,输出乘以2022。
样例
input:
3
3
2 3 2
2
1 3
3
1000000 1000000 1
output:
28308
8088
2022000000004044
算法
贪心的一个小方法,假设两个元素a,b,则a*b+1一定是大于等于a+b;
所以只要第一个元素是所有的数组原本所有的元素的积且其余都为1即可。
C++ 代码
#include<bits/stdc++.h>
#define int long long
void solve()
{
int n;
std::cin>>n;
int ans=1;
for(int i=1; i<=n; i++)
{
int a;
std::cin>>a;
ans*=a;
}
std::cout<<(ans+n-1)*2022<<"\n";
}
signed main()
{
int _=1;
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin>>_;
while(_--)
{
solve();
}
}
B题
题目描述
给定一个矩阵的宽度为n,矩阵的每个元素值为它所在的行乘以它所在的列。小明在坐标(1,1)走到坐标(n,n)且小明只能向右或向下走,小明每经过一个网格都会获取网格的上的值,问小明获得的值最大为多少,输出最大值乘以2022并对1e9+7取模。
样例
input:
4
2
3
50
1000000000
output:
14154
44484
171010650
999589541
算法
结论:对角线上所有的点(1,4,9,16.....)都经过时,那这条路径的权和就最大。
平方和公式为:
$$
\sum_{i=1}^n i*i=\frac{n*(n+1)*(2n+1)}{6}
$$
不难推导出最后答案的公式为:
$$
{n*(n+1)*(4n-1)*337}(mod 1e9+7)
$$
C++ 代码
#include<bits/stdc++.h>
#define int long long
const int mod=1e9+7;
int qmi(int a,int b){
int res=1;
a%=mod;
if(a==0)return b==0?1:0;
while(b){
if(b&1)res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
void solve()
{
int n;
std::cin>>n;
std::cout<<(4*n-1)*(n+1)%mod*n%mod*qmi(6,mod-2)%mod*2022%mod<<"\n";
}
signed main()
{
int _=1;
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin>>_;
while(_--)
{
solve();
}
}
C题
题目描述
给定一个数组a,找出有多少个连续子序列的异或和有偶数个因子。
样例
input:
4
3
3 1 2
5
4 2 1 5 3
4
4 4 4 4
7
5 7 3 7 1 7 3
output:
4
11
0
20
算法
首先如果一个数是平方数,那它的因子数量一定是奇数个,因为因子都是成对出现的唯独平方根不是。
所以找出有多少个区间的异或和是平方数即可。
因此可以通过哈希和前缀异或和来解决。
大致就是枚举 平方数k,令a为当前迭代到的异或和mp为哈希表表示前面出现这个数字多少次。
a^b=k,则b=a^k。
即mp[a^k]就是有区间为a时,异或和为k的数量。
枚举k的范围为 k*k<=2*n(乘2是将位数扩大一个,防止溢出)
C++ 代码
#include<bits/stdc++.h>
#define int long long
int in[210000];
int mp[2100000];
void solve()
{
int n;
std::cin>>n;
for(int i=1; i<=n; i++)
std::cin>>in[i],in[i]^=in[i-1];
for(int i=1; i<=2*n;i++)
mp[i]=0;
// mp.clear();
int ans=n*(n+1)/2;
mp[0]=1;
for(int i=1; i<=n; i++)
{
for(int j=0; j*j<=n*2; j++)
{
int k=j*j;
ans-=mp[in[i]^k];
}
mp[in[i]]++;
}
std::cout<<ans<<"\n";
}
signed main()
{
int _=1;
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin>>_;
while(_--)
{
solve();
}
}
D题
题目描述
给定一个矩阵,让找出最大的L,使得在矩阵中存在L*L的一个子矩阵,且子矩阵里面的每个元素至少为L。
样例
input:
4
2 2
2 3
4 5
1 3
1 2 3
2 3
4 4 3
2 1 4
5 6
1 9 4 6 5 8
10 9 5 8 11 6
24 42 32 8 11 1
23 1 9 69 13 3
13 22 60 12 14 17
output:
2
1
1
3
算法
典型的二分答案,不过要注意矩阵的范围是n<=m且n*m<=1e6,则整张图要用稀疏表存。
思路为二分答案L的值,每一次check函数要走以下流程:
1.在in(存图的数组)中找出每个元素开始,向下L个元素中的最小值为多少存入mm。
2.在mm数组中找出每个元素开始向右L个的元素的最小值为多少,来更新mm的值。
此时mm的数组每个mm[i][j]元素为以i j为右上角边长为L的正方形矩阵中最小值为多少。
3.最后如果存在某个值 大于check的L那就返回true否则返回false。
C++ 代码
#include<bits/stdc++.h>
#define int long long
const int mod=1e9+7;
int n,m;
std::vector<int>in[1100],mm[1100];
bool check(int ff)
{
for(int i=1; i<=m; i++)
{
std::deque<int>q;
for(int j=1; j<=ff; j++)
{
while(q.size()&&in[j][i]<=in[q.back()][i])q.pop_back();
q.push_back(j);
}
mm[1][i]=in[q.front()][i];
for(int j=2; j<=n-ff+1; j++)
{
while(q.size()&&q.front()<j)q.pop_front();
while(q.size()&&in[j+ff-1][i]<=in[q.back()][i])q.pop_back();
q.push_back(j+ff-1);
mm[j][i]=in[q.front()][i];
}
}
for(int i=1; i<=n-ff+1; i++)
{
std::deque<int>q;
for(int j=1; j<=ff; j++)
{
while(q.size()&&mm[i][j]<=mm[i][q.back()])q.pop_back();
q.push_back(j);
}
mm[i][1]=mm[i][q.front()];
for(int j=2; j<=m-ff+1; j++)
{
while(q.size()&&q.front()<j)q.pop_front();
while(q.size()&&mm[i][j+ff-1]<=mm[i][q.back()])q.pop_back();
q.push_back(j+ff-1);
mm[i][j]=mm[i][q.front()];
}
}
for(int i=1; i<=n-ff+1; i++)
for(int j=1; j<=m-ff+1; j++)
if(mm[i][j]>=ff)return true;
return false;
}
void solve()
{
std::cin>>n>>m;
for(int i=1; i<=n; i++)
{ in[i].clear();
mm[i].clear();
mm[i].push_back(0);
in[i].push_back(0);
int a;
for(int j=1; j<=m; j++)
{
std::cin>>a;
mm[i].push_back(0);
in[i].push_back(a);
}
}
int l=1,r=std::min(n,m);
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
std::cout<<l<<"\n";
}
signed main()
{
int _=1;
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin>>_;
while(_--)
{
solve();
}
}
所以呢就不快乐。