hdu 5084 前缀和预处理
2024-10-08 08:48:03
http://acm.hdu.edu.cn/showproblem.php?pid=5084
给出矩阵M,求M*M矩阵的r行c列的数,每个查询跟前一个查询的结果有关。
观察该矩阵得知,令ans = M*M,则 ans[x][y] = (n-1-x行的每个值)*(n-1+y列的每个值),即:
ans[x][y] = t[y] * t[2*n - 2 - x] +....+ t[y + n - 1]*t[n - 1 - x]
每一对的和为定值2*n-2-x-y,然后就是求每对i+j的前缀和(所有i+j值相同按顺序加起来)
#pragma comment(linker, "/STACK:36777216")
#pragma GCC optimize ("O2")
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define clr0(x) memset(x,0,sizeof(x))
#define eps 1e-9
const double pi = acos(-1.0);
typedef long long LL;
const int modo = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1005,maxm = 1e4 + 5;
int t[maxn<<1],ans[maxn<<1][maxn<<1],n,m; int main(){
int x,y,_n;
while(~RD(n)){
_n = n;
n = -2 + (n<<1);
clr0(ans);
for(int i = 0;i <= n;++i)
RD(t[i]);
for(int i = 0;i <= n;++i)
for(int j = 0;j <= n;++j)
ans[i][j] = t[i]*t[j]; for(int i = 1;i <= n;++i)
for(int j = 0;j < n;++j){
ans[i][j] += ans[i-1][j+1];
}
RD(m);
LL sum = 0;int res = 0;
while(m--){
RD2(x,y);
x = (x+res)%_n,y = (y+res)%_n;
int sx = _n - 1 + y,sy = _n - 1 - x;
res = ans[sx][sy];
if(sx - _n >= 0 && sy + _n <= n)
res -= ans[sx-_n][sy+_n];
sum += res;
// cout<<x<<','<<y<<endl;
// cout<<res<<endl;
}
printf("%I64d\n",sum);
}
return 0;
}
最新文章
- CRM 启用或禁用自定义代码执行
- 《SSM框架搭建》一.构建maven web项目
- linux系统下yum源的搭建
- UI学习笔记---第六天
- Intent的详细解析以及用法
- asp.net 发布后用IP访问正常,用机器名访问布局出错
- 八大排序方法汇总(选择排序,插入排序-简单插入排序、shell排序,交换排序-冒泡排序、快速排序、堆排序,归并排序,计数排序)
- 《C和指针》章节后编程练习解答参考——6.6
- ICE 介绍及实现
- Leetcode::JumpGame
- Spring总结_04_容器和bean
- 《Java从入门到放弃》JavaSE篇:程序结构
- Servlet的执行流程、生命周期
- 如何彻底解决MySQL更改默认字符集以及字符乱码问题!!!
- Azure按订阅,资源组,资源类型导出所有资源powershell命令
- appium框架之bootstrap
- 2018-软工机试-E-热河路(TLE只拿了90分,待思考)
- 自动化测试-20.selenium常用JS代码执行
- Python二维数组构造
- haproxy-1.7.7 源码安装