前言：lzz出题，海星，没有想象中的那样毒瘤
T1：
emmmmmmm大佬们做法都很简单，用树状数组维护加稍微推一下50几行就出来了。我用线段树nlogn维护每个数前面小于它大于它的个数和后面小于它大于它的个数，开始写了个(n^2+)暴力，后面照着暴力推出正解式子，最终233行才A...还是思路不行，下面看正解想法：考虑分别统计（a,b）的合法数p，（c,d） 的合法数q ，则ans=p*q减去一些不合法的四元组（a,b,c,d）的数⽬。这⾥不合法的四元组只有四种情况：a==c,a==d,b==c,b==d 。以a==c为例，把
每个数(i,si)看成点 ，则只需要对每个点求其右上方点数乘以其右下方点数即可，即往后比a小的*往后比a大的，离散化一下树状数组维护就能解决，同样对剩余三种情况处理并从答案减去即可。
从本质入手，深入思考
上代码:
1 #include<bits/stdc++.h> 2 #define maxn 100005 3 using namespace std; 4 int n; 5 typedef long long ll; 6 struct node{ 7 int v,id;//离散 8 9 friend bool operator <(node a,node b){ 10 if(a.v!=b.v) return a.v<b.v; 11 else return a.id<b.id; 12 } 13 }nd[maxn]; 14 bool cmp(node a,node b){ 15 return a.id<b.id; 16 } 17 int rk[maxn],lc[maxn<<1],rc[maxn<<1],rt=0,np=0; 18 ll sumq[maxn<<1],sumh[maxn<<1],addq[maxn<<1],addh[maxn<<1]; 19 void build(int &now,int l,int r){ 20 now=++np; 21 if(l==r){ 22 sumq[now]=l-1;sumh[now]=n-l;return; 23 } 24 25 int m=l+r>>1; 26 build(lc[now],l,m); 27 build(rc[now],m+1,r); 28 } 29 void downloadq(int now){ 30 if(addq[now]!=0){ 31 sumq[lc[now]]+=addq[now]; 32 addq[lc[now]]+=addq[now]; 33 sumq[rc[now]]+=addq[now]; 34 addq[rc[now]]+=addq[now]; 35 addq[now]=0; 36 } 37 } 38 void updateq(int now,int l,int r,int i,int j,int v){ 39 if(l>=i&&r<=j){ 40 sumq[now]+=v; 41 addq[now]+=v; 42 return; 43 } 44 downloadq(now); 45 46 int m=l+r>>1; 47 if(j<=m) updateq(lc[now],l,m,i,j,v); 48 else if(i>m) updateq(rc[now],m+1,r,i,j,v); 49 else{ 50 updateq(lc[now],l,m,i,j,v); 51 updateq(rc[now],m+1,r,i,j,v); 52 } 53 } 54 void downloadh(int now){ 55 if(addh[now]!=0){ 56 sumh[lc[now]]+=addh[now]; 57 addh[lc[now]]+=addh[now]; 58 sumh[rc[now]]+=addh[now]; 59 addh[rc[now]]+=addh[now]; 60 addh[now]=0; 61 } 62 } 63 void updateh(int now,int l,int r,int i,int j,int v){ 64 if(l>=i&&r<=j){ 65 sumh[now]+=v; 66 addh[now]+=v; 67 return; 68 } 69 downloadh(now); 70 71 int m=l+r>>1; 72 if(j<=m) updateh(lc[now],l,m,i,j,v); 73 else if(i>m) updateh(rc[now],m+1,r,i,j,v); 74 else{ 75 updateh(lc[now],l,m,i,j,v); 76 updateh(rc[now],m+1,r,i,j,v); 77 } 78 } 79 ll cdq(int now,int l,int r,int x){ 80 if(l==r) return sumq[now]; 81 82 downloadq(now); 83 84 int m=l+r>>1; 85 if(x<=m) return cdq(lc[now],l,m,x); 86 else return cdq(rc[now],m+1,r,x); 87 } 88 ll cdh(int now,int l,int r,int x){ 89 if(l==r) return sumh[now]; 90 91 downloadh(now); 92 93 int m=l+r>>1; 94 if(x<=m) return cdh(lc[now],l,m,x); 95 else return cdh(rc[now],m+1,r,x); 96 } 97 ll st[maxn],top; 98 ll rsumq[maxn],rsumh[maxn],summq=0,summh=0,xsumq[maxn],xsumh[maxn];//提取出来 99 void calc(){ 100 /*ll ans=0; 101 for(int i=1;i<=n;i++){ 102 for(int j=i+1;j<=n;j++){ 103 if(nd[j].v>nd[i].v){ 104 ans+=(summq-rsumq[i]-rsumq[j]); 105 } 106 } 107 } 108 printf("%lld",ans);*/ 109 /*ll ans=0; 110 for(int i=1;i<=n;i++){ 111 for(int j=1;j<=n;j++){ 112 if(i==j) continue; 113 ll lx=rsumq[i],sx=rsumh[j]; 114 if(j<i&&nd[j].v>nd[i].v) lx--; 115 else if(j<i&&nd[j].v<nd[i].v) sx--;//只有这种... 116 int calc=0; 117 if(j<i){ 118 for(int k=j+1;k<i;k++) 119 if(nd[k].v>nd[i].v&&nd[k].v>nd[j].v){calc++;} 120 } 121 if(lx<0) lx=0; 122 if(sx<0) sx=0; 123 ans+=lx*sx; 124 ans-=calc; 125 } 126 } 127 printf("%lld",ans);*/ 128 ll ans=0; 129 ans+=1ll*summq*summh; 130 for(int i=1;i<=n;i++){ 131 ans-=1ll*rsumq[i]*rsumh[i]; 132 ans-=1ll*xsumq[i]*xsumh[i]; 133 ans-=1ll*rsumq[i]*xsumq[i]; 134 ans-=1ll*xsumh[i]*rsumh[i]; 135 } 136 printf("%lld",ans); 137 } 138 bool cmp2(node a,node b){ 139 if(a.v!=b.v) return a.v>b.v; 140 else return a.id<b.id; 141 } 142 void run(){ 143 sort(nd+1,nd+n+1,cmp2); 144 for(int i=1;i<=n;i++){ 145 rk[i]=nd[i].id; 146 } 147 sort(nd+1,nd+n+1,cmp); 148 rt=np=0; 149 memset(sumq,0,sizeof(sumq)); 150 memset(sumh,0,sizeof(sumh)); 151 memset(addh,0,sizeof(addh)); 152 memset(addq,0,sizeof(addq)); 153 build(rt,1,n); 154 155 for(int i=1;i<=n;i++){ 156 int t=rk[i];//rk存的是id 157 top=0; 158 st[++top]=t; 159 int id=rk[i+1]; 160 while(nd[id].v==nd[t].v&&i+1<=n){ 161 st[++top]=id;i++; 162 id=rk[i+1]; 163 } 164 /*int pos=1; 165 while(pos<=top){ 166 /*int h=n-st[pos]; 167 h-=top-pos; 168 int tt=st[pos]; 169 updateh(rt,1,n,1,tt-1,-1); 170 updateq(rt,1,n,tt+1,n,-1); 171 pos++; 172 }*/ 173 for(int j=1;j<=top;j++){ 174 int tt=st[j]; 175 if(1<=tt-1) updateh(rt,1,n,1,tt-1,-1); 176 if(tt+1<=n) updateq(rt,1,n,tt+1,n,-1); 177 //printf("%lld %lld\n",cdq(rt,1,n,54),cdh(rt,1,n,54)); 178 } 179 for(int j=1;j<=top;j++){ 180 int tt=st[j]; 181 xsumq[tt]=cdq(rt,1,n,tt); 182 xsumh[tt]=cdh(rt,1,n,tt); 183 } 184 } 185 } 186 void init(){ 187 scanf("%d",&n); 188 for(int i=1;i<=n;i++) scanf("%d",&nd[i].v),nd[i].id=i; 189 sort(nd+1,nd+n+1); 190 for(int i=1;i<=n;i++){ 191 rk[i]=nd[i].id; 192 } 193 sort(nd+1,nd+n+1,cmp); 194 build(rt,1,n); 195 for(int i=1;i<=n;i++){ 196 int t=rk[i];//rk存的是id 197 top=0; 198 st[++top]=t; 199 int id=rk[i+1]; 200 while(nd[id].v==nd[t].v){ 201 st[++top]=id;i++; 202 id=rk[i+1]; 203 } 204 /*int pos=1; 205 while(pos<=top){ 206 /*int h=n-st[pos]; 207 h-=top-pos; 208 int tt=st[pos]; 209 updateh(rt,1,n,1,tt-1,-1); 210 updateq(rt,1,n,tt+1,n,-1); 211 pos++; 212 }*/ 213 for(int j=1;j<=top;j++){ 214 int tt=st[j]; 215 if(1<=tt-1) updateh(rt,1,n,1,tt-1,-1); 216 if(tt+1<=n) updateq(rt,1,n,tt+1,n,-1); 217 } 218 for(int j=1;j<=top;j++){ 219 int tt=st[j]; 220 rsumq[tt]=cdq(rt,1,n,tt); 221 summq+=rsumq[tt]; 222 rsumh[tt]=cdh(rt,1,n,tt); 223 summh+=rsumh[tt]; 224 } 225 } 226 run(); 227 calc(); 228 } 229 int main(){ 230 init(); 231 232 return 0; 233 }
T2：
一道动规题.....耐人琢磨，整体是从大字典序往小字典序传承，从右边状态推到左边状态，f[l][r][pos][c]思维表示字符串从s[l]到s[r]第pos位至少为c。关于方法数的计算可以理解一下，下有部分代码注释....
上代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define maxn 55 4 typedef long long ll; 5 const ll mod=990804011; 6 ll f[maxn][maxn][25][30]; 7 int n,len=0; 8 char s[maxn][25]; 9 ll dp(int l,int r,int pos,int c){ 10 if(f[l][r][pos][c]!=-1) return f[l][r][pos][c]; 11 ll &t=f[l][r][pos][c];//代名 12 if(c==27) return t=0;//已超 13 if(pos>len) return t=(l==r?1:0);//说明已经匹配完了，如果两个是一个字符串还行，严格小于 14 t=dp(l,r,pos,c+1);//c+1可以，那c可以，累加 15 for(int mid=l;mid<=r;mid++){ 16 if(s[mid][pos]=='?'&&c==0) break; 17 if(s[mid][pos]!='?'&&c!=s[mid][pos]-'a'+1) break;//任一个不满足都无法转移，只能继承上一个 18 ll tt=dp(l,mid,pos+1,0); 19 if(mid<r) tt=tt*dp(mid+1,r,pos,c+1)%mod; 20 t=(t+tt)%mod; 21 } 22 return t; 23 } 24 void init(){ 25 scanf("%d",&n); 26 for(int i=1;i<=n;i++){ 27 scanf("%s",s[i]+1); 28 int lenn=strlen(s[i]+1); 29 len=max(len,lenn); 30 } 31 for(int i=1;i<=n;i++){ 32 for(int j=int(strlen(s[i]+1)+1);j<=len;j++){ 33 s[i][j]='a'-1;//补位设为0 34 } 35 } 36 memset(f,-1,sizeof(f)); 37 printf("%lld",dp(1,n,1,0)); 38 } 39 int main(){ 40 init(); 41 42 return 0; 43 }
T3：
先咕咕咕了，回去有时间补....