7.2总结

得分情况：

估分：100+30+100=230

实际：100+10+90=200

Rank5

海星，没有欺诈题了。

T1

一眼就是线段树啦。

等等，为甚么\(n\leq7*10^6\)这么大？

不管了先打着。

(30min later)打完一看，极限数据1100ms

这题该不会是要我打树状数组吧，虽然是\(log^2\)级别的，但是常数小啊

码码码…

(20min later)树状数组极限数据4000ms…

先不管了，反正也有90分。

（剩20分钟）来改一改第一题吧

诶，这一段打的这么丑

int find(int k,int l,int r,int x,int y) { if ((l<=y)&&(r>=x)) { int mid=(l+r)/2; if ((l>=x)&&(r<=y)) { if (tree[k].sum>=z) { if (l==r) return l; if (tree[k*2].sum>=z) return find(k*2,l,mid,x,y); else { z-=tree[k*2].sum; return find(k*2+1,mid+1,r,x,y); } } else { z-=tree[k].sum; return 0; } } int tt=find(k*2,l,mid,x,y); if (tt!=0) return tt; else { tt=find(k*2+1,mid+1,r,x,y); return tt; } } else return 0; }

改成这样

int find(int k,int l,int r,int z) { int mid=(l+r)/2; if (l==r) return l; if (tree[k*2]>=z) return find(k*2,l,mid,z); else { return find(k*2+1,mid+1,r,z-tree[k*2]); } }

就切掉了…

后来发现还有两个地方可以优化…

我的代码怎么这么丑

T2

想了很久，差点就想到正解了

我比赛的时候想到了状压dp,但是没有想到怎么转移。

正解

首先，对于n>21的情况是无解的。

原因不明

对于n$\le$21的情况，我们设f[s]表示集合s中的字符已经有了全排列的最前位置。

设next[i][ch]表示位置i之后第一个出现字符ch的位置

方程就是\(f[s]=max(next[f[s-2^{x_i}]][x_i])\)

注意细节，next[n][i]=next[n+1][i]=n+1;

T3

一眼O(nm)dp,看到\(m\leq10^9\)自然而然地考虑矩乘，90分

原因是n=1的情况漏判断了。

我的矩阵长这样

sum[1][1]…sum[1][n]sum[2][1]…sum[2][n]

当N=1时是这样

sum[1][1]sum[2][1]

当我把sum[2][n]与sum[2][n-1]加起来是，我实际上加的是sum[2][1]与sum[1][1]

特判一下就好了

小结

注意细节（废话）没有了

随笔

今天下午zsh借我洗发水用，我的洗发水是清扬去屑洗发露，于是…

zsh用清扬的洗发水啦

ps:zsh喜欢的女生叫L清扬

转载于:https://www.cnblogs.com/leason-lyx/p/11148253.html

相关资源：2288h v5安装rhel server 7.2