牛客周赛129

锐评

难度：F > E > D > C > B > A


A

题目链接：https://ac.nowcoder.com/acm/contest/127264/A

代码：

/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
i64 inv[1000009];
i64 f_inv[1000009];
i64 ksm(i64 x, i64 y){
    i64 ans = 1;
    while(y > 0){
        if(y & 1){
            ans = ans * x % MOD;
        }
        y >>= 1;
        x = x * x % MOD;
    }
    return ans;
}
void inint(){
    inv[0] = 1;
    for(int i = 1;i <= 1000000; i++){
        inv[i] = inv[i-1] * i % MOD;
    }
    f_inv[1000000] = ksm(inv[1000000], MOD-2);
    for(int i = 999999; i >= 0; i--){
        f_inv[i] = f_inv[i+1] * (i+1) % MOD;
    }
}
i64 C(int n, int m){
    if(n < m || n < 0 || m < 0) return 0;
    return inv[n] * f_inv[n-m] % MOD * f_inv[m] % MOD;
}
i64 A(i64 n, i64 m){
    i64 ans = 1;
    for(int i = n;i >= n - m + 1; i--) ans = ans * i % MOD;
    return ans;
}
template<class T>
void solve(){
    int x;
    std::cin >> x;
    if(x == 1){
        std::cout << "equal\n";
    }else{
        std::cout << "right\n";
    }
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t=1;
    // inint();
	// cin>>t;
	while(t--)
		solve<int>();
	return 0;
}

B

题目链接：https://ac.nowcoder.com/acm/contest/127264/B

代码：

/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
i64 inv[1000009];
i64 f_inv[1000009];
i64 ksm(i64 x, i64 y){
    i64 ans = 1;
    while(y > 0){
        if(y & 1){
            ans = ans * x % MOD;
        }
        y >>= 1;
        x = x * x % MOD;
    }
    return ans;
}
void inint(){
    inv[0] = 1;
    for(int i = 1;i <= 1000000; i++){
        inv[i] = inv[i-1] * i % MOD;
    }
    f_inv[1000000] = ksm(inv[1000000], MOD-2);
    for(int i = 999999; i >= 0; i--){
        f_inv[i] = f_inv[i+1] * (i+1) % MOD;
    }
}
i64 C(int n, int m){
    if(n < m || n < 0 || m < 0) return 0;
    return inv[n] * f_inv[n-m] % MOD * f_inv[m] % MOD;
}
i64 A(i64 n, i64 m){
    i64 ans = 1;
    for(int i = n;i >= n - m + 1; i--) ans = ans * i % MOD;
    return ans;
}
template<class T>
void solve(){
    string s;
    std::cin >> s;
    string t = s;
    reverse(t.begin(), t.end());
    if(s == t){
        std::cout << "equal\n";
    }else if(t > s){
        std::cout << "right\n";
    }else{
        std::cout << "left\n";
    }
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t=1;
    // inint();
	// cin>>t;
	while(t--)
		solve<int>();
	return 0;
}

C

题目链接：https://ac.nowcoder.com/acm/contest/127264/C

思路：

对每个数从小到大遍历，若x+1 >= k则金币 += c / 2;mp[x+1] += c / 2;

代码：

/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
i64 inv[1000009];
i64 f_inv[1000009];
i64 ksm(i64 x, i64 y){
    i64 ans = 1;
    while(y > 0){
        if(y & 1){
            ans = ans * x % MOD;
        }
        y >>= 1;
        x = x * x % MOD;
    }
    return ans;
}
void inint(){
    inv[0] = 1;
    for(int i = 1;i <= 1000000; i++){
        inv[i] = inv[i-1] * i % MOD;
    }
    f_inv[1000000] = ksm(inv[1000000], MOD-2);
    for(int i = 999999; i >= 0; i--){
        f_inv[i] = f_inv[i+1] * (i+1) % MOD;
    }
}
i64 C(int n, int m){
    if(n < m || n < 0 || m < 0) return 0;
    return inv[n] * f_inv[n-m] % MOD * f_inv[m] % MOD;
}
i64 A(i64 n, i64 m){
    i64 ans = 1;
    for(int i = n;i >= n - m + 1; i--) ans = ans * i % MOD;
    return ans;
}
template<class T>
void solve(){
    i64 n, m, k;
    std::cin >> n >> m >> k;

    std::map<i64, i64> mp;
    for(int i = 0;i < n; i++){
        for(int j = 0;j < m; j++){
            int x;
            std::cin >> x;
            if(x != 0)
            mp[x] ++;
        }
    }
    //mp[0] = 0;
    i64 ans = 0, cost = 0, mm = 0;
    for(auto &[x, c] : mp){
        //c += mm;
        //if(x == 0) continue;
        if(c==0) break;
        i64 cnt = c / 2;
        cost += cnt;
        if(cnt == 0) continue;
        if(x + 1 >= k) ans += cnt;
        //mm = cnt;
        mp[x+1] += cnt;
        //std::cout << c << " ";
    }
    std::cout << cost << " " << ans << "\n";
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t=1;
    // inint();
	// cin>>t;
	while(t--)
		solve<int>();
	return 0;
}

D

题目链接：https://ac.nowcoder.com/acm/contest/127264/D

思路：

对于一个子串，如果我们要选择？101？，要想不改变他的块数，必须两边有一边与邻位相同，一边不相同。 还一种特殊情况就是所有字符全都翻转。所以总次数=1+一边相同总数*一边不相同总数


代码：

/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
i64 inv[1000009];
i64 f_inv[1000009];
i64 ksm(i64 x, i64 y){
    i64 ans = 1;
    while(y > 0){
        if(y & 1){
            ans = ans * x % MOD;
        }
        y >>= 1;
        x = x * x % MOD;
    }
    return ans;
}
void inint(){
    inv[0] = 1;
    for(int i = 1;i <= 1000000; i++){
        inv[i] = inv[i-1] * i % MOD;
    }
    f_inv[1000000] = ksm(inv[1000000], MOD-2);
    for(int i = 999999; i >= 0; i--){
        f_inv[i] = f_inv[i+1] * (i+1) % MOD;
    }
}
i64 C(int n, int m){
    if(n < m || n < 0 || m < 0) return 0;
    return inv[n] * f_inv[n-m] % MOD * f_inv[m] % MOD;
}
i64 A(i64 n, i64 m){
    i64 ans = 1;
    for(int i = n;i >= n - m + 1; i--) ans = ans * i % MOD;
    return ans;
}
template<class T>
void solve(){
    string s;
    std::cin >> s;

    int ans = 0, cnt = 0;
    //左右区间必须有一个相同，有一个不同。
    for(int i = 1;i < s.size(); i++){
        if(s[i] == s[i-1]) ans ++;
        else cnt ++;
    }
    //该序列本身也是一个。
    std::cout << 1LL * ans * cnt + 1 << "\n";
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t=1;
    inint();
	// cin>>t;
	while(t--)
		solve<int>();
	return 0;
}

E

题目链接：https://ac.nowcoder.com/acm/contest/127264/E

思路：

对于1~n的每一个i，就是i个1相加，坐标的每一位距离要么为1要么为0.所以为i，就是从n位中选取i位作为1，其余都为0。总共的种类就有C（n, i） * ksm（2, n）;由于会有n, v;v, n相同情况会重复计算，所以总结果/2.


代码：

/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
i64 inv[1000009];
i64 f_inv[1000009];
i64 ksm(i64 x, i64 y){
    i64 ans = 1;
    while(y > 0){
        if(y & 1){
            ans = ans * x % MOD;
        }
        y >>= 1;
        x = x * x % MOD;
    }
    return ans;
}
void inint(){
    inv[0] = 1;
    for(int i = 1;i <= 1000000; i++){
        inv[i] = inv[i-1] * i % MOD;
    }
    f_inv[1000000] = ksm(inv[1000000], MOD-2);
    for(int i = 999999; i >= 0; i--){
        f_inv[i] = f_inv[i+1] * (i+1) % MOD;
    }
}
i64 C(int n, int m){
    if(n < m || n < 0 || m < 0) return 0;
    return inv[n] * f_inv[n-m] % MOD * f_inv[m] % MOD;
}
i64 A(i64 n, i64 m){
    i64 ans = 1;
    for(int i = n;i >= n - m + 1; i--) ans = ans * i % MOD;
    return ans;
}
template<class T>
void solve(){
    int n;
    std::cin >> n;
    for(int i = 1;i <= n; i++){
        std::cout << C(n, i) * ksm(2, n-1) % MOD << " ";
    }
    std::cout << "\n";
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t=1;
    inint();
	// cin>>t;
	while(t--)
		solve<int>();
	return 0;
}

F

题目链接：https://ac.nowcoder.com/acm/contest/127264/F

思路： 每条魔法路径都是一条链，他不可能为树，对于每个魔法有两种情况，要么到达没有去过的点，要么到达去过的点。

到去过的点，他所增加的期望就是点前的魔法点亮的点数*父节点的概率/当前结点的边数

否则，就前往下个节点继续分析来到之前的两种情况。


代码：

/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
i64 inv[1000009];
i64 f_inv[1000009];
i64 ksm(i64 x, i64 y){
    i64 ans = 1;
    while(y > 0){
        if(y & 1){
            ans = ans * x % MOD;
        }
        y >>= 1;
        x = x * x % MOD;
    }
    return ans;
}
void inint(){
    inv[0] = 1;
    for(int i = 1;i <= 1000000; i++){
        inv[i] = inv[i-1] * i % MOD;
    }
    f_inv[1000000] = ksm(inv[1000000], MOD-2);
    for(int i = 999999; i >= 0; i--){
        f_inv[i] = f_inv[i+1] * (i+1) % MOD;
    }
}
i64 C(int n, int m){
    if(n < m || n < 0 || m < 0) return 0;
    return inv[n] * f_inv[n-m] % MOD * f_inv[m] % MOD;
}
i64 A(i64 n, i64 m){
    i64 ans = 1;
    for(int i = n;i >= n - m + 1; i--) ans = ans * i % MOD;
    return ans;
}
template<class T>
void solve(){
    int n;
    std::cin >> n;

    std::vector<vector<int>> adj(n+1);
    for(int i = 1;i < n; i++){
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    i64 ans = 0;
    //E(x) = depth * p/k;
    function<void(int, int, int, i64)> dfs = [&](int v, int parent, int step, i64 p){
        p = p * ksm(adj[v].size(), MOD-2) %MOD;
        for(auto &u : adj[v]){
            if(u != parent){
                dfs(u, v, step+1, p);
            }else{
                ans = (ans + 1LL * step * p % MOD) % MOD;
            }
        }
    };
    
    dfs(1, 1, 1, 1);
    
    std::cout << ans << "\n";
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t=1;
    //inint();
	// cin>>t;
	while(t--)
		solve<int>();
	return 0;
}
全部评论

相关推荐

02-21 16:39
上海交通大学 算法工程师
网易游戏用户运营一面
岗位名称：游戏用户运营面试时长：50min–1h自评分：8/10是否下一轮：是用户运营基础认知如何理解用户运营？你觉得用户运营在游戏中的核心价值是什么？（追问）如果用一句话概括用户运营的目标，你会怎么说？游戏用户运营的核心目标有哪些？不同阶段是否会有变化？（追问）游戏上线初期和成熟期在运营侧的重点会有什么不同？用户运营与内容运营、活动运营之间有什么区别和协同关系？（追问）如果三者目标发生冲突，你认为优先级如何判断？实习经历与岗位匹配你之前在网易的实习是在哪个分部？团队主要负责什么产品？在网易实习期间你主要承担了哪些工作？更偏执行还是策略？（追问）有没有参与到具体方案制定？还是更多落地执行？你觉...
运营必备题库
点赞 评论 收藏
分享
02-23 01:31
济南大学 Java
实习租房焚决
年后估计会有不少友友要去大城市实习租房了，鼠鼠租房也被坑过不少次，积累了一些经验可以参考一下&nbsp;1.&nbsp;找房渠道：&nbsp;自如，贝壳，各种公寓，这种属于是有保障，房源真实，不会被坑，住的也舒服，隔音好，但是大多数是合租，而且贵&nbsp;安居客，58同城，小红书中介等等&nbsp;这些平台没有什么保障，房源价格基本都是假的，等实地看可能都不一样，也会有很多坑中介，但是这里会比自如&nbsp;贝壳便宜一些&nbsp;小红书转租&nbsp;这个如果房源合适，价格租期都合理的话其实挺合适的，但是要跟个人对接&nbsp;线下扫楼&nbsp;&nbsp;实地看过&nbsp;不太容易通过这种方式找到，去线下问保安，去小区找租房的，你也没办法从线上看到房子啥样，时间成本很高&nbsp;总结：怕麻烦优先自如...
强大的马里奥：合租遇到情侣，晚上做双人运动，吵得睡不着觉
老东西终于把焚决交出来了
点赞 评论 收藏
分享
02-06 11:31
黑龙江工程学院 行政专员/助理
点赞 评论 收藏
分享
02-09 20:08
山东大学 组织发展
点赞 评论 收藏
分享
02-21 16:28
上海交通大学 算法工程师
HTTP 和 HTTPS 区别
面试题简述我们平时开发时经常看到&nbsp;HTTP&nbsp;和&nbsp;HTTPS，那你能说说它们之间的区别吗？为什么我们要用&nbsp;HTTPS？它到底比&nbsp;HTTP&nbsp;多了什么？面试官想听的1、HTTPS&nbsp;如何在&nbsp;HTTP&nbsp;基础上增加安全保障2、是否理解加密、认证、完整性的区别；3、能否举例说明浏览器访问网站时两者的不同面试回答举例HTTP&nbsp;和&nbsp;HTTPS&nbsp;本质上都是应用层协议，用于浏览器与服务器之间传输数据。两者的区别在于：HTTP&nbsp;是明文传输，而&nbsp;HTTPS&nbsp;在传输层加入了&nbsp;SSL/TLS&nbsp;加密层，实现了数据的加密、身份认证和完整性校验。举个例子：当我们访问&nbsp;http://example.com&nbsp;时，所有请求与响应的数据...
查看6道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# xx岗简历求拷打 #
1980次浏览 23人参与
# 金三银四，你有感觉到吗 #
688163次浏览 6071人参与
# 有转正机会的小厂实习值得去吗？ #
2970次浏览 41人参与
# 携程求职进展汇总 #
875080次浏览 5679人参与
# 你最讨厌面试被问什么 #
4132次浏览 47人参与
# 哪些公司开春招了？ #
29329次浏览 192人参与
# 秋招踩过的“雷”，希望你别再踩 #
187105次浏览 1694人参与
# 机械制造2024笔面经 #
1540648次浏览 13005人参与
# 毕业季等于分手季吗 #
54514次浏览 649人参与
# 牛客租房专区 #
157626次浏览 1788人参与
# 26届的你，投了哪些公司？ #
256434次浏览 1686人参与
# 文科生还参加今年的春招吗 #
13041次浏览 98人参与
# 找实习多的是你不知道的事 #
1805634次浏览 20691人参与
# 反问环节如何提问 #
132029次浏览 2702人参与
# 大家每天通勤多久？ #
87157次浏览 864人参与
# 记录实习开销 #
188222次浏览 999人参与
# 校招笔试 #
417916次浏览 2797人参与
# 找工作中的小确幸 #
81508次浏览 452人参与
# 正在实习的你，几点下班 #
300734次浏览 2239人参与
# 如何缓解入职前的焦虑 #
261476次浏览 1466人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务