少写了一个循环，用了cmach库的max函数，少开了几个数组，终于100了；
F: 统计子矩阵
本题总分：15
问题描述
给定一个N×M 的矩阵 A, 请你统计有多少个子矩阵 (最小 1×1, 最大 N×M) 满足子矩阵中所有数的和不超过给定的整数 K?
输入格式
第一行包含三个整数 N, M,和 K.
之后 N 行每行包含 M 个整数, 代表矩阵 A.
输出格式
一个整数代表答案。
样例输入
3 4 10 1 2 3 4 5 6 7 8 9 10 11 12
样例输出
19
样例说明
满足条件的子矩阵一共有 19 , 包含:
大小为 1×1 的有 10 个。
大小为 1×2 的有 3 个。
大小为 1×3 的有 2 个。
大小为 1×4 的有 1 个。
大小为 2×1 的有 3 个。
评测用例规模与约定
对于 30% 的数据, N,M≤20.
对于 70% 的数据, N,M≤100.
对于 100% 的数据, 1≤N,M≤500;0≤Aij≤1000;1≤K≤250000000.
运行限制
最大运行时间：1s
最大运行内存: 256M
本题为二维前缀和问题，首先纯暴力要6个for循环，肯定超时，用动态规划dp，将其二维矩阵和记录下来（以（1,1）为左上点的矩阵）。可以减少2个for循环，以空间换时间；
#include <iostream> using namespace std; int n,m,k; int dp[505][505]; int zanshi,ans; int main() { cin>>n>>m>>k; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>zanshi; dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+zanshi; //记录前二维矩阵和 } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ for(int x=i;x<=n;x++){ for(int y=j;y<=m;y++){ if(dp[x][y]-dp[x][j-1]-dp[i-1][y]+dp[i-1][j-1]<=k){ //求包括中间的矩阵和 ans++; } } } } } cout<<ans; return 0; }
嗯，怎么说，四个for循环时间复杂度还是高了点。再怎么优化呢？你想如果一个小的矩阵大于k的话，那么包含该矩阵大矩阵一定大于k，还是有优化空间的，优化一下。
#include <iostream> using namespace std; int n,m,k; int dp[505][505]; long long zanshi,ans; //ans要long long， int main() { cin>>n>>m>>k; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>zanshi; dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+zanshi; } } for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ for(int l=1,r=1;r<=m;r++){ while(l<=r&&(dp[j][r]-dp[j][l-1]-dp[i-1][r]+dp[i-1][l-1]>k)){ l++; } if(r>=l){ ans+=r-l+1; } } } } cout<<ans; return 0; }
终于100了，重点说一下以下代码，某个大佬写的，看了好久才看懂。
for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ for(int l=1,r=1;r<=m;r++){ while(l<=r&&(dp[j][r]-dp[j][l-1]-dp[i-1][r]+dp[i-1][l-1]>k)){ l++; } if(r>=l){ ans+=r-l+1; } } } }
首先前两层for循环，可以把i，j（横）看做两个木棍，初始化都是1，然后j向下运动，到达底端后，i下降到2，j返回到2，以此类推，最后i，j都到达n结束；再说第三层for循环。初始化l，r也是
看做两个木棍（竖），初始化都为1，也就是矩阵最左边。当r（右棍）>=l（左棍）时，判断四个木棍围成的矩阵是否符合小于k，大于k时左棍向右移动，矩阵变小。直到小于k，小于k时将可行方案加到总方案数种。
最最重要的是ans+=r-l+1；这行代码，我们只考虑列，因为行还在移动。如果r棍不动，那么l棍向r棍靠近，直到l=r。比如r=3，l=1，那么有三个单列矩阵，两个双列矩阵，一个三列矩阵，一共六个解。那么你可以算算，l第一次移动时ans=3，直到l=r，ans=6，刚刚好。但是当r向右移动时就比较复杂了，有两个大矩阵重合，此时ans的值应该等于两个大矩阵解的和减去中间重合矩阵（重合最大的矩阵），比如两个大矩阵边长分别是5和6，中间重合最大矩阵为3，此时ans解为5+4+3+2+1+6+5+4+3+2+1-3-2-1=6+5+4+3+2+1+5+4；你会发现正好是移动后矩阵解加上之前移动矩阵前加上的解。
G: 积木画
本题总分：15
小明最近迷上了积木画, 有这么两种类型的积木, 分别为 II 型（大小为 2 个单位面积) 和 LL 型 (大小为 3 个单位面积):
同时, 小明有一块面积大小为 2×N 的画布, 画布由 2×N个 1×1 区域构 成。小明需要用以上两种积木将画布拼满, 他想知道总共有多少种不同的方式? 积木可以任意旋转, 且画布的方向固定。
输入格式
输入一个整数 NN，表示画布大小。
输出格式
输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值。
样例输入
3
样例输出
5
样例说明
五种情况如下图所示，颜色只是为了标识不同的积木：
评测用例规模与约定
对于所有测试用例，1≤N≤10000000.
| 语言 | 最大运行时间 | 最大运行内存 |
| C++ | 2s | 256M |
| C | 2s | 256M |
| Java | 5s | 256M |
| Python3 | 10s | 256M |
动态规划题目，难点在于寻找递推公式。
不过里面有个小错误，不知道大家发现没有
这个结论正确，不过过程有个错误，
应该还要考虑没有剩余时的特殊情况。
#define m 1000000007 int n; long long dp[10000005]; int main() { cin>>n; dp[0]=1; dp[1]=1; dp[2]=2; dp[3]=5; for(int i=4;i<=n;i++){ for(int j=0;j<=i-1;j++){ dp[i]+=2*dp[j]; if(j==i-1 || j==i-2){ dp[i]=dp[i]-dp[j]; } } } cout<<(dp[n])%m; return 0; }
答案正确，但是存在超时和爆调的问题，通过率为0，爆 栈后答案就不对了。
#include <iostream> using namespace std; #define m 1000000007 int n; long long dp[10000005]; int main() { cin>>n; dp[0]=1; dp[1]=1; dp[2]=2; dp[3]=5; for(int i=4;i<=n;i++){ dp[i]=(dp[i-3]%m+2*dp[i-1]%m)%m; } cout<<(dp[n])%m; return 0; }
这个时间复杂度低，重要的是没有减法，可以任意取模，不存在爆栈问题；
H: 扫雷
本题总分：20
问题描述
小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下, 在一个二维平面上放置着 n 个炸雷, 第 i 个炸雷 (xi,yi,ri) 表示在坐标 (xi,yi) 处存在一个炸雷, 它的爆炸范围是以半径为 r的一个圆。
为了顺利通过这片土地, 需要玩家进行排雷。玩家可以发射 m 个排雷火 箭, 小明已经规划好了每个排雷火箭的发射方向, 第 j 个排雷火箭(xj,yj,rj) 表 示这个排雷火箭将会在 (xj,yj) 处爆炸, 它的爆炸范围是以半径为 r 的一个圆, 在其爆炸范围内的炸雷会被引爆。同时, 当炸雷被引爆时, 在其爆炸范围内的 炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷?
你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个 炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。
输入格式
输入的第一行包含两个整数 n 、m
接下来的 n行, 每行三个整数 xi,yi,ri, 表示一个炸雷的信息。
再接下来的 m 行, 每行三个整数 xj,yj,rj, 表示一个排雷火箭的信息。
输出格式
输出一个整数表示答案。
样例输入
2 1 2 2 4 4 4 2 0 0 5
样例输出
2
样例说明
示例图如下，排雷火箭 1 覆盖了炸雷 1，所以炸雷 1 被排除；炸雷 1 又覆盖了炸雷 2，所以炸雷 2 也被排除。
评测用例规模与约定
最大运行时间：1s
最大运行内存: 256M】
本题是我采用dfs算法，递归遍历。先遍历每一个火箭，然后搜寻每个炸弹，符合条件的炸弹进入dfs引爆；
#include <iostream> #include <cmath> using namespace std; int n,m; int ans; struct zhadan{ int x,y; int r; zhadan(){} zhadan(int xx,int yy,int rr){ x=xx; y=yy; r=rr; } }; float dd(zhadan a,zhadan b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } zhadan a[50005]; zhadan b[50005]; bool c[50005]; void dfs(zhadan v){ for(int i=0;i<n;i++){ if(dd(a[i],v)<=v.r && !c[i]){ c[i]=1; ans++; dfs(a[i]); } } } int main(){ cin>>n>>m; for(int i=0;i<n;i++){ cin>>a[i].x>>a[i].y>>a[i].r; } for(int i=0;i<m;i++){ cin>>b[i].x>>b[i].y>>b[i].r; } for(int i=0;i<m;i++){ dfs(b[i]); } cout<<ans; return 0; }
40通过率，再优化一下，我发现炸弹个数很多，但是爆照范围很小，我们尝试遍历边长为2r的正方形，而不是炸弹个数。遍历整个图形用bfs更好。
#include <iostream> #include <map> #include <set> #include <queue> using namespace std; const int N=50005; int ans; int n,m; struct node { int x; int y; int r; node(int xx,int yy,int rr) { x=xx; y=yy; r=rr; } }; int get_len(int x,int y,int i,int j) { return (x-i)*(x-i)+(y-j)*(y-j); } map<pair<int,int>,int> mp; set<pair<int,int>> s; queue<node> q; int main() { cin>>n>>m; for(int i=0;i<n;i++) { int x,y,r; cin>>x>>y>>r; int tmp=mp[{x,y}]+100; mp[{x,y}]=max(tmp,tmp/100*100+r); } for(int i=0;i<m;i++) { int x,y,r; cin>>x>>y>>r; q.push(node(x,y,r)); } int ans=0; while(q.size()) { int xx=q.front().x; int yy=q.front().y; int rr=q.front().r; q.pop(); for(int i=xx-rr;i<=xx+rr;i++) { for(int j=yy-rr;j<=yy+rr;j++) { pair<int,int> p(i,j); if(s.count(p)) { continue; } if(!mp.count(p)) { continue; } if(get_len(xx,yy,i,j)>rr*rr) { continue; } s.insert(p); q.push(node(i,j,mp[p]%100)); ans=ans+mp[p]/100; } } } cout<<ans; }
