hgoi#20190808
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;
}