A-牛牛爱学习 #二分答案 #贪心

题目链接

题意

给定$n (\leq1e6) $本书，每本书知识值为a[i]。如果同一天连续读k本书，获得知识力为a[i]-k+1。看书不需按顺序，且一本书只能看一次(即某一天看过这本书后，以后都不能再看了)，一天之内不一定要将所有书全都看了。现要求最少多少天才能获得大于等于m点知识点，若无法获得则输出-1。

分析

假设最坏情况下，一天只看一本书，即需要n天看完，由此获得的知识力一定是最大的，但我们试探发现，如果在某一天看两本书，由此再累计一下知识力，有可能仍能够大于m，而此时天数为n-1。因而观察到答案的单调性，试着二分可能的天数。

如何确实试探的天数x能否满足题意？利用贪心思想，先将所有书降序排序，再将前x本书分摊到x天，比较下当前累计知识力是否大于等于m，如果不满足，再从书堆中选择x本书继续分摊…只要当前累计知识力大于等于m，即能说明x天满足题意，可继续往下二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;
int n, m;
int a[MAXN];
bool Judge(int dd){
    int k = 1, cnt = 1;
    ll sum = 0; //注意long long，被卡了qwq
    for (int i = 1; i <= n; i++){ //将1-dd天，对每天的第k本书排好
        if(a[i] - k + 1 <= 0)
            break; //注意，不能直接返回false，不一定要将所有书都看完！
        sum += (ll)(a[i] - k + 1); 
        if(i % dd == 0) 
            k++;
    }
    if(sum >= (ll)m) return true;
    else return false;
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n, greater<int>());
    int lo = 1, hi = n + 1;
    bool f = false;
    while(lo < hi){
        int mid = (lo + hi) >> 1;
        if(Judge(mid)){
            hi = mid;
            f = true;//说明之前存在一个mid使得条件满足
        }
        else
            lo = mid + 1;
    }
    printf("%d\n", f ? lo : -1);
}

C-牛牛种花 #离散化 #树状数组 #离线处理

题目链接

题意

给定n(≤1e5)n(\leq 1e5)朵花，需要在无限大矩阵中，将第i朵花种到(xi,yi)(10−9≤xi,yi,ai,bi≤109)(xi, yi)(10^{-9} \leq xi,yi,ai,bi \leq 10^9)位置上。然后有m(≤1e5)m(\leq 1e5)次询问，每次给定(ai, bi)，询问在x≤aix \leq ai &&y≤biy\leq bi下种了多少朵花。同一个地方可以种多朵花。

分析

借鉴了官方题解的思路，离散化思路值得学习。将给定的种花位置以及询问的种花位置进行离散化。

如何用树状数组维护数量？我们利用树状数组维护一个维度的信息（代码中维护的是y轴信息）。我们先将所有位置进行排序（先排x坐标，再排y坐标）。由于题目要求的是“≤”“\leq”，接下来利用循环（即x坐标逐渐递增，相当于时间线），每一次循环迭代即更新覆盖y轴的信息，其中的迭代既包含了种花插入，又包含查询。最后按询问编号，离线输出答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
const int MOD = 1e4 + 7;
struct Node{
    int x, y, id;
    bool operator < (const struct Node& b) const {
        if(x == b.x) return y < b.y;
        else return x < b.x;
    }
} a[MAXN];
int n, m, tree[MAXN], pos[MAXN], ans[MAXN];//树状数组维护花在y坐标下数量
int lowbit(int x){ return x & (-x); }
void addDot(int x){
    for(; x <= n + m; x += lowbit(x)) tree[x] ++;
} //注意，是n+m啊！！！
int findLine(int x){
    int ans = 0;
    for (; x > 0; x -= lowbit(x)) ans += tree[x];
    return ans;
}
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n + m; i++){
        scanf("%d%d", &a[i].x, &a[i].y);
        pos[i] = a[i].y;
        a[i].id = 0;
        if(i > n) a[i].id = i - n; //i>n时用id记录该位置坐标所属的问题编号
    }
    sort(a + 1, a + n + m + 1); //对所有坐标升序排序
    sort(pos + 1, pos + n + m + 1); //对所有坐标中的y坐标升序排序，用于去重离散化
    int len = unique(pos + 1, pos + n + m + 1) - pos - 1;
    for (int i = 1; i <= n + m; i++){
        int idx = lower_bound(pos + 1, pos + 1 + len, a[i].y) - pos; 
        if(a[i].id == 0)  addDot(idx); //id==0就种花
        else ans[a[i].id] = findLine(idx); //查询
    }
    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}

D-失忆药水 #二分图

题目链接

题意

图中，a存在一条有向边指向b，说明a知道b的秘密。初始情况下，每个人都知道n-1个人的秘密。一瓶失忆药水可将任意两点间存在的所有边去除掉。现要求最少要多少瓶药水，能使得图中不存在奇数长度的圈。

分析

前置芝士：二分图性质

由题意可知，二分图不存在长度为奇数的圈。于是我们可将n个顶点任意划分为两个集合，每个集合中的所有顶点之间不存在任何一条边相连，而不同集合的顶点存在边相连。

既然初始情况为完全图（共有n∗(n−1)/2n*(n-1)/2条无向边），二分图最多边的情况即为，一个集合中所有顶点与另一集合所有顶点都有边相连（即n/2∗(n−n/2)n/2*(n-n/2)条边）

1
2
3
4
5
6
7
8
9
10
11
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
ll n;
int main(){
    while(cin >> n){
        cout << 1ll * n * (n - 1) / 2 - 1ll * (n / 2) * (n - n / 2) << '\n';
    }
    return 0;
}

E-牛牛走迷宫 #广搜 #贪心

题目链接

题意

01迷宫中，0代表该位置可走，1表示存在障碍。现要从(1,1)起点走到终点(n,m)。若可以走到终点，优先走路径最短的，同时走字典序最小的路径（D表示向下，L表示向左，R表示向右，U表示向上）。现要你求出路径长度，并输出用字母表示方向的路径。

分析

使用宽搜即可，宽搜过程中第一个遇到终点的路径，其长度一定是最短的。行进时注意方向，显然决策方向时，应先考虑D方向，再依次考虑L方向，R方向，U方向。

参考了官方题解，每个顶点结构体中都存有一字符串，实时记录到达该顶点的方向顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
using namespace std;
typedef long long ll;
const int MAXN = 505;
int n, m, G[MAXN][MAXN];
int di[5] = { 0, 1, 0, 0, -1};
int dj[5] = { 0, 0, -1, 1, 0};
typedef struct Node {
    int cx, cy; string str;
} Node;
char str[MAXN][MAXN];
bool vis[MAXN][MAXN];
void bfs(int cx, int cy) {
    queue<Node> myque;
    vis[1][1] = true;
    myque.push({ cx, cy, ""});
    while (!myque.empty()) {
        Node cur = myque.front();
        myque.pop();
        if (cur.cx == n && cur.cy == m) {
            cout << cur.str.length() << '\n';
            cout << cur.str << '\n';
            return;
        } //终点(边界条件)要放在外面判断，不要在决策方向时才判断，否则会发生莫名其妙的超时
        for (int t = 1; t <= 4; t++) { 
            Node v = cur;
            v.cx += di[t]; v.cy += dj[t];
            if (v.cx <= 0 || v.cx > n || v.cy <= 0 || v.cy > m || G[v.cx][v.cy] || vis[v.cx][v.cy]) continue;
            if (t == 1)      v.str.append("D");
            else if (t == 2) v.str.append("L");
            else if (t == 3) v.str.append("R");
            else if (t == 4) v.str.append("U");
            vis[v.cx][v.cy] = true;
            myque.push(v);
        }
    }
    printf("-1\n");
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%s", str[i]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            G[i][j] = str[i][j - 1] - '0';
    bfs(1, 1);
    return 0;
}

G-牛牛爱几何

题意

给出正方形边长，计算阴影面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ldd;
const int MAXN = 1e5;
const double PI = acos(-1);
int n, q;
int main(){
    while ((scanf("%d", &n)) != EOF){
        double ans = 0.25 * 2 * PI * n *  n  - 1.0 * n * n; //n*n前面一定要加1.0，否则出锅！
        printf("%.6f\n", ans);
    }
    return 0;
}

H-保卫家园 #STL #区间重复覆盖

题目链接

题意

已知法兰不死队最多能有k人。有n个人想加入，他们每人都有一个期望入伍时间s和退役时间t。入伍时间表示这个人如果要入伍只能在s时刻入伍。退役时间代表这个人可以在t时刻后退伍（退伍时间要严格大于t ）。队伍必须一直保持达到最大编制的状态，即队伍达到最大编制时候，队伍里有人可以退役的话，若无人接替这个人的位置就不能退役。问最少有多少人没有进入法兰不死队的经历。 同一时刻，允许多个人一起入伍或者退伍，该人是否入伍是你来决定的，即就算没达到最多编制人数k，到了某人的入伍时间，你可以选择不让他入伍。

分析

摘至官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
const int MAXN = 1e6+5;
struct Node{
    int lo, hi;
    bool operator < (const Node& b){
        if(lo == b.lo) return hi < b.hi;
        else return lo < b.lo;
    }
} a[MAXN];
multiset<int> myset;
int main(){
    int n, k; scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].lo, &a[i].hi);
    sort(a+1, a+1+n);
    int ans = 0;
    for (int i = 1; i <= n; i++){ //枚举所有以i为起点的线段
        while(!myset.empty() && *myset.begin() < a[i].lo) //先将在集合中的终点<当前点i起点都弹出集合
            myset.erase(myset.begin());
        myset.insert(a[i].hi); //存入该区间的终点
        while(myset.size() > k){
            myset.erase(--myset.end()); //弹出终点久的，也许能够在未来填上更多的区间
            ans++; //说明当前队列中终点久的区间不适合
        }
    }
    printf("%d\n", ans);
}

I-恶魔果实 #深搜

题目链接

题意

每个恶魔果实给予改变数字的能力，可以把某个数字a变成某个数字b，现有一个数字x，现吃完这n个恶魔果实后，求出可由数字x变成的数字种类数量，需要取模1e4+71e4+7。每个恶魔果实的能力可重复使用，也可不用，存在相同能力的恶魔果实。

分析

从每一种数字出发进行深搜，最后根据给定数字进行统计，具体见代码注释吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;
const int MOD = 1e4 + 7;
int n, m, x;
bool trans[11][11], vis[11];
ll sum[11];
void dfs(int cur, int fa){
    vis[cur] = true;
    sum[fa]++; //统计由fa变成的数字种类数量
    for(int i = 0; i <= 9; i++)
        if(trans[cur][i] && !vis[i])
            dfs(i, fa);
}
int main(){
    scanf("%d%d", &x, &m);
    for (int i = 1, u, v; i <= m; i++){
        scanf("%d%d", &u, &v);
        trans[u][v] = true; //说明可以转化
    }
    for (int i = 0; i <= 9; i++){ //每一种数字出发
        for (int j = 0; j <= 9; j++) vis[j] = false;
        dfs(i, i); 
    }
    ll ans = 1;
    while(x != 0){
        int cur = x % 10; //分解数字x的每一数位
        ans = (ans * sum[cur]) % MOD;
        x /= 10;
    }
    printf("%lld\n", ans);
}

J-牛牛喜欢字符串 #模拟 #贪心

题目链接

题意

现有一长度nn的字符串(仅包含小写字母)，现将该字符串，每隔k个就分出来一个子串，比如[1,k][1,k]为第一个子串，[k+1,2k][k+1,2k]为第二个、[2k+1,3k][2k+1,3k]为第三个…(保证nn%k==0) 。现想要把这些子串都变成一样（即每一子串均相同）。可选任意一个子串的任意一个字符进行更改，求出最少要进行的操作。

分析

与LeetCode 1566题有点类似。分段统计，最后累加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <string>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 1e6 + 5;
int n, q, k;
string str;
int vis[MAXN][30];
int main(){
    scanf("%d%d", &n, &k);
    cin >> str;
    int sum = 0, len = n / k;
    for(int i = 0; i < k; i++){ //枚举第一个子串中所有字符
        int mymax = -1;
        for(int j = i; j < n; j += k){ //周期前进，到达其他子串的对应位置
            char curchar = str[j];
            int cur = str[j] - 'a' + 1;
            vis[i][cur]++;
            mymax = max(mymax, vis[i][cur]);
        } //统计对应位置下出现频率最高的字符，即为不需要修改的字符
        sum += (len - mymax);
    }
    printf("%d\n", sum);
    return 0;
}