4.11
闲话
- 白天考试，依次是英语早读，理综，英语，数学，长达 \(2h\) 的文综自习，文综。
- 理综
- 物理
- 多选 \(BD\) 涂成了 \(CD\) ，挂了 \(3pts\) 。
- 因不知道水是比热容最大的液体，多分讨了一种情况，挂了 \(1pts\) 。
- 化学
- 物理
- 英语
- \(D\) 篇阅读感觉挺贴合自身实际的。
- 数学
- 已知 \(\frac{x+3}{(x-2)^{2}}=\frac{A}{(x-2)^{2}}+\frac{B}{(x-2)}\) ，求 \(A-B\) 。
- 正解：假设 \(A,B\) 为常数，然后就做完了。
- 非正解：不可做，跳了。
- “不透明的桌子”“不透明的正方体”
- 已知 \(\frac{x+3}{(x-2)^{2}}=\frac{A}{(x-2)^{2}}+\frac{B}{(x-2)}\) ，求 \(A-B\) 。
- 文综自习
- 课代表要求自由背诵，但前排靠门处在背诵，后排在聊天，被年级主任抓了，然后 \(D\) 了一顿。
- 文综
- 写完卷后 \(50min\) 都在罚坐，翻了翻世界古代史。
- 理综
- 晚上现班主任因我们太浮躁，还有被年级主任抓了的事情，把我们 \(D\) 了一顿。为了更好地营造反思环境，他甚至关了灯 \(D\) 我们。
做题纪要
4.12
闲话
- 白天讲评试卷，但体育课正常上。
- 物理课，物理老师讲了下今年强基的情况，劝诫我们不要偏科。
- 历史课前，历史老师统计了下班级总分排名情况和历史满分情况。信奥作为前两百最少的（ \(3/12\) ），历史满分却是最多的 （\(6/11\)） 。
- 化学老师请假了，请了化学奥赛教练来代课，讲完后不知道讲啥就讲了讲今年强基的情况和他当时在 HZ 的 \(whk\) 成绩，劝诫我们不要偏科。
- 因白天讲评占了奥赛课，所以第 \(9\) 节课到晚三都改奥赛。
做题纪要
luogu P7409 SvT
-
记给出的后缀去重后得到 \(a\) ，将其按 \(rk\) 排序后，由 1.字符串专题 B CF1073G Yet Another LCP Problem 有 \(\sum\limits_{i=1}^{|a|}\sum\limits_{j=i+1}^{|a|}LCP(s_{a_{i} \sim n},s_{a_{j} \sim n})=\sum\limits_{i=1}^{k}\sum\limits_{j=i}^{k}\min\limits_{h=i}^{j}\{ g_{h} \}\) 。
点击查看代码
const ll p=23333333333333333; ll sa[500010],rk[1000010],oldrk[1000010],id[500010],cnt[500010],key[500010],height[500010],a[3000010],fminn[500010][20],g[3000010]; __int128_t f[3000010]; char s[500010]; void write(__int128_t x) { if(x<0) { putchar('-'); x=-x; } if(x>9) { write(x/10); } putchar((x%10)+'0'); } bool cmp(ll a,ll b) { return rk[a]<rk[b]; } ll val(char x) { return (ll)x; } void counting_sort(ll n,ll m) { memset(cnt,0,sizeof(cnt)); for(ll i=1;i<=n;i++) { cnt[key[i]]++; } for(ll i=1;i<=m;i++) { cnt[i]+=cnt[i-1]; } for(ll i=n;i>=1;i--) { sa[cnt[key[i]]]=id[i]; cnt[key[i]]--; } } void init_sa(char s[],ll len) { ll m=127,tot=0,num=0,i,j,w; for(i=1;i<=len;i++) { rk[i]=val(s[i]); id[i]=i; key[i]=rk[id[i]]; } counting_sort(len,m); for(w=1;tot!=len;w<<=1,m=tot) { num=0; for(i=len;i>=len-w+1;i--) { num++; id[num]=i; } for(i=1;i<=len;i++) { if(sa[i]>w) { num++; id[num]=sa[i]-w; } } for(i=1;i<=len;i++) { key[i]=rk[id[i]]; } counting_sort(len,m); for(i=1;i<=len;i++) { oldrk[i]=rk[i]; } tot=0; for(i=1;i<=len;i++) { tot+=(oldrk[sa[i]]!=oldrk[sa[i-1]]||oldrk[sa[i]+w]!=oldrk[sa[i-1]+w]); rk[sa[i]]=tot; } } for(i=1,j=0;i<=len;i++) { j-=(j>=1); while(s[i+j]==s[sa[rk[i]-1]+j]) { j++; } height[rk[i]]=j; } } void init(ll n,ll a[]) { memset(fminn,0x3f,sizeof(fminn)); for(ll i=1;i<=n;i++) { fminn[i][0]=a[i]; } for(ll j=1;j<=log2(n);j++) { for(ll i=1;i<=n-(1<<j)+1;i++) { fminn[i][j]=min(fminn[i][j-1],fminn[i+(1<<(j-1))][j-1]); } } } ll query(ll l,ll r) { ll t=log2(r-l+1); return min(fminn[l][t],fminn[r-(1<<t)+1][t]); } __int128_t ask(ll n,ll k,ll a[]) { __int128_t sum=0; ll i; stack<ll>st; sort(a+1,a+1+k,cmp); for(i=1;i<=k;i++) { g[i]=query(rk[a[i-1]]+1,rk[a[i]]); } for(i=1;i<=k;i++) { while(st.empty()==0&&g[st.top()]>=g[i]) { st.pop(); } if(st.empty()==0) { f[i]=(f[st.top()]+g[i]*(i-st.top())%p)%p; } else { f[i]=(f[0]+g[i]*(i-0)%p)%p; } st.push(i); sum=(sum+f[i])%p; } return sum; } int main() { ll n,m,k,i,j; cin>>n>>m>>(s+1); init_sa(s,n); init(n,height); for(j=1;j<=m;j++) { cin>>k; for(i=1;i<=k;i++) { cin>>a[i]; } sort(a+1,a+1+k); k=unique(a+1,a+1+k)-(a+1); write(ask(n,k,a)); cout<<endl; } return 0; }