首页 > 代码库 > noip2016十连测 Round #3
noip2016十连测 Round #3
A：平均数
题目描述：有一天，小A得到了一个长度为n的序列。他把这个序列的所有连续子序列都列了出来，并对每一个子序列都求了其
平均值，然后他把这些平均值写在纸上，并对它们进行排序，最后他报出了第k小的平均值。你要做的就是模仿他
的过程。
思路：二分答案，然后判断二分的结果是不是恰好为第k位。首先统计出每一个元素和平均值的差值，记为d[i],对于区间[l,r]，
如果d[l]~d[r]之和要大于0，那么这段区间的平均值就一定要大于二分的答案。于是考虑求出前缀和，记为sumd[i]，那么
区间[l,r]的答案就是sumd[r]-sumd[l-1]，即有多少对sumd[r]-sumd[l-1]<0即为答案。喜闻乐见的求逆序对个数，
树状数组或归并排序即可，加上二分时间复杂度就是O(nlog^2n)
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 #define min(x,y) ((x)>(y)?(y):(x)) 8 #define max(x,y) ((x)>(y)?(x):(y)) 9 #define maxn 10001010 #define eps 1e-611 12 int n,k;13 double l,r,ans;14 int a[maxn],c[maxn];15 16 struct node{17 double sumave;18 int size;19 }d[maxn];20 bool operator <(node a,node b){return a.sumave>b.sumave||(a.sumave==b.sumave&&a.size<b.size);}21 22 int read(){23 int x=0,f=1;char ch=getchar();24 for (;ch<‘0‘||ch>‘9‘;ch=getchar()) if (ch==‘-‘) f=-1;25 for (;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) x=x*10+ch-‘0‘;26 return x*f;27 }28 29 void change(int x){30 while (x<=n){c[x]++;x+=x&(-x);}31 }32 33 int query(int x){34 int ans=0;35 while (x){ans+=c[x];x-=x&(-x);}36 return ans;37 }38 39 bool check(double x){40 int ck=0;41 for (int i=1;i<=n;i++){d[i].sumave=d[i-1].sumave+a[i]-x,d[i].size=i;if (d[i].sumave<0) ck++;}42 sort(d+1,d+n+1);memset(c,0,sizeof(c));43 for (int i=1;i<=n;i++) ck+=query(d[i].size),change(d[i].size);44 return ck>=k;45 }46 47 int main(){48 n=read(),k=read();49 for (int i=1;i<=n;i++) a[i]=read();50 l=-1e9,r=1e9;51 while (l+eps<r){52 double mid=(l+r)/2;53 if (check(mid)) r=mid,ans=mid;54 else l=mid;55 }56 printf("%.4lf\n",ans);57 return 0;58 }
B：涂色游戏
题目描述：小A和小B在做游戏。他们找到了一个n行m列呈网格状的画板。小A拿出了p支不同颜色的画笔，开始在上面涂色。看
到小A涂好的画板，小B觉得颜色太单调了，于是把画板擦干净，希望涂上使它看起来不单调的颜色（当然，每个格
子里只能涂一种颜色）。小B想知道一共有多少种不单调的涂色方案。我们定义一个涂色方案是不单调的，当且仅
当任意相邻两列都出现了至少q种颜色。
思路：
noip2016十连测 Round #3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。