【牛客练习赛74】A-C题解

A

对标cf难度：900
按题意模拟即可。
注意判断等比的时候要用乘法： $a/b=b/c$ 等价于 $b^2=a*c$ （a、b、c都是正整数），标程std是错的，无法通过以下hack数据：
3
200000000 400000000 800000001
参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,i;
    cin>>n;
    long long a[100010];
    for(i=0;i<n;i++)cin>>a[i];
    for(i=2;i<n;i++){
        if(a[i]-a[i-1]!=a[i-1]-a[i-2])break;

    }
    if(i==n){cout<<"YES";return 0;}
    for(i=2;i<n;i++){
        if(a[i-1]*a[i-1]!=a[i]*a[i-2])break;

    }
    if(i==n){cout<<"YES";return 0;}
    for(i=2;i<n;i++){
        if(a[i]%a[i-1]!=a[i-1]%a[i-2])break;

    }
    if(i==n){cout<<"YES";return 0;}
    cout<<"NO";
}

B

对标cf难度：1400
求一个字符串有多少子串包含"Nowcoder"的子串。
先找到每个子串"Nowcoder"的位置，然后枚举起点寻找不合法的子串，个数为（从该点到下一个"Nowcoder"的字符'e'位置）。之后用总数减去不合法的即可。

#include<bits/stdc++.h>
using namespace std;
string temp="NowCoder";
vector<int>dp;
int main(){
    string s;
    int i;
    cin>>s;
    long long cnt=0,n=s.length();
    long long all=n*(n+1)/2;
    for(i=0;i<s.length()-7;i++){
        int j=0;
        for(j=0;j<8;j++){
            if(s[i+j]!=temp[j])break;
        }
        if(j==8){
            dp.push_back(i);
        }
    }
    if(dp.size()==0){cout<<0;return 0;}
    long long sum=0;
    int r=0;
    for(i=0;i<n;i++){
        if(r<dp.size())sum+=dp[r]+7-i;
        else sum+=n-i;
       // cout<<sum<<endl;
        if(i==dp[r]){
            r++;
        }
    }
    cout<<all-sum;

}

C

对标cf难度：1700
用大小为 #k# 的菱形去覆盖正方形，求覆盖的数字之和的最大值。
将原地图旋转45度，相当于就是用正方形去覆盖了。转化的过程需要在纸上推演一下（尤其是特判不能超过边界。我的方法是找出菱形的四个顶点坐标对应到原地图，保证坐标的x和y都在区间 $[1,n]$ 即可）。之后就是经典的二维前缀和然后 $O(1)$ 查询了。

#include<bits/stdc++.h>
using namespace std;
int a[4040][4040];
long long sum[4040][4040];
int main(){
    int n,k,i,j;
    cin>>n>>k;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            scanf("%d",&a[i+j-1][j+n-i]);
        }
    }
    for(i=1;i<=2*n;i++){
        long long s=0;
        for(j=1;j<=2*n;j++){
            sum[i][j]=s+=a[i][j];
        }
    }
    for(j=1;j<=2*n;j++){
        for(i=1;i<=2*n;i++){
            sum[i][j]+=sum[i-1][j];
        }
    }
    long long ma=0;
    for(i=k;i<=2*n-k;i++){
        for(j=k;j<=2*n-k;j++){
            if((n+i-j)%2==1){
                int r=2*k-1;
                int x=(n+1+i-j)/2,y=(i+j+1-n)/2,x2=(n+1+i+r-1-j)/2,x3=(n+1+i-j-r+1)/2;
                int y2=(i+j+1-n+r-1)/2,y3=(i+j+1-n+r+r-2)/2;
                if(x>=1&&x<=n&&y>=1&&y<=n&&x2>=1&&x2<=n&&x3>=1&&x3<=n&&y2>=1&&y2<=n&&y3>=1&&y3<=n){
                    ma=max(ma,sum[i+r-1][j+r-1]+sum[i-1][j-1]-sum[i+r-1][j-1]-sum[i-1][j+r-1]);
                }
            }
        }
    }
    cout<<ma;
}