2023暑假集训杂题解题报告
UOJ NOI Round #7 Day1 那些你不要的
题目描述
给定长度为 \(n\) 的序列 \(A\)，保证 \(n\) 为奇数，你是先手，每次先手与后手分别取相邻的 \(2\) 个数，并将剩下的数合并。先手希望最后剩下的数最大，后手希望剩下的数最小，在最优策略下，最后剩下的数是多少？
题目分析
发现操作是对于相邻的元素进行的，可以想到对序列进行黑白染色。一次操作相当于删除一个黑色元素与一个白色元素，故偶数位的元素最后一定会被删完，所以只需要考虑奇数位的元素。奇数位元素是相互独立的，故答案就是奇数位元素的中位数。
JOISC 2022 Day4 鱼2
题目描述
定义对于长度为 \(n\) 的序列 \(A\) 的一次实验为：对于两只相邻的鱼 \(x\) 与 \(y\)，若 \(A_x \le A_y\) 那么鱼 \(y\) 可以吃掉鱼 \(x\)，若鱼 \(y\) 吃掉了鱼 \(x\)，那么 \(A_y=A_y+A_x\)。经过 \(n-1\) 次这样的操作，最后会剩下一条鱼 \(E\)。定义一个实验的结果为 \(E\) 不同的取值数量，即最后可能活下来的鱼的种类数。现在你有一长度为 \(n\) 的序列 \(a\)，需要支持一下两个操作：
-
将某个数 \(a_x\) 改变为 \(y\)。
-
询问区间 \(L\) 到 \(R\) 的子串的实验结果。
题目分析
考虑对长度为 \(n\) 的序列 \(A\) 进行实验。
若鱼 \(x\) 可以存活，其充要条件为：在任意时刻，鱼 \(x\) 可以吃掉它左右两边至少一边的鱼。
假设鱼 \(x\) 贪心的尽量将左右两边能吃的鱼全部吃掉后，能吃掉的区间为 \(L_x\) 到 \(R_x\)。考虑 \(L_x\) 的不同的取值个数。则有 \(\sum_{i=L_x}^{R_x} A_i < A_{L_x-1}\) 那么不同的 \(L_x\) 的取值只有 \(\log(|A|)\) 个。同理可得，不同的 \(R_x\) 的个数同样只有 \(\log(|A|)\) 个。
回到原问题，因为是区间查询，考虑使用线段树维护。因为我们只需要最后能存活的鱼的信息，故在线段树上，不需要维护 \(L_x\) 与 \(R_x\) 都在段内的鱼，所以我们维护左端点从 \(L_x\) 开始，当前右端点为整段右端点的鱼以及右端点从 \(R_x\) 开始，当前左端点为整段左端点的鱼。
考虑怎么合并区间的信息。不难发现，合并后的区间的 \(L_x\) 与 \(R_x\) 一定为子区间的子集。所以可以使用双指针进行合并。
时间复杂度 \(O(n \log^2(n))\) 。
代码实现
#include<bits/stdc++.h>
#define ll long long
#define inf vector<node>
using namespace std;
template <typename T> inline void read(T &x)
{
x=0;T f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-')f=-1;
for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x*=f;
}
template <typename T,typename ...Args>void read(T &x,Args&...args){read(x),read(args...);}
template <typename T> void print(T x)
{
if(x<0) x=-x,putchar('-');
if(x>9) print(x/10);
putchar(x%10+48);
}
template <typename T> void print(T x,char c){print(x); putchar(c);}
template<typename T>inline void output(T x){print(x,' ');}
template<typename T,typename ...Arg>inline void output(T x,Arg ...arg){output(x);output(arg...);}
const int N=100007;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,q,a[N];
struct node{ll sum,val;int num;};
struct segment_tree
{
#define ls (rt<<1)
#define rs (rt<<1|1)
inf fl[N<<2],fr[N<<2];
pair<inf,inf>merge(inf Ll,inf Lr,inf Rl,inf Rr)
{
ll suml=Ll.back().sum,sumr=Rl.back().sum,il=0,ir=0,tot=0;
Ll.pop_back(); Rr.pop_back();
vector<pair<ll,int>>vct;
for(auto x:Rl) if(x.val>suml)
Ll.push_back((node){x.sum+suml,x.val-suml,0});
for(auto x:Lr) if(x.val>sumr)
Rr.push_back((node){x.sum+sumr,x.val-sumr,0});
for(;il<Lr.size();il++)
{
tot+=Lr[il].num;
while(ir<Rl.size()&&Rl[ir].val<=Lr[il].sum) ir++;
if(Lr[il].val>Rl[ir].sum)
{
if(ir==Rl.size()-1)
vct.push_back({Lr[il].sum+sumr,tot});
if(il==Lr.size()-1) for(auto &it:Ll)
if(it.sum==Rl[ir].sum+suml) it.num+=tot;
tot=0;
}
}
for(int i=Rr.size()-1;i>=0;i--)
if(vct.size()&&Rr[i].sum==vct.back().first)
Rr[i].num+=vct.back().second,vct.pop_back();
for(il=0,ir=0;ir<Rl.size();ir++)
{
tot+=Rl[ir].num;
while(il<Lr.size()&&Lr[il].val<=Rl[ir].sum) il++;
if(Rl[ir].val>Lr[il].sum)
{
if(il==Lr.size()-1) vct.push_back({Rl[ir].sum+suml,tot});
if(ir==Rl.size()-1) for(auto &it:Rr)
if(it.sum==Lr[il].sum+sumr) it.num+=tot;
tot=0;
}
}
for(int i=Ll.size()-1;i>=0;i--)
if(vct.size()&&Ll[i].sum==vct.back().first)
Ll[i].num+=vct.back().second,vct.pop_back();
return make_pair(Ll,Rr);
}
pair<inf,inf>merge(pair<inf,inf>L,pair<inf,inf>R){return merge(L.first,L.second,R.first,R.second);}
void pushup(int rt)
{
auto res=merge(fl[ls],fr[ls],fl[rs],fr[rs]);
fl[rt]=res.first,fr[rt]=res.second;
}
void init(int rt,int x)
{
fl[rt].clear(); fr[rt].clear();
fl[rt].push_back((node){0,x,0});
fl[rt].push_back((node){x,INF,1});
fr[rt].push_back((node){0,x,0});
fr[rt].push_back((node){x,INF,1});
}
void build(int rt,int l,int r)
{
if(l==r) return init(rt,a[l]);
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(rt);
}
void update(int rt,int l,int r,int p,int x)
{
if(l==r) return init(rt,x);
int mid=(l+r)>>1;
if(p<=mid) update(ls,l,mid,p,x);
else update(rs,mid+1,r,p,x);
pushup(rt);
}
pair<inf,inf>ask(int rt,int l,int r,int L,int R)
{
if(L<=l&&r<=R) return make_pair(fl[rt],fr[rt]);
int mid=(l+r)>>1;
if(L<=mid&&R>mid) return merge(ask(ls,l,mid,L,R),ask(rs,mid+1,r,L,R));
if(L<=mid) return ask(ls,l,mid,L,R);
else return ask(rs,mid+1,r,L,R);
}
#undef ls
#undef rs
}Tree;
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(a[i]);
read(q); Tree.build(1,1,n);
for(int i=1,opt,l,r;i<=q;i++)
{
read(opt,l,r);
if(opt==1) Tree.update(1,1,n,l,r);
else print(Tree.ask(1,1,n,l,r).first.back().num,'\n');
}
return 0;
}
CEOI 2018 斐波那契表示法
题目描述
给定长度为 \(n\) 的序列 \(a\)。对于每个 \(i\) 询问 \(X=\sum_{j=1}^{i} fib(a_i)\) 表示为若干个不同的斐波那契数的和的方案数。其中 \(fib(i)\) 表示斐波那契数列的第 \(i\) 项。即 \(fib(1)=1\)，\(fib(2)=2\)，\(fib(i)=fib(i-1)+fib(i-2)\)。
题目分析
设数 \(X\) 的任意一种表示方法为 \(\sum fib(c_i)\) 其不同表示方法有两种产生方式：
-
若存在 \(c_i=c_j+1\) 则可合并 \(c_i\) 与 \(c_j\) 形成 \(c_i+1\)。
-
若存在 \(c_i > 2\) 则可以拆分 \(c_i\) 形成 \(c_i - 1\) 与 $c_i -2 $。
考虑先一直使用方法 \(1\) 合并 \(c\) 形成新的表示方法 \(X=\sum fib(d_i)\)。可以证明 \(d_i\) 互不相同。证明详见 Zeckendorf表达。
考虑拆分 \(d_i\) 。发现有如下性质：
- 若存在 \(d_i=d_j+1\) 那么 \(d_i\) 一定不能拆解。
证明：
若 \(d_i\) 拆解则有 \(1\) 个 \(d_i-2\) 与 \(2\) 个 \(d_i-1\) 。因为必须使用不同的数，所以至少需要拆解 \(1\) 个 \(d_i-1\)。拆解后即有 \(1\) 个 \(d_i-3\) 与 \(2\) 个 \(d_i-2\) 与 \(1\) 个 \(d_i-1\) 变为原问题，故可归纳证明，不可拆解 \(d_i\) 。
- 若存在至少 \(3\) 个 \(d_i\) 无论经过多少次拆分，一定不合法。
证明：
若存在 \(3\) 个 \(d_i\) 则至少需要拆解 \(2\) 个，即拥有 \(2\) 个 \(d_i-1\) 与 \(2\) 个 \(d_i-2\)，发现比上文更劣，故一定不合法。
根据性质 \(2\) 我们发现不论在什么中间状态，我们都最多只有 \(2\) 个 \(d_i\)。一个为原本 Zeckendorf表达 分解出的 \(d_i\) 一个为高位经过分解后退位下来的 \(d_i\)。
故我们可以设计出一个很简单的动态规划：
设 \(f[i][0/1]\) 表示考虑到 \(d_i\)，有无退位的 \(d_i\) 的方案数。转移根据发现的性质 \(1\) 可以做到只与 \(d_i - d_{i-1}\) 有关且为 \(O(1)\)。
总时间复杂度 \(O(n^2)\) 。
考虑动态规划第二维状态为 \(0/1\) 且转移只与 \(d_i - d_{i-1}\) 有关。可以使用自己喜欢的数据结构维护矩阵乘法即可优化到 \(O(n \log n k ^ 3)\)。
标签：rt,int,sum,back,fib,vct,2023,杂题,集训 From： https://www.cnblogs.com/slenbol/p/17556792.html