Codeforces Round #582 (Div. 3)

Question link: https://codeforces.com/contest/1213

Question meaning: the position of the given number, the position is an integer , Each number can be moved one or two squares to the left or right. It costs one coin to move one square, and no coins to move two squares. Ask all coins to move to the same position at least how many coins it costs

idea: The odd and even number of each number

 1 #include 

 2

 3 using  namespace std;

 4 int a[110], n, s1, s2;

 5

 6 int main()

 7 {

 8 cin >> n;

 9 for (int i = 0; i )

10  {

11 cin >> a[i];

12 if (a[i]% 2) s1 ++; // s1 is an even number

13 else s2 ++;

14 }

15 int ans = min(s1, s2);

16 cout << ans << endl;

17 return 0;

18 }

View Code

The meaning of the question: Given the daily price, if the price of the following days is lower than the current price, consider this day as a “bad” day, and ask how many days there are in total Is “bad”

idea: monotonous stack, traversed from the back to the front, time complexity O(n)

 1 #include 

 2 #include 

 3

 4 using  namespace std;

 5 const int MAXN = 1e6 + 10;

 6 int t, n, a[MAXN];

 7

 8 int main()

 9 {

10 cin >> t;

11 while (t --)

12  {

13 scanf("%d",&n);

14 for (int i = 0; i )

15 scanf("%d",&a[i]);

16

17 int ss = a[n-1], ans = 0;

18 for (int i = n-2; i >= 0; i --)

19  {

20 if (a[i]> ss) ans ++;

21 if (a[i]  a[i];

22 }

23 cout << ans << endl;

24 }

25 return 0;

26 }

View Code

Question meaning: enter n and m, and find the cumulative sum of the single digits of the number 1~n that can divide m.

idea: math problem, i * m% 10 = (10 + i) * m% 10, 0 <= i <= 9

< span style="color: #008080;"> 1 #include 

 2 #include 

 3

 4 using  namespace std;

 5 typedef long long ll;

 6 int q, a[10];

 7

 8 int main()

 9 {

10 cin >> q;

11 while (q --)

12  {

13 ll n, m, k, sum = 0, ans = 0;

14 cin >> n >> m;

15 for (int i = 0; i <10; i ++)

16  {

17 a[i] = m * (1 + i)% 10;

18 sum += a[i];

19 }

20

21 k = n / m;

22  ll s;

23 s = k% 10;

24 for (int i = 0; i  a[i];

25 ans += (k / 10) *  sum;

26 cout << ans << endl;

27 }

28 return 0;

29 }

View Code

D1:

The meaning of the question: Given some numbers, the number can become n / 2 (rounded down), and the question becomes a certain number m, and there are at least k numbers What is the minimum number of operations required to become m

idea: record the contribution of each number. If the number of m becomes greater than or equal to k, then the number of first k small operations can be accumulated (pure violence) Messing…)

 1 # include 

 2 #include 

 3 #include 

 4 #include 

 5

 6 using  namespace std;

 7 const int MAXN = 1e6;

 8 const int _inf = 0x3f3f3f;

 9 int k, n, a[MAXN] , b[MAXN], c[MAXN], ans = _inf;

10

11 int main()

12 {

13 cin >> n >> k;

14 for (int i = 0; i )

15 cin >> a[i];

16

17 int idd = 0;

18 for (int i = 0; i )

19  {

20 int x = a[i];

21 b[idd ++] = x;

22 while (x> 0)

23  {

24 x >>= 1;

25 b[idd ++] = x;

26 }

27 }

28

29 for (int i = 0; i )

30  {

31 int id = 0;

32 for (int j = 0; j )

33  {

34 int x = a[j], cur = 0;

35 while (x > b[i])

36  {

37 x >>= 1;

38 cur ++;

39 }

40 if (x == b[i]) {

41 c[id ++] = cur;

42 }

43 }

44 if (id >= k) {

45 int sum = 0;

46 sort(c, c + id);

47 for (int j = 0; j  c[j];

48 ans = min(ans, sum);

49 }

50 memset(c,0,sizeof c);

51 }

52 cout << ans << endl;

53 return 0;

54 }

View Code

PS: Because I am lazy, I took a long time to fill up the questions, I will fill up the questions as soon as possible in the future, concentrate on filling up the questions

Share a picture Share picture

 1 #include 

 2

 3 using  namespace std;

 4 int a[110], n, s1, s2;

 5

 6 int main()

 7 {

 8 cin >> n;

 9 for (int i = 0; i )

10  {

11 cin >> a[i];

12 if (a[i]% 2) s1 ++; // s1 is an even number

13 else s2 ++;

14 }

15 int ans = min(s1, s2);

16 cout << ans << endl;

17 return 0;

18 }

View Code

 1 #include 

 2

 3 using  namespace std;

 4 int a[110], n, s1, s2;

 5

 6 int main()

 7 {

 8 cin >> n;

 9 for (int i = 0; i )

10  {

11 cin >> a[i];

12 if (a[i]% 2) s1 ++; // s1 is an even number

13 else s2 ++;

14 }

15 int ans = min(s1, s2);

16 cout << ans << endl;

17 return 0;

18 }

share picture

 1 #include 

 2 #include 

 3

 4 using  namespace std;

 5 const int MAXN = 1e6 + 10;

 6 int t, n, a[MAXN];

 7

 8 int main()

 9 {

10 cin >> t;

11 while (t --)

12  {

13 scanf("%d",&n);

14 for (int i = 0; i )

15 scanf("%d",&a[i]);

16

17 int ss = a[n-1], ans = 0;

18 for (int i = n-2; i >= 0; i --)

19  {

20 if (a[i]> ss) ans ++;

21 if (a[i]  a[i];

22 }

23 cout << ans << endl;

24 }

25 return 0;

26 }

View Code

 1 #include 

 2 #include 

 3

 4 using  namespace std;

 5 const int MAXN = 1e6 + 10;

 6 int t, n, a[MAXN];

 7

 8 int main()

 9 {

10 cin >> t;

11 while (t --)

12  {

13 scanf("%d",&n);

14 for (int i = 0; i )

15 scanf("%d",&a[i]);

16

17 int ss = a[n-1], ans = 0;

18         for (int i = n - 2; i >= 0; i -- )

19         {

20             if (a[i] > ss)  ans ++ ;

21             if (a[i] < ss)  ss = a[i];

22         }

23         cout << ans << endl;

24     }

25     return 0;

26 }

分享图片

 1 #include 

 2 #include 

 3  

 4 using namespace std;

 5 typedef long long ll;

 6 int q, a[10];

 7  

 8 int main()

 9 {

10     cin >> q;

11     while (q -- )

12     {

13         ll n, m, k, sum = 0, ans = 0;

14         cin >> n >> m;

15         for (int i = 0; i < 10; i ++ )

16         {

17             a[i] = m * (1 + i) % 10;

18             sum += a[i];

19         }

20         

21         k = n / m;

22         ll s;

23         s = k % 10;

24         for (int i = 0; i < s; i ++ )  ans += a[i];

25         ans += (k / 10) * sum;

26         cout << ans << endl;

27     }

28     return 0;

29 }

View Code

 1 #include 

 2 #include 

 3  

 4 using namespace std;

 5 typedef long long ll;

 6 int q, a[10];

 7  

 8 int main()

 9 {

10     cin >> q;

11     while (q -- )

12     {

13         ll n, m, k, sum = 0, ans = 0;

14         cin >> n >> m;

15         for (int i = 0; i < 10; i ++ )

16         {

17             a[i] = m * (1 + i) % 10;

18             sum += a[i];

19         }

20         

21         k = n / m;

22         ll s;

23         s = k % 10;

24         for (int i = 0; i < s; i ++ )  ans += a[i];

25         ans += (k / 10) * sum;

26         cout << ans << endl;

27     }

28     return 0;

29 }

分享图片

 1 #include 

 2 #include 

 3 #include 

 4 #include 

 5  

 6 using namespace std;

 7 const int MAXN = 1e6;

 8 const int _inf = 0x3f3f3f;

 9 int k, n, a[MAXN], b[MAXN], c[MAXN], ans = _inf;

10  

11 int main()

12 {

13     cin >> n >> k;

14     for (int i = 0; i < n; i ++ )

15          cin >> a[i];

16          

17     int idd = 0;     

18     for (int i = 0; i < n; i ++ )

19     {

20         int x = a[i];

21         b[idd ++ ] = x;

22         while (x > 0)

23         {

24             x >>= 1;

25             b[idd ++ ] = x;

26         }

27     }

28  

29     for (int i = 0; i < idd; i ++ )

30  {

31         int id = 0;

32         for (int j = 0; j < n; j ++ )

33         {

34             int x = a[j], cur = 0;

35             while (x > b[i])

36             {

37                 x >>= 1;

38                 cur ++ ;

39             }

40             if (x == b[i]) {

41                 c[id ++ ] = cur;

42             }

43 }

44         if (id >= k) {

45             int sum = 0;

46             sort(c, c + id);

47             for (int j = 0; j < k; j ++ )   sum += c[j];

48             ans = min(ans, sum);

49         }

50         memset(c,0,sizeof c);

51     }

52     cout << ans << endl;

53     return 0;

54 }

View Code

 1 #include 

 2 #include 

 3 #include 

 4 #include 

 5  

 6 using namespace std;

 7 const int MAXN = 1e6;

 8 const int _inf = 0x3f3f3f;

 9 int k, n, a[MAXN], b[MAXN], c[MAXN], ans = _inf;

10  

11 int main()

12 {

13     cin >> n >> k;

14     for (int i = 0; i < n; i ++ )

15          cin >> a[i];

16          

17     int idd = 0;     

18     for (int i = 0; i < n; i ++ )

19     {

20         int x = a[i];

21         b[idd ++ ] = x;

22         while (x > 0)

23         {

24             x >>= 1;

25             b[idd ++ ] = x;

26         }

27     }

28  

29     for (int i = 0; i < idd; i ++ )

30  {

31         int id = 0;

32         for (int j = 0; j < n; j ++ )

33         {

34             int x = a[j], cur = 0;

35             while (x > b[i])

36             {

37                 x >>= 1;

38                 cur ++ ;

39             }

40             if (x == b[i]) {

41                 c[id ++ ] = cur;

42             }

43 }

44         if (id >= k) {

45             int sum = 0;

46             sort(c, c + id);

47             for (int j = 0; j < k; j ++ )   sum += c[j];

48             ans = min(ans, sum);

49         }

50         memset(c,0,sizeof c);

51     }

52     cout << ans << endl;

53     return 0;

54 }

codeforces, div

WordPress database error: [Table 'yf99682.wp_s6mz6tyggq_comments' doesn't exist]
SELECT SQL_CALC_FOUND_ROWS wp_s6mz6tyggq_comments.comment_ID FROM wp_s6mz6tyggq_comments WHERE ( comment_approved = '1' ) AND comment_post_ID = 5656 ORDER BY wp_s6mz6tyggq_comments.comment_date_gmt ASC, wp_s6mz6tyggq_comments.comment_ID ASC

Leave a Comment Cancel reply