玖的数学&算法录
0%

2024牛客寒假算法训练营1

发表于 更新于
本文字数： 4.3k 阅读时长 ≈ 4 分钟

个人难度顺序：AMGECLBFIHDKJ

A.DFS搜索

题意：

给你一个字符串s,问字符串s中是否含有DFS子序列与dfs子序列。

输出两个数字：第一个数字表示是否有DFS子序列，第二个数字表示是否有dfs子序列，1表示有，0表示没有。

数据范围

$$1\leq T\leq100$$

$$1 \leq n \leq 50$$

题解：模拟

按题意。

代码：
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
void JiuCherish() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    std::string t1 = "DFS";
    std::string t2 = "dfs";
    int idx1 = 0,idx2 = 0;
    for(int i=0;i<n;i++) {
        if(s[i] == t1[idx1]) {
            idx1 += 1;
        }
        if(s[i] == t2[idx2]) {
            idx2 += 1;
        }
    }
    if(idx1 == 3) {
        std::cout << 1 << ' ';
    } else {
        std::cout << 0 << ' ';
    }
    if(idx2 == 3) {
        std::cout << 1 << endl;
    } else {
        std::cout << 0 << endl;
    }
}

B.关鸡

题意：

如图所示，在一条宽为2、长为2 * 10 ^ 9 + 1的管道中，有一只鸡和若干着火点，鸡可以上下左右移动一格、不能出管道上下边界、不能进入着火地点。

鸡初始在 (1,0) 处，现在给出若干个着火点的坐标，请求出为了不让鸡逃出管道（即到达管道最左端或最右端），最少需要添加多少个着火点。

数据范围

$$1\leq T\leq 10^4$$

$$0 \leq n \leq 10^5$$

$$1 \leq r \leq 2, -10^9 \leq c \leq 10 ^ 9$$

$$保证 \sum n \leq 10^5$$

题解：模拟

首先需要研究第一行是否有2个着火点使得鸡不能在第一层跑出来。

其次需要研究第二行是否有2个着火点使得鸡不能在第二层跑出来。

再者需要研究左边的两个着火点是否相邻或者对角相连 和 右边的两个着火点是否相邻或者对角相连。

特别的：需要判断（1，0）这个点旁边是否存在着火点，如果有的话直接在（1，0）这个点围起来即可。

代码：
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
int dy[6]={-1,-1,-1,1,1,1},dx[6]={-1,0,1,1,0,-1};

void JiuCherish(){
	std::cin >> n;
    std::set<PII>S,S1,S2;
    for(int i=1;i<=n;i++) 
    {
        int x,y;
		std::cin >> y >> x;
        S.insert({x,y});
        if(x <= 0) S1.insert({x,y});
        if(x >= 0) S2.insert({x,y});
    }
    int ans = INF;
    int t = 0;
    if(!S.count({-1,1})) t++;
    if(!S.count({0,2})) t++;
    if(!S.count({1,1})) t++;
    ans = std::min(ans,t);
    t = 0;
    if(S1.size())
    {
        bool flag = false;
        for(auto &u : S1)
        {
            int x = u.fi,y = u.se;
            if(x == 0) continue;
            for(int i=0;i<6;i++)
                if(S.count({x + dx[i],y + dy[i]}))
                	flag = true;
        }
        if(!flag) t += 1;
    }
    else t += 2;
    if(S2.size())
    {
        bool flag = false;
        for(auto &u:S2)
        {
            int x = u.fi,y = u.se;
            if(x == 0) continue;
            for(int i=0;i<6;i++)
                if(S.count({x + dx[i],y + dy[i]}))
                	flag=true;
        }
        if(!flag) t += 1;
    }
    else t += 2;
    ans = std::min(ans,t);
    std::cout << ans << endl;
}

C.按闹分配

题意：

办事大厅目前有n个人和一个办事窗口，每个人都要在这个窗口办事，第iii个人办事所需时间为ti。

时刻0所有人都进入办事大厅，第i个人的不满意度D_i​定义为他的事情办完的那个时刻。定义所有人的总不满意度S=Σi=1^n Di

办事处工作人员会合理安排办事顺序，使得总不满意度最小，记为Smin。

现在，很急的鸡来办事了，鸡可以在任意时刻要求工作人员放下手头的事情，立刻来处理鸡的事情，鸡的事情需要t_c​时间处理完成。假设鸡插队后其余n人的总不满意度最小值变为S_c，若Sc−Smin≤M，则工作人员将允许鸡的插队，否则工作人员将拒绝。M是工作人员的容忍限度。

现在，请你回答Q组询问，即当工作人员的容忍限度为M时，鸡最早能在哪个时刻办完事。

数据范围

$$1\leq n,Q\leq 10^5, 1\leq t_c \leq 10^9$$

$$1 \leq t_i \leq 10^6$$

$$0 \leq M \leq 10^{18}$$

题解：前缀和

插队后，想要满足
$$S_c - S_{min} \leq M$$

实际上就是满足

$$(n - pos) * t_c \leq M$$

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
void JiuCherish(){
   std::cin >> n >> Q >> tc;
	for(int i=1;i<=n;i++) std::cin >> t[i];
	std::sort(t+1,t+n+1);
	for(int i=1;i<=n;i++) sum[i] = sum[i - 1] + t[i];
    while(Q--)
	{
		i64 x;
		std::cin >> x;
		int pos = std::min(x / tc,(i64) n);
      std::cout << tc + sum[n - pos] << endl;
	}
}

D.数组成鸡

E. 本题又主要考察了贪心

F 鸡数题！

G.why买外卖

题意：

有一个外卖程序有若干种满减优惠：第 i 个优惠是满ai减bi元，多个满减优惠可以叠加。

满减的具体结算流程是：假设鸡购买的食物原价共为x元，则所有满足x >= ai的满减优惠都可以一起同时被使用，优惠后价格记为 y，则鸡只要支付 y元就可以了（若y <= 0则不需要支付）。

数据范围

$$1\leq T\leq 10^4$$

$$1 \leq n \leq 10^5,1 \leq m \leq 10^9$$

$$1 \leq a_i,b_i \leq 10 ^ 9$$

$$保证 \sum n \leq 10^5$$

题解：模拟，排序

从小到大模拟即可。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
std::pair<int,int> a[MAXN];
void JiuCherish() {
    int n,m;
    std::cin >> n >> m;
    for(int i=1;i<=n;i++) {
        std::cin >> a[i].fi >> a[i].se;
    }
    std::sort(a + 1,a + n + 1);
    int mx = m,now = 0;
    for(int i=1;i<=n;i++) {
        if(a[i].fi - a[i].se - now <= m) {
            now += a[i].se;
            mx = std::max(mx,m + now);
        } else {
            now += a[i].se;
        }
    }
    std::cout << mx << endl;
}

H. 01背包，但是bit

I.It’s bertrand paradox. Again!

J.又鸟之亦心

K.牛镇公务员考试

L.要有光

题意：

算面积最大值

数据范围

$$1\leq T\leq 10^4$$

$$1 \leq c,d,h,w \leq 10^4$$

题解：数学

求梯形面积

代码：
1
2
3
4
5
void JiuCherish(){
    int c,d,h,w;
    std::cin >> c >> d >> h >> w;
    std::cout << 3 * w * c << endl;
}

M. 牛客老粉才知道的秘密

题意：

对于n道题的一场比赛，显示的六道题目中最左侧的题目一共有几种可能取值。

例如14道题： ABCDEFGHIJKLMN

最开始最左侧题目：A（原点）

第一次最左侧题目：G（右移）

第二次最左侧题目：I（右移）

第三次最左侧题目：C（左移）

第四次最左侧题目：A（左移）

所以是AGICA共四种。

数据范围

$$1\leq T\leq 10^5$$

$$6 \leq n \leq 10^9$$

题解：模拟，结论

首先统计右移有多少次，如果不能整除6那么说明有一次是特殊的移动。

然后再算左移有多少次。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
void JiuCherish() {
    int n;
    std::cin >> n;
    int ans = n / 6;
    if(n % 6) ans += 1;
    n = n - 6;
    if(n % 6 == 0) {
        std::cout << ans << endl;
        return;
    }
    ans += n / 6;
    std::cout << ans << endl;
}