●HDU6070 Dirt Ratio http://acm.hdu.edu.cn/showproblem.php?pid=6070
题意：
=========================================================================
题意：给长度为n的序列，找到并输出它的所有子序列区间[l,r]中数字种类/子序列长度的最小值。
（比完赛读懂题系列）（以为是求出现次数最多的数字然后用1除）（天真）
标程思路：
用size()表示区间[l,r]的题目种类数，mid表示正确率，目标是找到size(l,r)r−l+1≤mid
这个式子可以化简为size(l,r)+l*mid<=(r+1)*mid
把线段树初始化为l*mid
先偷偷复制一波师哥的程序假装是自己写的
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define LL long long #define read(a) scanf("%d",&a) const int maxn= 60000+10; double MID,L,R,t; int a[maxn],pre_pos[maxn];//pre_pos[a[i]]代表的是a[i]这个题上一次提交的位置 int n; int diff_num[maxn<<2];//diff_num存的是 线段树上某节点代表的区间 可以增加的不同的颜色的个数 double v[maxn<<2];//v数组 存的是 线段树上某点（包括这个点的子树） 的最小的 size+MID*l inline double min(double a,double b) { return a<b?a:b; } void build(int x,int l,int r) //建树过程不难理解，因为MID*l是不变的，提前做好初始化 { v[x]=MID*l; diff_num[x]=0; if(l==r) return; int mid=(l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); } inline void add(int x,int num) { v[x]+=num; diff_num[x]+=num; } inline void sonadd(int x) { if(diff_num[x]) { add(x<<1 ,diff_num[x]); add(x<<1|1,diff_num[x]); diff_num[x]=0; } } void change(int x,int l,int r,int pre,int now) { if(pre<=l&&r<=now)//pre<=l代表当前区间的左端点比遍历到的点的前一个位置大 //r<=now代表当前区间的右端点比遍历到的点的当前位置小或者等于 //这样的话代表这个区间可以多一个不同的贡献 //为什么是r<=now呢，是因为now参数代表的是我们枚举到的右端点 //所以树上的端点代表的区间只要右端点小于等于now，其实都可以看作是它的右端点是now //如果右端点比now大就不行了,那样的话区间就比我们枚举的区间大了，超范围了。 { add(x,1);//这里就是更新了，如果可以有一个不同的就加一个 return ; } sonadd(x); //这里表示如果该点的区间不符合，那么把他所有的子树更新，因为他的子树的区间范围是比该点小的 //所以他的子树一定可以获得和他的父节点一样的不同的贡献 //更新完，x的临时存储获得的不同贡献的diff_num数组要清零，否则下一次给子树更新会加重 int mid=(l+r)>>1; if(pre<=mid) change(x<<1,l,mid,pre,now); if(mid+1<=now) change(x<<1|1,mid+1,r,pre,now); v[x]=min(v[x<<1],v[x<<1|1]);//这一步可以很好的减少检索深度 // 这样的话最大的父节点就存储着包括他子树的最小的v[x]，只需要找到这个父节点就可以了， //不需要准确到代表那个区间的子树上的点 } void ask(int x,int l, int r,int right) { if(r<=right) { if(t>v[x]) t=v[x];//这里是我唯一的疑问，因为是自己理解然后手撕的代码，所以写的时候就在这里加了个括号 //就在下面的注释里面，但是那样子做就错了，我的理解t<v[x]的时候会一直搜索，导致搜索溢出 //但是还是不能说服自己，希望大牛看到可以帮忙解释一下 return; /* { t=v[x]; return; } */ } // sonadd(x); 这一步代码里有，但是我感觉没有用，我就给注释掉了，提交之后发现果然没有用，这是一步无用的更新 int mid=(l+r)>>1; ask(x<<1,l,mid,right); if(mid+1<=right) ask(x<<1|1,mid+1,r,right); } int main() { int T; read(T); while(T--) { read(n); for(int i=1;i<=n;i++) read(a[i]); L=0.0,R=1.0; for(int cnt=1;cnt<=24;cnt++)//标程里面是20次，无所谓的，这里就是致敬一下黑曼巴 { int i; MID=(L+R)/2; build(1,1,n); for( i=1;i<=n;i++) pre_pos[i]=0; for( i=1;i<=n;i++) { t=0x3f3f3f3f;//初始化最大值 change(1,1,n,pre_pos[a[i]]+1,i);//这里传的是pre_pos[a[i]]+1,奥秘在change里面，一想就明白，不解释了 ask(1,1,n,i); if(t-MID*(i+1)<=0)//这里就是公式的转化，size+MID*l-MID*(r+1) break; pre_pos[a[i]]=i; } if(i<=n)R=MID; else L=MID; } printf("%.10f\n",(L+R)/2); } return 0; }
