四道题都比较套路，AK了。
T1 [模拟赛20230112] 密接
枚举区间的左端点，再枚举众数出现的次数，那么满足条件的右端点就是一段区间。令 \(pos1_i\) 为第一个出现 \(i\) 次的数的位置，\(pos2_i\) 位第二个。那么这段区间就是 \([pos1_i,min{pos2_i,pos1_i+1})\)。
然后考虑维护 \(pos\)。从右往左枚举左端点，在左端点新加进来一个数，考虑这个数在之后出现的位置，可以有可能将 \(pos\) 变小，就直接更新。
复杂度 \(O(100n)\)。
#include<bits/stdc++.h>
using namespace std;
inline int in(){
int x;
scanf("%d",&x);
return x;
}
const int N=1e5+5;
int n,m,a[N],b[N];
int mn1[105],mn2[105];
int id[N],pos[N][105],cnt[N];
int main(){
// freopen("close.in","r",stdin);
// freopen("close.out","w",stdout);
n=in();
for(int i=1;i<=n;i++)a[i]=b[i]=in();
sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+m+1,a[i])-b;
id[i]=++cnt[a[i]];
pos[a[i]][cnt[a[i]]]=i;
}
for(int i=1;i<=101;i++)mn1[i]=mn2[i]=n+1;
long long ans=0;
for(int i=n;i>=1;i--){
int p=id[i];
for(int x=p,y=1;x<=cnt[a[i]];x++,y++){
int v=pos[a[i]][x];
if(v<mn1[y])mn2[y]=mn1[y],mn1[y]=v;
else if(v<mn2[y])mn2[y]=v;
}
for(int j=1;j<=100;j++){
ans+=min(mn1[j+1],mn2[j])-mn1[j];
}
}
cout<<ans<<endl;
return 0;
}
T2 [模拟赛20230112] 确诊
没什么好说的，直接单调队列维护sg转移就行。（好像这个题也可以直接贪心）
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int n,k;
int pri[N],inp[N],pc;
int f[N];
int q1[N],l1,r1,q2[N],l2,r2;
int q3[N],l3,r3,q4[N],l4,r4;
int main(){
// freopen("game.in","r",stdin);
// freopen("game.out","w",stdout);
cin>>n>>k;
for(int i=2;i<=n;i++){
if(!inp[i])pri[++pc]=i;
for(int j=1;j<=pc&&i*pri[j]<=n;j++){
inp[i*pri[j]]=1;
if(i%pri[j]==0)break;
}
}
l1=l2=l3=l4=1;
for(int i=2;i<n;i++){
while(l1<=r1&&i-k>q1[l1])l1++;
while(l2<=r2&&i-k>q2[l2])l2++;
while(l3<=r3&&i-k>q3[l3])l3++;
while(l4<=r4&&i-k>q4[l4])l4++;
if(inp[i]){
if(l2<=r2)f[i]=-f[q2[l2]]+1;
else if(l1<=r1)f[i]=-f[q1[l1]]-1;
if(f[i]>0){
while(l3<=r3&&f[q3[r3]]<=f[i])r3--;
q3[++r3]=i;
}else{
while(l4<=r4&&f[q4[r4]]<=f[i])r4--;
q4[++r4]=i;
}
}else{
if(l4<=r4)f[i]=-f[q4[l4]]+1;
else if(l3<=r3)f[i]=-f[q3[l3]]-1;
if(f[i]>0){
while(l1<=r1&&f[q1[r1]]<=f[i])r1--;
q1[++r1]=i;
}else{
while(l2<=r2&&f[q2[r2]]<=f[i])r2--;
q2[++r2]=i;
}
}
}
int ans=1e9;
for(int i=max(1,n-k);i<n;i++)if(!inp[i]){
if(ans==1e9)ans=f[i];
if(f[i]<=0&&ans>0)ans=f[i];
if(f[i]<=0||ans>0)ans=max(ans,f[i]);
}
if(ans==1e9)return cout<<0,0;
ans=-ans;if(ans>=0)ans++;else ans--;
cout<<ans<<endl;
return 0;
}
T3 [模拟赛20230112] 重症
比较套路的矩阵树板子题。
众所周知，矩阵树的边权不仅可以是一个数，还能是一个多项式。
但是我比较愚蠢，没有构造出多项式，不过这个东西是好用矩阵进行转移的，于是就突发奇想：能不能行列式套矩阵？
于是就试了试，具体地，要写矩阵加减乘以及求逆。但是就遇到了一个问题：矩阵乘法不满足交换律，那么求行列式时就不能进行行变换！
但是最后硬着头皮写完，居然AC了！
究其根本，虽然矩阵乘法没有交换律，但是这种矩阵树的题，矩阵对应的是每条边的边权，而对矩阵乘法的顺序进行交换，就相当于对树的dfs序的顺序进行交换，这显然是不会影响到最终的答案的，所以在矩阵树上套矩阵然后直接求行列式是正确的。
感觉矩阵树套矩阵可以解决很多问题，但是常数比直接套多项式大得多。
#include<bits/stdc++.h>
using namespace std;
inline int in(){
int x;
scanf("%d",&x);
return x;
}
const int N=205,mod=998244353;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int qpow(int a,int b){
int c=1;
for(;b;b>>=1,a=mul(a,a))if(b&1)c=mul(c,a);
return c;
}
struct mtx{
int a[4][4];
int* operator [](int x){return a[x];}
mtx(){
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
a[i][j]=0;
}
};
void print(mtx a){
for(int i=0;i<4;i++){
for(int j=0;j<4;j++)cout<<a[i][j]<<' ';
cout<<endl;
}
cout<<endl;
}
mtx I(){
mtx a;
for(int i=0;i<4;i++)a[i][i]=1;
return a;
}
mtx build(int c,int d){
mtx a=I();
a[0][1]=c,a[0][2]=d,a[0][3]=mul(c,d);
a[1][3]=d,a[2][3]=c;
return a;
}
mtx operator + (mtx a,mtx b){
mtx c;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
c[i][j]=add(a[i][j],b[i][j]);
return c;
}
mtx operator - (mtx a,mtx b){
mtx c;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
c[i][j]=add(a[i][j],mod-b[i][j]);
return c;
}
mtx operator * (mtx a,mtx b){
mtx c;
for(int i=0;i<4;i++)
for(int k=0;k<4;k++)
for(int j=0;j<4;j++)
c[i][j]=add(c[i][j],mul(a[i][k],b[k][j]));
return c;
}
mtx getinv(mtx a){
static int b[4][8];
for(int i=0;i<4;i++)
for(int j=0;j<8;j++){
if(j<4)b[i][j]=a[i][j];
else b[i][j]=(j==i+4);
}
for(int i=0;i<4;i++){
int inv=qpow(b[i][i],mod-2);
for(int j=i;j<8;j++)b[i][j]=mul(b[i][j],inv);
for(int j=i+1;j<4;j++){
for(int k=j+1;k<8;k++)
b[j][k]=add(b[j][k],mod-mul(b[i][k],b[j][i]));
}
}
for(int i=3;i>=0;i--){
for(int j=i-1;j>=0;j--){
int v=b[j][i];
for(int k=i;k<8;k++)
b[j][k]=add(b[j][k],mod-mul(v,b[i][k]));
}
}
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
a[i][j]=b[i][j+4];
return a;
}
int n,m;
mtx f[N][N];
mtx det(){
mtx res=I();
for(int i=1;i<n;i++){
res=res*f[i][i];
mtx inv=getinv(f[i][i]);
for(int j=i;j<n;j++)f[i][j]=f[i][j]*inv;
for(int j=i+1;j<n;j++){
for(int k=n-1;k>=i;k--)
f[j][k]=f[j][k]-(f[i][k]*f[j][i]);
}
}
return res;
}
int main(){
// freopen("icu.in","r",stdin);
// freopen("icu.out","w",stdout);
n=in(),m=in();
while(m--){
int x=in(),y=in(),c=in(),d=in();
mtx a=build(c,d);
f[x][x]=f[x][x]+a,f[y][y]=f[y][y]+a;
f[x][y]=f[x][y]-a,f[y][x]=f[y][x]-a;
}
mtx res=det();
cout<<res[0][3]<<endl;
return 0;
}
T4 [模拟赛20230112] 康复
比较套路的字符串题。
要字典序大于 \(X\),又要字典序最小，那么结果一定是 \(X\) 的一个前缀再加上一个字符。
于是枚举这个前缀 \(X_1 \sim X_i\)，找出 \([l,r]\) 区间内这个前缀的出现位置，看一看有没有接下来一个字符大于 \(X_{i+1}\) 的，然后要接下来一个字符最小的。
具体地，就直接在 SAM 的 parent 树上对 26 个字符分别用线段树维护其末尾位置，然后查询的时候枚举字符再区间查询。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=1e6+5;
int n,q,ql[N],qr[N],qk[N];
char s[N],ss[N],*t[N];
int *pos[N];
int fa[M],len[M],ch[M][26],lst=1,tot=1,tag[M];
void insert(int c){
int p=lst,np=++tot;lst=np;
len[np]=len[p]+1;
for(;!ch[p][c];p=fa[p])ch[p][c]=np;
if(!p){fa[np]=1;return;}
int q=ch[p][c];
if(len[q]==len[p]+1){fa[np]=q;return;}
int nq=++tot;len[nq]=len[p]+1;
fa[nq]=fa[q],fa[q]=fa[np]=nq;
for(int i=0;i<26;i++)ch[nq][i]=ch[q][i];
for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
}
vector<int> e[M];
int rt[M][26],tot1;
struct node{
int ls,rs;
}T[M*25];
#define ls(x) T[(x)].ls
#define rs(x) T[(x)].rs
void insert(int &p,int l,int r,int d){
if(!p)p=++tot1;
if(l==r)return;
int mid=l+r>>1;
if(d<=mid)insert(ls(p),l,mid,d);
else insert(rs(p),mid+1,r,d);
}
bool query(int p,int l,int r,int ql,int qr){
if(!p)return 0;
if(ql<=l&&r<=qr)return 1;
int mid=l+r>>1;bool res=0;
if(ql<=mid)res=query(ls(p),l,mid,ql,qr);
if(mid<qr&&!res)res=query(rs(p),mid+1,r,ql,qr);
return res;
}
int merge(int p,int q,int l,int r){
if(!p||!q)return p|q;
if(l==r)return p;
int mid=l+r>>1;
int x=++tot1;
ls(x)=merge(ls(p),ls(q),l,mid);
rs(x)=merge(rs(p),rs(q),mid+1,r);
return x;
}
void dfs(int x){
if(tag[x]||x==1){
int c=s[tag[x]+1]-'a';
insert(rt[x][c],0,n-1,tag[x]);
}
for(int y:e[x]){
dfs(y);
for(int i=0;i<26;i++)
rt[x][i]=merge(rt[x][i],rt[y][i],0,n-1);
}
}
int main(){
// freopen("heal.in","r",stdin);
// freopen("heal.out","w",stdout);
scanf("%s",s+1),n=strlen(s+1);
for(int i=1;i<n;i++){
insert(s[i]-'a');
while(len[fa[lst]]==len[lst])lst=fa[lst];
tag[lst]=i;
}
tag[1]=0;
scanf("%d",&q);
for(int i=1;i<=q;i++){
scanf("%d %d %s",ql+i,qr+i,ss+1);
qk[i]=strlen(ss+1);
t[i]=new char [qk[i]+3];
pos[i]=new int [qk[i]+2];
for(int j=0;j<qk[i]+2;j++)t[i][j]=ss[j];
lst=1;
for(int j=1;j<=qk[i];j++){
insert(ss[j]-'a');
while(len[fa[lst]]==len[lst])lst=fa[lst];
pos[i][j]=lst;
}
pos[i][0]=1;
}
for(int i=2;i<=tot;i++)e[fa[i]].push_back(i);
dfs(1);
for(int i=1;i<=q;i++){
int l=ql[i],r=qr[i],k=qk[i];
bool flag=0;
for(int j=min(r-l,k);j>=0;j--){
int c=j==k?0:t[i][j+1]-'a'+1,x=pos[i][j];
for(int y=c;y<26;y++){
if(query(rt[x][y],0,n-1,l+j-1,r-1)){
t[i][j+1]=y+'a',t[i][j+2]=0;
flag=1;break;
}
}
if(flag)break;
}
if(!flag)puts("-1");
else printf("%s\n",t[i]+1);
}
return 0;
}