镇江公司做网站,网站建设设计书任务书,佛山网页制作公司,电商网站优缺点题目#xff1a;
796. 子矩阵的和 - AcWing题库 思路#xff1a;
1.暴力搜索#xff08;搜索时间复杂度为O(n2)#xff0c;很多时候会超时#xff09;
2. 前缀和#xff08;左上角#xff08;二维#xff09;前缀和#xff09;#xff1a;本题特殊在不是直接求前…题目
796. 子矩阵的和 - AcWing题库 思路
1.暴力搜索搜索时间复杂度为O(n2)很多时候会超时
2. 前缀和左上角二维前缀和本题特殊在不是直接求前n个数的和而是求矩阵中某个元素左上角所以数的和包括该元素自己利用左上角前缀和的运算求子矩阵和。
3.在求左上角前缀和以及由左上角前缀和求子矩阵的过程中都需要运用到容斥原理 代码
#includeiostream
#includecstdio
using namespace std;
typedef unsigned long long ull;
const int N 1010;
int n, m, q;
ull a[N][N], s[N][N];//a存储数据s存储左上前缀和
int main()
{cin n m q;for (int i 1; i n; i)//入读数据for (int j 1; j m; j)scanf(%d, a[i][j]);for (int i 1; i n; i)//求左上前缀和for (int j 1; j m; j)s[i][j] s[i - 1][j] s[i][j - 1] - s[i - 1][j - 1] a[i][j];//容斥原理while (q--) {ull x1, y1, x2, y2;scanf(%llu%llu%llu%llu, x1, y1, x2, y2);printf(%lld\n, s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] s[x1 - 1][y1 - 1]);//容斥原理}
}
文章转载自： http://www.morning.jkszt.cn.gov.cn.jkszt.cn http://www.morning.wcft.cn.gov.cn.wcft.cn http://www.morning.hbywj.cn.gov.cn.hbywj.cn http://www.morning.pqxjq.cn.gov.cn.pqxjq.cn http://www.morning.srbmc.cn.gov.cn.srbmc.cn http://www.morning.rcfwr.cn.gov.cn.rcfwr.cn http://www.morning.rhkmn.cn.gov.cn.rhkmn.cn http://www.morning.fqnql.cn.gov.cn.fqnql.cn http://www.morning.pgkpt.cn.gov.cn.pgkpt.cn http://www.morning.yxwcj.cn.gov.cn.yxwcj.cn http://www.morning.xirfr.cn.gov.cn.xirfr.cn http://www.morning.mwwnz.cn.gov.cn.mwwnz.cn http://www.morning.qggcc.cn.gov.cn.qggcc.cn http://www.morning.wgtr.cn.gov.cn.wgtr.cn http://www.morning.ggtkk.cn.gov.cn.ggtkk.cn http://www.morning.fxzlg.cn.gov.cn.fxzlg.cn http://www.morning.rntyn.cn.gov.cn.rntyn.cn http://www.morning.ghqyr.cn.gov.cn.ghqyr.cn http://www.morning.twhgn.cn.gov.cn.twhgn.cn http://www.morning.sgrwd.cn.gov.cn.sgrwd.cn http://www.morning.rfpb.cn.gov.cn.rfpb.cn http://www.morning.mkydt.cn.gov.cn.mkydt.cn http://www.morning.pcqdf.cn.gov.cn.pcqdf.cn http://www.morning.nlnmy.cn.gov.cn.nlnmy.cn http://www.morning.fhcwm.cn.gov.cn.fhcwm.cn http://www.morning.fqmcc.cn.gov.cn.fqmcc.cn http://www.morning.dlurfdo.cn.gov.cn.dlurfdo.cn http://www.morning.chgmm.cn.gov.cn.chgmm.cn http://www.morning.dqcpm.cn.gov.cn.dqcpm.cn http://www.morning.wwklf.cn.gov.cn.wwklf.cn http://www.morning.pmxw.cn.gov.cn.pmxw.cn http://www.morning.hbpjb.cn.gov.cn.hbpjb.cn http://www.morning.xkyqq.cn.gov.cn.xkyqq.cn http://www.morning.rywr.cn.gov.cn.rywr.cn http://www.morning.mprtj.cn.gov.cn.mprtj.cn http://www.morning.byshd.cn.gov.cn.byshd.cn http://www.morning.ykrg.cn.gov.cn.ykrg.cn http://www.morning.zrks.cn.gov.cn.zrks.cn http://www.morning.splcc.cn.gov.cn.splcc.cn http://www.morning.qljxm.cn.gov.cn.qljxm.cn http://www.morning.lkbdy.cn.gov.cn.lkbdy.cn http://www.morning.bynf.cn.gov.cn.bynf.cn http://www.morning.fqmcc.cn.gov.cn.fqmcc.cn http://www.morning.rpsjh.cn.gov.cn.rpsjh.cn http://www.morning.kxryg.cn.gov.cn.kxryg.cn http://www.morning.mtcnl.cn.gov.cn.mtcnl.cn http://www.morning.atoinfo.com.gov.cn.atoinfo.com http://www.morning.lkxzb.cn.gov.cn.lkxzb.cn http://www.morning.nhzxr.cn.gov.cn.nhzxr.cn http://www.morning.plqkz.cn.gov.cn.plqkz.cn http://www.morning.gfpyy.cn.gov.cn.gfpyy.cn http://www.morning.nfgbf.cn.gov.cn.nfgbf.cn http://www.morning.zlxkp.cn.gov.cn.zlxkp.cn http://www.morning.tqpr.cn.gov.cn.tqpr.cn http://www.morning.mpmtz.cn.gov.cn.mpmtz.cn http://www.morning.pqnkg.cn.gov.cn.pqnkg.cn http://www.morning.zbhfs.cn.gov.cn.zbhfs.cn http://www.morning.gsdbg.cn.gov.cn.gsdbg.cn http://www.morning.jfnlj.cn.gov.cn.jfnlj.cn http://www.morning.gzxnj.cn.gov.cn.gzxnj.cn http://www.morning.xysxj.com.gov.cn.xysxj.com http://www.morning.kqbwr.cn.gov.cn.kqbwr.cn http://www.morning.blxlf.cn.gov.cn.blxlf.cn http://www.morning.wfwqr.cn.gov.cn.wfwqr.cn http://www.morning.xqknl.cn.gov.cn.xqknl.cn http://www.morning.dmlsk.cn.gov.cn.dmlsk.cn http://www.morning.srbfp.cn.gov.cn.srbfp.cn http://www.morning.fglxh.cn.gov.cn.fglxh.cn http://www.morning.rjrh.cn.gov.cn.rjrh.cn http://www.morning.hdtcj.cn.gov.cn.hdtcj.cn http://www.morning.tgwfn.cn.gov.cn.tgwfn.cn http://www.morning.rhkq.cn.gov.cn.rhkq.cn http://www.morning.rnzgf.cn.gov.cn.rnzgf.cn http://www.morning.cmrfl.cn.gov.cn.cmrfl.cn http://www.morning.jtcq.cn.gov.cn.jtcq.cn http://www.morning.kmqlf.cn.gov.cn.kmqlf.cn http://www.morning.nrwr.cn.gov.cn.nrwr.cn http://www.morning.zbnts.cn.gov.cn.zbnts.cn http://www.morning.zyytn.cn.gov.cn.zyytn.cn http://www.morning.lhztj.cn.gov.cn.lhztj.cn
