T1 命令方块
打炸了。。难过。。
发现，按照字典序排序是一种合法方案。
std 的解释：
- 我们用这些字符串构建出一棵字典树，我们发现，按照字典树的任意一种 d f s dfs dfs 序输出字符串都可以获得一个合法的答案。
- 简单起见，我们直接按字典序输出字符串即可。因此，将所有字符串使用 std :: sort 排序即可。
因此，我们知道了每一个数的起始位置和终点位置，每次把数字 i i i 放到 i i i 位置即可。
考试的时候对于位置的处理挂了，又从 rank1 掉到了 rank7。。
时间复杂度 O ( n ) O(n) O(n)。
#include<bits/stdc++.h>
using namespace std;
namespace IO{
const int Rlen=1<<22|1;
char buf[Rlen],*p1,*p2;
inline char gc(){
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T Read(){
char c=gc();T x=0,f=1;
while(!isdigit(c)) f^=(c=='-'),c=gc();
while( isdigit(c)) x=((x+(x<<2))<<1)+(c^48),c=gc();
return f?x:-x;
}
inline int gi() {return Read<int>();}
inline string gs(){
char c=gc();string S="";
while(!isalpha(c)) c=gc();
while( isalpha(c)) S+=c,c=gc();
return S;
}
}
using IO::gi;
using IO::gs;
const int N=1e6+5;
int n,pos[N];
struct node{string S;int id;}p[N];
bool operator<(const node &p,const node &q) {return p.S<q.S;}
int cnt;
pair<int,int>rec[N];
int main(){
n=gi();
for(int i=1;i<=n;++i){
p[i].id=i,p[i].S=gs();
}
sort(p+1,p+n+1);
for(int i=1;i<=n;++i) pos[p[i].id]=i;
for(int i=1;i<=n;++i)
if(p[i].id!=i) rec[++cnt]=make_pair(i,pos[i]),pos[p[i].id]=pos[i],swap(p[i],p[pos[i]]);
printf("%d\n",cnt);
for(int i=cnt;i>=1;--i) printf("%d %d\n",rec[i].first,rec[i].second);
return 0;
}
T2 骨粉
首先看到我们要最小化最大值，不难想到二分，考虑怎么 c h e c k check check 二分出的答案 λ \lambda λ。
可以对 t i t_i ti 排序，然后每次 upper_bound 找到第一个 > s + λ >s+\lambda >s+λ 的数（其位置设为 p o s pos pos），现在要对 p o s ∼ n pos\sim n pos∼n 的植物用 ≤ s \le s ≤s 次骨粉使它们的 t i t_i ti 都 ≤ s + λ \le s+\lambda ≤s+λ。而让它们都满足条件需用的骨粉数是：
∑ i = p o s n ⌈ t i − s − λ x ⌉ \sum_{i=pos}^n\lceil\frac{t_i-s-\lambda}{x}\rceil i=pos∑n⌈xti−s−λ⌉
设 v = s + λ v=s+\lambda v=s+λ，那么可以试着化一下这个式子：
⌈ t i − v x ⌉ = ⌈ ( ⌊ t i x ⌋ + { t i x } ) − ( ⌊ v x ⌋ + { v x } ) ⌉ = ⌊ t i x ⌋ − ⌊ v x ⌋ + ⌈ { t i x } − { v x } ⌉ = ⌊ t i x ⌋ − ⌊ v x ⌋ + [ { t i x } > { v x } ] = ⌊ t i x ⌋ − ⌊ v x ⌋ + [ ( t i m o d x ) > ( v m o d x ) ] \begin{aligned} \lceil\frac{t_i-v}x\rceil&=\lceil(\lfloor\frac{t_i}x\rfloor+\{\frac{t_i}x\})-(\lfloor\frac{v}x\rfloor+\{\frac{v}x\})\rceil\\ &=\lfloor\frac{t_i}{x}\rfloor-\lfloor\frac{v}{x}\rfloor+\lceil\{\frac{t_i}x\}-\{\frac vx\}\rceil\\ &=\lfloor\frac{t_i}{x}\rfloor-\lfloor\frac{v}{x}\rfloor+[\{\frac{t_i}x\}>\{\frac vx\}]\\ &=\lfloor\frac{t_i}{x}\rfloor-\lfloor\frac{v}{x}\rfloor+[(t_i\bmod x)>(v\bmod x)] \end{aligned} ⌈xti−v⌉=⌈(⌊xti⌋+{xti})−(⌊xv⌋+{xv})⌉=⌊xti⌋−⌊xv⌋+⌈{xti}−{xv}⌉=⌊xti⌋−⌊xv⌋+[{xti}>{xv}]=⌊xti⌋−⌊xv⌋+[(timodx)>(vmodx)]
其中 { x } \{x\} {x} 的意思是保留 x x x 的小数部分。
发现 ∑ i = p o s n ⌊ t i x ⌋ \sum_{i=pos}^n\lfloor\frac{t_i}{x}\rfloor ∑i=posn⌊xti⌋ 可以预处理出后缀和然后 O ( 1 ) O(1) O(1) 算， ∑ p o s n ⌊ v x ⌋ \sum_{pos}^n\lfloor\frac{v}{x}\rfloor ∑posn⌊xv⌋ 也可以 O ( 1 ) O(1) O(1) 算。
对于最后的那个式子，记 m i = t i % x m_i=t_i\%x mi=ti%x 的话，相当于是求 ∑ i = p o s n [ m i > ( v m o d x ) ] \sum_{i=pos}^n[m_i>(v\bmod x)] ∑i=posn[mi>(vmodx)]，用主席树做即可。
时间复杂度 O ( m log 2 n ) O(m\log^2n) O(mlog2n)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace IO{
const int Rlen=1<<22|1;
char buf[Rlen],*p1,*p2;
inline char gc(){
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T Read(){
char c=gc();T x=0,f=1;
while(!isdigit(c)) f^=(c=='-'),c=gc();
while( isdigit(c)) x=((x+(x<<2))<<1)+(c^48),c=gc();
return f?x:-x;
}
inline int gi() {return Read<int>();}
inline ll gl() {return Read<ll >();}
}
using IO::gi;
using IO::gl;
const int N=1e5+5,M=N<<6;
int n,m;
ll x,a[N];
namespace PST{
int tot,root[M],lc[M],rc[M],sum[M];
#define mid ((l+r)>>1)
void Insert(int y,int &x,ll l,ll r,ll val){
x=++tot;
lc[x]=lc[y],rc[x]=rc[y],sum[x]=sum[y]+1;
if(l==r) return;
if(val<=mid) Insert(lc[y],lc[x],l,mid,val);
else Insert(rc[y],rc[x],mid+1,r,val);
}
int Query(int root,ll l,ll r,ll val){
if(val==x||(!root)) return 0;
if(l>=val) return sum[root];
if(val<=mid) return sum[rc[root]]+Query(lc[root],l,mid,val);
return Query(rc[root],mid+1,r,val);
}
#undef mid
}
using namespace PST;
ll suf[N],Mod[N];
bool check(ll S,ll mid){
int pos=upper_bound(a+1,a+n+1,S+mid)-a;
if(pos>n) return true;
ll num=S+mid,div=num/x,mod=num%x;
return (suf[pos]-div*(n-pos+1)+Query(root[pos],0,x-1,mod+1))<=S;
}
int main(){
n=gi(),m=gi(),x=gl();
for(int i=1;i<=n;++i) a[i]=gl();
sort(a+1,a+n+1);
for(int i=n;i>=1;--i){
suf[i]=a[i]/x,Mod[i]=a[i]%x,suf[i]+=suf[i+1];
Insert(root[i+1],root[i],0,x-1,Mod[i]);
}
while(m--){
ll S=gl(),l=0,r=1e18,mid;
while(l<r) check(S,mid=(l+r)>>1)?r=mid:l=mid+1;
printf("%lld\n",l);
}
return 0;
}
T3 字符串问题
wcr 神仙太强辣，打表找出了规律。
我的思路是枚举每个区间算贡献，再算一下有多少种情况能计算到它（一个组合数），时间是 O ( n 2 ) O(n^2) O(n2) 的，有 60 60 60 分。
std 的暴力是，对于每一个数字算它的贡献，即我们枚举 j j j，计算它有 1 0 j 10^j 10j 的贡献时的情况数，即：
a n s = ∑ i = 1 n ∑ j = 0 n − i a i × 1 0 j × ( n − j − 2 + [ i + j = n ] k − 1 + [ i + j = n ] ) ans=\sum_{i=1}^{n}\sum_{j=0}^{n-i}a_i\times 10^j\times\binom{n-j-2+[i+j=n]}{k-1+[i+j=n]} ans=i=1∑nj=0∑n−iai×10j×(k−1+[i+j=n]n−j−2+[i+j=n])
也就是， i ∼ i + j i\sim i+j i∼i+j 这些数字之间不能放
+
号， i + j i+j i+j 后面强制放一个
+
，剩下的 n − 1 − j − 1 n-1-j-1 n−1−j−1 中放 k − 1 k-1 k−1 个
+
。
注意要特判一下 i + j = n i+j=n i+j=n 的情况，因为这时 i + j i+j i+j 后面是不能放
+
的。
然后可以交换枚举顺序：
a n s = ∑ j = 0 n − 1 1 0 j ∑ i = 1 n − j a i × ( n − j − 2 + [ i + j = n ] k − 1 + [ i + j = n ] ) = ∑ j = 0 n − 1 1 0 j ( ∑ i = 1 n − j − 1 a i ( n − j − 2 k − 1 ) + a n − j ( n − j − 1 k ) ) = ∑ j = 0 n − 1 1 0 j ( n − j − 2 k − 1 ) ∑ i = 1 n − j − 1 a i + ∑ j = 0 n − 1 a n − j ( n − j − 1 k ) \begin{aligned} ans&=\sum_{j=0}^{n-1}10^j\sum_{i=1}^{n-j}a_i\times\binom{n-j-2+[i+j=n]}{k-1+[i+j=n]}\\ &=\sum_{j=0}^{n-1}10^j\left(\sum_{i=1}^{n-j-1}a_i\binom{n-j-2}{k-1}+a_{n-j}\binom{n-j-1}{k}\right)\\ &=\sum_{j=0}^{n-1}10^j\binom{n-j-2}{k-1}\sum_{i=1}^{n-j-1}a_i+\sum_{j=0}^{n-1}a_{n-j}\binom{n-j-1}{k} \end{aligned} ans=j=0∑n−110ji=1∑n−jai×(k−1+[i+j=n]n−j−2+[i+j=n])=j=0∑n−110j(i=1∑n−j−1ai(k−1n−j−2)+an−j(kn−j−1))=j=0∑n−110j(k−1n−j−2)i=1∑n−j−1ai+j=0∑n−1an−j(kn−j−1)
也就是说，只要对 a i a_i ai 求个前缀和就可以轻松搞定了。
时间复杂度 O ( n ) O(n) O(n)。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,P=998244353;
int n,k,fac[N],ifac[N],pre[N];
int add(int x,int y) {return x+y>=P?x+y-P:x+y;}
int dec(int x,int y) {return x-y< 0?x-y+P:x-y;}
int mul(int x,int y) {return 1ll*x*y>=P?1ll*x*y%P:x*y;}
int power(int a,int b){
int ans=1;
for(;b;b>>=1,a=mul(a,a)) if(b&1) ans=mul(ans,a);
return ans;
}
int Inv(int x) {return power(x,P-2);}
void prework(){
fac[0]=fac[1]=1;
for(int i=2;i<N;++i) fac[i]=mul(fac[i-1],i);
ifac[N-1]=Inv(fac[N-1]);
for(int i=N-2;~i;--i) ifac[i]=mul(ifac[i+1],i+1);
}
int C(int n,int m) {return n<m?0:mul(fac[n],mul(ifac[m],ifac[n-m]));}
char S[N];
int main(){
scanf("%d%d%s",&n,&k,S+1),prework();
for(int i=1;i<=n;++i) pre[i]=add(pre[i-1],S[i]-'0');
int tmp=1,ans=0;
for(int i=0;i<n;++i){
ans=add(ans,mul(tmp,add(mul(C(n-i-2,k-1),pre[n-i-1]),mul(C(n-i-1,k),S[n-i]-'0'))));
tmp=mul(tmp,10);
}
printf("%d\n",ans);
return 0;
}