新生29场

方格稿纸:

题目描述

小猪在小学中认识了很多的字,终于会写一点作文了。某天小猪买了一张方格稿纸来写作文,n行m列,形状如下所示:
新生29场
上图中n=m=5。
某天小猪的邻居小小猪来小猪家玩,用黑墨水笔把小猪新买的方格稿纸涂黑了很多格子。每个格子不是完全黑色就是完全白色,如下图所示。
新生29场
小猪不能责怪小小猪。作文写不成了,他觉得很无聊,就开始数里面有多少魔幻方阵。 如果稿纸中一个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;
    
}

 

 

上一篇:HDU.2516.取石子游戏(博弈论 Fibonacci Nim)


下一篇:[Leetcode]29.二叉树中的最大路径和