A. string
类似 HEOI2016排序 。
排序这道题因为只询问单点最终答案，二分答案，
将小于和大于等于答案的数分别设为0 1，
用线段树维护0 1的排序即可。
算法一：
本题中的1～n变成了0～25（即a～z），单点询问变成了全体询问。
仿照排序那道题的做法，线段树优化桶排序。
维护每个节点每个字符的cnt值，区间查询后区间赋值即可。
然而up和down函数都是$O(26)$的，加上修改操作最多被拆分为26个，
总的复杂度为$O(nlogn26^2)$。
需要卡常。
考场上码出了80分，一次优化成了70，再一次优化成了60。
考后把第一次拿出来，加了快读，卡到了90。
循环展开AC。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define lch p<<1 5 #define rch p<<1|1 6 using namespace std; 7 const int N=100010; 8 int n,m,num[28]; 9 struct node{ 10 int l,r,cnt[26],set; 11 }s[N<<2]; 12 char ch; 13 inline void up(int p){ 14 s[p].cnt[0]=s[lch].cnt[0]+s[rch].cnt[0]; 15 s[p].cnt[1]=s[lch].cnt[1]+s[rch].cnt[1]; 16 s[p].cnt[2]=s[lch].cnt[2]+s[rch].cnt[2]; 17 s[p].cnt[3]=s[lch].cnt[3]+s[rch].cnt[3]; 18 s[p].cnt[4]=s[lch].cnt[4]+s[rch].cnt[4]; 19 s[p].cnt[5]=s[lch].cnt[5]+s[rch].cnt[5]; 20 s[p].cnt[6]=s[lch].cnt[6]+s[rch].cnt[6]; 21 s[p].cnt[7]=s[lch].cnt[7]+s[rch].cnt[7]; 22 s[p].cnt[8]=s[lch].cnt[8]+s[rch].cnt[8]; 23 s[p].cnt[9]=s[lch].cnt[9]+s[rch].cnt[9]; 24 s[p].cnt[10]=s[lch].cnt[10]+s[rch].cnt[10]; 25 s[p].cnt[11]=s[lch].cnt[11]+s[rch].cnt[11]; 26 s[p].cnt[12]=s[lch].cnt[12]+s[rch].cnt[12]; 27 s[p].cnt[13]=s[lch].cnt[13]+s[rch].cnt[13]; 28 s[p].cnt[14]=s[lch].cnt[14]+s[rch].cnt[14]; 29 s[p].cnt[15]=s[lch].cnt[15]+s[rch].cnt[15]; 30 s[p].cnt[16]=s[lch].cnt[16]+s[rch].cnt[16]; 31 s[p].cnt[17]=s[lch].cnt[17]+s[rch].cnt[17]; 32 s[p].cnt[18]=s[lch].cnt[18]+s[rch].cnt[18]; 33 s[p].cnt[19]=s[lch].cnt[19]+s[rch].cnt[19]; 34 s[p].cnt[20]=s[lch].cnt[20]+s[rch].cnt[20]; 35 s[p].cnt[21]=s[lch].cnt[21]+s[rch].cnt[21]; 36 s[p].cnt[22]=s[lch].cnt[22]+s[rch].cnt[22]; 37 s[p].cnt[23]=s[lch].cnt[23]+s[rch].cnt[23]; 38 s[p].cnt[24]=s[lch].cnt[24]+s[rch].cnt[24]; 39 s[p].cnt[25]=s[lch].cnt[25]+s[rch].cnt[25]; 40 } 41 inline void down(int p){ 42 s[lch].set=s[rch].set=s[p].set; 43 s[lch].cnt[0]=s[lch].cnt[1]=s[lch].cnt[2]=s[lch].cnt[3]=s[lch].cnt[4]=s[lch].cnt[5]=s[lch].cnt[6]=s[lch].cnt[7]=s[lch].cnt[8]=s[lch].cnt[9]=s[lch].cnt[10]=s[lch].cnt[11]=s[lch].cnt[12]=s[lch].cnt[13]=s[lch].cnt[14]=s[lch].cnt[15]=s[lch].cnt[16]=s[lch].cnt[17]=s[lch].cnt[18]=s[lch].cnt[19]=s[lch].cnt[20]=s[lch].cnt[21]=s[lch].cnt[22]=s[lch].cnt[23]=s[lch].cnt[24]=s[lch].cnt[25]=0; 44 s[rch].cnt[0]=s[rch].cnt[1]=s[rch].cnt[2]=s[rch].cnt[3]=s[rch].cnt[4]=s[rch].cnt[5]=s[rch].cnt[6]=s[rch].cnt[7]=s[rch].cnt[8]=s[rch].cnt[9]=s[rch].cnt[10]=s[rch].cnt[11]=s[rch].cnt[12]=s[rch].cnt[13]=s[rch].cnt[14]=s[rch].cnt[15]=s[rch].cnt[16]=s[rch].cnt[17]=s[rch].cnt[18]=s[rch].cnt[19]=s[rch].cnt[20]=s[rch].cnt[21]=s[rch].cnt[22]=s[rch].cnt[23]=s[rch].cnt[24]=s[rch].cnt[25]=0; 45 s[lch].cnt[s[p].set]=s[lch].r-s[lch].l+1; 46 s[rch].cnt[s[p].set]=s[rch].r-s[rch].l+1; 47 s[p].set=-1; 48 } 49 void build(int p,int l,int r){ 50 s[p].l=l; s[p].r=r; s[p].set=-1; 51 if(l==r){ 52 scanf(" %c",&ch); 53 ++s[p].cnt[s[p].set=ch-'a']; 54 return ; 55 } 56 int mid=l+r>>1; 57 build(lch,l,mid); 58 build(rch,mid+1,r); 59 up(p); 60 } 61 void query(int p,int l,int r){ 62 if(s[p].l>=l&&s[p].r<=r){ 63 num[0]+=s[p].cnt[0]; 64 num[1]+=s[p].cnt[1]; 65 num[2]+=s[p].cnt[2]; 66 num[3]+=s[p].cnt[3]; 67 num[4]+=s[p].cnt[4]; 68 num[5]+=s[p].cnt[5]; 69 num[6]+=s[p].cnt[6]; 70 num[7]+=s[p].cnt[7]; 71 num[8]+=s[p].cnt[8]; 72 num[9]+=s[p].cnt[9]; 73 num[10]+=s[p].cnt[10]; 74 num[11]+=s[p].cnt[11]; 75 num[12]+=s[p].cnt[12]; 76 num[13]+=s[p].cnt[13]; 77 num[14]+=s[p].cnt[14]; 78 num[15]+=s[p].cnt[15]; 79 num[16]+=s[p].cnt[16]; 80 num[17]+=s[p].cnt[17]; 81 num[18]+=s[p].cnt[18]; 82 num[19]+=s[p].cnt[19]; 83 num[20]+=s[p].cnt[20]; 84 num[21]+=s[p].cnt[21]; 85 num[22]+=s[p].cnt[22]; 86 num[23]+=s[p].cnt[23]; 87 num[24]+=s[p].cnt[24]; 88 num[25]+=s[p].cnt[25]; 89 return ; 90 } 91 if(~s[p].set) down(p); 92 if(l<=s[lch].r) query(lch,l,r); 93 if(r>=s[rch].l) query(rch,l,r); 94 up(p); 95 } 96 void set(int p,int l,int r,int val){ 97 if(s[p].l>=l&&s[p].r<=r){ 98 s[p].cnt[0]=s[p].cnt[1]=s[p].cnt[2]=s[p].cnt[3]=s[p].cnt[4]=s[p].cnt[5]=s[p].cnt[6]=s[p].cnt[7]=s[p].cnt[8]=s[p].cnt[9]=s[p].cnt[10]=s[p].cnt[11]=s[p].cnt[12]=s[p].cnt[13]=s[p].cnt[14]=s[p].cnt[15]=s[p].cnt[16]=s[p].cnt[17]=s[p].cnt[18]=s[p].cnt[19]=s[p].cnt[20]=s[p].cnt[21]=s[p].cnt[22]=s[p].cnt[23]=s[p].cnt[24]=s[p].cnt[25]=0; 99 s[p].cnt[val]=s[p].r-s[p].l+1; 100 s[p].set=val; 101 return ; 102 } 103 if(~s[p].set) down(p); 104 if(l<=s[lch].r) set(lch,l,r,val); 105 if(r>=s[rch].l) set(rch,l,r,val); 106 up(p); 107 } 108 void dfs(int p){ 109 if(s[p].l==s[p].r){ 110 putchar('a'+s[p].set); 111 return ; 112 } 113 if(~s[p].set) down(p); 114 dfs(lch); dfs(rch); 115 } 116 inline int read(){ 117 int x=0; char ch=getchar(); 118 while(!isdigit(ch)) ch=getchar(); 119 while(isdigit(ch)){ 120 x=(x<<1)+(x<<3)+(ch^48); 121 ch=getchar(); 122 } 123 return x; 124 } 125 int main(){ 126 n=read(); m=read(); 127 build(1,1,n); 128 for(int i=1,l,r,opt;i<=m;++i){ 129 l=read(); r=read(); opt=read(); 130 memset(num,0,sizeof(num)); 131 query(1,l,r); 132 if(opt){ 133 for(int i=1;i<26;++i) num[i]+=num[i-1]; 134 if(num[0]) set(1,l,l+num[0]-1,0); 135 for(int i=1;i<26;++i) if(num[i]-num[i-1]) set(1,l+num[i-1],l+num[i]-1,i); 136 } 137 else{ 138 for(int i=25;~i;--i) num[i]+=num[i+1]; 139 for(int i=25;~i;--i) if(num[i]-num[i+1]) set(1,l+num[i+1],l+num[i]-1,i); 140 } 141 } 142 dfs(1); puts(""); 143 return 0; 144 }
算法二（来自DeepinC）：
思路同样来自HEOI2016排序。
枚举i，范围为0～25，把大于i的字符设为1，反之设为0。
对于每个枚举，线段树维护桶排序，执行m次操作。
每两次枚举中，最终01串中由1变为0的，就是字符i。
复杂度$O(nlogn26)$然而好像常数巨大，只能卡到70分左右。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define lch p<<1 5 #define rch p<<1|1 6 using namespace std; 7 const int N=100010; 8 int n,m; 9 struct node{ 10 int l,r,cnt,set; 11 }s[N<<2]; 12 char ch[N]; 13 char ans[N]; 14 inline void up(int p){ 15 s[p].cnt=s[lch].cnt+s[rch].cnt; 16 } 17 inline void down(int p){ 18 s[lch].set=s[rch].set=s[p].set; 19 if(s[p].set) s[lch].cnt=s[lch].r-s[lch].l+1,s[rch].cnt=s[rch].r-s[rch].l+1; 20 else s[lch].cnt=s[rch].cnt=0; 21 s[p].set=-1; 22 } 23 void build(int p,int l,int r,int val){ 24 s[p].l=l; s[p].r=r; s[p].set=-1; 25 if(l==r){ 26 s[p].cnt=(ch[l]-'a'>val); 27 return ; 28 } 29 int mid=l+r>>1; 30 build(lch,l,mid,val); 31 build(rch,mid+1,r,val); 32 up(p); 33 } 34 int query(int p,int l,int r){ 35 if(s[p].l>=l&&s[p].r<=r) return s[p].cnt; 36 if(~s[p].set) down(p); 37 int ans=0; 38 if(l<=s[lch].r) ans+=query(lch,l,r); 39 if(r>=s[rch].l) ans+=query(rch,l,r); 40 return ans; 41 } 42 void set(int p,int l,int r,int val){ 43 if(s[p].l>=l&&s[p].r<=r){ 44 if(val) s[p].cnt=s[p].r-s[p].l+1; 45 else s[p].cnt=0; 46 s[p].set=val; 47 return ; 48 } 49 if(~s[p].set) down(p); 50 if(l<=s[lch].r) set(lch,l,r,val); 51 if(r>=s[rch].l) set(rch,l,r,val); 52 up(p); 53 } 54 void dfs(int p,int val){ 55 if(s[p].l==s[p].r){ 56 if(!s[p].cnt&&!ans[s[p].l]) ans[s[p].l]='a'+val; 57 return ; 58 } 59 if(~s[p].set) down(p); 60 dfs(lch,val); 61 dfs(rch,val); 62 } 63 inline int read(){ 64 int x=0; char ch=getchar(); 65 while(!isdigit(ch)) ch=getchar(); 66 while(isdigit(ch)){ 67 x=(x<<1)+(x<<3)+(ch^48); 68 ch=getchar(); 69 } 70 return x; 71 } 72 int l[N],r[N]; 73 bool opt[N]; 74 int main(){ 75 //freopen("x.in","r",stdin); 76 //freopen("me.out","w",stdout); 77 n=read(); m=read(); 78 scanf("%s",ch+1); 79 for(int i=1;i<=m;++i) l[i]=read(),r[i]=read(),opt[i]=read(); 80 for(int i=0;i<26;++i){ 81 build(1,1,n,i); 82 for(int j=1;j<=m;++j){ 83 int cnt=query(1,l[j],r[j]); 84 if(opt[j]){ 85 cnt=r[j]-l[j]+1-cnt; 86 if(cnt) set(1,l[j],l[j]+cnt-1,0); 87 if(l[j]+cnt<=r[j]) set(1,l[j]+cnt,r[j],1); 88 } 89 else{ 90 if(cnt) set(1,l[j],l[j]+cnt-1,1); 91 if(l[j]+cnt<=r[j]) set(1,l[j]+cnt,r[j],0); 92 } 93 } 94 dfs(1,i); 95 } 96 printf("%s\n",ans+1); 97 return 0; 98 }
算法三（好像是正解）：
用26棵线段树。
每棵线段树只维护0 1， 分别表示等于或不等于该字符。
其他同算法一，
总复杂度也为$O(nlogn26)$。
算法四（来自sdfzdky）：
维护线段树的每个节点是否全部相等，
如果是则直接返回区间大小，否则继续递归。
排序过程同算法一。
根据均摊的思想，复杂度是对的。
最差情况下$O(nlogn26)$，然而在随机数据下很优秀。
算法五（来自cbx）：
将连续的同一字符区间看作同一个元素。
暴力桶排序。
复杂度似乎也是对的。
B. matrix
考试时打了状压。
正解：
（右侧区间为由右端点m开始的区间，即$[r[i],m]$，左侧区间同理）
定义$f[i][j]$表示考虑前i列，前i列中有j列在右侧区间放1，已经考虑结束端点小于等于i的左侧区间。
状态定义很奇怪，但是是可以转移的。
定义$lp[i]$表示前缀和，$lp[i]$的含义是有多少个左侧区间已经在i点结束。
同理$rp[i]$的含义是i点有多少个右侧区间能放1。
$f[i][j]=f[i-1][j]+f[i-1][j-1]*(r[i]-j+1)$
加号前面的内容表示这个点不在右侧区间放1，
后面的内容表示由可以放1的任何一个右侧区间在这里放1。
转移后，考虑左侧区间。
$f[i][j]*=A_{i-j-l[i-1]}^{l[i]-l[i-1]}$。
$f[m][n]$就是答案。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 using namespace std; 5 const int N=3010; 6 const int mod=998244353; 7 int n,m,dp[N][N],l[N],r[N],js[N],jsinv[N]; 8 inline int qpow(int base,int k,int ans=1){ 9 while(k){ 10 if(k&1) ans=1ll*ans*base%mod; 11 base=1ll*base*base%mod; 12 k>>=1; 13 } 14 return ans; 15 } 16 inline int read(){ 17 int x; scanf("%d",&x); return x; 18 } 19 inline int A(int n,int m){ 20 if(m>n) return 0; 21 return 1ll*js[n]*jsinv[n-m]%mod; 22 } 23 int main(){ 24 scanf("%d%d",&n,&m); 25 for(int i=1;i<=n;++i) ++l[read()],++r[read()]; 26 for(int i=1;i<=m;++i) l[i]+=l[i-1],r[i]+=r[i-1]; 27 js[0]=1; 28 for(int i=1;i<=m;++i) js[i]=1ll*js[i-1]*i%mod; 29 jsinv[m]=qpow(js[m],mod-2); 30 for(int i=m;i;--i) jsinv[i-1]=1ll*jsinv[i]*i%mod; 31 dp[0][0]=1; 32 for(int i=1;i<=m;++i){ 33 dp[i][0]=1ll*dp[i-1][0]*A(i-l[i-1],l[i]-l[i-1])%mod; 34 for(int j=1;j<=min(i,n);++j) dp[i][j]=(dp[i-1][j]+1ll*dp[i-1][j-1]*max(r[i]-j+1,0)%mod)*A(i-j-l[i-1],l[i]-l[i-1])%mod; 35 } 36 printf("%d\n",dp[m][n]); 37 return 0; 38 }
C. big
考试时打了显然的暴力。
最后十分钟，想到了对x的操作可以转化为逻辑左移一位。
问题转化为取一个x，使得$((x$^$pre_i)<<1)$^$suf_{i+1}$取得最大值。
显然<<1可以拆开，又因为x<<1和x之间的映射是一一对应的。
问题又转化为取一个x，使得$x$^$((pre_i<<1)$^$suf_{i+1})$最大。
后者可以合并，使用trie树查询最大值和方案数。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 using namespace std; 5 const int M=100010; 6 int n,m,s[M],suf[M],ans,cnt; 7 struct trie{ 8 struct node{ 9 node *ch[2]; 10 }*root,pool[M*30],*ptr=pool; 11 void build(){ 12 root=ptr++; 13 } 14 void insert(int x){ 15 node *now=root; 16 for(int i=n-1;~i;--i){ 17 if(!now->ch[x>>i&1]) now->ch[x>>i&1]=ptr++; 18 now=now->ch[x>>i&1]; 19 } 20 } 21 void dfs(node *now,int k,int num){ 22 if(now->ch[0]&&now->ch[1]){ 23 dfs(now->ch[0],k-1,num); 24 dfs(now->ch[1],k-1,num); 25 } 26 else if(now->ch[0]) dfs(now->ch[0],k-1,num+(1<<k-1)); 27 else if(now->ch[1]) dfs(now->ch[1],k-1,num+(1<<k-1)); 28 else{ 29 if(num>ans) ans=num,cnt=1; 30 else if(num==ans) ++cnt; 31 } 32 } 33 }tr; 34 inline int turn(int x){ 35 return (x>>n-1&1)+(x<<1)&(1<<n)-1;//*/ +- <<>> & | ^ 36 } 37 int main(){ 38 scanf("%d%d",&n,&m); 39 for(int i=1;i<=m;++i) scanf("%d",&s[i]); 40 for(int i=m;i;--i) suf[i]=suf[i+1]^s[i]; 41 tr.build(); 42 tr.insert(suf[1]); 43 for(int i=1,pre=0;i<=m;++i){ 44 pre^=s[i]; 45 tr.insert(turn(pre)^suf[i+1]); 46 } 47 tr.dfs(tr.root,n,0); 48 printf("%d\n%d\n",ans,cnt); 49 return 0; 50 }
京公网安备 11010502036488号