集训
\(\texttt{2024 / 6 / 1 NOIP}\) 模拟赛
\(Rk9\)，分数 \(100+40+0+16=156.\)
\(T1\) 直接 \(30min\) 秒了，树剖调都没怎么调。
\(T2\) 上来就发现了一些性质，然后 \(1h\) 后就想出来了正解，然后开调。
但是可持久化线段树太过难写，最后发现还要两棵。
我甚至只知道可持久化线段树的原理，代码忘完了。
然后就写了 \(3h.\)
最后没写出来，但是也接近了。甚至还要维护一堆操作。怒不可遏！
代码 \(60\) 行，我调试 \(30\) 行，醉了。
主席树二分，哼哼哼哼哼！！！
不过刘彻的写法确实很是聪明。
\(\color{orange}\texttt{A}\)
考虑 \(LCA\) 之后判断，分类讨论即可。证明显然
彻证 ——— 刘彻
\(\color{orange}\texttt{B}\)
点一下就进题目。
考虑用线段树去掉最小数，直到没有小于 \(0\) 的数。
在删除一个数的时候，把那个数改成 \(+\infty\)，然后后面的数集体 \(-1.\)
以此类推。在第二轮的时候，还原线段树。
用栈记录每轮修改的数。
清栈显然是 \(\mathcal{O(1)}\) 的。
程式
#include <bits/stdc++.h>
#define ll long long
#define ls (u<<1)
#define rs (u<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,r
#define mid ((l+r)>>1)
#define file "book"
using namespace std;
const int N=5e5+10,inf=0x3f3f3f3f;
int n,d,cnt,a[N],st[N];
struct sgt{
int mn[N],ps[N],tg[N];
inline void pu(int u){if(mn[ls]>mn[rs])mn[u]=mn[rs],ps[u]=ps[rs];else mn[u]=mn[ls],ps[u]=ps[ls];}
inline void p(int u,int x){mn[u]+=x,tg[u]+=x;}
inline void pd(int u){if(tg[u])p(ls,tg[u]),p(rs,tg[u]),tg[u]=0;}
inline void upd(int u,int l,int r,int L,int R,int k){
if(R<L)return;
if(L<=l&&r<=R)return p(u,k);pd(u);
if(L<=mid)upd(lson,L,R,k);
if(R> mid)upd(rson,L,R,k);pu(u);
}
inline void bd(int u,int l,int r){
if(l==r)return ps[u]=l,mn[u]=a[l],void();
bd(lson),bd(rson),pu(u);
}
}t;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>d>>n;
for(int i=1;i<=n;++i)cin>>a[i];
t.bd(1,1,n);
for(int i=1;i<=n+1;++i){
int top=0;
if(i==n+1)return cout<<-1<<"\n",0;
for(;t.mn[1]<=0;){
int p=t.ps[1];
t.upd(1,1,n,p+1,n,-1),t.upd(1,1,n,p,p,inf),st[++top]=p,++cnt;
}
if(cnt==n)return cout<<i<<"\n",0;
for(int j=1;j<=top;++j)t.upd(1,1,n,st[j]+1,n,1);
t.upd(1,1,n,1,n,-top);
}
return 0;
}
\(\texttt{2024 / 5 / 2 NOIP}\) 模拟赛
\(90+85+0+45= 220\)
本来应该 \(100+100+15+45=260\) 的，这样的成绩是我彩笔导致的。
\(A\) 题前缀异或桶，开考半个小时就将之秒掉了，但是没开 \(\texttt{long long}\) 挂掉了 \(10pts.\) 非常生气。
\(\texttt{B}\)
思维题。
给一个 \(a_i(i=1,2,3,\cdots,n).\)
进行无数次下面两种操作：
-
在端点处删除一个数
-
在不是端点处将 \(a_{i-1},a_i,a_{i+1} \rightarrow a_{i-1}+a_{i+1}\)
直到只剩下一个数。最大化这个数的值并且操作次数最小。输出这两个值。
有发现：
在进行一次 \(2\) 操作之后，如果将池子里面的数重新编号，那么新加进来的数是 \(i-1\) 号，往后两位应该是 \(i,i+1\)。
显然奇偶性没有发生改变。那么考虑对奇偶拆开统计。
如果是负数不要，否则加进来。
只要把偶数位置上的正数求和，把奇数位置上的正数求和，得到 \(R_1,R_2\)，最后的答案就是 \(\max\{R_1,R_2\}.\)
操作次数：只要分开来统计一下就好了。
最后要特判一下全是负数的情况。取绝对值最小的那个负数就好了。
复杂度 \(\mathcal{O(n)}.\)
\(\texttt{C}\)
有两个序列 \(\{a_n\},\{b_n\}.\) 两个序列都是单调不降的。要让 \(\{a\}\) 变成 \(\{b\}\)，可以将 \(a \rightarrow a+x\)，代价是 \(x^2\)。在 \(\{a\}\) 时时刻刻单调不降的前提下使代价最小。
发现最后一句话的限制实际上是没有任何用处的。原因是可以调换增减顺序。
又发现我们所关注的不见得是 \(a_i,b_i\) ，而是差值 \(|a_i-b_i|.\)
要将 \(a_i\) 变作 \(b_i\) 并且消耗 \(m\) 刀，可以考虑平均下来每次的代价。
计算如下：
显然，\(f(x,y)\) 是随着 \(y\) 的增大而减小的。但是每一刀放在每个数身上减小是不同的。所以可以考虑用堆来维护。
思路类似于 \(P5283\) [十二省联考 2019] 异或粽子，其实还是比较巧妙的
程式
#include <bits/stdc++.h>
#define int long long
#define mod 998244353
#define file "attend"
using namespace std;
typedef __int128 lint;
typedef pair<lint,int> pii;
typedef priority_queue<pii> Pq;
Pq pq;
const int N=1e5+10;
lint f(int x,int y){ return (lint)(x/y)*(x/y)*(y-x%y)+(lint)(x/y+1)*(x/y+1)*(x%y); }
int n,m;
int cnt;
int a[N],b[N],v[N],p[N];
lint ans;
signed main(){
freopen(file ".in","r",stdin);
freopen(file ".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin>>n>>m;
for(register int i=1;i<=n;++i) cin>>a[i];
for(register int i=1;i<=n;++i) cin>>b[i],v[i]=abs(a[i]-b[i]) %mod;
for(register int i=1;i<=n;++i) cnt+=(a[i]!=b[i]),ans=ans+v[i]*v[i] %mod,p[i]=1;
if(m<cnt) return puts("-1"),0;
m-=cnt;
for(int i=1;i<=n;++i) if(v[i]>=2ll) pq.push(make_pair(f(v[i],1ll)-f(v[i],2ll),i));
while(!pq.empty()&&m){
m--;
int x=pq.top().second;
ans=(ans-pq.top().first) %mod;
p[x]++, pq.pop();
if(p[x]<v[x]) pq.push(make_pair((int)f(v[x],p[x])-(int)f(v[x],p[x]+1ll),x));
}
return printf("%lld",(int)((ans+mod) %mod)),0;
}
\(\texttt{2024 / 5 / 1 NOIP}\) 模拟赛
\(A\) 觉得很弱小的字符串， \(Trick\) 也比较明显。
\(\texttt{B}\)
神仙题。
输入 \(n\) 个数 \(\{a\}\)，问在 \(\{a\}\) 中，每个 \(a_i\) 至多可以减去 \(k\)（不能减成 \(0\) ），至多删去 \(f\) 个数，求最后合法的公约数 \(g\) 的全部方案。
60
考虑如果 \(g\) 是 \(a_i\) 的约数，那么 \(a_i-k=cg\ (c\in N).\)
而 \(k\) 已经给定，所以当且仅当 \(cg \leq a_i \leq cg+k\) 才行，也就是 \(a_i \bmod g \leq c.\)
计算 \(a_i\bmod g >c\) 这样的 \(a_i\) 数量，最后与 \(f\) 比较就好了。
100
考虑一种可以快速统计值出现在 \(l,r\) 的数的个数的方法。显然可以桶 \(+\) 前缀和处理。
而枚举提到的 \(d=cg\) ，然后统计出现在 \(d+k+1,d+g-1\) 的数的个数，最后与 \(f\) 比较就好了。
而 \(d\) 枚举次数出现在 \(n/1,n/2,n/3,\cdots,n/n\)，加起来是调和级数，最后复杂度明显是 \(\mathcal{O[T(\alpha\log \alpha+n)]}.\) 足以通过本题。
程式
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int T,n,k,f,maxi=0,dlt,ans;
int a[N],t[N],q[N];
inline int re(void){
int res=0; char ch=0;
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48), ch=getchar();
return res;
}
int main(){
freopen("tsuki.in","r",stdin);
freopen("tsuki.out","w",stdout);
T=re();
while(T--){
maxi=0;
memset(t,0,sizeof t);
memset(q,0,sizeof q);
n=re(),k=re(),f=re();
for(int i=1;i<=n;++i) a[i]=re(),t[a[i]]++,maxi=max(maxi,a[i]);
for(int i=1;i<=maxi;++i) q[i]=q[i-1]+t[i];
for(int g=1;g<=maxi;++g){
dlt=q[g-1];
for(int i=g;dlt<=f&&i+k+1<=maxi;i+=g) {
int l=i+k+1,rgt=min(maxi,i+g-1);
if(l<=rgt) dlt+=q[rgt]-q[l-1];
}
if(dlt<=f) printf("%d ",g);
}
puts("");
}
return 0;
}
觉得这种东西在考场上根本不能想到耶。