题解 | 牛客小白月赛43题解

解法：暴力即可

#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

int st[N];

bool check(int x) {
    vector<int> v;
    v.push_back(1);
    for (int i = 1; i * i <= x; i ++ ) {
        if (x % i == 0) {
            v.push_back(i);
            if (x / i == i) continue;
            v.push_back(x / i);
        }
    }
    sort(v.begin(), v.end());
    int m = (int)(v.size() - 1);
    if (v[m] % v[(m + 1) / 2] != 0) return false;
    return true;
}

void init() {
    int n = 1000;
    for (int i = 1; i <= n; i ++ ) {
        if (check(i)) st[i] ++;
    }
    for (int i = 1; i <= n; i ++ ) st[i] += st[i - 1];
}

inline void solve() {
    int n; cin >> n;
    cout << st[n] << endl;
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
    init();
    int T; cin >> T;
    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}

牛牛变魔术

解法：思维

容易知道当a，b有一个和target相同的时候就是0

否则就看target的奇偶性，由于每次操作都要乘2，所以target必定为偶数

最后看，如果要得到target，那么就要通过一次分配得到 $\frac{target}{2}$ ，所以只要看a + b够不够得到这个数字即可，如果不够就等到够为止

#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

inline void solve() {
    LL a, b, tar;
    cin >> a >> b >> tar;
    if (a == tar || b == tar) cout << 0 << endl;
    else {
        if (tar & 1) {cout << -1 << endl; return ;}
        if (a + b >= tar / 2) cout << 1 << endl;
        else {
            int cnt = 0;
            while (a + b < tar / 2) {
                cnt ++;
                a <<= 1;
                b <<= 1;
            }
            cout << cnt + 1 << endl;
        }
    }
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
    int T; cin >> T;
    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}

木棍游戏

解法：搜索

首先容易得出，每个木棍都有四个去处：

1、并到第一条边

2、并到第二条边

3、并到第三条边

4、不并到任何一条边

模拟四进制搜索即可，复杂度 $O (4^{n})$

最后得到的边由秦九韶公式得出面积，求出所有可能性后得一个最大值

#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

inline void solve() {
    function<double(int, int, int)> get_arr = [&](int a, int b, int c) {
        double p = (double)(a + b + c) / 2.0;
        double s = sqrt(p * (p - a) * (p - b) * (p - c));
        return s;
    };
    int n; cin >> n;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i ++ ) cin >> v[i];

    double res = -1;
    function<void(int, int, int, int)> dfs = [&](int u, int a, int b, int c) {
        if (u == n + 1) {
            if (a == 0 || b == 0 || c == 0) return ;
            if (a + b <= c || a + c <= b || b + c <= a) return ;
            res = max(res, get_arr(a, b, c));
            return ;
        }
        for (int i = 1; i <= 4; i ++ ) {
            if (i == 1) dfs(u + 1, a + v[u], b, c);
            if (i == 2) dfs(u + 1, a, b + v[u], c);
            if (i == 3) dfs(u + 1, a, b, c + v[u]);
            if (i == 4) dfs(u + 1, a, b, c);
        }
    };

    dfs(1, 0, 0, 0);
    if (res == -1) cout << -1 << endl;
    else cout << res << endl;
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
//    int T; cin >> T;
//    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}

有趣的区间

解法：计数

看题意，要一个连续区间的数或起来是奇数，那么区间内只要有一个奇数就够了

我们可以把区间内所有奇数的位置存下来，然后遍历计数即可

#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

inline void solve() {
    int n; cin >> n;
    vector<int> a(n + 1), pos;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        if (a[i] & 1) pos.push_back(i);
    }
    LL res = 0, last = 1;
    for (auto i : pos) {
        res += 1ll * (i - last + 1) * (n - i + 1);
        last = i + 1;
    }
    cout << res << endl;
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
//    int T; cin >> T;
//    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}

满意的集合

解法：DP

状态表达： $d p [i] [j]$ 表示用前i类数，得到的数的余数为j的方案数

状态转移：

$d p [i] [j] = d p [i] [j] + d p [i - 1] [j] * (c n t [i] + 3) / 3$

$d p [i] [j] = d p [i] [j] + d p [i - 1] [j - i] * (c n t [i] + 2) / 3$

$d p [i] [j] = d p [i] [j] + d p [i - 1] [j - 2 * i] * (c n t [i] + 1) / 3$

枚举当前的数是选0,3,5,9...个还是1, 4, 7...个还是2,5,8...个

#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

LL dp[11][4];

inline void solve() {
    vector<int> a(11);
    for (int i = 1; i <= 9; i ++ ) cin >> a[i];
    dp[0][0] = 1;
    for (int i = 1; i <= 9; i ++ ) {
        for (int j = 0; j < 3; j ++ ) {
            int n1 = ((j - i) % 3 + 3) % 3;
            int n2 = ((j - 2 * i) % 3 + 3) % 3;
            dp[i][j] = (dp[i][j] + dp[i - 1][j] * ((a[i] + 3) / 3) % MOD) % MOD;
            dp[i][j] = (dp[i][j] + dp[i - 1][n1] * ((a[i] + 2) / 3) % MOD) % MOD;
            dp[i][j] = (dp[i][j] + dp[i - 1][n2] * ((a[i] + 1) / 3) % MOD) % MOD;
        }
    }
    cout << dp[9][0] << endl;
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
//    int T; cin >> T;
//    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}

全体集合

解法：思维，染色

先说结论：有奇数环的时候，必定YES，有偶数环的时候染色，要求全部有人的点为同色即可

简单证明下，我们容易知道YES的条件是有人在的点中，两两之间存在一条长度为偶数的路径

那么如果图中有奇数环的话，我们假设有两点间的路径有奇数的，那么我们可以通过绕一圈奇数环，使二者的路径奇偶变换，如果不存在奇数环则无法变换，只能老实染色判断

#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 2e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

vector<int> g[N];

inline void solve() {
    int n, m, k; cin >> n >> m >> k;
    while (m -- ) {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> v(k + 1), c(n + 1);
    for (int i = 1; i <= k; i ++ ) cin >> v[i];
    if (k == 1) {cout << "YES" << endl; return;}
    else {
        bool is = false;
        function<void(int, int, int)> dfs = [&](int u, int col, int last) {
            c[u] = col;
            for (int v : g[u]) {
                if (v == last) continue;
                if (c[v]) {
                    if (c[v] == c[u]) is = true;
                } else dfs(v, 3 - col, u);
            }
        };
        dfs(v[1], 1, -1);
        if (is) cout << "YES" << endl;
        else {
            for (int i = 2; i <= k; i ++ ) {
                if (c[v[i]] != c[v[1]]) {cout << "NO" << endl; return ;}
            }
            cout << "YES" << endl;
        }
    }
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
//    int T; cin >> T;
//    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}