T1 缺少的数

$\color{green}{\mathcal{AcWing}}$

非常简单但是比较有趣的一道题，看完题目和数据范围后第一时间想到可以开一个桶，一开始读入每个数标记其对应下标，然后遍历一遍找出缺少的数，但其实还可以优化得更简单，由于是$1\sim n$中少了一个数，而$1\sim n$所有数的和很好求，为$\cfrac{n(n+1)}{2}$，因此可以先根据$n$求出$1\sim n$所有数的和，然后再减去所有出现了的$(n-1)$个数，最后就可以得出缺少的数是哪个了。

运行时间： 40 ms

运行空间： 220 KB

#include <iostream>

using namespace std;

inline void speedup(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main(){
    speedup();
    int n;
    long long sum=0;
    cin>>n;
    for (int i=0;i<n-1;i++){
        int tmp;
        cin>>tmp;
        sum+=tmp;
    }
    cout<<(long long)n*(n+1)/2-sum<<endl;
    return 0;
}

T2 选区间

$\color{green}{\mathcal{AcWing}}$

一眼贪心，但是实现起来有一定难度：首先显而易见的，想要取得最大值，肯定是两个尽量隔得远的最左和最右或最右和最左值之差，所以可以分辨计算两种区间各自的左右最大最小值，然后再判断是否可行并取得最终结果的最大值。

运行时间： 319 ms

运行空间： 8028 KB

#include <iostream>
#include <cmath>

using namespace std;

const int INF=0x3f3f3f3f;

inline void speedup(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main(){
    speedup();
    int n,m,ans=0;
    int axl=0,axr=0,anl=INF,anr=INF;
    int bxl=0,bxr=0,bnl=INF,bnr=INF;
    cin>>n;
    while (n--){
        int l,r;
        cin>>l>>r;
        axl=max(axl,l);
        axr=max(axr,r);
        anl=min(anl,l);
        anr=min(anr,r);
    }
    cin>>m;
    while (m--){
        int l,r;
        cin>>l>>r;
        bxl=max(bxl,l);
        bxr=max(bxr,r);
        bnl=min(bnl,l);
        bnr=min(bnr,r);
    }
    if (bxl>anr) ans=max(ans,abs(bxl-anr));
    if (axl>bnr) ans=max(ans,abs(axl-bnr));
    cout<<ans<<endl;
    return 0;
}

T3 选元素

$\color{green}{\mathcal{AcWing}}$

注意到只需要输出所有$x$个元素之和，不用输出具体是哪$x$个元素（无后效性），再结合题目里的一些别的信息和加以尝试可以知道此题采用dp做最好：

$$状态表示：dp[i][j]表示在前i个数中选j个数保证满足题目条件的所有集合$$

$$状态计算：dp[i][j]=max(dp[i][j],dp[t][j-1]+a[i]),i-k\leqslant t<i$$

$$（t表示选择的上一个点（选择的第j-1个点），由于连续子序列的长度为k，为保证全部覆盖到，两个点之间的距离不应大于k，所以t的取值范围在i-k到i-1之间）$$

$$Base Case：f[0][0]=0$$

记得开long long！！！

时间复杂度：$\mathcal{O}(n^3)$

运行时间： 22 ms

运行空间： 604 KB

#include <iostream>
#include <cstring>

using namespace std;

int a[210];
long long dp[210][210];

inline void speedup(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main(){
    speedup();
    int n,k,x;
    cin>>n>>k>>x;
    for (int i=1;i<=n;i++) cin>>a[i];
    memset(dp,-0x3f,sizeof(dp));
    dp[0][0]=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=x;j++)
            for (int t=max(i-k,0);t<i;t++) //小心越界
                dp[i][j]=max(dp[i][j],dp[t][j-1]+a[i]);
    long long ans=-1;
    for (int i=n-k+1;i<=n;i++) ans=max(ans,dp[i][x]);
    cout<<ans<<endl;
    return 0;
}

T4 K倍区间

$\color{green}{\mathcal{AcWing}}$

注意到题目中问的是关于区间和的问题，可以想到利用前缀和求解：如果一个区间[i,j]的数字和是k的倍数，则有$(pre[j]-pre[i-1])%k==0$ $\Rightarrow$ $pre[j]%k==pre[i-1]%k$，所以可以考虑求出所有的前缀和模$k$的值，然后算出余数为$0$的（前缀和直接就是$k$倍区间）以及余数相同的总个数即为答案。计算相同的余数的前缀和组的个数有很妙的方法：用一个数组记录当前的每种余数有多少个前缀和，然后之后一次次去更新答案和更新余数数组。

运行时间： 70 ms

运行空间： 2008 KB

#include <iostream>

using namespace std;

int a[100010],pre[100010],rem[100010];

inline void speedup(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main(){
    speedup();
    int n,k;
    long long ans=0;
    cin>>n>>k;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=n;i++) pre[i]=(pre[i-1]+a[i])%k; //初始化前缀和，记得取模 
    for (int i=0;i<=n;i++){
        ans+=rem[pre[i]]; //和前面所有前缀和模k的余数为pre[i]的区间构成符合条件的区间，更新答案 
        rem[pre[i]]++; //更新前缀和模k的余数为pre[i]的区间数
    }
    cout<<ans<<endl;
    return 0;
}