首页 > 代码库 > 济南学习 Day2 T2 am
济南学习 Day2 T2 am
【问题描述】
有??个数,随机选择一段区间,如果这段区间的所有数的平均值在[l,r]中则
你比较厉害。求你比较厉害的概率。
【输入格式】
第一行有三个数N,l,r,含义如上描述。
接下来一行有??个数代表每一个数的值。
【输出格式】
输出一行一个分数 a/b
代表答案,其中a,b互质。如果答案为整数则直接输出该
整数即可。
【样例输入 1】
4 2 3
3 1 2 4
【样例输出 1】
7/10
【样例输入 2】
4 1 4
3 1 2 4
【样例输出 2】
1
【样例解释】
塔外面有棵树。
【数据规模与约定】
对于30%的数据,1<=N<=10^4.
60%的数据,1 ≤ N≤ 10 5 。
对于100%的数据,1 ≤ N ≤ 5× 10 5 ,0 < l ≤ r ≤ 100。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #ifdef unix 7 #define LL "%lld" 8 #else 9 #define LL "%I64d" 10 #endif 11 #define lb(x) ((x)&(-(x))) 12 const int maxn=500010; 13 int n,l,r,y[maxn],z[maxn],w[maxn],x[maxn]; 14 bool cmp(int a,int b) 15 { 16 return z[a]>z[b]; 17 } 18 void insert(int p) 19 { 20 for (;p<=n;p+=lb(p)) 21 w[p]++; 22 } 23 int query(int p) 24 { 25 int ans=0; 26 for (;p;p-=lb(p)) 27 ans+=w[p]; 28 return ans; 29 } 30 long long solve() 31 { 32 for (int a=1;a<=n;a++) 33 z[a]+=z[a-1];// 前缀和 34 for (int a=n+1;a>=2;a--) 35 z[a]=z[a-1];// 向后平移一位 36 z[1]=0; 37 n++; 38 for (int a=1;a<=n;a++) 39 x[a]=a; 40 sort(x+1,x+n+1,cmp); 41 memset(w,0,sizeof(w)); 42 long long ans=0; 43 for (int a=1;a<=n;) 44 { 45 int b=a; 46 while (b<=n && z[x[b]]==z[x[a]]) 47 b++; 48 for (int c=a;c<b;c++) 49 ans+=query(x[c]-1); 50 for (int c=a;c<b;c++) 51 insert(x[c]); 52 a=b; 53 } 54 n--; 55 return ans; 56 } 57 long long gcd(long long a,long long b) 58 { 59 if (!b) return a; 60 else return gcd(b,a%b); 61 } 62 int main() 63 { 64 65 scanf("%d%d%d",&n,&l,&r); 66 for (int a=1;a<=n;a++) 67 scanf("%d",&y[a]); 68 for (int a=1;a<=n;a++) 69 z[a]=y[a]-l; 70 long long ans=solve(); 71 for (int a=1;a<=n;a++) 72 z[a]=r-y[a]; 73 ans+=solve(); 74 long long up=ans; 75 long long down=(long long)n*(n+1)/2; 76 up=down-up; 77 long long g=gcd(up,down); 78 up/=g; 79 down/=g; 80 if (up==0) printf("0\n"); 81 else 82 { 83 if (down==1) printf("1\n"); 84 else printf(LL "/" LL "\n",up,down); 85 } 86 87 return 0; 88 }
思路:转成区间和小于等于0,然后就是前缀和逆序对
济南学习 Day2 T2 am
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。