T1 Dove玩扑克
考场并查集加树状数组加桶期望$65pts$实际$80pts$，考后多开个数组记哪些数出现过，只扫出现过的数就切了。用$set$维护可以把被删没的数去掉，更快。
$code:$
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 const int NN=1e5+5;
5 int n,m,op,x,y,fa[NN],siz[NN],sum,cnt[NN],nums[NN];
6 bool vis[NN];
7 inline int getfa(int x){ return fa[x]==x?x:fa[x]=getfa(fa[x]); }
8 inline int read(){
9 int x=0,f=1; char ch=getchar();
10 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
11 while(ch<='9'&&ch>='0'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
12 return x*f;
13 }
14 inline void write(int x,char sp){
15 char ch[20]; int len=0;
16 if(x<0) x=~x+1, putchar('-');
17 do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);
18 for(int i=len-1;i>=0;--i) putchar(ch[i]); putchar(sp);
19 }
20 struct tree_array{
21 int c[NN+5];
22 inline int lowbit(int x){ return x&(-x); }
23 void insert(int pos,int v){
24 while(pos<=n){
25 c[pos]+=v;
26 pos+=lowbit(pos);
27 }
28 }
29 int query(int pos){
30 int res=0;
31 while(pos>0){
32 res+=c[pos];
33 pos-=lowbit(pos);
34 }
35 return res;
36 }
37 }t;
38 inline void merge(int x,int y){
39 x=getfa(x); y=getfa(y);
40 if(x==y) return;
41 t.insert(siz[y],-1); t.insert(siz[x],-1);
42 cnt[siz[y]]--; cnt[siz[x]]--;
43 fa[y]=x; siz[x]+=siz[y];
44 t.insert(siz[x],1);
45 if(!vis[siz[x]]) nums[++nums[0]]=siz[x];
46 cnt[siz[x]]++; sum--; vis[siz[x]]=1;
47 }
48 signed main(){
49 sum=n=read(); m=read();
50 for(int i=1;i<=n;i++)
51 fa[i]=i, siz[i]=1;
52 t.insert(1,n); cnt[1]=n;
53 while(m--){
54 op=read(); x=read();
55 if(op==1){ y=read(); merge(x,y); }
56 else if(!x){ write(sum*(sum-1)>>1,'\n'); }
57 else{
58 int ans=0;
59 for(int i=1;i<=nums[0];i++){
60 if(nums[i]<=x) continue;
61 if(!cnt[nums[i]]) continue;
62 ans+=cnt[nums[i]]*t.query(nums[i]-x);
63 }
64 write(ans,'\n');
65 }
66 }
67 return 0;
68 }
T1
T2 Cicada与排序
一看范围，直接模拟怕不是至少$50pts$，但连模拟都不会。。
考虑$DP$。设$f_{i,j,k}$表示归并排序递归第$i$层中原本在位置$j$的数排序后在$k$的概率。
发现并不好转移，设辅助数组$g_{i,j}$表示当前情况下归并排序指针同时指向$i$与$j$的概率。
之后再模拟归并排序的递归，同时大力分类讨论即可。
具体见代码。
$code:$
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 const int NN=505,p=998244353,inv2=499122177;
5 int n,a[NN],f[NN][NN][NN],g[NN][NN];
6 bool b;
7 inline int read(){
8 int x=0,f=1; char ch=getchar();
9 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
10 while(ch<='9'&&ch>='0'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
11 return x*f;
12 }
13 inline void write(int x,char sp){
14 char ch[20]; int len=0;
15 if(x<0) x=~x+1, putchar('-');
16 do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);
17 for(int i=len-1;i>=0;--i) putchar(ch[i]); putchar(sp);
18 }
19 void dfsort(int x,int l,int r){
20 if(l==r){ f[x][l][r]=1; return; }
21 int mid=l+r>>1;
22 dfsort(x+1,l,mid); dfsort(x+1,mid+1,r);
23 memset(g,0,sizeof(g)); g[0][0]=1;
24 for(int i=0;i<=mid-l+1;i++)
25 for(int j=0;j<=r-mid;j++)
26 if(i==mid-l+1) (g[i][j+1]+=g[i][j])%=p;
27 else if(j==r-mid) (g[i+1][j]+=g[i][j])%=p;
28 else if(a[i+l]<a[j+mid+1]) (g[i+1][j]+=g[i][j])%=p;
29 else if(a[i+l]>a[j+mid+1]) (g[i][j+1]+=g[i][j])%=p;
30 else (g[i+1][j]+=g[i][j]*inv2)%=p, (g[i][j+1]+=g[i][j]*inv2%p)%=p;
31 for(int i=l;i<=r;i++)
32 for(int j=0;j<=mid-l+1;j++)
33 for(int k=0;k<=r-mid;k++)
34 if(j==mid-l+1&&k==r-mid) continue;
35 else if(k==r-mid) (f[x][i][j+k+l]+=f[x+1][i][j+l]*g[j][k]%p)%=p;
36 else if(j==mid-l+1) (f[x][i][j+k+l]+=f[x+1][i][k+mid+1]*g[j][k]%p)%=p;
37 else if(a[j+l]<a[k+mid+1]) (f[x][i][j+k+l]+=f[x+1][i][j+l]*g[j][k]%p)%=p;
38 else if(a[j+l]>a[k+mid+1]) (f[x][i][j+k+l]+=f[x+1][i][k+mid+1]*g[j][k]%p)%=p;
39 else (f[x][i][j+k+l]+=(f[x+1][i][k+mid+1]+f[x+1][i][j+l])*inv2%p*g[j][k]%p)%=p;
40 sort(a+l,a+r+1);
41 }
42 signed main(){
43 n=read();
44 for(int i=1;i<=n;i++) a[i]=read();
45 dfsort(1,1,n);
46 for(int i=1;i<=n;i++){
47 int ans=0;
48 for(int j=1;j<=n;j++) (ans+=f[1][i][j]*j%p)%=p;
49 write(ans,' ');
50 }
51 return 0;
52 }
T2
T3 Cicada拿衣服
神TM拿(na)衣(i)服(ve)
$n^2$枚举，用线段树区间修改答案可以$64pts$，再加一些全无正确性的剪枝甚至能$A$。。
1 #include<bits/stdc++.h>
2 #define ld rt<<1
3 #define rd (rt<<1)|1
4 using namespace std;
5 const int NN=1e6+5;
6 int n,k,a[NN],orh,anh,maxn,minn,r;
7 inline int read(){
8 int x=0,f=1; char ch=getchar();
9 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
10 while(ch<='9'&&ch>='0'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
11 return x*f;
12 }
13 inline void write(int x){
14 char ch[20]; int len=0;
15 if(x<0) x=~x+1, putchar('-');
16 do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);
17 for(int i=len-1;i>=0;--i) putchar(ch[i]);
18 }
19 struct segment_tree{
20 int mx[NN<<2],laz[NN<<2];
21 void pushdown(int rt,int l,int r){
22 if(!laz[rt]||l==r) return;
23 mx[ld]=max(laz[rt],mx[ld]);
24 mx[rd]=max(laz[rt],mx[rd]);
25 laz[ld]=max(laz[ld],laz[rt]);
26 laz[rd]=max(laz[rd],laz[rt]);
27 laz[rt]=0;
28 }
29 void update(int rt,int l,int r,int opl,int opr,int val){
30 if(l>=opl&&r<=opr){
31 mx[rt]=max(mx[rt],val);
32 laz[rt]=max(laz[rt],val);
33 return;
34 }
35 pushdown(rt,l,r);
36 int mid=l+r>>1;
37 if(opl<=mid) update(ld,l,mid,opl,opr,val);
38 if(opr>mid) update(rd,mid+1,r,opl,opr,val);
39 }
40 int query(int rt,int l,int r,int pos){
41 if(l==r) return mx[rt];
42 pushdown(rt,l,r);
43 int mid=l+r>>1;
44 if(pos<=mid) return query(ld,l,mid,pos);
45 else return query(rd,mid+1,r,pos);
46 }
47 }s;
48 signed main(){
49 n=read(); k=read();
50 for(int i=1;i<=n;i++) a[i]=read();
51 for(int i=1;i<=n;i++){
52 maxn=minn=orh=anh=a[i]; r=0;
53 for(int j=i;j<=n;j++){
54 maxn=max(maxn,a[j]);
55 minn=min(minn,a[j]);
56 orh|=a[j]; anh&=a[j];
57 if(minn+orh-maxn-anh>=k) r=j;
58 else if(j-i+1>=100&&n>30000) break;
59 }
60 if(r) s.update(1,1,n,i,r,r-i+1);
61 }
62 for(int i=1;i<=n;i++){
63 int ans=s.query(1,1,n,i);
64 write(ans?ans:-1); putchar(' ');
65 }
66 return 0;
67 }
精髓在第58行
正解双是神仙。
不难发现$or-and$在区间增长时单调不减，$min-max$在区间增长时单调不增。
而$or-and$变化的位置最多只有$2log$个，可以用链表维护出$or-and$不变的区间，对每个固定的右端点从左往右找到第一个可行的区间，二分答案即可。$O(nlog_n)$
答案可以用线段树维护。由于只查询一次，可以标记永久化。
$STL$的链表调用要一堆迭代器，对我这种蒟蒻非常不友好。。
$code:$
1 #include<bits/stdc++.h>
2 #define ld rt<<1
3 #define rd (rt<<1)|1
4 using namespace std;
5 const int NN=1e6+5;
6 int n,k,a[NN],l2[NN],mx[NN][20],mn[NN][20];
7 struct lis{ int oo,aa,rr; };
8 list<lis> li;
9 inline int qmax(int l,int r){ int k=l2[r-l+1]; return max(mx[l][k],mx[r-(1<<k)+1][k]); }
10 inline int qmin(int l,int r){ int k=l2[r-l+1]; return min(mn[l][k],mn[r-(1<<k)+1][k]); }
11 inline bool check(list<lis>::iterator it,int l,int r){ return (it->oo-it->aa+qmin(l,r)-qmax(l,r))>=k; }
12 inline int read(){
13 int x=0,f=1; char ch=getchar();
14 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
15 while(ch<='9'&&ch>='0'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
16 return x*f;
17 }
18 inline void write(int x,char sp){
19 char ch[20]; int len=0;
20 if(x<0) x=~x+1, putchar('-');
21 do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);
22 for(int i=len-1;i>=0;--i) putchar(ch[i]); putchar(sp);
23 }
24 struct segment_tree{
25 int t[NN<<2];
26 void update(int rt,int l,int r,int opl,int opr){
27 if(opl<=l&&r<=opr){ t[rt]=max(t[rt],opr-opl+1); return; }
28 int mid=l+r>>1;
29 if(opl<=mid) update(ld,l,mid,opl,opr);
30 if(opr>mid) update(rd,mid+1,r,opl,opr);
31 }
32 void print(int rt,int l,int r){
33 if(l==r){ write(t[rt],' '); return; }
34 int mid=l+r>>1;
35 t[ld]=max(t[ld],t[rt]);
36 t[rd]=max(t[rd],t[rt]);
37 print(ld,l,mid); print(rd,mid+1,r);
38 }
39 }s;
40 void init(){
41 for(int i=2;i<=n;i++) l2[i]=l2[i>>1]+1;
42 for(int i=1;i<=n;i++) mx[i][0]=mn[i][0]=a[i];
43 for(int j=1;j<20;j++)
44 for(int i=1;i+(1<<j)-1<=n;i++){
45 mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]);
46 mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);
47 }
48 memset(s.t,-1,sizeof(s.t));
49 }
50 signed main(){
51 n=read(); k=read();
52 for(int i=1;i<=n;i++) a[i]=read();
53 init();
54 for(int i=1;i<=n;i++){
55 for(auto it=li.begin();it!=li.end();++it)
56 it->oo|=a[i], it->aa&=a[i];
57 li.push_back((lis){a[i],a[i],i});
58 for(auto itl=li.begin(),itr=itl;++itr!=li.end();)
59 if((itl->oo-itl->aa)==(itr->oo-itr->aa))
60 li.erase(itl), itl=itr;
61 else ++itl;
62 for(auto it=li.begin();it!=li.end();++it){
63 if(!check(it,it->rr,i)) continue;
64 int l=1,r=it->rr,mid,res;
65 if(it!=li.begin()) l=(--it)->rr+1, ++it;
66 while(l<=r){
67 mid=l+r>>1;
68 if(check(it,mid,i)) r=mid-1, res=mid;
69 else l=mid+1;
70 }
71 s.update(1,1,n,res,i);
72 break;
73 }
74 }
75 s.print(1,1,n);
76 return 0;
77 }
T3
![[考试反思]0801NOIP模拟测试11](https://www.kunjuke.com/file/css/thumb/8.jpg/280-180.jpg)
![[NOI.AC省选模拟赛3.23] 集合 [数学]](https://www.kunjuke.com/file/css/thumb/11.jpg/280-180.jpg)
![[NOI.AC省选模拟赛3.30] Mas的童年 [二进制乱搞]](https://www.kunjuke.com/file/css/thumb/6.jpg/280-180.jpg)
