2020牛客寒假算法基础集训营1

A 题

样例就跟没给一个效果

分类讨论底为1或2，这两种情况不能有交集。至于公式比较容易得出。

一开始wa的原因是没有最后一个%mod。。

#include <iostream>
#include <malloc.h>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long LL;
const int maxn = 200000 + 10;
const LL mod = 1e9 + 7;
const LL inf = 0x3f3f3f3f;
int a[maxn];
vector<int> v[26];
char s[maxn];
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    LL n, m, ans = 0;
    cin >> n >> m;
    ans += ((m - 2) * ((n - 1) % mod * 2 % mod) % mod) % mod * (m) % mod;
    ans += ((n - 2) * ((m - 1) % mod * 2 % mod) % mod) % mod * (n) % mod;
    // 计算 底 为 2 的所有三角形
    ans += (((m - 1) * (m - 2) % mod * (n - 2) % mod) % mod * 2 % mod) % mod;
    ans += (((n - 1) * (n - 2) % mod * (m - 2) % mod) % mod * 2 % mod) % mod;
    // 计算 底 为 1 的所有三角形
    cout << ans % mod << endl;
    return 0;
}

I 题 

线性DP！

没有题感觉。。其实挺简单的

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 300000 + 10;
LL dp[maxn];
char s[maxn];
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#endif
    //     nico 4
    //     niconi 6
    //     niconiconi 10
    LL i, n, x, y, z;
    cin >> n >> x >> y >> z;
    scanf("%s", s + 1);
    for (i = 1; i <= n; i++)
    {
        if (i > 1)
            dp[i] = dp[i - 1];
        if (i >= 4 && s[i - 3] == 'n' && s[i - 2] == 'i' && s[i - 1] == 'c' && s[i] == 'o')
            dp[i] = max(dp[i], dp[i - 3] + x);
        if (i >= 6 && s[i - 5] == 'n' && s[i - 4] == 'i' && s[i - 3] == 'c' && s[i - 2] == 'o' && s[i - 1] == 'n' && s[i] == 'i')
            dp[i] = max(dp[i], dp[i - 5] + y);
        if (i >= 10 && s[i - 9] == 'n' && s[i - 8] == 'i' && s[i - 7] == 'c' && s[i - 6] == 'o' && s[i - 5] == 'n' && s[i - 4] == 'i' && s[i - 3] == 'c' && s[i - 2] == 'o' && s[i - 1] == 'n' && s[i] == 'i')
            dp[i] = max(dp[i], dp[i - 9] + z);
    }
    cout << dp[n];
}

还有几个题目都没补，再说吧。