T1-最大子段和

给定一个数组，求\(\sum\limits_{i=A}^B{a_i}+\sum\limits_{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("%lld\n",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("%lld\n",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\mod2?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("%lld\n",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("%d\n",ans[n]);
    return 0;
}

hgoi#20190808

原文：https://www.cnblogs.com/muronglin/p/hgoi-20190808.html