正文

洛谷mnoip模拟赛day2-入阵曲

white_hat_hacker  white_hat_hacker  2022-09-26  449

关键词：

题目背景

pdf题面和大样例链接：http://pan.baidu.com/s/1cawM7c 密码：xgxv

丹青千秋酿，一醉解愁肠。 
无悔少年枉，只愿壮志狂。

题目描述

小 F 很喜欢数学，但是到了高中以后数学总是考不好。

有一天，他在数学课上发起了呆；他想起了过去的一年。一年前，当他初识算法竞赛的时候，觉得整个世界都焕然一新。这世界上怎么会有这么多奇妙的东西？曾经自己觉得难以解决的问题，被一个又一个算法轻松解决。

小 F 当时暗自觉得，与自己的幼稚相比起来，还有好多要学习的呢。

一年过去了，想想都还有点恍惚。

他至今还能记得，某天晚上听着入阵曲，激动地睡不着觉，写题写到鸡鸣时分都兴奋不已。也许，这就是热血吧。

技术分享

也就是在那个时候，小 F 学会了矩阵乘法。让两个矩阵乘几次就能算出斐波那契数列的第 $10^{100}10100 项，真是奇妙无比呢。$

不过，小 F 现在可不想手算矩阵乘法——他觉得好麻烦。取而代之的，是一个简单的小问题。他写写画画，画出了一个

小 F 想问问你，这个矩阵里有多少个不同的子矩形中的数字之和是 $(x_1,y_1,x_2,y_2)(x1?,y1?,x2?,y2?)，其中x_1 le x_2,y_1 le y_2x1?≤x2?,y1?≤y2?；那么，我们认为两个子矩形是不同的，当且仅当他们以 (x_1,y_1,x_2,y_2)(x1?,y1?,x2?,y2?) 表示时不同；也就是说，只要两个矩形以 (x_1,y_1,x_2,y_2)(x1?,y1?,x2?,y2?) 表示时相同，就认为这两个矩形是同一个矩形，你应该在你的答案里只算一次。$

输入输出格式

输入格式：

从标准输入中读入数据。

输入第一行，包含三个正整数

输入接下来 $a_{i,j}ai,j?。$

输出格式：

输出到标准输出中。

输入一行一个非负整数，表示你的答案。

输入输出样例

输入样例#1：复制

2 3 2 
1 2 1 
2 1 2

输出样例#1：复制

说明

【样例 1 说明】

这些矩形是符合要求的： (1, 1, 1, 3)，(1, 1, 2, 2)，(1, 2, 1, 2)，(1, 2, 2, 3)，(2, 1, 2, 1)，(2, 3, 2, 3)。

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。

每个测试点的数据规模及特点如下表：

技术分享

特殊性质：保证所有

暴力的话枚举就是了，预处理一下sum

同时所有a相同的情况可以骗到5分

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<map>
  7 #include<set>
  8 #include<queue>
  9 #include<vector>
 10 #define INF 0x7f7f7f7f
 11 #define pii pair<int,int>
 12 #define ll long long
 13 using namespace std;
 14 int n,m,k;
 15 int a[405][405];
 16 namespace solve1
 17 {
 18     int n,m,k;
 19     ll s[405][405];
 20     int a[405][405];
 21     void solve(){
 22         n=::n,m=::m,k=::k;
 23         memcpy(a,::a,sizeof(a));
 24         for(int i=1;i<=n;i++){
 25             for(int j=1;j<=m;j++){
 26                 s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
 27             }
 28         }
 29         ll ans=0;
 30         for(int i=1;i<=n;i++){
 31             for(int j=1;j<=m;j++){
 32                 for(int x=i;x<=n;x++){
 33                     for(int y=j;y<=m;y++){
 34                         if(!((s[x][y]-s[i-1][y]-s[x][j-1]+s[i-1][j-1])%k)){
 35                             ans++;
 36                         }
 37                     }
 38                 }
 39             }
 40         }
 41         printf("%lld
",ans);        
 42     }
 43 }
 44 namespace solve2
 45 {
 46     int n,m,k;
 47     int K;
 48     int a[405][405];
 49     int gcd(int x,int y){
 50         return (y==0?x:gcd(y,x%y));
 51     }    
 52     void solve(){
 53         n=::n,m=::m,k=::k;
 54         memcpy(a,::a,sizeof(a));    
 55         int g=gcd(a[1][1],k);
 56         K=k/g;
 57         ll ans=0;
 58         for(int i=1;i*K<=n*m;i++){
 59             int t=i*K;
 60             for(int j=1;j<=t;j++){
 61                 if(t%j==0){
 62                     int x=j,y=t/j;
 63                     if(x<=n&&y<=m){
 64                         ans+=(n-x+1)*(m-y+1);    
 65                     }
 66                 }
 67             }
 68         }
 69         printf("%lld
",ans);
 70     }
 71 }
 72 int read(){
 73     int x=0,f=1;char ch=getchar();
 74     while(ch<‘0‘||ch>‘9‘){if(‘-‘==ch)f=-1;ch=getchar();}
 75     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
 76     return x*f;
 77 }
 78 int main()
 79 {
 80 //    freopen("rally1.in","r",stdin);
 81     n=read(),m=read(),k=read();
 82     for(int i=1;i<=n;i++){
 83         for(int j=1;j<=m;j++){
 84             a[i][j]=read();
 85         }
 86     }
 87     int t=a[1][1],ok=1;
 88     for(int i=1;i<=n;i++){
 89         for(int j=1;j<=m;j++){
 90             if(t!=a[i][j]){
 91                 ok=0;
 92                 break;
 93             }
 94         }
 95         if(!ok){
 96             break;
 97         }
 98     }
 99     if(ok){
100         solve2::solve();
101     }
102     else{
103         solve1::solve();
104     }
105     return 0;
106 }

暴力

我们发现无法遍历所有的矩阵，一旦遍历就会超时

于是只能用一些鬼畜的计数方法，然而并不是很好发现

只好去一维看看：

给定一个序列，求连续的子序列之和是k的倍数的数目

然后我们鬼畜地想到了前缀和：如果两个前缀和模k相同，那么这两个前缀和之差对应的区间一定是k的倍数

这样就有了思路，统计所有前缀和模k的情况，然后对于模k结果相同的前缀，任选两个相减对应的区间一定是k的倍数

注意如果前缀和本身就是k的倍数，可以看成它和前零个数的前缀和构成k倍数的区间，所以把0的位置+1即可

这样的复杂度是O(n)

回到二维的情况：

发现问题迎刃而解，枚举压起来然后就是上面的问题了

O(n^3)

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<vector>
 6 #define MAXN 405
 7 #define ll long long
 8 using namespace std;
 9 int read(){
10     int x=0;char ch=getchar();
11     while(ch<‘0‘||ch>‘9‘){ch=getchar();}
12     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
13     return x;
14 }
15 ll ans;
16 int n,m,k;
17 int a[MAXN][MAXN];
18 ll s[MAXN][MAXN];
19 ll b[MAXN];
20 int t[1000005];
21 int vis[1000005],cnt;
22 void work(int x,int y){
23     cnt++;
24     vector<int> v;
25     for(int i=1;i<=m;i++){
26         b[i]=s[i][y]-s[i][x-1];
27     }
28     t[0]=1;
29     vis[0]=cnt;
30     v.push_back(0);
31     for(int i=1;i<=m;i++){
32         b[i]+=b[i-1];
33         int p=b[i]%k;
34         if(vis[p]!=cnt){
35             vis[p]=cnt;
36             t[p]=0;
37             v.push_back(p);
38         }
39         t[p]++;
40     }
41     for(int i=0;i<v.size();i++){
42         int x=v[i];
43         ans+=1LL*t[x]*(t[x]-1)/2;
44     }
45 }
46 int main()
47 {
48     n=read(),m=read(),k=read();
49     for(int i=1;i<=n;i++){
50         for(int j=1;j<=m;j++){
51             a[i][j]=read();
52         }
53     }
54     for(int j=1;j<=m;j++){
55         for(int i=1;i<=n;i++){
56             s[j][i]=s[j][i-1]+a[i][j];
57         }
58     }
59     for(int i=1;i<=n;i++){
60         for(int j=i;j<=n;j++){
61             work(i,j);
62         }
63     }
64     printf("%lld
",ans);
65     return 0;
66 }

总结：二维可以拿一维的思想来考虑，当枚举不能解决问题时肯定有计数的策略

洛谷mnoip模拟赛day2-将军令

题目背景pdf题面和大样例链接：http://pan.baidu.com/s/1cawM7c 密码：xgxv历史/落在/赢家/之手至少/我们/拥有/传说谁说/败者/无法/不朽拳头/只能/让人/低头念头/却能/让人/抬头抬头/去看/去爱/去追你心中的梦题目描述又想起了四月... 查看详情

noip模拟赛入阵曲

分析：其实很容易想到O(n^3m^3)的算法，枚举x1,x2,y1,y2,再统计一下和.求和可以用前缀和，能优化到O(n^2m^2),能得到60分.对于特殊性质的点，求一下a[i][j]与k的最小公倍数lcm,就可以推出来要选多少个点，乘法原理推一下就能解决了.&nb... 查看详情

luogup3941入阵曲

题目背景pdf题面和大样例链接：http://pan.baidu.com/s/1cawM7c 密码：xgxv丹青千秋酿，一醉解愁肠。无悔少年枉，只愿壮志狂。题目描述小F很喜欢数学，但是到了高中以后数学总是考不好。有一天，他在数学课上发起了呆；他想起... 查看详情

luogu3941入阵曲

题目大意给出一个$m$排$n$列的矩阵，求有多少个子矩阵满足子矩阵内的数字和为$k$的倍数。$m,n<=400,k<=10^6$。思路先考虑简单的问题。把矩阵换为线段，子矩阵换为子线段。对于原序列$a$，很容易我们想到用序列$s$来维护区间... 查看详情

luogu3941入阵曲(代码片段)

https://www.zybuluo.com/ysner/note/1301562题面统计在给出的(n*m)矩阵中，有多少个不同的子矩形中的数字之和是(k)的倍数？解析切不掉这道题是我傻逼显然预处理出每列的前缀和。然后枚举矩形的上界和下界，统计下范围内哪些列余数相... 查看详情

落谷p3941入阵曲

洛谷mnoip模拟赛day1-数颜色

传送门题目大意：给定一个序列，维护每个数字在[L,R]出现的次数以及交换a[x]和a[x+1]的操作一开始想的分桶法，感觉复杂度还可以吧，常数有点大，于是死得很惨（65分）1#include<cstdio>2#include<cstdlib>3#include<algorithm>4#i... 查看详情

洛谷mnoip模拟赛day1-分组

传送门首先是贪心的思路从后向前选，能多选就多选，理由：数字越少肯定越优，同时间隔尽量向前推，字典序尽量小对于K==1，枚举1~512直接判断对于K==2，需要用镜像并查集，来刻画“敌对关系”，如果a和b产生矛盾，就把... 查看详情

洛谷mnoip模拟赛day1-斐波那契

题目背景大样例下发链接：http://pan.baidu.com/s/1c0LbQ2 密码：jigg题目描述小C养了一些很可爱的兔子。有一天，小C突然发现兔子们都是严格按照伟大的数学家斐波那契提出的模型来进行繁衍：一对兔子从出生后第二个月起，每个... 查看详情

题解入阵曲luogu3941前缀和压维

丹青千秋酿，一醉解愁肠。无悔少年枉，只愿壮志狂。题目题目描述小F很喜欢数学，但是到了高中以后数学总是考不好。有一天，他在数学课上发起了呆；他想起了过去的一年。一年前，当他初识算法竞赛的时候，觉得整个世... 查看详情

luogup3941入阵曲前缀和bycellur925(代码片段)

题目传送门题目大意：给你一个(n)*(m)的矩阵，每个位置都有一个数，求有多少不同的子矩阵使得矩阵内所有数的和是(k)的倍数。数据范围给的非常友好233，期望得到的暴力分：75分。前12个点可以用(O(n^4))算法水过，对于(<=400)... 查看详情

洛谷mnoip模拟赛day1t1斐波那契

题目传送门：https://www.luogu.org/problemnew/show/P3938这题出得特别吼啊~~通过打表或者大胆猜想斐波那契数列的一些性质，我们不难发现对于一只兔子$x$，其父亲必为$x-Fk$（$F$为斐波那契数列，且$F_{k}$为不大于$x$的最大数字），举个... 查看详情

p3941入阵曲(代码片段)

...了，想想都还有点恍惚。他至今还能记得，某天晚上听着入阵曲，激动地睡不着觉，写题写到鸡鸣时分都兴奋不已。也许，这就是热血吧。也就是在那个时候，小F学会了矩阵乘法。让两个矩阵乘几次就能算出斐波那契数列的第(1... 查看详情

2017-10-13noip模拟赛

入阵曲 #include<iostream>#include<cstdio>#definemaxn401#ifdefWIN32#definePLL"%I64d"#else#definePLL"%lld"#endifusingnamespacestd;intn,m,K,a[maxn][maxn],sum[maxn][m 查看详情

2017.11.2洛谷mnoip比赛|t1斐波那契找规律

Day1T1 斐波那契找规律。我们发现，兔子的编号减去斐波那契数列中第一个比它小的数之后就可以得到它的父亲。一直找减找减找减...就ok了。题解（%%%dalao‘s代码）查看详情

mnoip模拟赛day1t2数颜色

题目传送门：https://www.luogu.org/problemnew/show/P3939题外话：写完这题后本地跑了下极限数据，用时1.5s，于是马上用fread+fwrite优化至0.3s，交至OJ，跑了600+ms，好奇地去掉fread和fwrite，居然只跑了700+ms（总感觉哪里不太对劲）。此题有... 查看详情

洛谷p1083[noip2012提高组day2t2]借教室

P1083借教室题目描述在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我... 查看详情

洛谷p1970[noip2013提高组day2t2]花匠

P1970花匠题目描述花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。具... 查看详情