牛客第一周补题

╰+哭是因爲堅強的太久メ 2022-11-18 04:40 182阅读 0赞

**签到题I**

The fruit harvest has been good this year, which means that your jam-selling company, which produces the price-winning Berry Artisanal and Pure Compote, is shipping out jam left and right! A customer has recently placed a huge order of n jars of jam. To ship these jars, you put them into boxes, each of which can hold up to k jars.

As is always the case with fragile goods, the jars might break in the process of being delivered. You want to avoid the jars bouncing around in their boxes too much, as that signifificantly increases the chance that they break. To circumvent this, you want to avoid having boxes that are too empty: that would inevitably result in the uncontrolled bouncing around, and subsequently breaking, of the jars. In particular, you want the box with the least number of jars to be as full as possible. In order to estimate the risk you are taking with your precious jars, you would like to know: how many jars does this box contain?  
输入描述:  
The input consists of:  
• A line with two integers n (1 ≤ n ≤ 1018), the number of jars that need to be packed, and k (1 ≤ k ≤ 1018), the number of jars a single box can hold.  
输出描述:  
Output the number of jars that the least fifilled box contains.  
示例1  
输入

10 3  
输出  
2

示例2  
输入  
16 4  
输出  
4

示例3  
输入  
1 2  
输出  
1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]

题目没看到好  
向上取整的[证明][Link 1]  
int cnt = (n -1) / k +1;  
向下取整：int cnt = n / k;

#include<bits/stdc++.h>
    #define ll long long
    #define ios ios::sync_with_stdio(false);cin.tie(0)
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define mem(x,y) memset(x,y,sizeof(x))
    #define inf 2147483647
    const int mod=1e9+7;
    const int maxn=1e5+7;
    using namespace std;
    
    
    int main()
    { 
        ios;
    	ll n,k,ans;
    	cin >> n;
    	cin >> k;
    	ll cnt = (n + k - 1) / k; 
    	// 这不是向下取整，不能使用floor
        ans = n / cnt;
    	printf("%lld",ans);
        return 0;
    }

**H题**  
题目描述

Woe is you – for your algorithms class you have to write a sorting algorithm, but you missed the relevant lecture! The subject was in-place sorting algorithms, which you deduce must be algorithms that leave each input number in its place and yet somehow also sort the sequence.  
.  
Of course you cannot change any of the numbers either, then the result would just be a difffferent sequence. But then it hits you: if you flflip a 6 upside-down, it becomes a 9, and vice versa! Certainly no one can complain about this since you changed none of the digits! The deadline to hand in the exercise is in fifive hours. Try to implement this sorting algorithm before then!  
输入描述:  
The input consists of:  
• A line with an integer n (2 ≤ n ≤ 10 000), the number of integers in the input sequence.  
• n lines, the ith of which contains a positive integer xi (1 ≤ xi ≤ 1018), the ith number of the sequence.  
输出描述:  
If the sequence cannot be sorted non-decreasingly by flipping some number 6 or 9 in input 1, output “not possible”. Otherwise, output “possible” followed by the sorted sequence - each number on its own line.  
If there is more than one valid solution, please output the smallest sequence.

输入样例  
4  
9  
7  
7  
9  
输出  
possible  
6  
7  
7  
9  
思路：  
输入一个数字，位数6全部换成9  
对于每一个数，再从左到右，把9依次换成6，  
这里有两种情况，如果比前一个数大，可以换；  
如果比前一个数小，对这个数的下一位进行讨论。  
一些范围：  
需要long long 才能过  
pow()函数返回int 值，不能与long long 直接乘

ac代码：

#include<bits/stdc++.h>
    #define ll long long
    #define ios ios::sync_with_stdio(false);cin.tie(0)
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    using namespace std;
    
    vector <ll> a;
    string str;
    
    ll fun(string str)
    { 
        ll temp = 0;
        ll cnt = 1;
        int len = str.length()-1;
        for(int i = len; i >= 0; i--){ 
            temp += (str[i]-'0')*cnt;
            cnt *= 10;
        }
        return temp;
    }
    
    int main()
    { 
        ios;
    	int n;
        cin >> n;
        bool flag = true;
        ll pre = 0;
        rep(i,1,n)
        { 
            cin >> str;
            rep(j,0,str.length()-1) if(str[j]=='6') str[j]='9';
            rep(j,0,str.length()-1){ 
                if(str[j]=='9' && fun(str) >= pre) str[j] = '6';
                if(str[j]=='6' && fun(str) < pre) str[j] = '9';
            }
            if(fun(str) < pre) flag = false;
            else { 
                pre = fun(str);
                a.push_back(pre);
            }
        }
        if(flag == false) { cout << "impossible";return 0;}
        cout << "possible\n";
        for(int i = 0; i < a.size(); i++) cout << a[i] << endl;
        return 0;
    }

**F Group Project**

The big day has fifinally arrived: today you are going to form groups of two in which you will do the end-of-the-year project. When you arrive at school, you learn that the teacher of the other class is sick, and that your teacher, Mr. B.A.P. Cee, will also have to make groups for the other class. Mr. B.A.P. Cee is a smart guy and realizes that he can use these unfortunate circumstances to his advantage.

Ending up with groups of one should be avoided at all cost, so mixing the students of the two classes may avoid this situation. However, while it is easy to pair up two students from the same class, it is more diffiffifficult to match up students from difffferen classes. Throughout the years there has been a lot of rivalry between the two groups, and many students dislike students in the other class. Mr. B.A.P. Cee knows which pairs of students will result in a fifight and a failed project.

You are given a list of pairs of students who cannot work together. How many disjoint groups of two can Mr. B.A.P. Cee make that will not result in a failed project?  
输入描述:  
The input consists of:  
• A line with two integers n (1 ≤ n ≤ 105), the number of students, and m (0 ≤ m ≤ 2 · 105), the number of pairs of students who cannot work together.  
• m lines, each with two distinct integers i and j (1 ≤ i, j ≤ n, i = j), giving a pair of students who cannot work together.  
Students are identifified by the numbers 1 through n. It is guaranteed that it is possible to split the students into two classes in such a way that all students from the same class get along.  
输出描述:  
Output the number of pairs of students Mr. B.A.P. Cee can make without making any pair of students who cannot work together.

输入

复制  
6 6  
1 4  
2 5  
3 6  
1 5  
3 5  
2 6  
输出

复制  
3

#include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+5;
    
    int vis[maxn];
    vector<int> a[maxn];
    
    void dfs(int u, int p){ 
        if(vis[u]) return;
        vis[u] = p;
        for(auto v : a[u])
            dfs(v, 3 - p);
    }
    int main(){ 
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
        { 
            int u, v;
            cin >> u >> v;
            u--, v--;
            a[u].push_back(v);
            a[v].push_back(u);
        }
        dfs(0 , 1);
        int s = count(begin(vis), end(vis), 1);
        int t = count(begin(vis), end(vis), 2);
        if(s + t == n && s * t == m)
            cout << s/2 + t/2 << endl;
        else
            cout << n/2 << endl;
        return 0;
    }

思路和代码来自官方题解

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]: /images/20221022/7d634ffa2aec4a17b120fe5f77c93a60.png
[Link 1]: https://blog.csdn.net/a197p/article/details/45506821