首页 > 代码库 > HDU 5084 HeHe --找规律
HDU 5084 HeHe --找规律
题意： 给出矩阵M，求M*M矩阵的r行c列的数，每个查询跟前一个查询的结果有关。
解法： 观察该矩阵得知，令ans = M*M，则 ans[x][y] = (n-1-x行的每个值)*(n-1+y列的每个值)。直接对每个查询做n次累加(n*m=10^8的复杂度)竟然可以水过。
官方题解给的是n^2的算法，维护一个前缀和，即sum[i][j] 表示 i+j不变的所有sum[i][j]之和。
因为
ans[x][y]就是 a[y]*a[2*n-x] + .... + a[y+n-1]*a[n-x+1]，乘的这部分a[i]*a[j]，i+j是定值，求一个前缀和后O(1)求ans[x][y]，
ans[x][y] = sum[2*n-x-2][y]-sum[n-2-x][n+y]; 这点我还不太理解。
先贴O(n*m)的代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define lll __int64using namespace std;#define N 100007int t[2010];int main(){ int n,m,i,j; int x,y,ans; while(scanf("%d",&n)!=EOF) { for(i=0;i<=2*n-2;i++) scanf("%d",&t[i]); scanf("%d",&m); lll sum = 0; ans = 0; for(i=0;i<m;i++) { scanf("%d%d",&x,&y); x = (x+ans)%n; y = (y+ans)%n; ans = 0; for(j=0;j<n;j++) ans += t[n-1-x+j]*t[n-1+y-j]; sum += ans; } cout<<sum<<endl; } return 0;}
再附上meetzyc的官方做法代码：
#include <iostream> #include <cstring> #include <stdio.h> #include <string> #include <math.h> using namespace std; int x,y,i,j,n,m,a[3000],e[2010][2010]; int main() { while(scanf("%d",&n)!=EOF) { for(i=0;i<2*n-1;i++) scanf("%d",&a[i]); memset(e,0,sizeof(e)); for(i=0;i<=2*n-1;i++) { e[i][2*n-2]=a[i]*a[2*n-2]; for(j=2*n-1;j>=0;j--) e[i][j]=e[i-1][j+1]+a[i]*a[j]; } scanf("%d",&m); __int64 sum=0; int ans=0; for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); x = (x+ans)%n; y = (y+ans)%n; ans = e[2*n-x-2][y]-e[n-2-x][n+y]; sum += ans; } printf("%I64d\n",sum); } return 0; }
HDU 5084 HeHe --找规律
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。