【考试总结】2022-02-21
排队
因为序列最终会变成有序的，那么没有说过悄悄话的女生 (upd:thefalse4338 说这里一定要写同学，因为我不一定知道题干中写的“她们”一定代表这些人是有性别的) 的身高一定是单调的
那么问题转化成了求最长上升子序列的长度和求哪些元素是一定在 \(\rm LIS\) 中
那么计算 \(\rm LIS\) 的方案数使对大质数取模即可
我使用了 unsigned long long 就挂了
Code Display
int pref[N],suff[N];
int dp1[N],dp2[N],n,a[N];
struct Fenwick{
int met[N];
int c[N];
inline void insert(int x,pair v){
for(;x<=n;x+=x&(-x)){
if(c[x]==v.fir) ckadd(met[x],v.sec);
else if(c[x] query(int x){
pair res={0,1};
for(;x;x-=x&(-x)){
if(c[x]>res.fir) res.fir=c[x],res.sec=met[x];
else if(c[x]==res.fir) ckadd(res.sec,met[x]);
}
return res;
}
}T;
signed main(){
freopen("queue.in","r",stdin); freopen("queue.out","w",stdout);
n=read();
rep(i,1,n){
a[i]=read();
pair now=T.query(a[i]);
dp1[i]=now.fir+1;
pref[i]=now.sec;
T.insert(a[i],make_pair(dp1[i],pref[i]));
}
memset(T.met,0,sizeof(T.met));
memset(T.c,0,sizeof(T.c));
rep(i,1,n) a[i]=n-a[i]+1;
Down(i,n,1){
pair now=T.query(a[i]);
dp2[i]=now.fir+1;
suff[i]=now.sec;
T.insert(a[i],make_pair(dp2[i],suff[i]));
}
int sum=0,Mx=0;
rep(i,1,n) ckmax(Mx,dp1[i]+dp2[i]);
rep(i,1,n) if(dp2[i]==1&&dp1[i]+dp2[i]==Mx) ckadd(sum,pref[i]);
print(Mx-1); putchar('\n');
for(int i=1;i<=n;++i){
if(dp1[i]+dp2[i]==Mx&&mul(pref[i],suff[i])==sum) print(i);
} putchar('\n');
return 0;
}
树论
一个比较基础的 \(\rm DP\) 就是设 \(f_{x,i}\) 表示 \(x\) 为根的子树里面 \(x\) 的数值是 \(i\) 的方案数
暴力是以每个节点为根 \(dfs\) 求出来方案数乘权值 \(i\) 贡献给答案
我们将转移式子写出来看看：\(dp_{x,i}\times dp_{t,j}[(i,j)=1]\to dp_{x,i}\)
这个东西是非常基础的反演式子，使用调和级数复杂度的统计方式就行了
复杂度并不允许每个点 \(dfs\)，所以就可以写个换根 \(\rm DP\)
Code Display
const int N=60,M=50010;
int dp[N][M],n,l[N],r[N];
vector G[N];
bool fl[M];
int pri[M],mu[M],cnt;
int sum[M],ton[M];
inline void dfs(int x,int fat){
rep(i,l[x],r[x]) dp[x][i]=1;
for(auto t:G[x]) if(t!=fat){
dfs(t,x);
rep(i,1,r[t]){
for(int j=(l[t]+i-1)/i*i;j<=r[t];j+=i) ton[i]+=dp[t][j];
}
for(int i=1;i<=r[x];++i) if(ton[i]){
for(int j=(l[x]+i-1)/i*i;j<=r[x];j+=i){
sum[j]+=ton[i]*mu[i];
}
}
for(int i=l[x];i<=r[x];++i){
sum[i]=(sum[i]%mod+mod)%mod;
ckmul(dp[x][i],sum[i]);
sum[i]=0;
}
rep(i,1,r[t]) ton[i]=0;
}
return ;
}
int tmp[M];
inline void get_ans(int x,int fat){
for(auto t:G[x]) if(t!=fat){
rep(i,1,r[t]){
for(int j=(l[t]+i-1)/i*i;j<=r[t];j+=i) ton[i]+=dp[t][j];
}
for(int i=1;i<=r[x];++i) if(ton[i]){
for(int j=(l[x]+i-1)/i*i;j<=r[x];j+=i){
sum[j]+=ton[i]*mu[i];
}
}
for(int i=l[x];i<=r[x];++i){
sum[i]=(sum[i]%mod+mod)%mod;
tmp[i]=mul(ksm(sum[i],mod-2),dp[x][i]);
sum[i]=0;
}
rep(i,1,r[t]) ton[i]=0;
rep(i,1,r[x]){
for(int j=(l[x]+i-1)/i*i;j<=r[x];j+=i) ton[i]+=tmp[j];
tmp[i]=0;
}
for(int i=1;i<=r[t];++i) if(ton[i]){
for(int j=(l[t]+i-1)/i*i;j<=r[t];j+=i){
sum[j]+=ton[i]*mu[i];
}
}
for(int i=l[t];i<=r[t];++i){
ckmul(dp[t][i],(sum[i]%mod+mod)%mod);
sum[i]=0;
}
rep(i,1,r[x]) ton[i]=0;
get_ans(t,x);
} return ;
}
signed main(){
freopen("tree.in","r",stdin); freopen("tree.out","w",stdout);
n=50000; mu[1]=1;
for(int i=2;i<=n;++i){
if(!fl[i]) pri[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&i*pri[j]<=n;++j){
fl[i*pri[j]]=1;
if(i%pri[j]==0) break;
mu[i*pri[j]]=-mu[i];
}
}
n=read();
rep(i,1,n) l[i]=read();
rep(i,1,n) r[i]=read();
for(int i=1,u,v;i 麻烦的杂货店
设 \(pre_i=\min\{j|sum_j=sum_i,\forall\ k\in[j,i]sum_k\ge sum_i\}\)，\(next_i=\max\{j|sum_j=sum_i,\forall\ k\in[i,j]sum_k\ge sum_i\}\)，这个正反两边扫就能找到了
对于每组询问，找到区间内部前缀和最小的点的第一和最后一次出现位置 \(fa,la\) ，那么选择这段子区间是合法的
对于 \([ql,fa]\) 和 \([la,qr]\) 两部分，本质上是求区间里面 \(i-pre_i,nxt_i-i\) 和最大值，使用 \(\rm ST\) 表维护即可，同时上面找最小值第一/最后一次出现也可以使用 \(\rm ST\) 表维护
Code Display
const int N=2e5+10;
int lst[N],lef[20][N],lg[N],rig[20][N],sum[N],n;
char s[N];
int pre[N],nxt[N],st[20][N],ed[20][N],Q;
inline int argmin(int a,int b){return sum[a]<=sum[b]?a:b;}
signed main(){
freopen("grocery.in","r",stdin); freopen("grocery.out","w",stdout);
n=2e5; for(int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
n=read(); Q=read(); scanf("%s",s+1);
for(int i=1;i<=n;++i) sum[i]=sum[i-1]+(s[i]=='F'?1:-1);
for(int i=1;i<=n;++i) lef[0][i]=rig[0][i]=i;
for(int j=1;(1<这场放到联赛前可能多数同学和现在考试得到的分数是类似的