数学期望+区间标记-白红宇

数学期望+区间标记

阅读量：4614 次

发布时间：2019-06-09

本文共 1883 字，大约阅读时间需要 6 分钟。

https://vjudge.net/contest/237352#problem/G

题意：有n个玩具，编号为1到n，其中编号为i的玩具价值为wi。有m个区间，其中第i个区间为[li,ri]，

1 //#include
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               12 #include 
                
                 13 #include 
                 
                  14 #include 
                  
                   15 #include 
                   
                    16 #define ms(a, b) memset(a, b, sizeof(a));17 using namespace std;18 typedef long long LL;19 typedef pair
                    
                      pii;20 const int INF = 0x3f3f3f3f;21 const int maxn = 5e4 + 10;22 const int MAXN = 2e4 + 10;23 const double eps = 1e-8;24 const int mod = 1e9 + 7;25 int n, m;26 int w[maxn], f[maxn];27 28 LL C(LL k) {29 return k * (k-1) * (k-2) / 6;30 }31 32 LL gcd(LL a, LL b) {33 while(b) {34 LL tmp = a % b;35 a = b;36 b = tmp;37 }38 return a;39 }40 41 void solve() {42 43 return ;44 }45 46 47 int main() {48 #ifdef local49 freopen("case.in", "r", stdin);50 // freopen("case.out", "w", stdout);51 #endif52 // ios::sync_with_stdio(false);53 // cin.tie(0);54 int T;55 scanf("%d", &T);56 while(T--) {57 scanf("%d%d", &n, &m);58 for(int i = 1; i <= n; i++)59 scanf("%d", &w[i]);60 ms(f, 0);61 for(int i = 0; i < m; i++) {62 int l, r;63 scanf("%d%d", &l, &r);64 f[l]++;65 f[r+1]--;66 }67 LL cnt = 0, up = 0;68 for(int i = 1; i <= n; i++) {69 cnt += f[i];70 if(cnt >= 3) up += w[i] * C(cnt);71 }72 LL down = C(m);73 LL div = gcd(up, down);74 if(div > 0) {75 up /= div;76 down /= div;77 if(down == 1) printf("%lld\n", up);78 else printf("%lld/%lld\n", up, down);79 }80 else printf("0\n");81 }82 // solve();83 return 0;84 }