Codeforces Round #582 (Div. 3)

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


A:

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

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

B:

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)

Share a 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

C:

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

share picture

< 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…)

share picture

 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

 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 }

Leave a Comment

Your email address will not be published.