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
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)
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
< 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; ia[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; jc[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
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 }
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 }