前言

比赛的时候做题顺序为$ABCF$,由于$F$的做法太傻,导致调了有点久,没有时间做$D$了. 比赛刚结束的时候,排在$official$的$rk44$. 结果一觉醒来,别人的$E$大部分都被$hack$了… 我居然上了$rk5$(大雾…

妈妈我上首页啦

$A$

给定3条边.让你再造一条边使得可以围成4边形.

设三条边分别为$a,b,c$,那么$a+b+c-1$为第4边.

$B$

给定一个$n\ast m$的矩阵. 每次只能让一个值变化1. 问至少多少次操作才能使得每行每列都回文.

根据回文的定义, 矩阵内有3种情况: $1/2/4$个数要相等.

我们只要找到数的中位数就好.

int n,m; ll ans,a[110][110]; void solve() { qr(n); qr(m); ans=0; rep(i,1,n) rep(j,1,m) qr(a[i][j]); rep(i,1,(n+1)/2) rep(j,1,(m+1)/2) { vector<ll> cur={a[i][j],a[n-i+1][j],a[i][m-j+1],a[n-i+1][m-j+1]}; sort(all(cur)); ll t=cur[1]; if(i*2-1 == n&&j*2-1==m) ; else if(i*2-1 == n|| j*2-1 ==m) ans+=cur[2]-cur[1]; else rep(k,0,3) ans += abs(t-cur[k]); } pr2(ans); }

$C$

给定一个商品的价格$n(\lg n\le 1e5)$. 你是一个砍价高手,你可以删除任意一个非空连续子段,删除后两部分相接. 老板说,如果你能算出所有情况下的价格总和$\mathrm{m}\mathrm{o}\mathrm{d}p$,那么商品就送你了~~

定义$len$为数位总数. 我们考虑删除一个区间$[l,r]$的贡献: $num=f(1,l-1)\ast 10^{len-r}+f(r+1,len)$. 其中$f(i,j)$为$[i,j]$形成的数.

那么我们只要拆开两个部分分别贡献即可.

int n; char str[N]; ll x,ans,s[N],p[N]; void solve() { x=ans=0;scanf("%s",str+1); n=strlen(str+1); p[0]=s[0]=1; rep(i,1,n) p[i]=p[i-1]*10%mod,s[i]=(s[i-1]+p[i])%mod,str[i] -= '0'; rep(i,1,n-1) { x=(x*10+str[i])%mod; ad(ans,x*s[n-i-1]%mod); } x=0; REP(i,1,n) { x=(x+str[i]*p[n-i])%mod; ad(ans,x*(i-1)%mod); } pr2(ans); }

$D$

在2维平面内,给定起点和终点. 同时,还有$m$个传送门,当你和任意一个传送门有相同的$x/y$坐标时,你可以选择瞬移到该传送门的位置.(不花费时间) 与此同时,你可以选择往4个方向走一个单位,耗时1个单位. 问从起点到终点的最小花费.

$dijkstra$即可. 一个显然的做法是要移动到传送门,我们只会改变$x/y$.一定不可能一起改变. 所以,我们先从起点移动到任意传送门. 然后,从传送门互相转移. 因为我们只用移动$x/y$,所以每个点只需向$x/y$相邻的点连边即可. 最后再考虑从每个点移动到终点即可.

int n,m,u[N],v[N],d[N]; vector<pii> X,Y; V<int> e[N]; void add(int x,int y) { e[x].pb(y); e[y].pb(x); } priority_queue<pii,vector<pii>,greater<pii> > q; void insert(int x,int y) { int D=d[x]+min(abs(u[x]-u[y]),abs(v[x]-v[y])); if(d[y] > D) { d[y]=D; q.push(mk(D,y)); } } void solve() { qr(n); qr(m); m += 2; rep(i,1,m) { qr(u[i]); qr(v[i]); if(i > 2) X.pb(mk(u[i],i)),Y.pb(mk(v[i],i)); } sort(all(X)); sort(all(Y)); rep(i,0,SZ(X)-2) { add(X[i].se,X[i+1].se); add(Y[i].se,Y[i+1].se); } memset(d,63,sizeof d);d[1]=0; rep(i,3,m) insert(1,i); while(q.size()) { int D=q.top().fi,x=q.top().se; q.pop(); if(D>d[x]) continue; for(int y:e[x]) insert(x,y); } int ans=abs(u[1]-u[2])+abs(v[1]-v[2]); rep(i,3,m) cmin(ans,d[i]+abs(u[i]-u[2])+abs(v[i]-v[2])); pr2(ans); }

$E$

给定一个长度为$n$的串,然后对于每个后缀输出字典序最小的答案. 假如有$s_i=s_{i+1}$,那么你可以选择删除两个字符. 删除完后,得到答案. $n\le 1e5$.

如果能删除就删除的话不一定是最优的,比如abbf的情况. 因为是后缀处理,所以我们从后往前求解. 如果$s_i=s_{i+1}$,我们考虑删除和不删除哪个的字典序更小. 设$an{s}_i$表示后缀$i$的答案. 那么删除就是$an{s}_{i+2}$,否则为$s_i+s_i+an{s}_{i+2}$. 我们当然不能$O(n)$判断字符串大小. 实际上,我们只要知道$an{s}_{i+2}$的开头两个不同的字符即可.(可以尝试写几个串来感受一下). 然后,我们不需要直接求出$an{s}_i$,只用用指针指向去掉首字符后的位置即可.

int n,pos[N],tot,nxt[N]; char s[N],ch[N],str[N][2]; bool vis[N]; string ans[N]; int len[N]; void dfs(int x) { if(vis[x]) return ; vis[x]=1; dfs(nxt[x]); len[x]=len[nxt[x]]+1; char c=ch[x]; ans[x]=c+ans[nxt[x]]; if(len[x]>10) ans[x].erase(5,1); if(len[x] == 11) ans[x][5]=ans[x][6]=ans[x][7]='.'; } void solve() { scanf("%s",s+1); n=strlen(s+1); pos[n+1]=tot=0; vis[0]=1; REP(i,1,n) { if(s[i] == s[i+1]) { pair<char,char>now; int x=pos[i+2]; now=mk(str[x][0],str[x][1]); if(mk(s[i],s[i])<now) { pos[i]=++tot; nxt[tot]=pos[i+1]; ch[tot]=s[i]; if(s[i] == str[x][0]) str[tot][0]=str[x][0],str[tot][1]=str[x][1]; else str[tot][1]=str[x][0],str[tot][0]=s[i]; } else pos[i]=pos[i+2]; } else { pos[i]=++tot; nxt[tot]=pos[i+1]; ch[tot]=s[i]; int x=pos[i+1]; if(s[i] == str[x][0]) str[tot][0]=str[x][0],str[tot][1]=str[x][1]; else str[tot][1]=str[x][0],str[tot][0]=s[i]; } } rep(i,1,tot) dfs(i); rep(i,1,n) { int x=pos[i]; pr1(len[x]); puts(ans[x].c_str()); } }

$F$

强制在线求区间$lcm$. $n\le 1e5,a_i\le 2e5$.

比赛的时候想了一种很傻的笛卡尔树套树套树的做法. 这种做法劣在没有考虑到可以使用逆元,所以模数可以任意,但是复杂度较高.

实际上我们并不用建出笛卡尔树,只用存栈即可. 然后树套树可以用主席树代替. 其中主席树$root[r]$存的是,当右端点为$r$时,各个左端点的答案.

显然长度越长,$lcm$非降. 对于一个质数$p$而言就是指数从左往右下降. 我们只要仔细维护单调栈即可. 当出现当前位置的指数比前面一段的大的时候,我们撤销前面一段即可. 下面的代码实现是用差分搞的,这就要求一定要有逆元. 我们可以改为区间乘法,这样就不用要求逆元,复杂度不变.

复杂度为$O(n\log n\log max{a}_i)$.其中$\log max{a}_i$表示的是质因子个数,所以这个常数较小.

int n,a[N],inv[N],mx,prime[N],tot,v[N],id[N]; struct node {int l,r,c; } tr[M]; int cnt,root[N]; int upd(int p,int l,int r,int pos,ll d) { int x=++cnt; tr[x]=tr[p]; tr[x].c=tr[x].c*d%mod; if(l == r) return x; int mid=(l+r)/2; if(pos<=mid) lc=upd(tr[p].l,l,mid,pos,d); else rc=upd(tr[p].r,mid+1,r,pos,d); return x; } int ask(int x,int l,int r,int pos) {//<=pos if(l>pos) return 1; if(r<=pos) return tr[x].c; int mid=(l+r)/2; return (ll)ask(lson,pos)*ask(rson,pos)%mod; } void solve() { qr(n); rep(i,1,n) qr(a[i]),cmax(mx,a[i]); inv[0]=inv[1]=1; rep(i,2,mx) { inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod; if(!v[i]) { v[i]=prime[++tot]=i; for(ll j=i;j<=mx;j *= i) id[j]=tot; } rep(j,1,tot) { int k=i*prime[j]; if(k>mx) break; if(i%prime[j] ==0 ){v[k]=v[i]*prime[j]; break;} else v[k]=prime[j]; } } V<V<pii> > sta(tot+1,{mk(0,0)}); tr[0].c=1; rep(i,1,n) { root[i]=root[i-1]; int x=a[i]; while(x>1) { int y=v[x],p=id[y]; x /= y; while(sta[p].size() > 1 && y > sta[p].back().se) { int pos=sta[p].back().fi,z=sta[p].back().se; sta[p].pop_back(); root[i]=upd(root[i],1,n,sta[p].back().fi+1,inv[z]); root[i]=upd(root[i],1,n,pos+1,z); } root[i]=upd(root[i],1,n,sta[p].back().fi+1,y); sta[p].emplace_back(i,y); } if(i<n) root[i]=upd(root[i],1,n,i+1,inv[a[i]]); } int l,r,ans=0,q; qr(q); while(q--) { qr(l); qr(r); l=(l+ans)%n+1; r=(r+ans)%n+1; if(l > r) swap(l,r); pr2(ans=ask(root[r],1,n,l)); } }