https://ac.nowcoder.com/acm/contest/13493

试题A：门牌制作

1-2020有多少个‘2’

思路：遍历1-2020，将int转换为string
用sum变量累加，count方法计算每一个字符串中字符‘2’出现的次数

#include<bits/stdc++.h>
using namespace std;
void s2i(int num,string &ss ){
    stringstream temps;
    temps<<num;
    temps>>ss;
}
int main()
{
    int sum=0;
    for(int i=1;i<=2020;i++)
    {
        string temp;
        s2i(i,temp);
        sum+=count(temp.begin(),temp.end(),'2');
    }
    cout<<sum;
    return 0;
} 

知识点：利用字符流将数字转换为字符串
用count方法计算字符串中某个字符出现次数

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int sum=0;
    for(int i=1;i<=2020;i++){
        int temp;
        int x=i;
        while(x>0){
            temp=x%10;
            x/=10;
            if(temp==2)sum++;
        }
    }
    cout<<sum;
    return 0;
}

试题B：既约分数

如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。 
例如，3/4, 5/2 , 1/8, 7/1 都是既约分数。 
请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1 和 2020）？

思路:辗转相除法枚举两个数的最大公约数
判断其最大公约数是否是1

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    a=abs(a);
    b=abs(b);
    while(b!=0){
        a=a%b;
        swap(a,b); 
    }
    return a;
}
int main()
{
    int sum=0;
    for(int i=1;i<=2020;i++){
        for(int j=1;j<=2020;j++){
            if(gcd(i,j)==1){
                sum++;
            }
        }
    }
    cout<<sum;
    return 0;
}

试题C 辗转相除

链接： [https://ac.nowcoder.com/acm/contest/13493/C](https://) 
来源：牛客网

小明最近痴迷于斐波那契数列（1，1，2，3，5……），
但是最近他又有了新的奇思妙想，就是对于斐波那契数列的相邻的两个数相乘取倒数
然后将每一项进行相加，由于小明只喜欢思考不喜欢动手，所以现在他想让你帮他算下
这样一个新的数列的前13项的和为多少？（结果用分数表示，且保留最简分数）

思路：过程中计算，来一个数加一个数，新来的数相当于(分子分母)扩大前一个数的分母倍
前一个数相当于(分子分母)扩大新来的数的分母倍，此时两个分数分母相同，可以相加

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100;
ll arr[N];
ll fb(int n){
    arr[1]=arr[2]=1;
    for(int i=3;i<=n;i++){
        arr[n]=arr[n-1]+arr[n-2];
    }
    return arr[n];
}
ll gcd(ll a,ll b){
    a=abs(a);
    b=abs(b);
    while(b!=0){
        a=a%b;
        swap(a,b);
    }
    return a;
}
int main()
{
    ll fz,fm;
    ll x1=1;//1*1
    ll x2=2;//1*2
    fz=x1+x2;
    fm=x1*x2;
    for(int i=3;i<=13;i++){
        ll xs=fb(i)*fb(i+1);
        fz=fz*xs+fm;
        fm=fm*xs;
        ll ys=gcd(fz,fm);
        fz/=ys;
        fm/=ys;
    }
    // cout<<gcd(22,11)<<endl; 
    cout<<fz<<"/"<<fm; 
    return 0;
} 

试题F 字符串

链接：https://ac.nowcoder.com/acm/contest/13493/F
来源：牛客网

又是努力刷题的一天。众所周知wyk是国一大佬喜欢帮群友解答问题。
现在xmy好奇群里的聊天记录有多少条是@wyk的，但是他在忙着摸鱼。
所以找到了你，给了你N条聊天记录，让你帮他算一下。

注意：保证聊天记录的字母都是在ASSIC内。聊天记录存在空格，
也可能以空格开头或结尾。@wyk必须连续才能生效，一条聊天记录保证在一行

注意说明了输入数据需要处理，不能单纯的用cin，因为
cin输入分割：Tab,Space,Enter 缓冲区输入结束：Enter
所以用getline接收数据。在cin后,从缓冲区用getline()
读入数据时需要加上getchar(),因为getline接收缓冲区的\n
数据处理后在api中找到find函数的用法，进行@wyk查找

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    getchar();
    string a;
    int cnt=0;
    for(int i=0;i<n;i++){
        getline(cin,a);
        int loc=a.find("@wyk",0);
        //cout<<loc<<endl; 
        if(loc!=string::npos){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
} 

G最强对手矩阵

链接：https://ac.nowcoder.com/acm/contest/13493/G
来源：牛客网

这一天你来到了蓝桥杯的考场，你发现考场是一个N*M的矩阵。
因为你的群友很多，你知道考场内每个人有多强，并且把实力换算成了数值。(因为有的人太弱了
所以可能出现实力值是负数的可能)
你想知道考场内实力总和最大的矩阵区域的实力和是多少。
（注意:区域是按照矩形划分的）

用二维前缀和写o(n^4)内存爆了.给的数据范围是(1≤N×M≤2e5)，所以我看题解都是用vector存储
 vector<vector<int>> a(n+1,vector<int>(m+1));

#include<bits/stdc++.h>
using namespace std;
const int N=100;
int arr[N][N];
int dp[N][N];
int val[N][N][N][N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>arr[i][j] ;
        } 
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+arr[i][j];  
        }
    }
    //cout<<"*******(0,0)到该点所有数的和*************"<<endl;
//  for(int i=0;i<n;i++){
//      for(int j=0;j<m;j++){
//          cout<<dp[i][j]<<" ";
//      }
//      cout<<endl;
//  }
//  cout<<"********************"<<endl;
    long long max=-2000;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            for(int l=0;l<n;l++){
                for(int r=0;r<m;r++){
                    val[i][j][l][r]=dp[l][r]-dp[l][j-1]-dp[i-1][r]+dp[i-1][j-1];
                    if(val[i][j][l][r]>max)max=val[i][j][l][r];
                }
            }   
        }
    }
    cout<<max<<endl;
    return 0;
} 

新学的优化方法，把枚举四个点改为枚举边界。
其实就是降维，将每一列的前缀和算出来，求的时候将下长和上长相减就可
得到一个长条，没有宽约束的矩形，现在就可以把它想成一维了
i代表当前位置
若f[i-1]>0，则要，f[i]=f[i-1]+a[i]
若f[i-1]<0，则不要，f[i]=0+a[i]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int n,m;
    cin>>n>>m;
    int a[n+1][m+1],b[n+1][m+1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j]; 
            b[i][j]=b[i][j-1]+a[i][j];
        } 
    }
    int res=-9999999;

    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=m;j++){
            int last=0;
            for(int k=1;k<=n;k++){
                last=max(0,last)+b[k][j]-b[k][i-1];
                res=max(res,last);
            }
        }
    }


    cout<<res;
    return 0;
}