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
时间超限了。
我猜是因为以数组为形参会把数组的数都遍历一遍,就和暴力的复杂度一样了
上一篇:【BF算法】