Warning: session_start(): open(/tmp/sess_0343445aea5501260c6bd5d96c476daf, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/8/8fe637ac40e9dfa91f93fbcd08d065e4.captchaip failed

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:legal_string:jxm2001:other:错题集_1 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:other:错题集_1

错题集 1

1、Fake Maxpooling

题意

给定一个 $n\times m$ 矩阵,$a_{i,j}=\text{lcm}(i,j)$,设 $f(i,j)=\{\max a_{x,y}|i\le x\lt i+k,j\le y\lt j+k\}$,求

\begin{equation}\sum_{i=1}^{n-k+1}\sum_{j=1}^{m-k+1}f(i,j)\end{equation}

题解

记忆化搜索求 $\text{gcd}$,二维单调队列维护最大值,时间复杂度 $O(nm)$。

查看代码

查看代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cassert>
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
inline int read_int(){
	int t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline LL read_LL(){
	LL t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline char get_char(){
	char c=getchar();
	while(c==' '||c=='\n'||c=='\r')c=getchar();
	return c;
}
inline void write(LL x){
	register char c[21],len=0;
	if(!x)return putchar('0'),void();
	if(x<0)x=-x,putchar('-');
	while(x)c[++len]=x%10,x/=10;
	while(len)putchar(c[len--]+48);
}
inline void space(LL x){write(x),putchar(' ');}
inline void enter(LL x){write(x),putchar('\n');}
const int MAXN=5005;
int a[MAXN][MAXN],b[MAXN][MAXN],que[MAXN];
int main()
{
	int n=read_int(),m=read_int(),k=read_int(),u,v;
	_rep(i,1,n)
	_rep(j,1,m){
		if(!a[i][j]){
			for(int k=1;k*i<=n&&k*j<=m;k++)
			a[i*k][j*k]=i*j*k;
		}
	}
	_rep(i,1,n){
		int front=1,tail=0;
		_for(j,1,k){
			while(front<=tail&&a[i][que[front]]<=a[i][j])front++;
			que[++tail]=j;
		}
		_rep(j,k,m){
			while(front<=tail&&j-que[front]>=k)front++;
			while(front<=tail&&a[i][que[front]]<=a[i][j])front++;
			que[++tail]=j;
			b[i][j]=a[i][que[front]];
		}
	}
	LL sum=0;
	_rep(j,k,m){
		int front=1,tail=0;
		_for(i,1,k){
			while(front<=tail&&b[que[front]][j]<=b[i][j])front++;
			que[++tail]=i;
		}
		_rep(i,k,n){
			while(front<=tail&&i-que[front]>=k)front++;
			while(front<=tail&&b[que[front]][j]<=b[i][j])front++;
			que[++tail]=i;
			sum+=b[que[front]][j];
		}
	}
	enter(sum);
	return 0;
}
2020-2021/teams/legal_string/jxm2001/other/错题集_1.1594993929.txt.gz · 最后更改: 2020/07/17 21:52 由 jxm2001