test21
摩尔县mex
首先 \(\text{mex} \{a_{l,\dots,r}\}\neq k\) 的条件是 \(\exists i\in [l,r],a_i=k\) 或者 \(\exists v\in [0,k),\forall a_i\neq v\)。所以我们修改的办法有两种， \((a_i<k)\to k\) 阻隔跨越左右的贡献，或者 \((a_i<k)\to (a_i\geq k)\) 来制造第二类阻碍。所以只 \((a_i<k)\to k\) 是对的， 那么不妨考虑 \(f_i\) 表示考虑到 \(i\) 时 \(a_i=k\) 的最小操作数，可转移的 \(j\) 满足 \(\text{mex}\{a_{j+1,\dots,i-1}\}\neq k\)，讨论一下。
- \(\exists u\in(j,i),a_u=k\)，设最后一个原始 \(k\) 在 \(pre\) 显然直接从那里转移最惹。
- \(\exists v\in[0,v),\forall u\in(j,i),a_u\neq k\)，这是一个后缀 \(j\in [l,i-1]\)，\(l\) 显然对每个 \(v\) 的 maxpos 取 \(\min\) 即可。不妨设 \(pre<l\)，那么注意到只从 \(l\) 转移不劣。
构造方案是显然的，考虑从哪里转移即可。特别的，对于 \(k>n\) 答案一定为 \(0\)，对于 \(k=0\) 需要 \(\forall a_i=0\) 因为前面的做法依托于 \(v\) 的存在也需要特判。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)using namespace std;const int N=100005;int Pluto, T, n, k, a[N], f[N], g[N], lst[N], pre[N], suf[N];void mian() {cin >> n >> k, a[0]=a[n+1]=k;up(i,1,n) cin >> a[i];if(k>n) {cout << 0 << '\n';up(i,1,n) cout << a[i] << ' '; cout << '\n';return;}if(k==0) {int cnt=0;up(i,1,n) cnt+=(a[i]>0);cout << cnt << '\n';up(i,1,n) cout << 0 << ' '; cout << '\n';return;}int j=n+1, pos=0;up(i,0,k-1) lst[i]=0;up(i,1,n) if(a[i]<k) pre[i]=lst[a[i]], lst[a[i]]=i;up(i,0,k-1) j=min(j,lst[i]);dn(i,n+1,1) {if(a[i]<k) j=min(j,pre[i]);suf[i]=j;}up(i,1,n+1) {j=suf[i];if(pos>j) f[i]=f[pos]+(a[i]!=k), g[i]=pos;else f[i]=f[j]+(a[i]!=k), g[i]=j;if(a[i]==k) pos=i;}for(int i=g[n+1]; i; i=g[i]) a[i]=k;cout << f[n+1] << '\n';up(i,1,n) cout << a[i] << ' '; cout << '\n';
}signed main() {
// freopen("1.txt","r",stdin);freopen("mex.in","r",stdin);freopen("mex.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> Pluto >> T;while(T--) mian();return 0;
}
亿万富翁richest
设一个集合 \(S\) 的平均数为 \(mid\)，严格更大/小的集合为 \(l/r(L=|l|,R=|r|)\)，合法条件等价于 \(\frac{1}{L}\sum (l_i-mid)<\frac{1}{R}\sum(mid-r_i)\)，化简就是 \(\frac{\sum l_i}{L}+\frac{\sum r_i}{R}<2mid\)，意思是 \(l,r\) 的绝对大小不影响答案，在这个前提下尽量少拿肯定是不劣的，可以理解成加多余的只会让 \(l/r\) 的极值去极端化。那么判定拿两个大的一个小的是不是都合法即可， \(|S|=3\) 的情况，不妨设 \(a\geq b>c\)，那么要求 \(b>\frac{a+b+c}{3}>c\)，转化一下就是 \(a-b\geq b-c\)。考虑一个贪心，枚举 \(\min\{a_i'\}\) 之后从小到大尽量多选，注意到差值倍增可以二分暴力求出方案。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)using namespace std;const int N=100005;int Pluto, T, len, n, m, a[N], b[N], ans;void mian() {cin >> n, ans=n;up(i,1,n) cin >> a[i];sort(a+1,a+1+n);up(l,1,n-1) {
// cout << "Round " << l << "\n"; int res=n-2, r=l+1, p;while((p=lower_bound(a+r+1,a+1+n,2*a[r]-a[l])-a)<=n) --res, r=p;ans=min(ans,res);}
// up(i,1,m) cout << b[i] << ' '; cout << '\n';cout << ans << '\n';
}signed main() {
// freopen("1.txt","r",stdin);freopen("richest.in","r",stdin);freopen("richest.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> Pluto >> T;while(T--) mian();return 0;
}
众字母letter
这个不是 lyq 的 SAO 嘛，再问一遍原出题人为什么这个不出成交互啊真的好误导人 /fad
找出第一/最后的 \(a\) 是容易的，之后判断一下一个很明显的充分条件能不能在前缀/后缀成为 \(a\) 的新贡献，然后注意到如果不能的话左右众数一定都不是 \(a\)，判断一下不和两边贡献相等即可。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)using namespace std;const int N=1005;int id, T, n, f[N][N], l, r, tag[N];void mian() {memset(tag,0,sizeof(tag));memset(f,0,sizeof(f));cin >> n, l=1, r=n;up(i,1,n) up(j,i,n) cin >> f[i][j];while(f[1][n]==f[l+1][n]) ++l;while(f[1][n]==f[1][r-1]) --r;tag[l]=tag[r]=1;up(i,l+1,r-1) { if(f[l][i]==f[l+1][i]+1&&f[l][i]==f[l][i-1]+1) tag[i]=1;if(f[i][r]==f[i][r-1]+1&&f[i][r]==f[i+1][r]+1) tag[i]=1;if(f[l+1][i-1]==f[l][i]&&f[i+1][r-1]==f[i][r]) tag[i]=1;}up(i,1,n) if(tag[i]) cout << i << ' '; cout << '\n';
}signed main() {freopen("letter.in","r",stdin);freopen("letter.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cin >> id >> T;while(T--) mian();return 0;
}染色color
考虑从大往小染，发现不在原序列上连着的区间只要缝隙里面都被染色就可以少染一次。哦那考虑每一个缝隙中有没有更小的颜色，有的话成为坏的缝隙。想要知道答案只需要计算中间夹着的坏的缝隙数和颜色种类数就好了，这是两个超级经典的问题。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pii pair<int,int>
#define mp make_pairusing namespace std;const int N=500005;int id, n, m, len, q, a[N], sp[N], lst[N], tr[N], Ans[N], stk[N], top;
struct QUR { int l, r, id; } cha[N];
pii u[N];inline void add(int x,int v) {for( ; x<=n; x+=x&-x) tr[x]+=v;
}inline int ask(int x) {int res=0;for( ; x; x-=x&-x) res+=tr[x];return res;
}signed main() {freopen("color.in","r",stdin);freopen("color.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cin >> id >> n >> q;up(i,1,n) cin >> a[i], sp[++m]=a[i];sort(sp+1,sp+1+m), m=unique(sp+1,sp+1+m)-sp-1;up(i,1,n) a[i]=lower_bound(sp+1,sp+1+m,a[i])-sp;up(i,1,q) cha[i].id=i, cin >> cha[i].l >> cha[i].r;sort(cha+1,cha+1+q,[](QUR A,QUR B){return A.r<B.r;});int j=1;up(i,1,n) {if(lst[a[i]]) add(lst[a[i]],-1);add(lst[a[i]]=i,1);while(j<=q&&cha[j].r==i) {Ans[cha[j].id]+=ask(i)-ask(cha[j].l-1);++j;}}up(i,1,m) lst[i]=0;up(i,1,n) {while(top&&a[stk[top]]>=a[i]) --top;if(lst[a[i]]&&stk[top]>lst[a[i]]) u[++len]=mp(lst[a[i]],i);stk[++top]=i, lst[a[i]]=i;}sort(u+1,u+1+len,[](pii A,pii B){return A.second<B.second;}); memset(tr,0,sizeof(tr));j=1;up(i,1,q) {while(j<=len&&u[j].second<=cha[i].r) {add(u[j].first,1);++j;}Ans[cha[i].id]+=ask(n)-ask(cha[i].l-1);}up(i,1,q) cout << Ans[i] << '\n';return 0;
}