Codeforces Round #667 (Div. 3) A - D题题解

Codeforces Round #667 (Div. 3) A - D

Problem A - Yet Another Two Integers Problem

https://codeforces.com/contest/1409/problem/A

Example

input

6
5 5
13 42
18 4
1337 420
123456789 1000000000
100500 9000

output

0
3
2
92
87654322
9150

题意：

给定两个数 ，问题最少多少次（每次能加 能使 变为

思路：

水题，直接看代码更快点

#include<bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int N = 1e5 + 100;
ll n, m, a[N], i, j;
void solve() {
   cin >> n >> m;
   ll cnt = abs(n - m) / 10;
   if (abs(n - m) % 10 != 0)cnt++;
   cout << cnt << endl;
}
int main() {
   //freopen("in.txt", "r", stdin);
   ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
   int t; cin >> t;
   while (t--) solve();
}

Problem B - Minimum Product

https://codeforces.com/contest/1409/problem/B

Example

input

7
10 10 8 5 3
12 8 8 7 2
12343 43 4543 39 123212
1000000000 1000000000 1 1 1
1000000000 1000000000 1 1 1000000000
10 11 2 1 5
10 11 9 1 10

output

70
77
177177
999999999000000000
999999999
55
10

题意：

给定 求，在 次 或 使得 $ a * b$ 最小。

思路：

先求出 %2C%20max(b%20-%20n%2C%20y))#card=math&code=mins%20%3D%20min%28max%28a%20-%20n%2C%20x%29%2C%20max%28b%20-%20n%2C%20y%29%29) 。所以目标值一定是 %20-%20mins)#card=math&code=mins%20%2A%20%28max%28a%20%2B%20b%20-%20n%2C%20x%20%2B%20y%29%20-%20mins%29)。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve() {
    ll a, b, x, y, n;
    cin >> a >> b >> x >> y >> n;
    ll mins = min(max(a - n, x), max(b - n, y));
    cout << mins * (max(a + b - n, x + y) - mins) << endl;
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--) solve();
}

Problem C - Yet Another Array Restoration

https://codeforces.com/contest/1409/problem/C

Example

input

5
2 1 49
5 20 50
6 20 50
5 3 8
9 13 22

output

1 49 
20 40 30 50 10
26 32 20 38 44 50 
8 23 18 13 3 
1 10 13 4 19 22 25 16 7

就是从后往前预处理出来一个最大值就ok了，详情请看代码

#include<bits/stdc++.h>
using namespace std;
int t,n,x,y; 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>x>>y;
        int dist =y-x;//获取2点之间的距离 
        int idx;
        for(idx=n-1;;idx--)//从后往前预处理最大值，如果等于n 就等于5个1是不行的
        //就是相当于把y到x的区间分成最长距离的多少份 
        {
            if(dist%idx==0)break;
        }
        dist/=idx;//获取最大值 
        for(int i=0;i<n-1&&y-dist>0;i++)//找到第一个元素 
        {
            y-=dist;
        }
        for(int i=0;i<n;i++)
        {
            cout<<y<<' ';
            y+=dist;
        }
        cout<<endl;
    }
    return 0;
 }

Problem D - Decrease the Sum of Digits (思维问题+构造)

https://codeforces.com/contest/1409/problem/D

Example

input

5
2 1
1 1
500 4
217871987498122 10
100000000000000001 1

output

8
0
500
2128012501878
899999999999999999

题意：

给定一个大数 和 ,求最小移动次数#card=math&code=%28n%20%3D%20n%20-%201%29) 以使 小于或等于 。

理解完题意就很简单了。只需要去处理各位的情况的即可，关键语句在

while (gsm(n) > s) {
    ll cur = n / cn; cur %= 10;
    ans += (10 - cur) * cn;
    n += (10 - cur) * cn;
    cn *= 10;
}//仔细理解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gsm(ll n) {
    ll re = 0;
    while (n) {
        re += n % 10; n /= 10;
    }
    return re;
}
int main() {
    int t; cin >> t;
    while (t--) {
        ll n, s;
        cin >> n >> s;
        ll cn = 1, ans = 0;
        while (gsm(n) > s) {
            ll cur = n / cn; cur %= 10;
            ans += (10 - cur) * cn;
            n += (10 - cur) * cn;
            cn *= 10;
        }
        cout << ans << "\n";
    }
}