大佬教程收集整理的这篇文章主要介绍了NOIP 模拟十，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
首先谈本次考试的问题：
1>：算法拓展应用（本质认知） 2>：转化问题（问题本质分析）
之前题解中的反思过于注重对问题的探讨而忽略了问题的解决方法及应用拓展导致考场上只能抽象问题而不能解决问题
信息竞赛是一门理论与应用相结合的学问，故应兼重。对本人而言要多思考算法解决的类型问题及拓展应用领域
T1：入阵曲
首先抽象问题，问题本质上是说给定一个矩阵，其单位元均带权，求存在多少子矩阵满足子矩阵权值和被K整除
也就是说本题实际上是对范围信息的查询，那么对于范围信息的查询，我们通常考虑的是采取前缀和与差分，排序，倍增
的手段来对范围信息进行记录或预处理，从而优化算法复杂度（应该多考虑算法应用域而非仅关注抽象问题）。考虑通过
前缀和预处理后我们可以通过O(n^4)的效率枚举每个矩阵并以O(1)复杂度查询矩阵权值和。
然而我们发现以O(n^4)的效率无法通过本题，这也在提醒我们：存在一种方法能够优化枚举过程或非枚举手段，继续考虑优化。
（当问题规模复杂难以进行时，考虑归纳，即降低问题规模，试图类比推出原问题解决方案）此时考虑一维情况，枚举复杂度为O(n^2),
然而观察问题发现还有一个条件为使用，即我们并非要枚举每一个子空间计算权值和，而是要求存在多少子空间满足被K整除，考虑
从此入手去优化。当问题为一维时我们发现若只判断子区间被K整除，仅需考虑存在多少对前缀和满足在模K的意义下同余即可，
此时只需O(n)扫描前缀和并开一个桶来统计K同余类中各存在对前缀和即可
这样问题只需拓展到二维即可，同样的情况，只要满足二维前缀和关于K同余即可。此时类比一维，我们并不需完全枚举子矩阵坐标，
只需满足其处于同一前缀和下即可，这样就优化掉一维列的枚举。
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define I int 4 #define LL long long 5 #define C char 6 #define RE register 7 #define L inline 8 I n,m,mod,prefix[@H_801_75@405][@H_801_75@405],pos[@H_801_75@405],num[@H_801_75@1000005]; 9 LL res; 10 L I read(); 11 signed main(){ 12 n = read(); m = read(); mod = read(); 13 for(RE I i(@H_801_75@1);i <= n; ++ i) 14 for(RE I j(@H_801_75@1);j <= m; ++ j) 15 prefix[i][j] = (prefix[i][j - @H_801_75@1] + prefix[i - @H_801_75@1][j] + read() - prefix[i - @H_801_75@1][j - @H_801_75@1] + mod) % mod; 16 for(RE I i(@H_801_75@0);i < n; ++ i) 17 for(RE I j(i + @H_801_75@1);j <= n; ++ j){ 18 num[@H_801_75@0] = @H_801_75@1; 19 for(RE I k(@H_801_75@1);k <= m; ++ k) res += num[(pos[k] = prefix[j][k] - prefix[i][k] + mod) %= mod]++; 20 for(RE I k(@H_801_75@1);k <= m; ++ k) num[pos[k]] = @H_801_75@0; 21 } 22 printf("%lld",res); 23 } 24 L I read(){RE I x(@H_801_75@0);RE C z(getchar());while(!isdigit(z))z=getchar();while(isdigit(z))x=(x<<@H_801_75@3)+(x<<@H_801_75@1)+(z^@H_801_75@48),z=getchar();return x;} 25
反思对与问题算法应用的理解，多拓展思路，考虑各种算法可能的不同的用法
T2：将军令
考场试图写出神仙树形DP，然而果不其然WA，警示考场上考虑代码复杂度，合理分配时间，事实上必然存在极优做法
问题一个很重要的性质为边权为一，此时模拟过程发现满足贪心最优解，也就是说只需要从叶节点向上枚举，若当前节点未被覆盖
则在其k级祖先处安置，并由其k级祖先处更新未被覆盖的节点（dfs），预处理可以利用bfs倒序确定枚举顺序（考虑算法拓展应用）
时间复杂度O(kn)（考场上记得计算时间复杂度，不要思考不必要的优化，一可能并不存在，二可能增加代码复杂度并浪费时间）
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define I int 4 #define C char 5 #define RE register 6 #define V void 7 #define L inline 8 const I MAXN = 1e5 + @H_801_75@5; 9 I n,res,len,typ,tot,head[MAXN],h,t,q[MAXN],father[MAXN],f[MAXN]; 10 struct Lym{I to,nxt;}node[MAXN << @H_801_75@1]; 11 L I read(); L V store(I,I); V dfs(I); 12 signed main(){ 13 n = read(); len = read(); typ = read(); tot = @H_801_75@1; 14 for(RE I i(@H_801_75@1);i < n; ++ i) store(read(),read()); 15 h = @H_801_75@0; t = @H_801_75@1; q[++h] = @H_801_75@1; father[@H_801_75@1] = @H_801_75@1; 16 while(h <= t){ 17 I x = q[h++]; 18 for(RE I i(head[x]),y(node[i].to); i ;i = node[i].nxt,y = node[i].to) 19 if(!father[y]){ 20 father[y] = x; 21 q[++t] = y; 22 } 23 } 24 memset(f,-@H_801_75@1,sizeof(f)); 25 for(RE I i(n); i ; -- i) 26 if(f[q[i]] == -@H_801_75@1){ 27 res++; 28 I y = q[i]; 29 for(RE I j(len); j ; -- j) y = father[y]; 30 f[y] = len; 31 dfs(y); 32 } 33 printf("%d",res); 34 } 35 L I read(){RE I x(@H_801_75@0);RE C z(getchar());while(!isdigit(z))z=getchar();while(isdigit(z))x=(x<<@H_801_75@3)+(x<<@H_801_75@1)+(z^@H_801_75@48),z=getchar();return x;} 36 L V store(I x,I y){ 37 node[++tot].to = y; node[tot].nxt = head[x]; head[x] = tot; 38 node[++tot].to = x; node[tot].nxt = head[y]; head[y] = tot; 39 } 40 V dfs(I from){ 41 if(!f[from]) return ; 42 for(RE I i(head[from]),y(node[i].to); i ;i = node[i].nxt,y = node[i].to) 43 if(f[y] < f[from] - @H_801_75@1){ 44 f[y] = f[from] - @H_801_75@1; 45 dfs(y); 46 } 47 }
以上是大佬教程为你收集整理的NOIP 模拟十全部内容，希望文章能够帮你解决NOIP 模拟十所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
