Codeforces Round #841 (Div. 2)

2023-05-16

B Kill Demodogs

分析

显然要选择 $(i,i)$ 和 $(i,i+1)$ 两斜线的元素相加

所以答案可以表示为： $\sum\limits_{i=1}^n i^2 + \sum\limits_{i=1}^{n-1} (i+1)i$

即： $2\sum\limits_{i=1}^{n-1} i^2+n^2+\sum\limits_{i=1}^{n-1}i$

根据公式 $\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}$

得答案为 $\frac{(n-1)n(2n-1)}{3}+n^2+\frac{n(n-1)}{2}$

但答案不能直接得这个。因为n的范围为1e9，而ull的范围为1e20，答案的第一项中 $n^3$ 项最大为1e27，会导致溢出，因此要对答案式子进行变换。

能直接将式子中的每个部分直接逐个放到答案ans上吗？不行

因为 $(n-1)n(2n-1)$ 能被3整除，但分开后不一定能被3整除，进而导致在相乘->取余->相乘的过程中产生误差。

所以要将原式分解为整数相乘相加的形式。

经过一系列因式分解可得式子 $\frac{n(2n^2+1)}{3}+\frac{n(n-1)}{2}$

因为原式第一项的分子 $(n-1)n(2n-1)$ 能被3整除，而变换后的式子第一项分子相当于减了一个 $3n^2$ (3的倍数)，还能被3整除。

所以，如果n不能被3整除，则 $n(2n^2+1)$ 的因子3必然在 $2n^2+1$ 中存在；否则因子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^2$ (k=0,1,2...)。长度为n的子区间段总数为 $\frac{n(n+1)}{2}$ ，所以总数减去不符合要求的区间段个数就是答案ans。

小知识：异或前缀和。若 $sum5=a_{1}\oplus a_{2}\oplus a_{3}\oplus a_{4}\oplus a_{5}$ ， $sum2=a_{1}\oplus a_{2}$ ，则 $a_{3}\oplus a_{4}\oplus a_{5}=sum5\oplus sum2$

在算异或前缀和的过程中处理答案。步骤：①算出当前位置的异或前缀和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，然后令开一个数组存二维前缀和，将判断范围由“单个方块”变为“一个区块”。好处是，原来需要对一个区块的每个元素都做一次判断，单次判断的复杂度为 $O(mid^2)$ ，而现在有了橙色的预处理步骤，对一个区块可以直接通过一步简单运算（二维前缀和的运算）判断该区块是否符合要求，复杂度为 $O(1)$ 。预处理结束后暴力判断整个n*m区域的每个mid*mid的区块。复杂度 $O(n*m*log(min(n,m)))$ ，最大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(使用前将#替换为@)