Noip模拟36 2021.8.11
2024-09-01 17:03:45
刚题的习惯还是改不了，怎么办？？？
T1 Dove打扑克
考场上打的动态开点线段树+并查集，考后发现自己像一个傻子，并查集就行。。
这几天恶补数据结构疯了
用树状数组维护后缀和，$siz_i$表示编号为$i$的牌堆的卡牌个数，并使用桶记录一下这种数量级的牌堆的个数
同时使用$set$维护一下还存在的牌堆的编号
在合并的时候按照题目原理对各种维护数组加加减减操作就行，注意在一类数量级的桶没有东西之后，要将$set$中的相应元素删掉
查询的时候遍历$set$中的元素，查询即可。
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 inline int read(){
5 int x=0,f=1; char ch=getchar();
6 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
7 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}
8 return x*f;
9 }
10 const int NN=1e5+5;
11 int n,m,fa[NN],tr[NN],r,siz[NN],t[NN];
12 set<int> S;
13 inline int lowbit(int x){return x&(-x);}
14 inline void update(int x,int v){for(;x;x-=lowbit(x)) tr[x]+=v;}
15 inline int query(int x){int ans=0; for(;x<=n;x+=lowbit(x)) ans+=tr[x];return ans;}
16 inline int getfa(int x){return fa[x]=((fa[x]==x)?x:getfa(fa[x]));}
17 inline void merge(int x,int y){
18 int xx=getfa(x),yy=getfa(y);
19 if(xx==yy) return;
20 update(siz[xx],-1);--t[siz[xx]];if(!t[siz[xx]]) S.erase(S.find(siz[xx]));
21 update(siz[yy],-1);--t[siz[yy]];if(!t[siz[yy]]) S.erase(S.find(siz[yy]));
22 ++t[siz[xx]+siz[yy]]; update(siz[xx]+siz[yy],1); if(t[siz[xx]+siz[yy]]==1) S.insert(siz[xx]+siz[yy]);
23 if(siz[xx]>siz[yy]) swap(xx,yy);
24 fa[xx]=yy; siz[yy]+=siz[xx];
25 --r;
26 }
27 namespace WSN{
28 inline short main(){
29 n=read(); m=read(); t[1]=r=n;
30 for(int i=1;i<=n;++i) siz[i]=1,fa[i]=i;
31 update(1,n); S.insert(1);
32 while(m--){
33 int opt=read();
34 if(opt==1){
35 int x=read(),y=read();
36 merge(x,y);
37 continue;
38 }
39 if(opt==2){
40 int c=read();
41 if(!c) printf("%lld\n",r*(r-1)/2);
42 else{
43 int ans=0;
44 for(auto val:S) if(val+c<=n){
45 int res=query(val+c);
46 ans+=res*t[val];
47 if(!res) break;
48 }else break;
49 printf("%lld\n",ans);
50 }
51 continue;
52 }
53 }
54 return 0;
55 }
56 }
57 signed main(){return WSN::main();}
T2 Cicada与排序
考场上居然在大力的刚一道不可做的题，针不戳。
一直在想如何魔改贵并排序的板子，考后看题解发现是$dp$，果然看题没思路就往$dp$想
记录$rk_{i,j}$表示原数组第$i$个数在排列后出现在$j$的概率，那么我们用这个就可以求出答案
其他详情见学长博客
太可恶了，题根本改不完，昨天四道题两道没改。
1 #include<bits/stdc++.h>
2 #define int long long
3 //出现在mid一侧的相同数期望相同
4 using namespace std;
5 inline int read(){
6 int x=0,f=1; char ch=getchar();
7 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
8 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}
9 return x*f;
10 }
11 inline void write(int x){
12 char ch[20]; int len=0;
13 if(x<0) x=~x+1, putchar('-');
14 do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);
15 for(int i=len-1;i>=0;--i) putchar(ch[i]); putchar(' ');
16 }
17 #define yi 0
18 #define er 1
19 const int p=998244353,NN=1005,inv=499122177;
20 int n,a[NN],dp[NN][NN][2],rk[NN][NN];
21 int lt[NN],rt[NN],zz[NN];
22 vector<int> vl[NN],vr[NN];
23 void merge_sort(int le, int ri){
24 if(le==ri) return; int mi=(le+ri)>>1;
25 merge_sort(le,mi); merge_sort(mi+1,ri);
26 for(int i=le;i<=mi;i++) ++lt[a[i]],vl[a[i]].push_back(i);
27 for(int i=mi+1;i<=ri;i++) ++rt[a[i]],vr[a[i]].push_back(i);
28 for(int i=1;i<=1000;i++){
29 for(int l=0;l<=lt[i];l++) for(int r=0;r<=rt[i];r++) dp[l][r][0]=dp[l][r][1]=0;
30 dp[0][0][0]=1;
31 for(int l=0;l<=lt[i];l++) for(int r=0;r<=rt[i];r++){
32 if(l!=lt[i]&&r!=rt[i]){
33 (dp[l+1][r][yi]+=(dp[l][r][yi]+dp[l][r][er])*inv%p)%=p;
34 (dp[l][r+1][er]+=(dp[l][r][yi]+dp[l][r][er])*inv%p)%=p;
35 }
36 else if(l!=lt[i]) (dp[l+1][r][yi]+=dp[l][r][yi]+dp[l][r][er])%=p;
37 else if(r!=rt[i]) (dp[l][r+1][er]+=dp[l][r][yi]+dp[l][r][er])%=p;
38 }
39 for(int j=0;j<lt[i];j++){
40 for(int k=1;k<=lt[i];k++) for(int r=0;r<=rt[i];r++)
41 (zz[k+r]+=rk[vl[i][j]][k]*dp[k][r][0])%=p;
42 for(int k=1;k<=lt[i]+rt[i];k++) rk[vl[i][j]][k]=zz[k],zz[k]=0;
43 }
44 for(int j=0;j<rt[i];j++){
45 for(int k=1;k<=rt[i];k++) for(int l=0;l<=lt[i];l++)
46 (zz[k+l]+=rk[vr[i][j]][k]*dp[l][k][1])%=p;
47 for(int k=1;k<=lt[i]+rt[i];k++) rk[vr[i][j]][k]=zz[k],zz[k]=0;
48 }
49 vl[i].clear(),vr[i].clear(); lt[i]=rt[i]=0;
50 }
51 }
52 void bu_shan_hui_si(){
53 freopen("1.in","r",stdin);
54 freopen("1.out","w",stdout);
55 }
56 namespace WSN{
57 inline short main(){
58 n=read(); for(int i=1;i<=n;i++) a[i]=read();
59 for(int i=1;i<=n;i++) rk[i][1]=1;
60 merge_sort(1,n);
61 for(int i=1;i<=n;i++) ++lt[a[i]];
62 for(int i=0;i<=1000;i++) lt[i]+=lt[i-1];
63 for(int i=1;i<=n;i++){
64 int ans=0;
65 for(int j=1;j<=lt[a[i]]-lt[a[i]-1];j++) (ans+=rk[i][j]*j%p)%=p;
66 write(ans+lt[a[i]-1]);
67 }
68 return 0;
69 }
70 }
71 signed main(){return WSN::main();}
T3 Cicada拿衣服
乱搞题，$AC$全靠勇气。一波巧妙判断搞定$O(n^2)$复杂度
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 #define lid (id<<1)
5 #define rid (id<<1|1)
6 inline int read(){
7 int x=0,f=1; char ch=getchar();
8 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
9 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}
10 return x*f;
11 }
12 inline void write(int x){
13 char ch[20]; int len=0;
14 if(x<0) x=~x+1, putchar('-');
15 do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);
16 for(int i=len-1;i>=0;--i) putchar(ch[i]); putchar(' ');
17 }
18 const int NN=1e7+5;
19 int n,k,a[NN];
20 struct SNOWtree{
21 int ll[NN<<2],rr[NN<<2];
22 int maxn[NN<<2],laz[NN<<2];
23 inline void pushup(int id){
24 if(ll[id]==rr[id]) return;
25 maxn[id]=max(maxn[lid],maxn[rid]);
26 }
27 inline void pushdown(int id){
28 if(!laz[id]||ll[id]==rr[id]) return;
29 laz[lid]=max(laz[lid],laz[id]);
30 laz[rid]=max(laz[rid],laz[id]);
31 maxn[lid]=max(maxn[lid],laz[id]);
32 maxn[rid]=max(maxn[rid],laz[id]);
33 laz[id]=0;
34 }
35 void build(int id,int l,int r){
36 ll[id]=l;rr[id]=r; maxn[id]=-1;
37 if(l==r) return;int mid=l+r>>1;
38 build(lid,l,mid); build(rid,mid+1,r);
39 }
40 void update(int id,int l,int r,int val){
41 if(l<=ll[id]&&rr[id]<=r){
42 maxn[id]=max(maxn[id],val);
43 laz[id]=max(laz[id],val);return;
44 }pushdown(id);int mid=ll[id]+rr[id]>>1;
45 if(l<=mid) update(lid,l,r,val);
46 if(r>mid) update(rid,l,r,val);
47 pushup(id);
48 }
49 int query(int id,int pos){
50 if(ll[id]==rr[id]) return maxn[id];
51 pushdown(id); int mid=ll[id]+rr[id]>>1;
52 if(pos<=mid) return query(lid,pos);
53 else return query(rid,pos);
54 }
55 }tr;
56 namespace WSN{
57 inline short main(){
58 n=read();k=read();
59 for(register int i=1;i<=n;++i) a[i]=read();
60 tr.build(1,1,n); int mx,mn,s1,s2,now;
61 for(register int l=1;l<=n;++l){
62 mx=mn=s1=s2=a[l]; now=0;
63 for(register int r=l;r<=n;++r){
64 mx=max(mx,a[r]);
65 mn=min(mn,a[r]);
66 s1=s1|a[r];
67 s2=s2&a[r];
68 if(mn+s1-mx-s2>=k) now=r;
69 else if(r-l+1>100&&n>30000) break;
70 }
71 if(now) tr.update(1,l,now,now-l+1);
72 }
73 for(register int i=1;i<=n;++i){
74 int ans=tr.query(1,i);
75 write(ans);
76 }
77 return 0;
78 }
79 }
80 signed main(){return WSN::main();}
说说正解，$ST$表+链表$list$，比较离谱，头一次接触链表这种东西
也是第一次在代码里面使用这么多的指针，
将柿子倒位置，发现$MAX-MIN$较好维护，直接用$ST$表处理即可
对于$OR-AND$，考虑按位运算的性质，一个范围内的这个值不改变当且仅当同一位置上的数都一样
我们考虑找到这样的一段区间，然后就直接在线段树上插入长度，最后出解即可
使用链表维护这段区间，这段区间合法与否可用是否大于$k$来判断。二分判断
注意边界是上一个链表最右端+1。
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 inline int read(){
5 int x=0,f=1; char ch=getchar();
6 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
7 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}
8 return x*f;
9 }
10 inline void write(int x){
11 char ch[20]; int len=0;
12 if(x<0) x=~x+1, putchar('-');
13 do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);
14 for(int i=len-1;i>=0;--i) putchar(ch[i]); putchar(' ');
15 }
16 const int NN=1e6+5;
17 int n,k,a[NN],lgn,lg[NN],mn[27][NN],mx[27][NN];
18 struct SNOW{int r,mo,ma;};list<SNOW> lis;
19 inline int qmx(int l,int r){int k=lg[r-l+1];return max(mx[k][l],mx[k][r-(1<<k)+1]);}
20 inline int qmn(int l,int r){int k=lg[r-l+1];return min(mn[k][l],mn[k][r-(1<<k)+1]);}
21 inline bool check(list<SNOW>::iterator it,int l,int r){return it->mo-it->ma+qmn(l,r)-qmx(l,r)>=k;}
22 inline void ST_table(){
23 for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
24 for(int j=1;j<=lgn;j++) for(int i=1,t=(1<<j-1);i+(1<<j)-1<=n;i++)
25 mn[j][i]=min(mn[j-1][i],mn[j-1][i+t]),mx[j][i]=max(mx[j-1][i],mx[j-1][i+t]);
26 }
27 struct SNOWtree{
28 #define lid (id<<1)
29 #define rid (id<<1|1)
30 int ans[NN<<2];
31 inline void insert(int id,int l,int r,int L,int R,int val){
32 if(L<=l&&r<=R){ans[id]=max(ans[id],val);return;}
33 int mid=l+r>>1;
34 if(L<=mid) insert(lid,l,mid,L,R,val);
35 if(R>mid) insert(rid,mid+1,r,L,R,val);
36 }
37 inline void print(int id,int l,int r){
38 if(l==r){write(ans[id]);return;}
39 int mid=l+r>>1;
40 ans[lid]=max(ans[lid],ans[id]);
41 ans[rid]=max(ans[rid],ans[id]);
42 print(lid,l,mid); print(rid,mid+1,r);
43 }
44 }tr;
45 namespace WSN{
46 inline short main(){
47 n=read();k=read(); lgn=log(n)/log(2);
48 for(int i=1;i<=n;i++) mx[0][i]=mn[0][i]=a[i]=read();
49 ST_table(); memset(tr.ans,-1,sizeof(tr.ans));
50 for(int R=1;R<=n;R++){
51 for(auto it=lis.begin();it!=lis.end();++it) it->mo|=a[R],it->ma&=a[R];
52 lis.push_back((SNOW){R,a[R],a[R]});
53 for(auto itl=lis.begin(),itr=itl;++itr!=lis.end();)
54 if( (itl->mo-itl->ma) == (itr->mo-itr->ma) )
55 lis.erase(itl),itl=itr;
56 else ++itl;
57 for(auto it=lis.begin();it!=lis.end();++it) if(check(it,it->r,R)){
58 int ll=1,rr=it->r,ans=0;
59 if(it!=lis.begin()) ll=(--it)->r+1,++it;
60 while(ll<=rr){
61 int mid=ll+rr>>1;
62 if(check(it,mid,R)) rr=mid-1,ans=mid;
63 else ll=mid+1;
64 }
65 tr.insert(1,1,n,ans,R,R-ans+1);
66 break;
67 }
68 }
69 tr.print(1,1,n);
70 return 0;
71 }
72 }
73 signed main(){return WSN::main();}
最新文章
- 01背包问题python 2.7实现
- 实战动态PDF在线预览及带签名的PDF文件转换
- python3的编码问题
- [译]SQL Server分析服务的权限配置
- HTML5与CSS3权威指南
- 使用火狐的restclient发送http接口post及get请求
- Cobertura 代码覆盖率测试
- bootstrap API地址
- java中文件操作的工具类
- Visual Studio 使用调试技巧
- iOS 开发之照片框架详解之二 —— PhotoKit 详解（上）
- PHP对象相关知识点的总结
- 屏幕录制软件camtasia studio 8序列号激活
- 单系统登录机制SSO
- C# 定时器和队列结合，卖包子啦，Timer、 AutoResetEvent、 ManualResetEvent
- [日常工作] Inspur 服务器安装ESXi的简单过程
- USDT（omniCore）测试环境搭建
- Android 单元测试四大组件Activity，Service，Content Provider ， Broadcast Receiver
- html中文显示乱码的处理方法
- 微服务深入浅出（9）-- Nginx