2020-2021:teams:legal_string:组队训练比赛记录:contest10
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest10 [2021/08/03 14:57] jxm2001 |
2020-2021:teams:legal_string:组队训练比赛记录:contest10 [2021/08/11 16:00] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| ^ 题目 ^ 蒋贤蒙 ^ 王赵安 ^ 王智彪 ^ | ^ 题目 ^ 蒋贤蒙 ^ 王赵安 ^ 王智彪 ^ | ||
| - | | A | 0 | 0 | 0 | | + | | A | 0 | 1 | 2 | |
| | B | 0 | 0 | 0 | | | B | 0 | 0 | 0 | | ||
| - | | C | 1 | 0 | 0 | | + | | C | 1 | 0 | 2 | |
| - | | D | 2 | 0 | 0 | | + | | D | 2 | 1 | 0 | |
| - | | E | 0 | 0 | 0 | | + | | E | 2 | 0 | 0 | |
| - | | G | 0 | 0 | 0 | | + | | G | 0 | 1 | 2 | |
| - | | J | 2 | 0 | 0 | | + | | J | 2 | 0 | 1 | |
| - | | K | 0 | 0 | 0 | | + | | K | 2 | 0 | 0 | |
| ====== 题解 ====== | ====== 题解 ====== | ||
| + | |||
| + | ===== A. Contracting Convex Hull ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给了 $n(n≤1000)$ 个点的凸包，这个凸包每条边以 $1$ 的速度向内收缩。给 $q$ 组询问，每组询问一个时间，求这个时间凸包的面积。 $(q≤100000)$ 。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 这绝对是最容易理解的解法，没有之一！（因为看了别人的神仙代码看不懂，于是自己亲自动手了...） | ||
| + | |||
| + | 由角分线定理知，每个点的移动轨迹其实是这个点在凸包内的夹角的角平分线。 | ||
| + | |||
| + | 于是我们可以求每个角，也就知道每个点的轨迹，知道轨迹就可以知道这个边什么时候收缩到一个点。 | ||
| + | |||
| + | 烦人的是因为有的边收缩成点，会改变凸包形状，于是相邻的角会变，然后相邻的边的收缩时间会变，所以这是个动态的过程，这也是我考场上不知道怎么解决的地方，对不起我的队友... | ||
| + | |||
| + | 于是我这个暴力狂 $(×)$ ，自然每次都暴力求一下所有点的收缩时间，选出最短的时间，同时有一点很显然，就是将询问时间排序，模拟凸包收缩的过程。当 当前询问的时间 在现在时间+最近删除时间之后时，说明我们要删除一个点，于是我们模拟删除的过程，并更新凸包周长面积和周长缩小速度（暴力更新即可，因为每次删除也是 $O(n)$ 的，除非你闲出屁...）。 | ||
| + | |||
| + | 然后面积就是删除后的当前时间距离询问时间这个时间内缩小之后的周长（是时间的一次函数，可以直接 $O(1)$ 得到）+之前周长（也就是梯形的上底加下底）乘时间除以 $2$ 即可，也就是我们把两个凸包之间的区域看成 $n$ 个梯形，搞一下就出来了~。 | ||
| + | |||
| + | 别忘了，当删剩下的点不足 $2$ 的时候，直接输出 $0$ ，因为已经没有面积，不然样例都过不去 $(×)$ 。 | ||
| + | |||
| + | <hidden 代码> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | //这绝对是最粗暴并且最易懂的做法！！！ | ||
| + | #include<bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | const int M=100100; | ||
| + | const long double eps=1e-12; | ||
| + | int n,q,erase; | ||
| + | long double ans[M],ti,tot,V,Len,dans; | ||
| + | int sgn(long double a) { | ||
| + | if(fabs(a)<eps)return 0; | ||
| + | if(a>0)return 1; | ||
| + | else return -1; | ||
| + | } | ||
| + | struct QQ { | ||
| + | int id; | ||
| + | long double t; | ||
| + | } Q[M]; | ||
| + | int cmp(QQ a,QQ b) { | ||
| + | return a.t<b.t; | ||
| + | } | ||
| + | |||
| + | int nxt(int i,int n) { | ||
| + | i++; | ||
| + | if(i==n+1) return 1; | ||
| + | return i; | ||
| + | } | ||
| + | |||
| + | struct node { | ||
| + | long double x,y,dx,dy; | ||
| + | node operator +(const node&tmp)const { | ||
| + | return (node) {x+tmp.x,y+tmp.y,dx+tmp.dx,dy+tmp.dy}; | ||
| + | } | ||
| + | node operator -(const node&tmp)const { | ||
| + | return (node) {x-tmp.x,y-tmp.y,dx-tmp.dx,dy-tmp.dy}; | ||
| + | } | ||
| + | node operator /(const long double &a)const { | ||
| + | return (node) {x/a,y/a,dx/a,dy/a}; | ||
| + | } | ||
| + | long double length() { | ||
| + | return sqrt(x*x+y*y); | ||
| + | } | ||
| + | long double v() { | ||
| + | return sqrt(dx*dx+dy*dy); | ||
| + | } | ||
| + | long double dis(node nd) { | ||
| + | return sqrt((x-nd.x)*(x-nd.x)+(y-nd.y)*(y-nd.y)); | ||
| + | } | ||
| + | } A[M],now; | ||
| + | long double Angle(node a,node b) { | ||
| + | return acos((a.x*b.x+a.y*b.y)/a.length()/b.length()); | ||
| + | } | ||
| + | node rotate(node a,long double t) { | ||
| + | return (node) {a.x*cos(t)-a.y*sin(t),a.x*sin(t)+a.y*cos(t),0,0}; | ||
| + | } | ||
| + | void init(long double &a,long double &b,long double &c) { | ||
| + | if(n<3)return; | ||
| + | a=0,b=0,c=0; | ||
| + | int m=0; | ||
| + | while(erase&&n>=3) { | ||
| + | for(int i=erase; i<n; i++) A[i]=A[i+1];//把删除的点挤掉 | ||
| + | n--;//少了一个点 | ||
| + | erase=0;//把消除标记打掉 | ||
| + | A[0]=A[n],A[n+1]=A[1]; | ||
| + | for(int i=1; i<=n; i++) { | ||
| + | long double t; | ||
| + | now=A[i+1]-A[i]; | ||
| + | t=now.length()/now.v(); | ||
| + | if(sgn(t-ti)==0) erase=i;//这个点也应该这个点删掉 那就继续删 | ||
| + | } | ||
| + | } | ||
| + | if(n<3)return; | ||
| + | for(int i=1; i<=n; i++) { | ||
| + | A[i].x=A[i].x+A[i].dx*ti;//移动速度*时间 | ||
| + | A[i].y=A[i].y+A[i].dy*ti; | ||
| + | } | ||
| + | A[0]=A[n],A[n+1]=A[1]; | ||
| + | for(int i=1; i<=n; i++) { | ||
| + | long double th=Angle(A[i-1]-A[i],A[i+1]-A[i])/2;//移动按照角分线移动 | ||
| + | now=rotate(A[i+1]-A[i],th);//旋转到角分线位置 | ||
| + | now=now/now.length()/sin(th);//如果凸包缩小1 这个点沿角分线移动now的距离 | ||
| + | A[i].dx=now.x;//dx赋值 | ||
| + | A[i].dy=now.y; | ||
| + | } | ||
| + | A[0]=A[n],A[n+1]=A[1]; | ||
| + | tot+=ti; | ||
| + | ti=1e9; | ||
| + | for(int i=1; i<=n; i++) { | ||
| + | now=A[i+1]-A[i]; | ||
| + | long double t=now.length()/now.v();//发现速度垂直于线的分量被两边消掉了 只剩下沿线方向的 于是就直接除就是这个边消失的时间 | ||
| + | if(sgn(t-ti)<0) {//看看接下来应该删什么 | ||
| + | ti=t; | ||
| + | erase=i; | ||
| + | } | ||
| + | } | ||
| + | V=0; | ||
| + | Len=0; | ||
| + | dans=0; | ||
| + | for(int i=1;i<=n;i++) { | ||
| + | V+=(A[i+1]-A[i]).v();//暴力计算周长缩小的速度 | ||
| + | Len+=(A[i+1]-A[i]).length();//暴力计算当前周长 | ||
| + | dans+=(A[i].x*A[nxt(i,n)].y-A[i].y*A[nxt(i,n)].x)/2;//暴力计算当前面积 | ||
| + | } | ||
| + | dans=fabs(dans);//三角剖分求面积需要绝对值 | ||
| + | } | ||
| + | |||
| + | void solve() { | ||
| + | long double a=0,b=0,c=0; | ||
| + | init(a,b,c); | ||
| + | for(int i=1; i<=q; i++) { | ||
| + | while(n>=3&&sgn(tot+ti-Q[i].t)<=0) init(a,b,c); //当 当前时间+最快要删除的点的时间和小于等于这个时间说明要删这个点 | ||
| + | if(n<3) ans[Q[i].id]=0;//不足三个点 图形都围不成直接0 | ||
| + | else ans[Q[i].id]=dans-(Len+Len-(Q[i].t-tot)*V)*(Q[i].t-tot)/2;//不然就是当前面积-所有的梯形面积就是（原周长+现在周长）*时间/2 | ||
| + | } | ||
| + | } | ||
| + | int main() { | ||
| + | scanf("%d",&n); | ||
| + | for(int i=1; i<=n; i++) { | ||
| + | A[i].dx=A[i].dy=0; | ||
| + | scanf("%LF%LF",&A[i].x,&A[i].y); | ||
| + | } | ||
| + | scanf("%d",&q); | ||
| + | for(int i=1; i<=q; i++) { | ||
| + | Q[i].id=i;//标记是哪个问题 | ||
| + | scanf("%LF",&Q[i].t); | ||
| + | } | ||
| + | sort(Q+1,Q+1+q,cmp);//将点的移动按照时间排序 | ||
| + | solve(); | ||
| + | for(int i=1; i<=q; i++) printf("%.10LF\n",ans[i]); | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
| ===== D. Gambling Monster ===== | ===== D. Gambling Monster ===== | ||
| 行 123: | 行 283: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== E. Growing Tree ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一棵树，初始时只有一个颜色为 $c$ 的 $1$ 号结点，接下来 $m$ 个操作： | ||
| + | |||
| + | - 对结点 $u$ 添加一个颜色为 $c$ 的叶子结点 $n+1$(设当前共有 $n$ 个结点) | ||
| + | - 查询结点 $u$ 子树颜色为 $c$ 的结点数量 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 维护每个结点 $u$ 的最新儿子 $\text{hson}(u)$ 以及每个结点的子树在单括号序列的终止结点 $\text{dfr}(u)$(子树不包含该点)。 | ||
| + | |||
| + | 于是新插入叶子结点 $n+1$ 时，如果 $u$ 没有叶子结点，则有 $\text{dfr}(n+1)\gets \text{dfr}(u)$，否则有 $\text{dfr}(n+1)\gets \text{hson}(u)$。 | ||
| + | |||
| + | 然后将 $\text{hson}(u)$ 更新为 $n+1$ 即可实现序列的维护。$u$ 的子树查询等价于查询序列 $[\text{pos}(u),\text{pos}(\text{dfr}(u)))$ 的信息。 | ||
| + | |||
| + | 接下来为每种颜色开一个平衡树，每棵平衡树维护该颜色结点的所有位置。 | ||
| + | |||
| + | 则操作 $2$ 等价于查询颜色为 $c$ 的平衡树中位置位于 $[\text{pos}(u),\text{pos}(\text{dfr}(u)))$ 的结点个数。 | ||
| + | |||
| + | 发现 $\text{pos}(u)$ 是动态更新的，但是 $\text{pos}(u),\text{pos}(v)$ 的相对大小是不会改变的，因此考虑建立一棵平衡树维护所有 $\text{pos}(u)$。 | ||
| + | |||
| + | 如果用 $\text{splay}$ 维护 $\text{pos}(u)$，则每次查询 $\text{pos}(u)$ 时间复杂度为 $O(\log n)$，在颜色为 $c$ 的平衡树查询的结点数的时间复杂度为 $O\left(\log^2 n\right)$。 | ||
| + | |||
| + | 考虑 $O(1)$ 查询 $\text{pos}(u)$。一种想法是将 $\text{pos}(u)$ 映射到实数空间，每次插入叶子结点则将 $\text{pos}(n+1)$ 赋值为 $\cfrac {\text{pos}(u)+\text{pos}(v)}{2}$。 | ||
| + | |||
| + | 其中 $u,v$ 表示 $n+1$ 在单括号序列的左右相邻结点，但这样会导致精度误差。 | ||
| + | |||
| + | 考虑替罪羊树维护 $\text{long long}$ 空间，替罪羊树定期重构重新赋值部分 $\text{pos}(u)$，保证了树的深度，不会导致精度误差。 | ||
| + | |||
| + | 算法总时间复杂度变为 $O(n\log n)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=5e5+5; | ||
| + | const LL MAXV=1LL<<62; | ||
| + | LL val[MAXN]; | ||
| + | namespace Tree1{ | ||
| + | #define lch(k) node[node[k].lch] | ||
| + | #define rch(k) node[node[k].rch] | ||
| + | const double alpha=0.70; | ||
| + | struct Node{ | ||
| + | int lch,rch,sz; | ||
| + | }node[MAXN]; | ||
| + | int root,a[MAXN],n; | ||
| + | bool isbad(int k){ | ||
| + | return alpha*node[k].sz<max(lch(k).sz,rch(k).sz); | ||
| + | } | ||
| + | void build(int &k,int lef,int rig,LL vl,LL vr){ | ||
| + | if(lef>rig) return k=0,void(); | ||
| + | int mid=lef+rig>>1; | ||
| + | k=a[mid]; | ||
| + | val[k]=vl+vr>>1; | ||
| + | if(lef==rig){ | ||
| + | node[k].lch=node[k].rch=0; | ||
| + | node[k].sz=1; | ||
| + | return; | ||
| + | } | ||
| + | build(node[k].lch,lef,mid-1,vl,val[k]-1); | ||
| + | build(node[k].rch,mid+1,rig,val[k]+1,vr); | ||
| + | node[k].sz=lch(k).sz+rch(k).sz+1; | ||
| + | } | ||
| + | void dfs(int k){ | ||
| + | if(!k)return; | ||
| + | dfs(node[k].lch); | ||
| + | a[++n]=k; | ||
| + | dfs(node[k].rch); | ||
| + | } | ||
| + | void rebuild(int &k,LL vl,LL vr){ | ||
| + | n=0; | ||
| + | dfs(k); | ||
| + | build(k,1,n,vl,vr); | ||
| + | } | ||
| + | void check(int &k,int id,LL vl,LL vr){ | ||
| + | if(k){ | ||
| + | if(isbad(k)) | ||
| + | rebuild(k,vl,vr); | ||
| + | else if(val[id]<val[k]) | ||
| + | check(node[k].lch,id,vl,val[k]-1); | ||
| + | else | ||
| + | check(node[k].rch,id,val[k]+1,vr); | ||
| + | } | ||
| + | } | ||
| + | void Insert(int &k,int id){ | ||
| + | if(!k){ | ||
| + | k=id; | ||
| + | node[k].lch=node[k].rch=0; | ||
| + | node[k].sz=1; | ||
| + | return; | ||
| + | } | ||
| + | node[k].sz++; | ||
| + | if(val[id]<val[k]) | ||
| + | Insert(node[k].lch,id); | ||
| + | else | ||
| + | Insert(node[k].rch,id); | ||
| + | } | ||
| + | void Insert(int id){ | ||
| + | Insert(root,id); | ||
| + | check(root,id,0,MAXV); | ||
| + | } | ||
| + | #undef lch | ||
| + | #undef rch | ||
| + | } | ||
| + | namespace Tree2{ | ||
| + | struct Node{ | ||
| + | int r,sz,ch[2]; | ||
| + | }node[MAXN]; | ||
| + | #define lch(k) node[node[k].ch[0]] | ||
| + | #define rch(k) node[node[k].ch[1]] | ||
| + | void push_up(int k){ | ||
| + | node[k].sz=lch(k).sz+rch(k).sz+1; | ||
| + | } | ||
| + | void split(int k,int &k1,int &k2,LL v){ | ||
| + | if(!k) return k1=k2=0,void(); | ||
| + | if(val[k]<=v){ | ||
| + | k1=k; | ||
| + | split(node[k].ch[1],node[k1].ch[1],k2,v); | ||
| + | push_up(k1); | ||
| + | }else{ | ||
| + | k2=k; | ||
| + | split(node[k].ch[0],k1,node[k2].ch[0],v); | ||
| + | push_up(k2); | ||
| + | } | ||
| + | } | ||
| + | void merge(int &k,int k1,int k2){ | ||
| + | if(!k1||!k2)return k=k1|k2,void(); | ||
| + | if(node[k1].r>node[k2].r){ | ||
| + | k=k1; | ||
| + | merge(node[k].ch[1],node[k1].ch[1],k2); | ||
| + | push_up(k); | ||
| + | }else{ | ||
| + | k=k2; | ||
| + | merge(node[k].ch[0],k1,node[k2].ch[0]); | ||
| + | push_up(k); | ||
| + | } | ||
| + | } | ||
| + | void Insert(int &root,int id){ | ||
| + | node[id].r=rand(); | ||
| + | node[id].sz=1; | ||
| + | node[id].ch[0]=node[id].ch[1]=0; | ||
| + | int lef,rig; | ||
| + | split(root,lef,rig,val[id]); | ||
| + | merge(lef,lef,id); | ||
| + | merge(root,lef,rig); | ||
| + | } | ||
| + | int rank(int root,LL v){ | ||
| + | int lef,rig,ans; | ||
| + | split(root,lef,rig,v-1); | ||
| + | ans=node[lef].sz+1; | ||
| + | merge(root,lef,rig); | ||
| + | return ans; | ||
| + | } | ||
| + | int query(int root,LL vl,LL vr){ | ||
| + | return rank(root,vr)-rank(root,vl); | ||
| + | } | ||
| + | #undef lch | ||
| + | #undef rch | ||
| + | }; | ||
| + | int root[MAXN],col[MAXN],hson[MAXN],dfr[MAXN]; | ||
| + | void solve(){ | ||
| + | int n=1; | ||
| + | col[1]=read_int(); | ||
| + | val[1]=0; | ||
| + | val[0]=MAXV; | ||
| + | Tree1::Insert(1); | ||
| + | Tree2::Insert(root[col[1]],1); | ||
| + | int m=read_int(),lastans=0; | ||
| + | while(m--){ | ||
| + | int t=read_int()^lastans,u=read_int()^lastans,c=read_int()^lastans; | ||
| + | if(t==1){ | ||
| + | int v=hson[u]?hson[u]:dfr[u]; | ||
| + | hson[u]=++n; | ||
| + | col[n]=c; | ||
| + | dfr[n]=v; | ||
| + | val[n]=val[u]+val[v]>>1; | ||
| + | Tree1::Insert(n); | ||
| + | Tree2::Insert(root[c],n); | ||
| + | } | ||
| + | else{ | ||
| + | lastans=Tree2::query(root[c],val[u],val[dfr[u]]); | ||
| + | enter(lastans); | ||
| + | } | ||
| + | } | ||
| + | Tree1::root=0; | ||
| + | _rep(i,1,n){ | ||
| + | root[col[i]]=0; | ||
| + | hson[i]=dfr[i]=0; | ||
| + | } | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int T=read_int(); | ||
| + | while(T--) | ||
| + | solve(); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== G. Hasse Diagram ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给一个根节点的值，然后它延伸出去的点的值都是这个值恰好除以它的一个素因子得到的值，我们把一个点的 $f$ 函数值记做这个图的边数，求 $f(x)$ 的前缀和。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 题干给了 $12$ 的图，可以观察到，如果只是一个 $3$ 的图，也就是 $3$ 和 $1$ 两个点的图。 | ||
| + | |||
| + | $12$ 的图在这个基础上，可以分为 $12$ 和 $4$ ， $6$ 和 $2$ 这两组点，每组都和 $3$ 的图一样，并且这些图之间有边相连，比如 $12$ 连 $6$ ， $6$ 连 $3$ ， $4$ 连 $2$ ， $2$ 连 $1$ ，这些边的个数是 $3$ 的因子数乘 $12$ 除以 $3$ 是 $12$ 除以 $6$ 的多少次幂。 | ||
| + | |||
| + | 如果看到这里，可以推出递推式： $f(n)=(e+1)f({\frac n {p^{e}}})+ed({\frac n {p^{e}}})$ 。 | ||
| + | |||
| + | 经过这道题才知道从 $f(x)$ 推出 $f({\frac n {p^{e}}})$ 的结构也可以用 $Min-25$ 筛来做，原来一直以为必须是积性函数的... | ||
| + | |||
| + | 于是我们对板子魔改一下，变成同时求 $f$ 和 $d$ 的。 $d$ 显然是积性函数，并且 $d(p)$ 和 $d(p^{t})$ 都是很好算的，于是在筛中一起解决， $f$ 用到 $d$ 的结果，一并算出就结束了~ | ||
| + | |||
| + | <hidden 代码> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include<cstdio> | ||
| + | #include<algorithm> | ||
| + | #include<cstring> | ||
| + | #include<cmath> | ||
| + | #define ll long long | ||
| + | using namespace std; | ||
| + | const ll MOD=1145140019,inv2=(MOD+1)>>1,N=3e6,maxn=5e6; | ||
| + | ll prime[maxn],num,sp0[maxn]; | ||
| + | ll n,Sqr,tot,g0[maxn],w[maxn],ind1[maxn],ind2[maxn]; | ||
| + | bool flag[maxn]; | ||
| + | void pre(int n) { //预处理，线性筛 | ||
| + | flag[1]=1; | ||
| + | for(int i=1; i<=n; i++) { | ||
| + | if(!flag[i]) { | ||
| + | prime[++num]=i; | ||
| + | sp0[num]=(sp0[num-1]+1)%MOD; | ||
| + | } | ||
| + | for(int j=1; j<=num&&prime[j]*i<=n; j++) { | ||
| + | flag[i*prime[j]]=1; | ||
| + | if(i%prime[j]==0)break; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | pair<ll,ll> S(ll x,int y) { //第二部分 | ||
| + | if(prime[y]>=x)return make_pair(0,0); | ||
| + | ll k=x<=Sqr?ind1[x]:ind2[n/x]; | ||
| + | ll ansf=(g0[k]-sp0[y]+MOD)%MOD,ansd=ansf*2%MOD; | ||
| + | for(int i=y+1; i<=num&&prime[i]*prime[i]<=x; i++) { | ||
| + | ll pe=prime[i]; | ||
| + | for(int e=1; pe<=x; e++,pe=pe*prime[i]) { | ||
| + | pair<ll,ll> pp=S(x/pe,i); | ||
| + | ansf=(ansf+1ll*(e+1)*pp.first%MOD+1ll*e*(pp.second+(e!=1))%MOD)%MOD; | ||
| + | ansd=(ansd+(e+1)*(pp.second+(e!=1))%MOD); | ||
| + | } | ||
| + | } | ||
| + | ansf%=MOD; | ||
| + | ansd%=MOD; | ||
| + | return make_pair(ansf,ansd); | ||
| + | } | ||
| + | int main() { | ||
| + | int t; | ||
| + | scanf("%d",&t); | ||
| + | pre(N); | ||
| + | while(t--) { | ||
| + | scanf("%lld",&n); | ||
| + | Sqr=sqrt(n); | ||
| + | tot=0; | ||
| + | for(ll i=1; i<=n;) { | ||
| + | ll j=n/(n/i); | ||
| + | w[++tot]=n/i; | ||
| + | g0[tot]=(w[tot]%MOD-1+MOD)%MOD; | ||
| + | if(n/i<=Sqr)ind1[n/i]=tot; | ||
| + | else ind2[n/(n/i)]=tot; | ||
| + | i=j+1; | ||
| + | } | ||
| + | for(int i=1; i<=num; i++) { | ||
| + | for(int j=1; j<=tot&&prime[i]*prime[i]<=w[j]; j++) { | ||
| + | ll k=w[j]/prime[i]<=Sqr?ind1[w[j]/prime[i]]:ind2[n/(w[j]/prime[i])]; | ||
| + | g0[j]=(g0[j]-(g0[k]-sp0[i-1])%MOD+MOD)%MOD; | ||
| + | } | ||
| + | } | ||
| + | printf("%lld\n",S(n,0).first); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| </hidden> | </hidden> | ||
| 行 236: | 行 688: | ||
| solve(); | solve(); | ||
| } | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== K. Starch Cat ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一棵点权树，每次询问一条路径的最大权值，强制在线。其中，路径的权值定义为该路径上的最大权点集，满足点集中所有点都不相邻。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 考虑建立点分树。对固定的根节点 $\text{rt}$，设 $\text{dp}(u,0/1,0/1)$ 表示从根节点出发到 $u$ 的路径，选/不选根节点以及选/不选 $u$ 结点得到的最大权值。 | ||
| + | |||
| + | 不难得到状态转移方程，进一步，设 $f(d,u,0/1)$ 表示 $u$ 在点分树上根节点深度为 $d$ 的结点到 $u$ 的路径，选/不选根节点的最大权值。 | ||
| + | |||
| + | 最后对于询问操作，可以找到 $u,v$ 在点分树上的 $\text{LCA}$，设 $\text{LCA}$ 在点分树的深度为 $d$，则答案为 | ||
| + | |||
| + | $$ | ||
| + | \max(f(d,u,0)+f(d,v,0),f(d,u,1)+f(d,v,1)-a_{\text{LCA}}) | ||
| + | $$ | ||
| + | |||
| + | 时间复杂度 $O((n+m)\log n)$，尽管 $m$ 很大，但常数很小而且时限比较宽松，所以能过。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | struct Rand{ | ||
| + | unsigned int n,seed; | ||
| + | Rand(unsigned int n,unsigned int seed) | ||
| + | :n(n),seed(seed){} | ||
| + | int get(long long lastans){ | ||
| + | seed ^= seed << 13; | ||
| + | seed ^= seed >> 17; | ||
| + | seed ^= seed << 5; | ||
| + | return (seed^lastans)%n+1; | ||
| + | } | ||
| + | }; | ||
| + | const int MAXN=5e5+5,MAXD=20; | ||
| + | const LL inf=1e15; | ||
| + | struct Edge{ | ||
| + | int to,next; | ||
| + | }edge[MAXN<<1]; | ||
| + | int head[MAXN],edge_cnt; | ||
| + | void Insert(int u,int v){ | ||
| + | edge[++edge_cnt]=Edge{v,head[u]}; | ||
| + | head[u]=edge_cnt; | ||
| + | } | ||
| + | int sz[MAXN],mson[MAXN],tot_sz,root,root_sz; | ||
| + | bool vis[MAXN]; | ||
| + | int a[MAXN],rt[MAXD][MAXN]; | ||
| + | LL dp[MAXN][2][2],dp2[MAXD][MAXN][2]; | ||
| + | void dfs(int u,int fa,int dep){ | ||
| + | rt[dep][u]=root; | ||
| + | if(fa==0){ | ||
| + | dp[u][0][0]=0; | ||
| + | dp[u][1][1]=a[u]; | ||
| + | dp[u][1][0]=dp[u][0][1]=-inf; | ||
| + | } | ||
| + | else{ | ||
| + | dp[u][0][0]=max(dp[fa][0][0],dp[fa][0][1]); | ||
| + | dp[u][0][1]=dp[fa][0][0]+a[u]; | ||
| + | dp[u][1][0]=max(dp[fa][1][0],dp[fa][1][1]); | ||
| + | dp[u][1][1]=dp[fa][1][0]+a[u]; | ||
| + | } | ||
| + | dp2[dep][u][0]=max(dp[u][0][0],dp[u][0][1]); | ||
| + | dp2[dep][u][1]=max(dp[u][1][0],dp[u][1][1]); | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | if(vis[v]||v==fa) | ||
| + | continue; | ||
| + | dfs(v,u,dep); | ||
| + | } | ||
| + | } | ||
| + | void solve2(int u,int dep){ | ||
| + | dfs(u,0,dep); | ||
| + | } | ||
| + | void find_root(int u,int fa){ | ||
| + | sz[u]=1;mson[u]=0; | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | if(vis[v]||v==fa) | ||
| + | continue; | ||
| + | find_root(v,u); | ||
| + | sz[u]+=sz[v]; | ||
| + | mson[u]=max(mson[u],sz[v]); | ||
| + | } | ||
| + | mson[u]=max(mson[u],tot_sz-sz[u]); | ||
| + | if(mson[u]<root_sz){ | ||
| + | root=u; | ||
| + | root_sz=mson[u]; | ||
| + | } | ||
| + | } | ||
| + | void solve(int u,int dep){ | ||
| + | int cur_sz=tot_sz; | ||
| + | vis[u]=true; | ||
| + | solve2(u,dep); | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | if(vis[v]) | ||
| + | continue; | ||
| + | tot_sz=sz[v]>sz[u]?cur_sz-sz[u]:sz[v]; | ||
| + | root_sz=MAXN; | ||
| + | find_root(v,u); | ||
| + | solve(root,dep+1); | ||
| + | } | ||
| + | } | ||
| + | LL query(int u,int v){ | ||
| + | int d=0; | ||
| + | while(rt[d][u]&&rt[d][u]==rt[d][v])d++; | ||
| + | d--; | ||
| + | return max(dp2[d][u][0]+dp2[d][v][0],dp2[d][u][1]+dp2[d][v][1]-a[rt[d][u]]); | ||
| + | } | ||
| + | int main(){ | ||
| + | int n=read_int(),m=read_int(),seed=read_int(); | ||
| + | _rep(i,1,n)a[i]=read_int(); | ||
| + | _rep(i,2,n){ | ||
| + | int f=read_int(); | ||
| + | Insert(f,i); | ||
| + | Insert(i,f); | ||
| + | } | ||
| + | root_sz=MAXN; | ||
| + | tot_sz=n; | ||
| + | find_root(1,0); | ||
| + | solve(root,0); | ||
| + | long long lastans=0,ans=0; | ||
| + | constexpr int P=998244353; | ||
| + | Rand rand(n,seed); | ||
| + | for(int i=0;i<m;i++){ | ||
| + | int u=rand.get(lastans); | ||
| + | int v=rand.get(lastans); | ||
| + | int x=rand.get(lastans); | ||
| + | lastans=query(u,v);//calculate the answer | ||
| + | ans=(ans+lastans%P*x)%P; | ||
| + | } | ||
| + | enter(ans); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest10.1627973878.txt.gz · 最后更改: 2021/08/03 14:57 由 jxm2001
