T1- 最大子段和

给定一个数组，求 $ \sum_{i=A}^B{a_i}+\sum_{i=C}^D{a_i}(1\leq A\leq B< C\leq D\leq n)$ 的最大值

解法

求出 $fl_i$ 表示 1 到 i 的最大子段和，$fr_i$ 表示 i 到 n 的最大子段和 然后枚举断点即可

ac 代码

#include<bits/stdc++.h>
#define ll long long
#define N 100000
#define MAXN N+10
using namespace std;
template<typename T>void read(T &x)
{
    ll f=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-f;
    for(;isdigit(c);c=getchar())x=x*10+c-'0';
    x*=f;
}
ll n,ans,a[MAXN],fl[MAXN],fr[MAXN];
int main()
{
    freopen("sum.in","r",stdin),freopen("sum.out","w",stdout);
    read(n);
    for(ll i=1;i<=n;i++)read(a[i]);
    for(ll i=1;i<=n;i++)fl[i]=max(fl[i-1]+a[i],a[i]);
    for(ll i=n;i>=1;i--)fr[i]=max(fr[i+1]+a[i],a[i]);
    for(ll i=1;i<=n;i++)fl[i]=max(fl[i-1],fl[i]);
    for(ll i=n;i>=1;i--)fr[i]=max(fr[i+1],fr[i]);
    for(ll i=1;i<n;i++)ans=max(fl[i]+fr[i+1],ans);
    printf("%lldn",ans);
    return 0;
}

T2- 序列

一个长度为 n 的初始为 0 的序列，m 次操作 每次操作对区间 $[l,r]$ 加上一个首项为 s，末项为 e 的等差数列 保证等差数列都是整数

解法

分别差分首项末项以及公差 注意公差差分在 l + 1 与 r +1

ac 代码

#include<bits/stdc++.h>
#define ll long long
#define N 500000
#define MAXN N+10
using namespace std;
template<typename T>void read(T &x)
{
    ll f=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar())if (c=='-')f=-f;
    for(;isdigit(c);c=getchar())x=x*10+c-'0';
    x*=f;
}
ll n,m,l,r,st,ed,nw,ans,s[MAXN],k[MAXN];
int main()
{
    freopen("sequence.in","r",stdin),freopen("sequence.out","w",stdout);
    read(n),read(m);
    for(ll i=1;i<=m;i++)
    {
        read(l),read(r),read(st),read(ed);
        s[l]+=st,s[r+1]-=ed;
        k[l+1]+=(ed-st)/(r-l),k[r+1]-=(ed-st)/(r-l);
    }
    for(ll i=1;i<=n;i++)k[i]+=k[i-1],nw+=s[i]+k[i],ans^=nw;
    printf("%lldn",ans);
    return 0;
}

T3- 余数

给定 n，求 n 的全排列中，相邻两种排列不同数字的个数和

解法

$f_i$ 表示 i 的全排列的答案 可以递推，发现 $f_i$ 中有 $ i*f_{i-1} $ 剩余的就是组间的贡献
如果是奇数，组间全部不同，即 $ i*(i-1) $
如果是偶数，除一二组全部不同外，其余两组之间有一个相同，即 $ i*(i-1)-(i-2) $
综合下来就是 $ f_i=i*f_{i-1}+i*(i-1)-(i \mod 2 ? 0 : i-2) $

ac 代码

#include<bits/stdc++.h>
#define ll long long
#define N 10000000
#define MAXN N+10
using namespace std;
template<typename T>void read(T &x)
{
    ll f=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-f;
    for(;isdigit(c);c=getchar())x=x*10+c-'0';
    x*=f;
}
ll T,n,p,dp[MAXN];
void solve(){for(ll i=1;i<=n;i++)dp[i]=((dp[i-1]+i-1)*i-((i%2)?(0):(i-2)))%p;}
int main()
{
    freopen("mod.in","r",stdin),freopen("mod.out","w",stdout);
    read(T);
    while(T--)read(n),read(p),solve(),printf("%lldn",dp[n]);
    return 0;
}

T4- 合并果子

n 个柠檬，初始 1 个柠檬 1 堆 m 次操作，合并 2 堆柠檬或将 1 堆柠檬中每个柠檬榨 x 毫升汁 求出每个柠檬被榨汁毫升数

解法

将柠檬看做森林，每次合并就是将两棵树并到一个新节点上 榨汁操作就是在这棵树的根节点上加上 x 最后做一遍树上前缀和

ac 代码

#include<bits/stdc++.h>
#define N 500000
#define MAXN (N<<1)
using namespace std;
template<typename T>void read(T &x)
{
    int f=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-f;
    for(;isdigit(c);c=getchar())x=x*10+c-'0';
    x*=f;
}
struct node{int to,next;}e[MAXN];
int n,m,opt,x,y,cnt,ret,f[MAXN],ans[MAXN],head[MAXN],used[MAXN];
void add(int from,int to){e[++cnt]={to,head[from]},head[from]=cnt,f[to]=f[from];}
int find(int u){return (f[u]==u)?(u):(f[u]=find(f[u]));}
void dfs(int u)
{
    used[u]=1;
    for(int i=head[u];i;i=e[i].next)
        ans[e[i].to]+=ans[u],dfs(e[i].to);
}
void solve(){for(int i=1;i<=ret;i++)if(!used[i])dfs(find(i));}
int main()
{
    freopen("merge.in","r",stdin),freopen("merge.out","w",stdout);
    read(n),read(m),ret=n;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++)
    {
        read(opt),read(x),read(y);
        if(opt==1)
        {
            if(find(x)==find(y))continue;
            f[++ret]=ret,add(ret,f[x]),add(ret,f[y]);
        }
        else ans[find(x)]+=y;
    }
    solve();
    for(int i=1;i<n;i++)printf("%d ",ans[i]);
    printf("%dn",ans[n]);
    return 0;
}