02-02 23:50 已编辑浙江警官职业学院发布于贵州

关注

2024牛客寒假算法集训营1题解 7/13

7/13

A DFS搜索

题目大意：

给定一个长度为 $n$ 的字符串 $s$ 判断是否有 $dfs | DFS$ 子串

实现思路：

爆搜的时间复杂度是 $O(n)$

代码：

#include <bits/stdc++.h>

using namespace std ;

int main()
{
    int t ;
    cin >> t ;
    while (t--) {
        int n ;
        string str ;
        cin >> n >> str ;
        for(auto p : {"DFS" , "dfs"}) {
            int i = 0 , f = 0 ;
            for(int j = 0 ; j < n ; ++ j) 
                if ( str[j] == p[i] ) {
                    ++i ;
                    if ( i == 3 ) {
                        f = 1 ;
                        break ; 
                    }
                }
            cout << f << ' ' ; 
        }
        cout << '\n' ;
    }
    return 0 ;
}

B 关鸡

题目大意：

在2*2e9+1的矩阵中，鸡初始在(1,0)位置，已知 $n$ 处着火点求至少需要再添加多少个着火点才能困住鸡

实现思路：

分类讨论

代码：

#include <bits/stdc++.h>

using namespace std ;
typedef pair<int , int> PII ;

int main()
{
    int t ;
    cin >> t;
    while (t--) {
        map<int , PII> mp ;
        int n , l = 0 , r = 0 ; 
        cin >> n ;
        while (n--) {
            int x , y ;
            cin >> x >> y ;
            if ( x == 1 ) mp[y].first = 1 ;
            else mp[y].second = 1 ;
            if ( y < 0 ) l = max({l , mp[y].first + mp[y].second , mp[y + 1].first + mp[y].second , mp[y - 1].first + mp[y].second , mp[y].first + mp[y - 1].second , mp[y].first + mp[y + 1].second}) ;
            else if ( y > 0 ) r = max({r , mp[y].first + mp[y].second , mp[y + 1].first + mp[y].second , mp[y - 1].first + mp[y].second , mp[y].first + mp[y - 1].second , mp[y].first + mp[y + 1].second}) ;
        }
        cout << min({3 - mp[0].second - mp[-1].first - mp[1].first , 4 - l - r , 4 - mp[-1].first - mp[0].second - r , 4 - mp[1].first - mp[0].second - l}) << '\n' ;
    }
    return 0 ;
}

C 按闹分配

题目大意：

题目问题背景是放在排队接水问题上进行改编的并定义了所有人的不满意度 $S=\sum_{i=1}^{n}D_i$ 有个鸡要插队问最早这个鸡的办完事时刻

实现思路：

数学推导

假设原序列得到 $S_{min}$ 时的排序：

$b_i$ 表示第 $i$ 只鸡办完事的时刻

$a_1$ 、 $a_2$ 、 $a_3$ 、 $a_4$

$b_i = \sum_{j=1}^i a_j$

$D_i = \sum_{j=1}^i b_i$

若插队鸡的后面有2个鸡则会得到

$D_n = (n - 2) \ast t_c$

设 $cnt$ 表示插队鸡后面有多少人

$\because \Delta = cnt \ast t_c <= m$

$\therefore cnt = min(n , \frac{m}{t_c})$

$\therefore result = \sum_{i=1}^{n-cnt}b_i tc$

代码：

#include <bits/stdc++.h>

using namespace std ;
typedef long long i64 ;
const int N = 1e5 + 10 ;

i64 sum[N] ;
int a[N] ;

int main()
{
    int n , q , tc ;
    cin >> n >> q >> tc ; 
    for(int i = 1 ; i <= n ; i++) 
        cin >> a[i] ;
    sort(a + 1 , a + 1 + n) ;
    for(int i = 1 ; i <= n ; i++) 
        sum[i] = sum[i - 1] + a[i] ;
    while (q--)
    {
        i64 m ; 
        cin >> m ;
        int cnt = min((i64)n , m / tc) ;
        cout << sum[n - cnt] + tc  << '\n' ;
    }
    return 0 ; 
}

D 数组成鸡

E 本题又主要考察贪心

题目大意：

有 $n$ 只鸡决斗初始每只鸡的得分是 $a_i$ ,决斗一局有俩种结果

$win 3 , loser 0$
$draw , all 1$

实现思路：

爆搜

时间复杂度 $O(2^m\ast n)$

代码：

#include <bits/stdc++.h>

using namespace std ;

const int N = 20 ; 

struct node {
   int u , v ; 
} A[N];

int a[N] , ans , n , m ;

void dfs(int pos) {
    if ( pos > m ) {
        map<int , int , greater<int>> mp ;
        for(int i = 1 ; i <= n ; i++) ++ mp[a[i]] ;
        int ret = 0 ;
        for(auto p : mp) {
            if ( p.first == a[1] ) break ;
            else ret += p.second ; 
        }
        ans = min(ans , ret + 1) ;
        return ; 
    }
    int u = A[pos].u , v = A[pos].v ;
    ++ a[u] , ++ a[v] ;
    dfs(pos + 1) ;
    -- a[u] , -- a[v] ;
    a[u] += 3 ;
    dfs(pos + 1) ;
    a[u] -= 3; 
    a[v] += 3;
    dfs(pos + 1) ;
    a[v] -= 3 ;
}

int main()
{
    int t ;
    cin >> t ;
    while (t--)
    {
        cin >> n >> m ;
        ans = 0x3f3f3f3f ;
        for(int i = 1 ; i <= n ; i++) cin >> a[i] ;
        for(int i = 1 ; i <= m ; i++) cin >> A[i].u >> A[i].v; 
        dfs(1) ;
        cout << ans << '\n' ;
    }
    return 0 ; 
}

F 鸡数题（第二类斯特林数）

G why买外卖

题目大意：

原持有金额为 $x$ , 买东西现有 $n$ 个优惠卷满 $a_i$ 则减 $b_i$ 已知 $n$ 、 $a_i$ 、 $b_i$ 求 $x$ 。

实现思路：

枚举

代码 :

#include <bits/stdc++.h>

using namespace std ;
typedef long long i64 ; 
const int N = 1e5 + 10 ;

struct node {
    i64 a , b ;
    bool operator < (const node c) const {
        return a < c.a ; 
    }
} A[N];

i64 sum ;

int main()
{
    int t ; 
    cin >> t ;
    while (t--)
    {
        int n , m ; 
        cin >> n >> m ; 
        for(int i = 1 ; i <= n ; i++){
            cin >> A[i].a >> A[i].b ;
        }
        sort(A + 1 , A + 1 + n) ;
        i64 ret = m ;
        sum = 0 ;
        for(int i = 1 ; i <= n ; i++)
        {
            sum += A[i].b ;
            if ( A[i].a - sum <= m ) ret = A[i].a + max((i64)0 , m - A[i].a + sum);
        }
        cout << ret << '\n' ;
    }
    return 0 ;
}

H 01背包，但是bit

I It's bertrand paradox. Again!

题目大意：

bit-noob 和 buaa-noob 完成一项作业随机生成 $1e5$ 个合法圆但是二者随机生成的方法不同

bit-noob :

随机等概率低从开区间（-100，100）生成俩个整数 $x$ , $y$
随机等概率低从闭区间 [1 , 100]中生成一个 $r$
判断( $x$ , $y$ )为圆心， $r$ 为半径的圆是否满足要求在 -100 <= x <= 100 && -100 <= y <= 100 的平面上若不满足返回操作2直到满足后加入到结果中

buaa-noob :

随机等概率低从开区间（-100，100）生成俩个整数 $x$ , $y$ , 随机等概率低从闭区间 [1 , 100]中生成一个 $r$
判断( $x$ , $y$ )为圆心， $r$ 为半径的圆是否满足要求在 -100 <= x <= 100 && -100 <= y <= 100 的平面上若不满足返回操作1直到满足后加入到结果中

给出50组随机数据判断分别是哪个的作业

实现思路：

打表找规律

T_T 这道题告诉我们没想法打个表先看看）不同角度统计都可以通过这道题

bit-noob:

$\sum_{i=1}^{100000} r_i >= 5000$

$\sum_{i=1}^{100000} abs(x_i y_i) >= 6000000$

…………

打表代码：

#include <bits/stdc++.h>

using namespace std ;

const int N = 1e5 + 10 ; 


int main()
{
    freopen("out.txt","w",stdout) ;
    //c++11 random library 产生均匀分布的整数函数 
    std::default_random_engine e;
    std::uniform_int_distribution<int> u(1,100); // 左闭右闭区间
    std::uniform_int_distribution<int> v(-99,99); // 左闭右闭区间

    e.seed(time(0)) ;
//map<int , int> A , B ;
    int A = 0 , B = 0;
    for(int i = 1 ; i <= 100000 ; i++) 
    {
        int x = v(e) , y = v(e) , r = u(e) ;
        while ( x + r > 100 || x - r < -100 || y + r > 100 || y - r < -100 ) r = u(e) ;
        A += abs(x + y) ; 
    }
    for(int i = 1 ; i <= 100000 ; i++) 
    {
        int x = v(e) , y = v(e) , r = u(e) ;
        while ( x + r > 100 || x - r < -100 || y + r > 100 || y - r < -100 ) r = u(e) , x = v(e) , y = v(e) ;
        B += abs(x + y);
    }

    cout << "A : \n" ;
    cout << A ;
    cout << "\n\nB : \n" ;
    cout << B ;

    return 0 ;
}

J 又鸟又亦心

K 牛镇公务员考试

L 要有光

实现思路：

画图显然可知答案即 $3\ast w \ast c$

代码：

t = eval(input())

for i in range(0 , t) :
    c,d,h,w = map(int,input().split()) ;
    print(3*w*c)

M 牛客老粉才知道的秘密

实现思路：

读题）

代码：

#include <bits/stdc++.h>

using namespace std ;

int main()
{
    int t ; 
    cin >> t; 
    while (t--)
    {
        int n ; 
        cin >> n ; 
        cout << (n / 6 + ( n % 6 ? n / 6 : 0)) << '\n' ;       
    }
    return 0 ;
}