牛客月赛49

本篇题解只是记录我的做题过程代码，不提供最优解
（另外这里所有的时间复杂度都只分析单个样例，不算 t t t的时间复杂度）

点击此处查看对应的题目.
本题设计算法：逆元 + 快速幂 + 二次函数性质

本题要求得到两和之差的最大值： 由图像可知，S(b) - S(a - 1) 即为f(x) 的最大值（类似前缀和）。

所以这里我们要求得S(a) 和 S(b)，所以，我们要得到求 S 的公式

S ( x ) S(x) S(x) = − ∑ 1 x x 2 + ( a + b ) ∑ 1 x x + ( a ∗ b ) ∑ 1 x 1 -displaystyle sum_{1}^{x}x^2 + (a + b)displaystyle sum_{1}^{x}x +(a * b)displaystyle sum_{1}^{x}1 −1∑x​x2+(a+b)1∑x​x+(a∗b)1∑x​1

分别求和

• ∑ 1 x x 2 displaystyle sum_{1}^{x}x^2 1∑x​x2：数学归纳法：
  
• ∑ 1 x x displaystyle sum_{1}^{x}x 1∑x​x：等差数列求和
• ∑ 1 x 1 displaystyle sum_{1}^{x}1 1∑x​1：即为 n

最后还需要注意一点：
由于本题需要对答案取模运算，且本题目的求和公式中包含除法取模操作，所以，不能直接取模，被除数直接乘上除数的乘法逆元即可与之等效。

求乘法逆元：由于本题的 mod 值是质数，所以我们可以用快速幂求逆元的方法求出乘法逆元

时间复杂度 O ( l o g n ) O(logn) O(logn)

#include 
#include 
#include 
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10,mod = 998244353;

ll qmi(ll a,ll b) 
{
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}
ll S(ll n,ll a,ll b)
{
    ll x = n * (n + 1ll) % mod * (2ll * n + 1ll) % mod * qmi(6,mod - 2) % mod;
    ll y = (a + b) * n % mod * (n + 1ll) % mod * qmi(2,mod - 2) % mod;
    ll z = a * b % mod * n % mod;
    ll res = (-x + y - z) % mod;
    res = (res + mod) % mod;
    return res;
}
int main()
{
    int t;
    cin >> t;
    while (t -- ) {
        ll a,b;
        cin >> a >> b;
        cout << (S(b,a,b) - S(a - 1,a,b) + mod) % mod << 'n';
    }
    return 0; 
}

点击此处查看对应的题目.
本题设计算法：递推 / 思维DP?

本题主要需要通过对比可能的数据，我们可以发现一下特点

• 每次走一步都必须比原来的数字+1
• dp[i] = dp[i - 1]/dp[i + 1] - a[i] 的规律（dp[i]表示从第 i 个点开始的最小初始值）

对比数据:
1 2 3 4 0
2 2 1 10 0
2 1 0 1 2

时间复杂度 O ( n ) O(n) O(n)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const ll N = 3e6 + 10,INF = 1e18;
ll a[N],dp[N];//dp[i]表示从第 i 个点开始的最小初始值

void solve()
{
    int n,idx;
    cin >> n;
    for (int i = 1;i <= n;i ++ ) {
        scanf("%lld",&a[i]);
        if (!a[i]) idx = i;
    }
    if (n == 1) {
        puts("No Solution");
        return;
    }
    for (int i = 1;i <= n + 5;i ++ ) dp[i] = INF; 
    for (int i = idx - 1;i >= 1; i -- ) {
        dp[i] = a[i] + 1;
        if (i != idx - 1) dp[i] = max(dp[i],dp[i + 1] - a[i]);
    }
    for (int i = idx + 1;i <= n;i ++ ) {
        dp[i] = a[i] + 1;
        if (i != idx + 1) dp[i] = max(dp[i],dp[i - 1] - a[i]);
    }
    ll res = INF;
    for (int i = 1;i <= n;i ++ ) res = min(res,dp[i]);
    cout << res << 'n';
}
int main()
{
    int t;
    cin >> t;
    while (t -- ) solve();
    return 0;
}