B Kill Demodogs
分析
显然要选择
和
两斜线的元素相加
所以答案可以表示为:![\sum\limits_{i=1}^n i^2 + \sum\limits_{i=1}^{n-1} (i+1)i](https://latex.codecogs.com/gif.latex?%5Csum%5Climits_%7Bi%3D1%7D%5En%20i%5E2%20+%20%5Csum%5Climits_%7Bi%3D1%7D%5E%7Bn-1%7D%20%28i+1%29i)
即:![2\sum\limits_{i=1}^{n-1} i^2+n^2+\sum\limits_{i=1}^{n-1}i](https://latex.codecogs.com/gif.latex?2%5Csum%5Climits_%7Bi%3D1%7D%5E%7Bn-1%7D%20i%5E2+n%5E2+%5Csum%5Climits_%7Bi%3D1%7D%5E%7Bn-1%7Di)
根据公式![\sum\limits_{k=1}^n k^2=1^2+2^2+3^2+...+n^2=\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}=\frac{n(n+1)(2n+1)}{6}](https://latex.codecogs.com/gif.latex?%5Csum%5Climits_%7Bk%3D1%7D%5En%20k%5E2%3D1%5E2+2%5E2+3%5E2+...+n%5E2%3D%5Cfrac%7Bn%5E3%7D%7B3%7D+%5Cfrac%7Bn%5E2%7D%7B2%7D+%5Cfrac%7Bn%7D%7B6%7D%3D%5Cfrac%7Bn%28n+1%29%282n+1%29%7D%7B6%7D)
得答案为![\frac{(n-1)n(2n-1)}{3}+n^2+\frac{n(n-1)}{2}](https://latex.codecogs.com/gif.latex?%5Cfrac%7B%28n-1%29n%282n-1%29%7D%7B3%7D+n%5E2+%5Cfrac%7Bn%28n-1%29%7D%7B2%7D)
但答案不能直接得这个。因为n的范围为1e9,而ull的范围为1e20,答案的第一项中
项最大为1e27,会导致溢出,因此要对答案式子进行变换。
能直接将式子中的每个部分直接逐个放到答案ans上吗?不行
因为
能被3整除,但分开后不一定能被3整除,进而导致在相乘->取余->相乘的过程中产生误差。
所以要将原式分解为整数相乘相加的形式。
经过一系列因式分解可得式子![\frac{n(2n^2+1)}{3}+\frac{n(n-1)}{2}](https://latex.codecogs.com/gif.latex?%5Cfrac%7Bn%282n%5E2+1%29%7D%7B3%7D+%5Cfrac%7Bn%28n-1%29%7D%7B2%7D)
因为原式第一项的分子
能被3整除,而变换后的式子第一项分子相当于减了一个
(3的倍数),还能被3整除。
所以,如果n不能被3整除,则
的因子3必然在
中存在;否则因子3一定在n中存在。
至此,可以使用long long进行程序实现。
代码实现
#include<bits/stdc++.h>
#define ll long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
void solve(){
ll n;
ll ans=0;
cin>>n;
if(n%3==0){
ans=2*n*n+1;
ans=ans%1000000007;
ans*=n/3;
ans=ans%1000000007;
}
else{
ans=(2*n*n+1)/3;
ans=ans%1000000007;
ans*=n;
ans=ans%1000000007;
}
ans+=(n-1)*n/2;
ans=ans%1000000007;
ans=ans*2022;
ans=ans%1000000007;
cout<<ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
C. Even Subarrays
分析
容易看出,不符合要求的区间段异或结果为
(k=0,1,2...)。长度为n的子区间段总数为
,所以总数减去不符合要求的区间段个数就是答案ans。
小知识:异或前缀和。若
,
,则![a_{3}\oplus a_{4}\oplus a_{5}=sum5\oplus sum2](https://latex.codecogs.com/gif.latex?a_%7B3%7D%5Coplus%20a_%7B4%7D%5Coplus%20a_%7B5%7D%3Dsum5%5Coplus%20sum2)
在算异或前缀和的过程中处理答案。步骤:①算出当前位置的异或前缀和x;②暴力查找x分别与所有平方数的异或结果是否出现过(num=cut[x^平方数]),出现次数为numi,ans-=numi;③更新cnt数组,cnt[x]++;
代码实现
#include<bits/stdc++.h>
#define ll long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int cnt[1000006];
int sum[1000006];
vector<int>sqr;
void solve(){
ll n, ans=0;
memset(cnt,0,sizeof(cnt));
cnt[0]++;
cin>>n;
ans=n*(n+1)/2;
rep(i,1,n){
cin>>sum[i];
sum[i] ^= sum[i-1];
for(auto x : sqr){
ans -= cnt[sum[i]^x];
}
cnt[sum[i]]++;
}
cout<<ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for(int i=0;i*i<=400005;i++){
sqr.push_back(i*i);
}
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
D. Valiant's New Map
分析
关键字:二分答案,二维前缀和处理降低check复杂度。
要敢于大胆地断定可以二分答案。(其实看到n*m<=1e6时就该有所反应。1e6乘上log级的二分很难超过1e9的极限)
然后是确定边界,以及怎么check。
边界:l=1,r=mid(n,m)。可以看出r最大为1e3,很小。
check:对于每个mid,先将原数组a[i][j]中令符合条件的元素等于1,不符合条件的元素等于0,然后令开一个数组存二维前缀和,将判断范围由“单个方块”变为“一个区块”。好处是,原来需要对一个区块的每个元素都做一次判断,单次判断的复杂度为
,而现在有了橙色的预处理步骤,对一个区块可以直接通过一步简单运算(二维前缀和的运算)判断该区块是否符合要求,复杂度为
。预处理结束后暴力判断整个n*m区域的每个mid*mid的区块。复杂度
,最大1e7。
PS:
①代码中的注释为一种 二分不容易错 的写法,值得注意。
②二维vector的定义方法,值得记忆。
代码实现
#include<bits/stdc++.h>
#define ll long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define V vector<int>
#define VV vector<V>
#define pii pair<int,int>
#define Vpii vector<pii>
using namespace std;
int n,m;
bool check(int mid, VV a){
VV sum(n+1, V(m+1));
rep(i,1,n){
rep(j,1,m){
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];
}
}
rep(i,1,n-mid+1){
rep(j,1,m-mid+1){
if(sum[i+mid-1][j+mid-1] - sum[i+mid-1][j-1] - sum[i-1][j+mid-1] + sum[i-1][j-1] == mid*mid)
return true;
}
}
return false;
}
void solve(){
int l=1,r,mid;
cin>>n>>m;
r=min(n,m);
VV a(n+1,V(m+1));
rep(i,1,n){
rep(j,1,m){
cin>>a[i][j];
}
}
while(l<r){
mid=(l+r+1)>>1;
if(check(mid, a)) l=mid;
else r=mid-1;
}
/*
int ans;
while(l<=r){
mid=(l+r)>>1;
if(check(mid, a)){
ans=mid;
l=mid+1;
}
else r=mid-1;
}
cout<<ans<<"\n";
*/
cout<<r<<"\n";
}
int main(){
fastio();
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)