题解 a
2021/8/14 6:35:46
本文主要是介绍题解 a,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门
和入阵曲那题很像
这里 \(n\) 很小,可以直接 \(n^2\) 压成一维考虑
然后就是对每个 \(j\) 查询 \([j-r, j-l]\) 中数的个数
这里我是用树状数组求的,带个log,被卡成了80pts
发现随着 \(j\) 单增, \(j-r, j-l\) 单调不减
所以可以双指针
题目里这些奇奇怪怪的单调性如何发现啊……
Code:
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define N 100010 #define ll long long #define reg register int //#define int long long inline int read() { int ans=0, f=1; char c=getchar(); while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();} while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();} return ans*f; } int n, m, L, R; int mat[35][50010], sum[35][50010]; char tem[50010]; namespace force{ ll ans; void solve() { for (int i=1; i<=n; ++i) { for (int j=1; j<=m; ++j) sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mat[i][j]; } for (int i=1; i<=n; ++i) { for (int j=1; j<=m; ++j) { for (int k=1; k<=i; ++k) { for (int h=1; h<=j; ++h) { int t=sum[i][j]-sum[k-1][j]-sum[i][h-1]+sum[k-1][h-1]; if (t>=L && t<=R) ++ans; } } } } printf("%lld\n", ans); exit(0); } } namespace task1{ ll ans; int a[1500010], lim; inline void upd(int i) {for (; i<=lim; i+=i&-i) ++a[i];} inline int query(int i) {int ans=0; for (; i; i-=i&-i) ans+=a[i]; return ans;} void solve() { lim=n*m+5; for (reg j=1; j<=m; ++j) for (reg i=1; i<=n; ++i) sum[i][j] = sum[i-1][j]+mat[i][j]; for (reg l=1,sum2; l<=n; ++l) { for (reg i=l; i<=n; ++i) { //cout<<i<<": "<<l<<endl; memset(a, 0, sizeof(int)*lim); sum2=1; upd(1); for (reg j=1; j<=m; ++j) { sum2 += sum[i][j]-sum[i-l][j]; if (sum2>L) ans+=query(sum2-L)-(sum2-R>1?query(max(sum2-R-1, 0)):0); upd(sum2); } } } printf("%lld\n", ans); exit(0); } } namespace task{ ll ans; int cnt[1500010], cnt2[1500010]; void solve() { for (reg j=1; j<=m; ++j) for (reg i=1; i<=n; ++i) sum[i][j] = sum[i-1][j]+mat[i][j]; for (reg l=1,pos1,pos2,sum2; l<=n; ++l) { for (reg i=l; i<=n; ++i) { sum2=1; pos1=pos2=0; cnt[1]=1; for (reg j=1; j<=m; ++j) { sum2 += sum[i][j]-sum[i-l][j]; while (pos1<sum2-R-1) {cnt[pos1]=cnt2[pos1]=0; ++pos1;} while (pos2<sum2-L) {++pos2; cnt2[pos2]=cnt2[pos2-1]+cnt[pos2];} if (sum2>L) ans+=cnt2[pos2]-cnt2[pos1]; ++cnt[sum2]; if (pos2==sum2) ++cnt2[pos2]; } for (reg j=pos1; j<=sum2; ++j) cnt[j]=cnt2[j]=0; } } printf("%lld\n", ans); exit(0); } } signed main() { n=read(); m=read(); for (reg i=1; i<=n; ++i) { scanf("%s", tem+1); for (reg j=1; j<=m; ++j) mat[i][j]=tem[j]-'0'; } L=read(); R=read(); task::solve(); return 0; }
这篇关于题解 a的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)