站外模拟赛题(矩阵操作,异或)求助(悬关)
  • 板块学术版
  • 楼主3wykx
  • 当前回复13
  • 已保存回复13
  • 发布时间2023/10/3 21:29
  • 上次更新2023/11/2 15:59:55
查看原帖
站外模拟赛题(矩阵操作,异或)求助(悬关)
499140
3wykx楼主2023/10/3 21:29

前言(废话):CSP-S模拟赛,赛场上想了个解法没有证明,直接7分,还没暴力分高,感觉是道简单题,但不会。应该是学多了糊了

题目描述: 考虑一个n*n的矩阵A,所有初始元素全为0。

执行q次如下操作:给定四个整数r,c,l,s,对每个满足x∈[r,r+l],y∈[c,x-r+c]的元素(x,y),权值增加s。也就是,给一个左上顶点为(r,c)、直角边长为l的下三角区域加上s。

输出最终矩阵的元素异或和。

数据范围:n≤10³,q≤3*10⁵


样例输入:

10 4

1 1 10 1

5 5 4 4

1 9 4 3

3 3 5 2

样例输出:0

结尾的废话(本人思考历程):首先,这个鬼题暴力能偷57分令人很不爽。 首先,排除暴力,直接炸。其次,该题题面简单,于是没有考虑使用复杂数据结构维护,于是考虑思维题。觉得可以分开维护每个下三角的异或,最后合并处理,事实证明会写挂。最后实在想不到,直接放弃去弄t2t3了。

2023/10/3 21:29
加载中...