牛客小白月赛26

个人博客：http://www.kindkidll.com/index.php/archives/153

A-牛牛爱学习

知识点：二分

答案具有单调性，二分所需要的天数，将书按知识力降序排列求和进行判断。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
LL m, a[MAXN];
bool check(int x) {
    LL sum = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] - i / x < 0) return false;
        sum += a[i] - i / x;
        if(sum >= m) return true;
    }
    return false;
}
int erfen() {
    int l = 1, r = n;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(check(mid)) r = mid - 1;
        else l = mid + 1;
    }
    if(l == n + 1) return -1;
    return l;
}
int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n, greater<int>());
    printf("%d\n", erfen());
    return 0;
}

B-牛牛爱数学

知识点：恒等变化

将式子变化得，则。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
LL a, b, c;
int main() {
    cin >> T;
    while(T--) {
        cin >> a >> b >> c;
        if(b * c % a == 0)cout << b*c / a << endl;
        else cout << -1 << endl;
    }
    return 0;
}

C-牛牛种花

知识点：离线、离散化、树状数组

把种花和询问离线排序，以坐标为第一关键字、坐标为第二关键字、是否是询问为第三关键字。排序之后对于任意一次询问，在其前方的坐标都比其小，只需要找出坐标也小的，这时采用树状数组维护即可。坐标范围较大需要离散化。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m;
int t[MAXN], tot;// 离散化
int tree[MAXN];// 树状数组
int ans[MAXN];// 答案
struct flower {
    int x, y;
    int isInquiry;
    int id;
} a[MAXN];// 离线
bool cmp(flower a, flower b) {
    if(a.x != b.x) return a.x < b.x;
    if(a.y != b.y) return a.y < b.y;
    return a.isInquiry < b.isInquiry;
}
int get_hash(int x) {
    return lower_bound(t, t + tot, x) - t + 1;
}
int lowbit(int x) {
    return x & -x;
}
void update(int id) {
    while(id < MAXN) {
        tree[id]++;
        id += lowbit(id);
    }
}
int quiry(int id) {
    int ret = 0;
    while(id) {
        ret += tree[id];
        id -= lowbit(id);
    }
    return ret;
}
void init() {
    tot = 0;
    memset(tree, 0, sizeof(tree));
    memset(a, 0, sizeof(a));
}
int main() {
    init();
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
        t[tot++] = a[i].y;
    }
    for(int i = 0; i < m; i++) {
        scanf("%d%d", &a[i + n].x, &a[i + n].y);
        a[i + n].isInquiry = 1;
        a[i + n].id = i;
        t[tot++] = a[i + n].y;
    }
    sort(t, t + tot);
    tot = unique(t, t + tot) - t;
    sort(a, a + n + m, cmp);
    for(int i = 0; i < n + m; i++) {
        if(a[i].isInquiry) ans[a[i].id] = quiry(get_hash(a[i].y));
        else update(get_hash(a[i].y));
    }
    for(int i = 0; i < m; i++) printf("%d\n", ans[i]);
    return 0;
}

D-失忆药水

知识点：图论

个点最多可以连多少条边且不存在大于3的奇数阶完全子图。高阶完全子图中一定包含3阶子图，即图中不含3阶完全子图，二分图满足条件。要使边数最多则点数应均分，完全图边数为，二分图边数为。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

LL n;
int main() {
    while(cin >> n) {
        cout << n*(n - 1) / 2 - n / 2 * (n - n / 2) << endl;
    }
    return 0;
}

E-牛牛走迷宫

知识点：搜索

要求路径最短且字典序最小，采用且按下左右上的优先级走。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m;
char s[517][517];
int bex[517][517], bey[517][517];
char t[517][517];
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, -1, 1, 0};
char p[4] = {'D', 'L', 'R', 'U'};
char ans[MAXN];
struct node {
    int x, y, step;
} now, ne;
bool check(node a) {
    if(a.x < 0 || a.x >= n) return false;
    if(a.y < 0 || a.y >= m) return false;
    if(s[a.x][a.y] == '1') return false;
    return true;
}
int bfs() {
    queue<node> q;
    q.push({0, 0, 0});
    s[0][0] = '1';
    while(!q.empty()) {
        now = q.front();
        q.pop();
        if(now.x == n - 1 && now.y == m - 1) {
            printf("%d\n", now.step);
            return  0;
        }
        for(int i = 0; i < 4; i++) {
            ne.x = now.x + dx[i];
            ne.y = now.y + dy[i];
            ne.step = now.step + 1;
            if(check(ne)) {
                q.push(ne);
                s[ne.x][ne.y] = '1';
                bex[ne.x][ne.y] = now.x;
                bey[ne.x][ne.y] = now.y;
                t[ne.x][ne.y] = p[i];
            }
        }
    }
    return -1;
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%s", s[i]);
    int tt = bfs();
    if(tt == -1) puts("-1");
    else {
        int tot = 0, x = n - 1, y = m - 1;
        while(x || y) {
            ans[tot++] = t[x][y];
            int t = bex[x][y];
            y = bey[x][y];
            x = t;
        }
        for(int i = tot - 1; i >= 0; i--) putchar(ans[i]);
        putchar(10);
    }
    return 0;
}

F-牛牛的序列

知识点：数论

区间内所有数的因子和的奇偶性取决于区间内有多少个因子和为奇数的数，根据区间减法将问题转换为求前个数中因子和为奇数的数的个数。

关于因子和直接放结论，详情见博客因子个数以及因子和。

要为奇数，则每个括号里的和都是奇数，所以为偶数或者。
假设不存因子2，则任意为偶数，所以是一个奇数平方数。同时乘以二次幂，的因子和仍为奇数。
即若的因子和为奇数，则是一个奇数平方数乘以二次幂，问题转换为求奇数平方数的二次幂倍数的个数。
奇数平方数乘以二的偶次幂是一个平方数，个数为。
奇数平方数乘以二的奇次幂均比相邻的偶次幂小一倍，个数为。

注：出题人题解评论区提到了库函数sqrt()的精度问题。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int t;
LL a, b;
LL sqr(LL n) {
    LL ret = sqrt(n) + 1;
    while(ret * ret > n) ret--;
    return ret;
}
int main() {
    cin >> t;
    while(t--) {
        cin >> a >> b;
        if(a > b) swap(a, b);
        LL ans = sqr(b) + sqr(b / 2) - sqr(a - 1) - sqr((a - 1) / 2);
        cout << ans % 2 << endl;
    }
    return 0;
}

G-牛牛爱几何

知识点：几何

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;

double r;
int main() {
    cin >> r;
    r /= 2;
    printf("%.6f\n", r * r * (pi / 4 - 0.5) * 8);
    return 0;
}

H-保卫家园

知识点：贪心

维护一个集合保存当前选取区间的终点，对于每个时刻弹出集合中终点小于当前时刻的区间，然后添加新的区间，若集合大小大于则弹出终点最大的区间。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, k;
int l, r;
multiset<int> s;
vector<int> t[MAXN];
int main() {
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &l, &r);
        t[l].push_back(r);
    }

    int cnt = 0;
    for(int i = 1; i <= 1000000; i++) {
        while(!s.empty() && *s.begin() < i) s.erase(s.begin());
        for(auto it : t[i]) {
            s.insert(it);
            if(s.size() > k) {
                cnt++;
                s.erase(--s.end());
            }
        }
    }
    printf("%d\n", cnt);
    return 0;
}

I-恶魔果实

知识点：搜索

先搜索每个数字有多少种变化，再根据乘法原理对按位计算结果。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int x, n;
int cnt[17];
bool to[17][17];
bool f[17];
void dfs(int id, int x) {
    if(f[x]) return;
    f[x] = true;
    cnt[id]++;
    for(int i = 0; i < 10; i++)
        if(to[x][i]) dfs(id, i);
}
int main() {
    scanf("%d%d", &x, &n);
    while(n--) {
        int a, b;
        scanf("%d%d", &a, &b);
        to[a][b] = true;
    }
    for(int i = 0; i < 10; i++) {
        memset(f, false, sizeof(f));
        dfs(i, i);
    }

    LL sum = 1;
    while(x) {
        sum *= cnt[x % 10];
        x /= 10;
    }
    printf("%lld\n", sum % 10007);
    return 0;
}

J-牛牛喜欢字符串

知识点：计数

统计拆分后的子串中出现次数最多的字母，改变其他字母即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, k;
char s[MAXN];
int cnt[MAXN][30], num[MAXN];
int main() {
    scanf("%d%d", &n, &k);
    scanf("%s", s);
    for(int i = 0; i < n; i++) {
        cnt[i % k][s[i] - 'a']++;
        num[i % k] = max(num[i % k], cnt[i % k][s[i] - 'a']);
    }
    int sum = 0;
    for(int i = 0; i < k; i++) {
        sum += n / k - num[i];
    }
    printf("%d\n", sum);
    return 0;
}