11.12 game
题单介绍
### t1
定义函数 $f(x)$：
你有一个分数 $\dfrac{0}{x}$，每次你可以执行以下两种操作：
- 分子加 ```1```。
- 分子和分母均加 ```1```。
每次操作后，如果分子分母能够约分，化简到最简形式。
直到分数的值等于 ```1``` 时操作结束。
$f(x)$ 的值为最小操次数。
每次输入给定正整数 $n$，输出 $\sum_{i=1}^{n}f(i) \bmod 998244353$。
诈骗题。
先考虑尽可能约分减小速度最快。
发现和 ```2``` 约分所需的前置操作次数最少；具体地，最优策略为：
- 第一次使用操作 ```1```。
- 然后如果分子分母同奇偶就使用操作 ```2```，否则使用操作 ```1```，这样必能约调一个 ```2```。
容易发现操作次数为 $\lceil \log_{2}i\rceil+1$，然后直接算即可。
时间复杂度 $O(\log n)$。
```cpp
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <algorithm>
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
#define ll long long
static char stkk[200];
template<typename T>inline void output(T x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
const int N = 100,nf = 1e9+10,mo = 998244353;
static ll pw[N];
signed main(){
freopen("function.in","r",stdin);
freopen("function.out","w",stdout);
ll n;readx(n);
if(n==1)return output(1),0;
if(n==2)return output(3),0;
pw[0] = 1;
for(int i = 1;pw[i-1]<=1e18;++i)pw[i] = pw[i-1]<<1;
ll ans = 0;
for(int i = 2;i;++i){
if(pw[i]<=n){
ans = (0ll+ans+1ll*(pw[i]-pw[i-1])%mo*(i+1)%mo)%mo;
}
else{
ans = (0ll+ans+1ll*(n-pw[i-1])%mo*(i+1)%mo)%mo;
break;
}
}
output((0ll+ans+3)%mo);
return 0;
}
```
### t2
定义 $f(x)$，表示对可重集 $S$，每次操作可以选取 $S$ 的任意非空子集 $T$，将 $T$ 从 $S$ 中删去，并在 $S$ 中加入 $T$ 的 ```mex```。
$f(S)$ 是任意操作后当 $S$ 中只剩一个元素时该元素的最大值。
给定长度为 $n$ 的序列 $a$，请求出对于 $a$ 的每一个前缀 $S$ 的 $f(S)$。
$1 \leq n \leq 4 \times 10^5$。
对于 $a_i \geq n$ 的数，其必然不可能直接贡献 ```mex```，直接将其变成 ```0``` 即可。
答案不降，不妨思考如何判等。
对于答案 $x$，要求 $[0,x-1]$ 都至少被覆盖。
从大到小扫描 $[0,x-1]$，记 $c_i$ 表示数字 $i$ 出现个数；维护 ```p``` ```s``` 分别表示 【当前位合法至少要出现 $p$ 次】和 【如果有 $c_i \gt p$，就将多余 $c_i-p$ 变成 ```0```，这样的数的个数】。
每次扫到一个 $i$，有 $s \gets s+\max(0,c_i-p)$，$p \gets p+\max(0,p-c_i)$；```p``` 更新的含义是当前数少了 $p-c_i$，将其分摊到前缀。
更新式和 ```p``` 紧密相关，考虑在 $x$ 个不同的 $i$ 位置 ```p``` 被贡献，那么对 $\sum c_i$ 的要求至少增多了 $O(x^2)$，所以有效位置至多 $O(\sqrt n)$ 个。
考虑每次向左寻找第一个满足 $c_i \lt p$ 的位置，那么剩余的位置都满足 $c_i \geq p$，会对 $s$ 产生 $(\sum_j c_j)-totp$ 的贡献，```tot``` 是剩余位置数；
考虑在线段树上维护 $c_i$ 的最小值以及 $c_i$ 的和，然后每次直接在线段树上二分有效位置，并更新 $s,p$；时间复杂度 $O(n\sqrt n \log n)$。
考虑直接 ```dfs``` 线段树，这样时间复杂度是 $O(n \sqrt n)$；
对线段树的每层节点考虑，每层如果有 $x$ 个不同的节点的子数内存在 $c_i$ 会贡献 $p$，则其至少对 $\sum c_i$ 产生 $O(2^kx^2)$ 的贡献，所以一层至多有 $\sqrt{\dfrac{n}{2^k}}$ 个可贡献的节点；对不同层求和后量级显然是 $O(\sqrt n)$ 的。
```cpp
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <algorithm>
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
#define ll long long
static char stkk[200];
template<typename T>inline void output(T x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
const int N = 4e5+10;
struct work1{
int a[N],n;
struct D{
int mi[N<<2],su[N<<2];
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
inline void pushup(int x){
mi[x] = std::min(mi[ls],mi[rs]);
}
void my_pos(int x,int l,int r,int pos){
if(r<pos||l>pos)return;
++su[x];
if(l==r)return ++mi[x],void();
my_pos(ls,l,mid,pos),my_pos(rs,mid+1,r,pos);
pushup(x);
}
void qy(int x,int l,int r,int pl,int pr,ll &s,ll &p,int tot){
if(p>tot)return;
if(r<pl||l>pr)return s+=su[x],void();
if(pl<=l&&r<=pr){
if(mi[x]>p)return s+=su[x]-1ll*(r-l+1)*(p+1),void();
// printf("l:%d r:%d su:%d s:%lld p:%lld %lld\n",l,r,su[x],s,p,su[x]-1ll*(r-l+1)*(p+1)),
// printf("l:%d r:%d su:%d\n",l,r,su[x]),
}
if(l==r)return p+=p+1-su[x],void();
qy(rs,mid+1,r,pl,pr,s,p,tot),qy(ls,l,mid,pl,pr,s,p,tot);
}
#undef ls
#undef rs
#undef mid
}t0;
inline void add(int x){
if(x>n)t0.my_pos(1,0,n,0);
else t0.my_pos(1,0,n,x);
}
inline bool check(int x,int i){
ll s,p;s = p = 0;
// printf("x:%d i:%d\n",x,i);
t0.qy(1,0,n,1,x-1,s,p,i);
// printf("s:%lld p:%lld\n",s,p);
return s>=p+1;
}
void main(){
readx(n);
int pre = 2;
FOR(i,1,n){
readx(a[i]);
add(a[i]);
if(i==1)output(std::max(a[1],1));
else{
for(;check(pre,i);++pre);
output(pre-1);
}
putchar(' ');
}
putchar(10);
}
}A;
signed main(){
freopen("mex.in","r",stdin);
freopen("mex.out","w",stdout);
A.main();
return 0;
}
```
### t3
给定 $n$ 个传送器，每个传送器有两个属性：位置 $p_i$，功率 $f_i$。
一个位于位置 $A$ 的人，使用了编号为 $i$ 的传送器，会被传送到 $2p_i-A$ 的位置。
有两人 $a,b$ 分别位于 $A_i,B_i$ 位置，她们每次会各自选择两个传送器 $i,j$，然后一起传送，定义该次传送的代价为 $|f_i-f_j|$；
她们想要通过使用功率位于 $[L_i,R_i]$ 传送器相遇；定义这次相遇的代价为每次传送代价的最大值。
请对每次询问，如果可以相遇，输出相遇代价的最小值；否则输出 ```-1```。
$1 \leq n,m \leq 5 \times 10^4$
两人一起传送可以看作一人传送两次。
不妨记奇数次选择的传送器位置集合为 $x$，偶数次选择的传送器位置集合为 $y$，则有位置相同等价于 $2(x_i-y_i)=A-B$，所以 $A,B$ 必须同奇偶，并且形如 $x_i-y_i$ 的数集的 $\gcd$ 必须是 $A-B$ 的因子。
暴力的想法是从大到小扫描询问的左端点，用维护三元组 $(|p_i-p_j|,|f_i-f_j|,j)$，用 ```set``` 让其第二个键值升序。可以做到 $O(n^2\log n+qn^2)$。
考虑优化，瓶颈在于数集的大小为 $O(n^2)$ 的；考虑只保留数集中 $c_i=p_i-p_{i-1}$ 的数，这样是正确的 [AI 证明](https://www.luogu.com.cn/article/jjh6n9bz)。
然后可以整体二分，用线段树维护区间 $\gcd$，可以做到 $O(n \log^2 n \log V)$，由于 $\gcd$ 常数很小，可以视为 $O(n \log^2 n)$。
```cpp
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
static char stkk[200];
template<typename T>inline void output(T x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
const int N = 5e4+10;
struct work{
int n,m;
struct node1{int f,pos;bool operator<(const node1 &A)const {return f<A.f;}}a[N];
struct node2{
int l,r,id,v;
}qy[N],qytmp[N];
int tp,ans[N];
bool flg[N];
struct node3{
int cpos,cf,id;bool operator<(const node3 &A)const {return cf<A.cf;}
}c[N];
struct D{
int t[N<<2];
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
inline void pushup(int x){t[x] = std::__gcd(t[ls],t[rs]);}
void bd(int x,int l,int r,node3 *c){
if(l==r)return t[x] = c[l].cpos,void();
bd(ls,l,mid,c),bd(rs,mid+1,r,c);
pushup(x);
}
void my_pos(int x,int l,int r,int pos,int d){
if(r<pos||l>pos)return;
if(l==r)return t[x]=d,void();
my_pos(ls,l,mid,pos,d),my_pos(rs,mid+1,r,pos,d);
pushup(x);
}
int qy(int x,int l,int r,int pl,int pr){
if(r<pl||l>pr)return 0;
if(pl<=l&&r<=pr)return t[x];
return std::__gcd(qy(ls,l,mid,pl,pr),qy(rs,mid+1,r,pl,pr));
}
#undef ls
#undef rs
#undef mid
}t0;
void solve(int l,int r,int L,int R){
if(l>r)return;
int mid = (l+r)>>1;
FOR(i,mid+1,r)t0.my_pos(1,1,n-1,c[i].id,0);
FOR(i,L,R){
int tmp = t0.qy(1,1,n-1,qy[i].l,qy[i].r);
if(tmp&&!(qy[i].v%tmp))ans[qy[i].id] = c[mid].cf,flg[i] = 1;
else flg[i] = 0;
}
int tl = L-1,tr;
FOR(i,L,R)if(flg[i])qytmp[++tl] = qy[i];
tr = tl;
FOR(i,L,R)if(!flg[i])qytmp[++tr] = qy[i];
if(tr^R)puts("?"),exit(0);
FOR(i,L,R)qy[i] = qytmp[i];
t0.my_pos(1,1,n-1,c[mid].id,0);
solve(l,mid-1,L,tl);
FOR(i,mid,r)t0.my_pos(1,1,n-1,c[i].id,c[i].cpos);
solve(mid+1,r,tl+1,R);
}
void main(){
readx(n),readx(m);
FOR(i,1,n)readx(a[i].pos);
FOR(i,1,n)readx(a[i].f);
std::sort(a+1,a+1+n);
//c
FOR(i,1,n-1)c[i] = (node3){std::abs(a[i+1].pos-a[i].pos),a[i+1].f-a[i].f,i};
//qy
int p0,p1,tl,tr;
FOR(i,1,m){
ans[i] = -1;
readx(p0),readx(p1),readx(tl),readx(tr);
if(p0==p1)ans[i] = 0;
else if((p0-p1)&1^1){
int pl = std::lower_bound(a+1,a+1+n,(node1){tl,0})-a,pr = std::upper_bound(a+1,a+1+n,(node1){tr,0})-a-1;
if(pl<pr)qy[++tp] = (node2){pl,pr-1,i,std::abs(p0-p1)/2};
}
}
//solve
t0.bd(1,1,n-1,c);
std::sort(c+1,c+n);
solve(1,n-1,1,tp);
FOR(i,1,m)output(ans[i]),putchar(' ');
putchar(10);
}
}A;
signed main(){
freopen("teleporters.in","r",stdin);
freopen("teleporters.out","w",stdout);
// output((int)(N*std::__lg(N)*std::__lg((int)(1e9))));
A.main();
return 0;
}
```
### t4
定义 $f(x)$ 为 $x$ 各位数字之和。
给定长度为 $n$ 的序列 $a$，输出 $\min_{k=0}\{\sum_{i=1}^{n}f(a_i+x)\}$。
$1 \leq n \leq 10^6$。
定义个位为第 ```1``` 位，十位为第 ```2``` 位，以此类推。
从各位考虑加上 $x$ 的影响。
发现答案可以分成三部分：
$\sum_{i=1}^{n}f(a_i),f(x)n,-9c$，$c$ 是每个数的各位上的进位次数和。
第一部分是好做的。考虑对后两部分 ```dp```。
关于进位，有以下两个性质：
- $x$ 的前 $i-1$ 位至多对第 $i$ 位产生 ```1``` 的进位。
- 对于同样的 $x$，前 $i-1$ 位越大的数 $a_i$ 越容易进位。
所以定义 $f_{i,j}$ 表示考虑了前 $i$ 位，贡献了 $j$ 个进位的后两部分的最小和。
每次从 $f_{i,j}$ 主动转移，枚举 $x$ 在 $i+1$ 位的数。
细节：记得考虑进位，特殊考虑进位前该位数为 ```9``` 的数。
这样可以做到 $O(nB\log V+n\log n\log V)$ 的复杂度，瓶颈在排序；换成基数排序，可以做到 $O(nB \log V+n\log V)$。
```cpp
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <algorithm>
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
// #define int long long
static char stkk[200];
template<typename T>inline void output(T x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
const int N = 1e6+10,B = 20,nf = 2e9+10,base[] = {0,1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
struct work1{
int f[N],g[N],a[N],ct[B],n,mx,c[N];
inline void ckmax(int &x,int y){x<y&&(x=y);}
inline void ckmin(int &x,int y){x>y&&(x=y);}
inline void cal(int &ans,int &mx,int x){
int ct = 0;
for(;x;ans+=x%10,x/=10,++ct);
ckmax(mx,ct);
}
inline void dp(){
FOR(wei,1,mx){
std::swap(g,f);
FOR(i,0,n)f[i] = nf;
FOR(i,0,9)ct[i] = 0;
FOR(i,1,n)++ct[(a[i]/base[wei])%10];
FOR(i,1,9)ct[i]+=ct[i-1];
for(int p = 0,pre = 0;p <= n;++p){
if(p){
int x = (a[p]/base[wei])%10;
if(x==9)++pre;
--ct[x];
}
FOR(i,0,9){
ckmin(f[pre+ct[9]-ct[9-i]],g[p]+i*n-9*(pre+ct[9]-ct[9-i]));
}
}
// sort
FOR(i,0,9)ct[i] = 0;
FOR(i,1,n)++ct[(a[i]/base[wei])%10];
REP(i,8,0)ct[i]+=ct[i+1];
REP(i,n,1)c[ct[(a[i]/base[wei])%10]--] = a[i];
FOR(i,1,n)a[i] = c[i];
// FOR(i,1,n){
// printf("%d ",a[i]%(base[wei+1]));
// }putchar(10);
}
}
inline void main(){
readx(n);int ans = 0,tmp = 0;
FOR(i,1,n)readx(a[i]),cal(ans,mx,a[i]),f[i] = nf;
dp();
FOR(i,0,n)ckmin(tmp,f[i]);
output(ans+tmp);
}
}A;
signed main(){
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
A.main();
return 0;
}
```