当前位置: 首页 > news >正文

笔趣阁 网站开发沈阳做网站培训

笔趣阁 网站开发,沈阳做网站培训,个人能免费做网站,个人微商城怎么开通正题 题目链接:https://www.luogu.com.cn/problem/P7324 题目大意 给一个只包含mmm个值的表达式#xff0c;表前后取最小值#xff0c;表前后取最大#xff0c;???可以是小于也可以是大于。 然后nnn次给出这mmm个值#xff0c;所有方案下表达…正题 题目链接:https://www.luogu.com.cn/problem/P7324 题目大意 给一个只包含mmm个值的表达式表前后取最小值表前后取最大???可以是小于也可以是大于。 然后nnn次给出这mmm个值所有方案下表达式取值的和。输出这nnn次答案的和。 1≤n≤5×104,1≤m≤10,1≤∣S∣≤5×1041\leq n\leq 5\times 10^4,1\leq m\leq 10,1\leq |S|\leq 5\times 10^41≤n≤5×104,1≤m≤10,1≤∣S∣≤5×104 解题思路 有括号所以先把表达树建出来考虑到mmm很小应该和状压有点关系。暴力的做法是直接做nnn次时间复杂度是O(nm∣S∣)O(nm|S|)O(nm∣S∣)显然过不了。 因为取值只有mmm个考虑把所有的信息压缩起来。实际上我们需要的信息就只有mmm个数之间的大小顺序这样的状态数是m!m!m!个要搞起来时间复杂度最快是O(m!∣S∣)O(m!|S|)O(m!∣S∣)也过不了。 但是对于一个数字来说我们就只需啊哟考虑它和其他数字的大小关系状态数是2m2^m2m。设fx,s,0/1f_{x,s,0/1}fx,s,0/1​表示到节点xxx时小于数字xxx的值状态是sss时到该节点的数字小于/大于数字xxx的方案数。 然后对于每个sss跑出来一个答案然后按照这个后面就很好做了。 时间复杂度O(2m∣S∣nmlog⁡n)O(2^m|S|nm\log n)O(2m∣S∣nmlogn) code #includecstdio #includecstring #includealgorithm #includestack #define ll long long using namespace std; const ll N1e510,P1e97; ll n,m,k,cnt,L,ans,a[10][N],p[10],rev[N]; ll ls[N],rs[N],f[N][2],z[N],c[N]; char s[N];stackll st; ll Build(ll l,ll r){if(lr){cnt;c[cnt]s[l]-0;return cnt;}if(rev[r]l)return Build(l1,r-1);ll xcnt;if(rev[r]){ls[x]Build(l,rev[r]-2);rs[x]Build(rev[r]1,r-1);c[x]s[rev[r]-1];}else{ls[x]Build(l,r-2);rs[x]Build(r,r);c[x]s[r-1];}return x; } void dfs(ll x,ll s){f[x][0]f[x][1]0;if(c[x]10){f[x][!(s(1c[x]))]1;return;}dfs(ls[x],s);dfs(rs[x],s);if(c[x]!){for(ll i0;i2;i)for(ll j0;j2;j)(f[x][min(i,j)]f[ls[x]][i]*f[rs[x]][j]%P)%P;}if(c[x]!){for(ll i0;i2;i)for(ll j0;j2;j)(f[x][max(i,j)]f[ls[x]][i]*f[rs[x]][j]%P)%P;}return; } bool cmp(ll x,ll y) {return a[x][k]a[y][k];} signed main() {scanf(%lld%lld,n,m);for(ll i0;im;i)for(ll j1;jn;j)scanf(%lld,a[i][j]);scanf(%s,s1);Lstrlen(s1);for(ll i1;iL;i){if(s[i]()st.push(i);else if(s[i])){ll xst.top();rev[x]i;rev[i]x;st.pop();}}Build(1,L);ll MS(1m);for(ll i0;iMS;i)dfs(1,i),z[i]f[1][1];for(k1;kn;k){for(ll i0;im;i)p[i]i;sort(p,pm,cmp);(ansz[0]*a[p[0]][k]%P)%P;ll S0;for(ll i1;im;i){S|(1p[i-1]);(ansz[S]*(a[p[i]][k]-a[p[i-1]][k])%P)%P;}}printf(%lld\n,(ansP)%P);return 0; }
http://wiki.neutronadmin.com/news/413207/

相关文章:

  • 建设网站里的会员系统百度云wordpress教程视频
  • mysql 网站空间贵州建设网站
  • 网站建设公司的性质软件项目管理制度
  • 国内f型网页布局的网站pk10代码网站开发
  • 网站分页符怎么做建设一个国外服务器的网站
  • 培训网站平台怎样做网站自身维护
  • 哪里有免费的网站推广wordpress建站社区
  • 深圳网站制作平台博客网
  • 做搬家广告哪家网站有优wordpress 更新文章
  • 网站建设课程学习wordpress 插件开启
  • 做原油的网站深圳百度推广公司
  • 重庆学校网站推广青岛商网站建设
  • 网站设计方案大全自学室内装修设计教程
  • 案例查询网站软件著作权查询入口
  • 网站建设单位做c 题的网站
  • 文章响应式网站如何制作购物网站
  • 湖南网站搜索排名优化公司关于做网站的论文
  • 做网站必须有站点吗做网站的安全证书
  • 在网站中动态效果怎么做中小学智慧校园建设平台网站
  • 内蒙古兴安盟建设局网站平面设计师的培训机构
  • seo 成功网站影楼网站设计
  • 校园网站建设简介菏泽网站建设设计
  • 怎么做自已的网站网站建设财务分析
  • 潍坊网站开发公司ui设计的基本流程
  • 台州做网站的电话php网站开发环境说明
  • 长沙网站制作关键词推广江苏省和住房城乡建设厅网站
  • 电子商务网站的主要功能wordpress该怎么教
  • 音乐类网站模板连云港专业网站制作公司
  • 网站建设整个过程谷歌 网站做推广
  • 中邮保险网站wordpress 网页