noip38
2021/8/14 6:35:50
本文主要是介绍noip38,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
T1
有个朴素的暴力,枚举每一个子矩形,复杂度 \(O(n^{2}m^{2})\),观察数据范围,n很小,考虑枚举行,对于 \(m\) 用 \(two\;pointers\) 来维护。
先预处理出每一列的前缀和,然后枚举行,对于列,用个双指针,把 \([l,r]\) 这一段区间卡出来,答案每回累加合法的区间长度即可。
复杂度 \(O(n^{2}m)\)
Code
#include<cmath> #include<cstdio> #define MAX 50100 #define re register #define int long long namespace OMA { char ch[MAX]; int n,m,l,r,tot[MAX]; int ans,sum[33][MAX]; struct stream { template<typename type>inline stream &operator >>(type &s) { int w=1; s=0; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*=w,*this; } }cin; signed main() { //freopen("node.in","r",stdin); cin >> n >> m; for(re int i=1; i<=n; i++) { scanf("%s",ch+1); for(re int j=1; j<=m; j++) { sum[i][j] = sum[i-1][j]+(ch[j]=='1'); } } cin >> l >> r; for(re int i=1; i<=n; i++) { for(re int j=i; j<=n; j++) { int lp = 0,rp = 0; for(re int k=1; k<=m; k++) { //printf("i=%lld j=%lld k=%lld ",i,j,k); tot[k] = tot[k-1]+sum[j][k]-sum[i-1][k]; //printf("tot[%lld]=%lld\n",k,tot[k]); while(tot[k]-tot[lp]>r&&lp+1<k) { lp++; } while(tot[k]-tot[rp+1]>=l&&rp+1<k) { rp++; } if(tot[k]-tot[rp]>=l) { ans += rp-lp+1; } } } } printf("%lld\n",ans); return 0; } } signed main() { return (OMA::main(),0); }
T2
题意转换
好了,现在你已经知道转换后的题意,问题在于如何求解 \(cnt\) 数组和答案。
对于每一行,我们都开一个桶记录 \(a\) 出现的次数。
然后枚举每一行,再从1枚举到最大值,再枚举当前枚举的数的倍数,加上上边说的桶即可 建议看code
这样得到的 \(cnt_{i,j}\) 表示第i行有多少个数为j的倍数,每一行求和就是总的,而我们要的是j,所以考虑一波容斥,即减去j的其他倍数即可,这样的话就要倒序枚举最大值。
复杂度 \(O(n(m+\max\{a\}\ln\max\{a\}))\) 。
Code
#include<cstdio> #define MAX 100010 #define re register #define int long long const int N = 22; namespace OMA { int n,m,xam,ans; int a[N][MAX]; int buc[N][MAX]; int cnt[N][MAX],sum[MAX]; const int p = 1e9+7; struct stream { template<typename type>inline stream &operator >> (type &s) { int w=1; s=0; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*=w,*this; } }cin; inline int max(int a,int b) { return a>b?a:b; } signed main() { cin >> n >> m; for(re int i=1; i<=n; i++) { for(re int j=1; j<=m; j++) { cin >> a[i][j]; xam = max(xam,a[i][j]); buc[i][a[i][j]]++; } } for(re int i=1; i<=n; i++) { for(re int j=1; j<=xam; j++) { for(re int k=1; j*k<=xam; k++) { cnt[i][j] += buc[i][j*k]; } } } /*for(re int i=1; i<=n; i++) { for(re int j=1; j<=xam; j++) { printf("%lld ",cnt[i][j]); } printf("\n"); }*/ for(re int j=xam; j; j--) { sum[j] = 1; for(re int i=1; i<=n; i++) { (sum[j] *= cnt[i][j]+1) %= p; } sum[j] -= 1; if(!sum[j]) { continue ; } for(re int k=2; k*j<=xam; k++) { sum[j] -= sum[k*j]; } (ans += j*sum[j]) %= p; } printf("%lld\n",(ans+p)%p); return 0; } } signed main() { return OMA::main(); }
T3
点分治,不会,爬了
这篇关于noip38的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-30Dnd-Kit学习:新手快速入门指南
- 2024-09-30ESLint学习:初学者指南
- 2024-09-30Formik学习:从入门到实践指南
- 2024-09-30Hooks 规则学习:从入门到上手的简单教程
- 2024-09-30Husky学习:初学者必备指南
- 2024-09-30Immer不可变数据用法入门教程
- 2024-09-30JWT 用户校验学习:简易教程与实战演练
- 2024-09-30MobX用法入门教程:轻松掌握MobX基础
- 2024-09-30Nest学习:入门到实践的简易教程
- 2024-09-30Nest学习:新手入门指南