牛客寒假算法基础训练营day-1

写在前面：寒假之前报名了牛客的寒假算法训练营，当时没有好好参加，主要还是自己太菜，正好临近五一，所以计划每天学习一下当时比赛时候的题目和相关算法，因为这次训练营的题目是针对竞赛的，所以很多知识点我都还没学过，所以这里只记录一下相对来说简单一点的题目，后续学习了相关知识点后会持续补充~

官方题解地址:https://ac.nowcoder.com/discuss/364600?type=101&order=0&pos=1&page=3&channel=-1

A. honoka和格点三角形

因为是格点三角形且面积为1，所以只存在两种形式的三角形：底为2高为1的和底为1和高为2的，题目还要求三角形至少有一条边是与坐标轴平行的，所以我们再分为两条边都平行和只有一条边平行这两类进行讨论：
贴张我自己的笔记：

note

代码：

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long LL;

const int mod = 1e9+7;
LL n,m;
int main()
{
    LL ans = 0;
    cin>>n>>m;
    
    //两边平行
    ans = 4 * ((n-1)*(m-2)%mod + (n-2)*(m-1)%mod)%mod;
    
    //底边与x轴平行
    ans = (ans + 2 *(n-1)*(m-2)%mod*(m-2) + 2*(m-1)*(n-2)%mod*(n-2)%mod)%mod;
    
    //底边与y轴平行
    ans = (ans + 2 * (m-1)*(n-2)%mod*(m-2)%mod + 2*(n-1)*(m-2)%mod*(n-2)%mod)%mod;
    
    cout<<ans<<endl;
    return 0;
}

G.eli和字符串

对每个字母都预处理一个数组，然后用尺取法(双指针)对26个数组依次进行扫描，更新答案

代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <unordered_map>

using namespace std;

const int N = 200100;
string s;
int n,k;
int a[30][N];

int main()
{
    cin>>n>>k;
    cin>>s;
    s = " " + s;
    
    //预处理
    for(int i = 0; i<26; i++){
        for(int j = 1; j<=n; j++)
            if(s[j] == ('a' + i))
                a[i][j] = 1;
    }
 
    int ans = 1e9;
    for(int i = 0; i<26; i++){
        int res = N,l = 1,r = 1,sum = 0;
        while(1){
            while(r<=n && sum<k) sum += a[i][r++];
            if(sum < k) break;
            res = min(res,r-l);
            sum -= a[i][l++];
        }
        //cout<<res<<endl;
        ans = min(ans,res);
    }
    if(ans == N) cout<<-1<<endl;
    else cout<<ans<<endl;
    
    return 0;
}

H.nozomi和字符串

也是用尺取法，找到满足条件的最大区间

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

string s;
int n,k;

//尺取法
int solve(char a,char b){
    int l = 0, r = 0,cnt = 0,res = 1;
    
    for(int i = 0; i<n; i++){
        if(s[i] == a){
            if(cnt <k){
                cnt++;
                r++;
            }
            else{
                while(l<=r && s[l] != a) l++;
                l++,r++;
            }
        }
        else r++;
        res = max(res,r-l);
    }
    return res;
}
int main()
{
    cin>>n>>k>>s;
    int ans = max(solve('0','1'),solve('1','0'));
    cout<<ans<<endl;
    return 0;
}

I.nico和niconiconi

DP问题，dp[i]表示前i个字符的最大得分，状态转移方程为：
if(s.substr(i - 3, 4) == "nico")then dp[i] = max(dp[i],dp[i - 4] + a)
if(s.substr(i - 5, 6) == "niconi")then dp[i] = max(dp[i],dp[i- 6] + b)
if(s.substr(i - 9,10) == "niconiconi")then dp[i] = max(dp[i], dp[i - 10]+ c)

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

using namespace std;

const int N = 300010;
int a,b,c;
int n;
long long dp[N];
string s;

int main()
{
    cin>>n>>a>>b>>c>>s;
    s = " " + s;
    long long ans = 0;
    if(n>=4){
        for(int i = 1; i<=n; i++){
            dp[i] = dp[i-1];
            if(i>=4)
                if(s.substr(i-3,4) == "nico") 
                    dp[i] = max(dp[i-4] + a,dp[i]);
            if(i>=6){
                if(s.substr(i-5,6) == "niconi")
                    dp[i] = max(dp[i-6] + b,dp[i]);
            }
            if(i>=10){
                if(s.substr(i-9,10) == "niconiconi")
                    dp[i] = max(dp[i-10] + c,dp[i]);
            }
            
        }
        ans = dp[n];
    }
    //for(int i = 1; i<=n; i++) cout<<dp[i]<<endl;
    cout<<ans<<endl;
    return 0;
}

至此，day-1还有一个图论题，一个数论题，后面再更新~
2020 4.30 凌晨0.27分，顶不住了，溜了。