题目链接

A. Div. 7

题意：
给定一个数n， 操作可以每次修改一位数的值，用最小操作数使得可以被7整除，并求出这个数
思路：
注意到n大于等于10， 整除7个一循环，枚举最后一位即可
代码：

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 1e5 + 10;
int n;
void solve(){
    cin >> n;
    if (n % 7 == 0){
        cout << n << endl;
        return;
    }
    int x = n / 10;
    for (int i = 0; i <= 9; i ++){
        if ((x * 10 + i) % 7 == 0){
            cout << x * 10 + i << endl;
            return;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T --){
        solve();
    }
    return 0;
}

B. Minority

题意：
给定 1 个 01 串，一个子串的价值是子串中较少的字符的个数（若 0 和 1 的个数相同则价值为 0），输出所有子串的价值的最大值。
思路：
贪心的想，当0和1个数不相同时，所选择的子串长度越大价值越大，所以循环一遍当个数不同时记录答案即可。
代码：

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 1e5 + 10;
void solve(){
    string s;
    cin >> s;
    int cnt0 = 0, cnt1 = 0;
    int ans = 0;
    for (int i = 0; i < s.size(); i ++){
        if (s[i] == '0') cnt0 ++;
        else cnt1 ++;
        if (cnt1 != cnt0){
            ans = max(ans, min(cnt1, cnt0));
        }
    }
    cout << ans << endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T --){
        solve();
    }
    return 0;
}

C. Kill the Monster

题意：
一个游戏中，若我方角色的生命值为 hC，攻击力为 dC；对手角色的生命值为 hM，攻击力为 dM，双方进行一场战斗时，过程如下：

我方攻击对方，对方生命值减少 dC；
对方攻击我方，我方生命值减少 dM；
我方攻击对方，对方生命值减少 dC；
对方攻击我方，我方生命值减少 dM；
……
重复上述过程直到有一方生命值为 0 或负数，那一方就输了。
现在我方角色生命值为 hC，攻击力为 dC；对手角色的生命值为 hM，攻击力为 dM。且我方角色有 k 枚金币，每枚金币能永久提升 w 点战斗力或 a 点生命值。求我方能否打败对方。
思路：
胜利条件 $\lceil \frac{hc}{hm}\rceil ⩾\lceil \frac{hm}{dc}\rceil$
暴力枚举k的用途，x点用于战斗力，k - x 用于生命值
代码：

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 1e5 + 10;
int hc, dc, hm, dm, k, w, a;
void solve(){
    cin >> hc >> dc >> hm >> dm >> k >> w >> a;
    bool ok = false;
    hc --;
    hm --;
    for (int i = 0; i <= k; i ++){
        int nowhc = hc + i * a;
        int nowdc = dc + (k - i) * w;
        if (nowhc / dm >= hm / nowdc){
            ok = true;
            break;
        }
    }
    if (ok) cout << "YES" << endl;
    else cout << "NO" << endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T --){
        solve();
    }
    return 0;
}

D. Make Them Equal

题意：
数组a有n个元素，初始值为1。每次操作可以任选一个正整数x，使a[i]=a[i]+a[i]/x，当a[i]与b[i]相等时，获得价值c[i]。最多执行k次操作，求获得最大价值。
思路：
注意到b[i] 的大小并不大，我们可以提前预处理出来每个数所需要的操作步数，然后01背包。
刚开始以为操作是贪心进行wa了次，其实直接暴力预处理就行。
代码：

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 1e6 + 10;
int v[N];
int n, k, b[N], w[N];
int dp[N];
void init(){
    for (int i = 1; i <= 1000; i ++) v[i] = INF;
    v[1] = 0; v[2] = 1;
    for (int i = 1; i <= 1000; i ++){
        for (int j = 1; j <= i; j ++){
            if (i + i / j <= 1000)
                v[i + i / j] = min(v[i + i / j], v[i] + 1);
        }
    }
}
void solve(){
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i ++) scanf("%d", &b[i]);
    for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);
    for (int i = 0; i <= k; i ++) dp[i] = 0;
 
    for (int i = 1; i <= n; i ++){
        for (int j = k; j >= v[b[i]]; j --){
            dp[j] = max(dp[j], dp[j - v[b[i]]] + w[i]);
        }
    }
    printf("%d\n", dp[k]);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    scanf("%d", &T);
    init();
    while (T --){
        solve();
    }
    return 0;
}