UPD 7:46 马上就要模拟赛了 希望这次能考得好一点
UPD 14:20 233感觉博客的保佑非常有效,实力进前十 以后也这么干
也是一道KD-Tree
先 $O(n)$ 预处理出DFS序和深度,
这样就能知道每个点的子树以及与它的距离
把第 $i$ 个点当做 $(st_i,dep_i)$ 放到平面上
然后每次修改时修改$ \{st_u,dep_u,en_u,dep_u+l\} $这个矩阵内的点就可以了
不过要注意直接找是找不到的
因为深度可能会一样,而 $nth\_element$ 找的不一定是深度一样中最右边那一个
也就是说深度和某个点一样的可能在它的右子树而不是左子树
所以要记录一下编号
#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #include<set> #include<map> #include<bitset> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Drp(x,a,b) for (int x=a;x>=b;x--) #define Cross(x,a) for (int x=head[a];~x;x=next[x]) #define ll long long #define oo (1<<29) #define mk(a,b) make_pair(a,b) #define fr first #define sc second #define MOD 1000000007 using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } inline void OUT(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) OUT(x/10),putchar(x%10+'0'); else putchar(x+'0'); } const int N=100005; int D,n,c,q; struct KDT{ int d[2],col,lzc,Mn[2],Mx[2],t,lzt,id; KDT *Fa,*l,*r; bool operator <(const KDT&x)const{return d[D]==x.d[D]?d[D^1]<x.d[D^1]:d[D]<x.d[D];} }a[N],*R,qry; int to[N],next[N],head[N],cnt,pos[N]; inline void AddEdge(int u,int v){ to[cnt]=v;next[cnt]=head[u];head[u]=cnt++; } int st[N],en[N],Tm,dep[N]; void DFS(int u){ st[u]=++Tm; Cross(i,u) dep[to[i]]=dep[u]+1,DFS(to[i]); en[u]=Tm; } void Update(KDT *x,KDT *y){ if (!y) return; Rep(i,0,1) x->Mn[i]=min(x->Mn[i],y->Mn[i]), x->Mx[i]=max(x->Mx[i],y->Mx[i]); } KDT *Build(int l,int r,int nd,KDT *f){ if (r<l) return 0; D=nd;int mid=l+r>>1; nth_element(a+l,a+mid,a+r+1); a[mid].col=a[mid].lzc=1; pos[a[mid].id]=mid; Rep(i,0,1) a[mid].Mn[i]=a[mid].Mx[i]=a[mid].d[i]; a[mid].Fa=f; a[mid].l=Build(l,mid-1,nd^1,a+mid); a[mid].r=Build(mid+1,r,nd^1,a+mid); Update(a+mid,a[mid].l),Update(a+mid,a[mid].r); return a+mid; } int Query(KDT *qry){ D=0; int Mxt=qry->t,ret=qry->col; KDT *now=qry; while (now->Fa){ now=now->Fa; if (now->lzt>Mxt) Mxt=now->lzt,ret=now->lzc; D^=1; } return ret; } void Modify(KDT *u,int X1,int Y1,int X2,int Y2,int col){ if (!u) return; if (u->Mx[0]<X1||u->Mn[0]>X2||u->Mx[1]<Y1||u->Mn[1]>Y2) return; if (u->Mn[0]>=X1&&u->Mx[0]<=X2&&u->Mn[1]>=Y1&&u->Mx[1]<=Y2){ u->lzt=u->t=Tm,u->col=u->lzc=col; return; } if (u->d[0]>=X1&&u->d[0]<=X2&&u->d[1]>=Y1&&u->d[1]<=Y2){u->t=Tm,u->col=col;} Modify(u->l,X1,Y1,X2,Y2,col),Modify(u->r,X1,Y1,X2,Y2,col); } int main(){ int T=IN(); while (T--){ n=IN(),c=IN(),q=IN(); memset(head,-1,sizeof head);cnt=0; Rep(i,2,n){ int u=IN(); AddEdge(u,i); } Tm=0,dep[1]=1,DFS(1); memset(a,0,sizeof a); Rep(i,1,n) a[i].d[0]=st[i],a[i].d[1]=dep[i],a[i].id=i; R=Build(1,n,0,0); Tm=0; int Ans=0; Rep(i,1,q){ Tm++; int u=IN(),l=IN(),c=IN(); if (c==0) (Ans+=1ll*Query(a+pos[u])*i%MOD)%=MOD; else Modify(R,st[u],dep[u],en[u],dep[u]+l,c); } OUT(Ans),putchar('\n'); } }
今天模拟赛出了这道题……离上次做的183E仅仅只有一墙之隔……
然而Dirak说上次我给他说了183E之后他不小心去看了D的题解
好气啊!!!!(虽然也就比我高了10分)
概率DP+贪心
令 $g_{i,j,k}$ 表示当前是第 $i$ 种袜子,问到第 $j$ 个人,初始有 $k$ 双袜子的送出期望
$g_{i,j,k}=(g_{i,j-1,k-1}+1)*a_{j,i}+g_{i,j-1,k}*(1-a_{j,i})$
比较显然的就是同一种袜子,拿得越多与上一次的相差就越小
于是就先预处理出$g_{i,n,1} (1≤i≤m)$
一开始什么都不拿
然后每次把贡献最大那种袜子的加到答案里,更新一下拿下一只这种袜子的贡献
复杂度$O(n^2+n*m)$
需要滚存
#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #include<set> #include<map> #include<bitset> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Drp(x,a,b) for (int x=a;x>=b;x--) #define Cross(x,a) for (int x=head[a];~x;x=next[x]) #define ll long long #define oo (1<<29) #define mk(a,b) make_pair(a,b) #define fr first #define sc second using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } inline void OUT(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) OUT(x/10),putchar(x%10+'0'); else putchar(x+'0'); } const int N=3005,M=305; int n,m,p; double a[N][M],g[M][N][2],Ans; bool G[M]; int main(){ n=IN(),m=IN(); Rep(i,1,n) Rep(j,1,m) a[i][j]=IN()/1000.0; Rep(i,1,m) Rep(j,1,n) g[i][j][G[i]]=(g[i][j-1][G[i]^1]+1)*a[j][i]+g[i][j-1][G[i]]*(1-a[j][i]); Rep(i,1,n){ double Mx=0; Rep(j,1,m) if (g[j][n][G[j]]-g[j][n][G[j]^1]>Mx) Mx=g[j][n][G[j]]-g[j][n][G[j]^1],p=j; Ans+=Mx,G[p]^=1; Rep(j,1,n) g[p][j][G[p]]=(g[p][j-1][G[p]^1]+1)*a[j][p]+g[p][j-1][G[p]]*(1-a[j][p]); } printf("%.15lf\n",Ans); return 0; }
为了复习(预习?)一下AC自动机而做的一道题
答案就是所有可能的文本减去没有单词出现的文本
先构造AC自动机,然后 $dp_{i,j}$ 表示走了 $i$ 步,当前在节点 $j$ 的方案数
搞一搞就好了
#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #include<set> #include<map> #include<bitset> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Drp(x,a,b) for (int x=a;x>=b;x--) #define Cross(x,a) for (int x=head[a];~x;x=next[x]) #define ll long long #define oo (1<<29) #define mk(a,b) make_pair(a,b) #define fr first #define sc second #define MOD 10007 using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } inline void OUT(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) OUT(x/10),putchar(x%10+'0'); else putchar(x+'0'); } const int N=65,L=105; int n,m,Cnt=0,dp[L][L*N]; char s[L]; struct Trie{ Trie *next[26],*fail; bool fin; }a[N*L],*R; void Insert(char *s){ int len=strlen(s); Trie *now=a; Rep(i,0,len-1){ if (!now->next[s[i]-'A']) now->next[s[i]-'A']=++Cnt+a; now=now->next[s[i]-'A']; } now->fin=1; } queue<Trie*>q; void Build(){ Rep(i,0,25){ Trie *&v=a[0].next[i]; if (v) v->fail=a,q.push(v); else v=a; } while (!q.empty()){ Trie *now=q.front();q.pop(); Rep(i,0,25){ Trie *&v=now->next[i]; if (v){ q.push(v); Trie *Fa=now->fail; while (Fa!=a&&!Fa->next[i]) Fa=Fa->fail; v->fail=Fa->next[i]; v->fin|=Fa->next[i]->fin; } else v=now->fail->next[i]; } } } int main(){ n=IN(),m=IN(); R=a,Cnt=0; Rep(i,1,n){ scanf("%s",s); Insert(s); } Build(); dp[0][0]=1; Rep(i,1,m) Rep(j,0,Cnt){ if (!dp[i-1][j]||a[j].fin) continue; Rep(k,0,25){ Trie *v=a[j].next[k]; if (!v->fin) (dp[i][v-a]+=dp[i-1][j])%=MOD; } } int Ans=1; Rep(i,1,m) (Ans*=26)%=MOD; Rep(i,0,Cnt) if (!a[i].fin) (Ans+=MOD-dp[m][i])%=MOD; OUT(Ans); }