亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

CodeForces Round 198

系統 2162 0

??? 總體感覺這次出的題偏數學,數學若菜表示果斷被虐.不過看起來由于大家都被虐我2題居然排到331,rating又升了74.
Div2-A
A. The Wall
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Iahub and his friend Floyd have started painting a wall. Iahub is painting the wall red and Floyd is painting it pink. You can consider the wall being made of a very large number of bricks, numbered 1, 2, 3 and so on.
Iahub has the following scheme of painting: he skips x - 1 consecutive bricks, then he paints the x-th one. That is, he'll paint bricks x, 2·x, 3·x and so on red. Similarly, Floyd skips y - 1 consecutive bricks, then he paints the y-th one. Hence he'll paint bricks y, 2·y, 3·y and so on pink.
After painting the wall all day, the boys observed that some bricks are painted both red and pink. Iahub has a lucky number a and Floyd has a lucky number b. Boys wonder how many bricks numbered no less than a and no greater than b are painted both red and pink. This is exactly your task: compute and print the answer to the question.
Input
The input will have a single line containing four integers in this order: x, y, a, b. (1 ≤ x, y ≤ 1000, 1 ≤ a, b ≤ 2·109, a ≤ b).
Output
Output a single integer — the number of bricks numbered no less than a and no greater than b that are painted both red and pink.
Sample test(s)
Input
2 3 6 18
Output
3
Note
Let's look at the bricks from a to b (a = 6, b = 18). The bricks colored in red are numbered 6, 8, 10, 12, 14, 16, 18. The bricks colored in pink are numbered 6, 9, 12, 15, 18. The bricks colored in both red and pink are numbered with 6, 12 and 18.
題意:兩個人刷墻,一個人刷編號是x的倍數的,另一個刷編號是y倍數的.求在[a,b]上有多少個墻被兩個人同時刷了.
思路:第一題不水沒道理.被同時刷的墻是x和y最小公倍數的倍數.

        #include<stdio.h>

        
          int
        
         gcd(
        
          int
        
         a,
        
          int
        
        
           b)
{
 
        
        
          if
        
         (a==
        
          0
        
        ) 
        
          return
        
        
           b;
 
        
        
          return
        
         gcd(b%
        
          a,a);
}

        
        
          int
        
        
           main()
{
 
        
        
          int
        
        
           x,y;
 __int64 a,b;
 scanf(
        
        
          "
        
        
          %d%d%I64d%I64d
        
        
          "
        
        ,&x,&y,&a,&
        
          b);
 
        
        
          int
        
         M=x/gcd(x,y)*
        
          y;
 __int64 l
        
        =a/M,r=b/
        
          M;
 
        
        
          if
        
         (l*M<a) l++
        
          ;
 printf(
        
        
          "
        
        
          %I64d\n
        
        
          "
        
        ,r-l+
        
          1
        
        
          );
 
        
        
          return
        
        
          0
        
        
          ;
}
        
      
View Code

Div2-B
B. Maximal Area Quadrilateral
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Iahub has drawn a set of n points in the cartesian plane which he calls "special points". A quadrilateral is a simple polygon without self-intersections with four sides (also called edges) and four vertices (also called corners). Please note that a quadrilateral doesn't have to be convex. A special quadrilateral is one which has all four vertices in the set of special points. Given the set of special points, please calculate the maximal area of a special quadrilateral.
Input
The first line contains integer n (4 ≤ n ≤ 300). Each of the next n lines contains two integers: xi, yi ( - 1000 ≤ xi, yi ≤ 1000) — the cartesian coordinates of ith special point. It is guaranteed that no three points are on the same line. It is guaranteed that no two points coincide.
Output
Output a single real number — the maximal area of a special quadrilateral. The answer will be considered correct if its absolute or relative error does't exceed 10 - 9.
Sample test(s)
Input
50 00 44 04 42 3
Output
16.000000
Note
In the test example we can choose first 4 points to be the vertices of the quadrilateral. They form a square by side 4, so the area is 4·4 = 16.
題意:給出一些點,從其中找出4個點構成四邊形,求面積最大的四邊形的面積.
思路:一開始被嚇尿了,想dfs發現那是不可能的事,后來想能不能把四邊形分成兩個三角形來處理.經過觀察發現不論四個點怎么擺必會發生這樣的情況:中間一條線段,線段左右兩邊各有一個點.于是思路就有了:先O(N^2)枚舉這樣的線段,然后O(N)枚舉左右兩邊的點.總時間復雜度為O(N^3).不過要特別注意的是有可能出現一條線段某一側沒有點的情況.

        #include<math.h>
        
          
#include
        
        <stdio.h> 

        
          struct
        
        
           vect
{
 
        
        
          int
        
        
           x,y;
};

        
        
          double
        
         x[
        
          500
        
        ],y[
        
          500
        
        
          ];

        
        
          int
        
        
           mult(vect v1,vect v2)
{
 
        
        
          return
        
         v1.x*v2.y-v2.x*
        
          v1.y;
}

        
        
          int
        
        
           main()
{
 
        
        
          int
        
        
           N;
 scanf(
        
        
          "
        
        
          %d
        
        
          "
        
        ,&
        
          N);
 
        
        
          for
        
         (
        
          int
        
         i=
        
          1
        
        ;i<=N;i++) scanf(
        
          "
        
        
          %lf%lf
        
        
          "
        
        ,&x[i],&
        
          y[i]);
 
        
        
          double
        
         Max=
        
          0
        
        
          ;
 
        
        
          for
        
         (
        
          int
        
         i=
        
          1
        
        ;i<=N;i++
        
          )
  
        
        
          for
        
         (
        
          int
        
         j=
        
          1
        
        ;j<=N;j++
        
          )
  
        
        
          if
        
         (i!=
        
          j)
  {
   vect seg,tmp;
   seg.x
        
        =x[i]-
        
          x[j];
   seg.y
        
        =y[i]-
        
          y[j];
   
        
        
          double
        
         l=
        
          0
        
        ,r=
        
          0
        
        
          ;
   
        
        
          for
        
         (
        
          int
        
         k=
        
          1
        
        ;k<=N;k++
        
          )
   
        
        
          if
        
         (k!=i && k!=
        
          j)
   {
    tmp.x
        
        =x[k]-
        
          x[j];
    tmp.y
        
        =y[k]-
        
          y[j];
    
        
        
          int
        
         dir=
        
          mult(seg,tmp);
    
        
        
          if
        
         (dir<
        
          0
        
        
          )
    {
     
        
        
          double
        
         S=
        
          0.5
        
        *fabs(x[i]*y[j]+y[i]*x[k]+x[j]*y[k]-y[j]*x[k]-y[i]*x[j]-x[i]*
        
          y[k]);
    
        
        
          if
        
         (S>l) l=
        
          S;
    }
    
        
        
          else
        
        
           
    {
     
        
        
          double
        
         S=
        
          0.5
        
        *fabs(x[i]*y[j]+y[i]*x[k]+x[j]*y[k]-y[j]*x[k]-y[i]*x[j]-x[i]*
        
          y[k]);
     
        
        
          if
        
         (S>r) r=
        
          S;
    }
   }
   
        
        
          if
        
         (l+r>Max && l>
        
          0
        
         && r>
        
          0
        
        ) Max=l+
        
          r;
  }
 printf(
        
        
          "
        
        
          %.9lf\n
        
        
          "
        
        
          ,Max);
 
        
        
          return
        
        
          0
        
        
          ;
}
        
      
View Code

Div2-C/Div1-A
C. Tourist Problem
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Iahub is a big fan of tourists. He wants to become a tourist himself, so he planned a trip. There are n destinations on a straight road that Iahub wants to visit. Iahub starts the excursion from kilometer 0. The n destinations are described by a non-negative integers sequence a1, a2, ..., an. The number ak represents that the kth destination is at distance ak kilometers from the starting point. No two destinations are located in the same place.
Iahub wants to visit each destination only once. Note that, crossing through a destination is not considered visiting, unless Iahub explicitly wants to visit it at that point. Also, after Iahub visits his last destination, he doesn't come back to kilometer 0, as he stops his trip at the last destination.
The distance between destination located at kilometer x and next destination, located at kilometer y, is |x?-?y| kilometers. We call a "route" an order of visiting the destinations. Iahub can visit destinations in any order he wants, as long as he visits all n destinations and he doesn't visit a destination more than once.
Iahub starts writing out on a paper all possible routes and for each of them, he notes the total distance he would walk. He's interested in the average number of kilometers he would walk by choosing a route. As he got bored of writing out all the routes, he asks you to help him.
Input
The first line contains integer n (2?≤?n?≤?105). Next line contains n distinct integers a1, a2, ..., an (1?≤?ai?≤?107).
Output
Output two integers — the numerator and denominator of a fraction which is equal to the wanted average number. The fraction must be irreducible.
Sample test(s)
Input
32 3 5Output
22 3Note
Consider 6 possible routes:
[2, 3, 5]: total distance traveled: |2 – 0| + |3 – 2| + |5 – 3| = 5;
[2, 5, 3]: |2 – 0| + |5 – 2| + |3 – 5| = 7;
[3, 2, 5]: |3 – 0| + |2 – 3| + |5 – 2| = 7;
[3, 5, 2]: |3 – 0| + |5 – 3| + |2 – 5| = 8;
[5, 2, 3]: |5 – 0| + |2 – 5| + |3 – 2| = 9;
[5, 3, 2]: |5 – 0| + |3 – 5| + |2 – 3| = 8.
The average travel distance is? =? = .
題意:一條路上n個景點,可以按任意順序全部訪問一遍,求走路的平均長度.
思路:這是官方題解
Despite this is a math task, the only math formula we'll use is that number of permutations with n elements is n!. From this one, we can deduce the whole task.
The average formula is sum_of_all_routes / number_of_routes. As each route is a permutation with n elements, number_of_routes is n!. Next suppose you have a permutation of a: p1, p2, …, pn. The sum for it will be p1 + |p2 – p1| + … + |pn – pn-1|. The sum of routes will be the sum for each possible permutation.
We can calculate sum_of_all routes in two steps: first time we calculate sums like “p1” and then we calculate sums like “|p2 – p1| + … + |pn – pn-1|” for every existing permutation.
First step Each element of a1, a2, …, an can appear on the first position on the routes and needs to be added as much as it appears. Suppose I fixed an element X for the first position. I can fill positions 2, 3, .., n – 1 in (n – 1)! ways. Why? It is equivalent to permuting n – 1 elements (all elements except X). So sum_of_all = a1 * (n – 1)! + a2 * (n – 1)! + … * an * (n – 1)! = (n – 1)! * (a1 + a2 + … + an).
Second step For each permutation, for each position j between 1 and n – 1 we need to compute |pj — p(j?+?1)|. Similarly to first step, we observe that only elements from a can appear on consecutive positions. We fix 2 indices i and j. We’re interested in how many permutations do ai appear before aj. We fix k such as on a permutation p, ai appears on position k and aj appears on a position k + 1. In how many ways can we fix this? n – 1 ways (1, 2, …, n – 1). What’s left? A sequence of (n – 2) elements which can be permuted independently. So the sum of second step is |ai?-?aj| * (n – 1) * (n – 2)!, for each i != j. If I note (a1 + a2 + … + an) by S1 and |ai?-?aj| for each i != j by S2, the answer is (N – 1)! * S1 + (N – 1)! * S2 / N!. By a simplification, the answer is (S1 + S2) / N.
The only problem remained is how to calculate S2. Simple iteration won’t enter in time limit. Let’s think different. For each element, I need to make sum of differences between it and all smaller elements in the array a. As well, I need to make sum of all different between bigger elements than it and it. I’ll focus on the first part. I sort increasing array a. Suppose I’m at position i. I know that (i – 1) elements are smaller than ai. The difference is simply (i — 1) * ai — sum_of_elements_before_position_i. Sum of elements before position i can be computed when iterating i. Let’s call the obtained sum Sleft. I need to calculate now sum of all differences between an element and bigger elements than it. This sum is equal to Sleft. As a proof, for an element ai, calculating the difference aj — ai when aj > ai is equivalent to calculating differences between aj and a smaller element of it (in this case ai). That’s why Sleft = Sright.
As a conclusion, the answer is (S1 + 2 * Sleft) / N. For make fraction irreducible, you can use Euclid's algorithm. The complexity of the presented algorithm is O(N?*?logN), necessary due of sorting. Sorting can be implemented by count sort as well, having a complexity of O(maximalValue), but this is not necessary.

        #include<stdio.h>
        
          
#include
        
        <stdlib.h>
        
          
#include
        
        <math.h>
        
          
#include
        
        <
        
          string
        
        .h>

        
          #define
        
         N 100005

        
          long
        
        
          long
        
        
           a[N];

        
        
          long
        
        
          long
        
         gcd(
        
          long
        
        
          long
        
         a,
        
          long
        
        
          long
        
        
           b)
{
    
        
        
          return
        
         b gcd(b,a%
        
          b):a;
}

        
        
          int
        
         cmp(
        
          const
        
        
          void
        
         *a,
        
          const
        
        
          void
        
         *
        
          b)
{
    
        
        
          return
        
         *(
        
          long
        
        
          long
        
        *)a-*(
        
          long
        
        
          long
        
         *
        
          )b;
}

        
        
          int
        
        
           main()
{
    
        
        
          long
        
        
          long
        
         n,sum=
        
          0
        
        
          ,p,q,d,tot;
    
        
        
          while
        
        (~scanf(
        
          "
        
        
          %I64d
        
        
          "
        
        ,&
        
          n))
    {
        
        
        
          for
        
        (
        
          int
        
         i=
        
          0
        
        ;i<n;i++
        
          )
            scanf(
        
        
          "
        
        
          %I64d
        
        
          "
        
        ,a+
        
          i);
        
        
        
          for
        
        (
        
          int
        
         i=
        
          0
        
        ;i<n;i++
        
          )
            sum
        
        +=
        
          a[i];
        qsort(a,n,
        
        
          sizeof
        
        (a[
        
          0
        
        
          ]),cmp);
        p
        
        =
        
          0
        
        ;q=n-
        
          1
        
        
          ;
        tot
        
        =
        
          n;
        
        
        
          while
        
        (p<
        
          q)
        {
            sum
        
        +=
        
          2
        
        *(tot-
        
          1
        
        )*(a[q]-
        
          a[p]);
            p
        
        ++
        
          ;
            q
        
        --
        
          ;
            tot
        
        -=
        
          2
        
        
          ;
        }
        d
        
        =
        
          gcd(sum,n);
        sum
        
        /=d,n/=
        
          d;
        printf(
        
        
          "
        
        
          %I64d %I64d\n
        
        
          "
        
        
          ,sum,n);
    }
    
        
        
          return
        
        
          0
        
        
          ;
}
        
      
View Code

?

CodeForces Round 198


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: jizz免费在线观看 | 亚洲免费精品视频 | 亚洲图片欧美日韩 | 亚洲国产高清美女在线观看 | 国产激情视频在线 | 亚洲一级免费毛片 | free性欧美极度另类超级大 | xxxx成年视频免费 | 亚洲12色吧| 国产大尺度福利视频在线 | 日本不卡一区二区三区视频 | 99在线视频观看 | 国产日韩欧美二区 | 91视频免费网站 | 日韩中文字幕免费观看 | 国产日韩欧美一区二区 | 午夜时刻免费实验区观看 | 精品外国呦系列在线观看 | 综合网视频 | 精品一区二区视频 | 免费大片黄在线观看yw | 国产成人亚洲综合欧美一部 | 奇米影视778成人四色狠狠 | 天天干天天射天天 | 奇米7777第四色 | 国产一级毛片视频 | 亚洲va欧美va国产 | 一区二区三区鲁丝不卡麻豆 | 亚洲va天堂va欧美ⅴa | 色老成人精品视频在线观看 | 久久伊人成人 | 亚洲精品一区二区三区香蕉在线看 | 成人久久久久久 | 亚洲国产成人久久午夜 | 欧美啪啪毛片一区二区 | 国产午夜亚洲精品国产 | 99久久99 | 国产精品成人久久久久久久 | 岛国片欧美一级毛片 | 全黄h全肉边做边吃奶在线观看 | 成人欧美精品一区二区不卡 |