方格稿纸:
题目描述
小猪在小学中认识了很多的字,终于会写一点作文了。某天小猪买了一张方格稿纸来写作文,n行m列,形状如下所示:上图中n=m=5。
某天小猪的邻居小小猪来小猪家玩,用黑墨水笔把小猪新买的方格稿纸涂黑了很多格子。每个格子不是完全黑色就是完全白色,如下图所示。
小猪不能责怪小小猪。作文写不成了,他觉得很无聊,就开始数里面有多少魔幻方阵。 如果稿纸中一个k×k的正方形区域满足以下两个条件,那么它就是魔幻方阵: 1.黑白格子的数量差不能超过1; 2.k不能小于2。 上图染色后的方格稿纸共有9个魔幻方阵(6个2×2的魔幻方阵,3个3×3的魔幻方阵),现在请你帮小猪求出他被染色的稿纸里面有多少个魔幻方阵。
输入
输入中的第一行有二个正整数n和m(互相之间以一个空格分隔),表示稿纸共有n行m列。接下来n行,每行有m个0或1的整数(互相之间以一个空格分隔),代表每个格子的颜色。如果这个数是1则为黑色,是0则为白色。
输出
输出中仅有一行,该行只有一个整数,表示稿纸中魔幻方阵的个数。样例输入 Copy
5 5 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1
样例输出 Copy
9
提示
50%的数据,1≤n≤10,1≤m≤10;75%的数据,1≤n≤180,1≤m≤180;
100%的数据,1≤n≤300,1≤m≤300。 题解:这个题的大概思路就是用二位前缀和,求出每个正方形里面的数字之和,用总共的面积减这个数字就是白格的数量 经过一位大佬的修正,刚开始我就直接两个相减了,其实是白的减黑的绝对值<=1
#include<iostream> #include<cmath> using namespace std; const int N=500; int s[N][N]; int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>s[i][j]; } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++ ) { s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; } int k=1,t=0; while((k+1)<=min(n,m)) { for(int i=1;i<=n-k;i++) { for(int j=1;j<=m-k;j++) { int x1=i,y1=j,x2=i+k,y2=j+k,sum; int ans=(k+1)*(k+1); sum=s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]; if(abs(sum-(ans-sum))<=1) { t++; } } } k++; } cout<<t<<endl; return 0; }
找朋友:
题目描述
小学毕业后,同学们都进入了不同的初中,小明非常想念小伙伴们,所以他打算联系小学的同学们。现在他得到了市内某所初中的所有名单,找出其中小明的小伙伴们。
输入
第一行一个整数n,表示某初中人数。接下来n行,每行一个字符串,只有小写字母组成,表示该校每个人的拼音。数据保证没有人拼音相同,且已经按照字典序从小到大排序。
第n+2行有一个整数m,表示小明的小伙伴个数。
最后m行,每行一个字符串,只有小写字母组成,表示每个小伙伴的拼音,同样保证没有重复。
输出
输出所有在该校的小伙伴的拼音。每行一个拼音,顺序按照小伙伴给出的顺序。
样例输入 Copy
3 alice bob zhangsan 2 lisi zhangsan
样例输出 Copy
zhangsan
提示
对于70%的数据,n≤1000,m≤100对于100%的数据,n<=100000,m<=10000,每个人拼音长度不超过15。 所有数据,学校学生名单中的姓名,都是按照字典序从小到大排序 题解:这题二分也能做,但听说会tl,用map,这么巧妙,我的天哪hhh
#include<iostream> #include<map> using namespace std; map<string,bool> mp; int main(){ int n,m; cin>>n; string ch; for(int i=0;i<n;i++) { cin>>ch; mp[ch]=true; } cin>>m; for(int i=0;i<m;i++) { cin>>ch; if(mp[ch]) cout<<ch<<endl; } return 0; }