牛客周赛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;
}
全部评论

相关推荐

头像
昨天 19:29
小天才_电子工程师(准入职员工)
腾讯内推，腾讯内推码
腾讯CSIG腾讯云后端二面面经面试时间：2025.10算法1.&nbsp;编辑距离2.&nbsp;LRU实习介绍下实习中的困难，最后怎么解决的八股缓存穿透，缓存击穿，缓存雪崩分别是什么，如何解决Redis集群有哪几种Redis&nbsp;Cluster自动故障转移是怎么实现的，这个没答好了解一致性哈希吗HTTPS底层怎么实现的腾讯2027届可转正实习启动！无限复活甲，鹅厂不设限：1.&nbsp;只要当前未在面试流程中，可随时切换岗位，投递无上限！2.&nbsp;如3个工作日后意向部门未发起面试，全公司所有岗位/部门均可能向你发起面试，发起次数无上限！3.&nbsp;同学可根据个人意愿拒绝面试，腾讯承诺，拒绝面试不会对你之后的面试机会产生任何影响！招聘岗...
点赞 评论 收藏
分享
今天 10:40
华中师范大学 产品经理
点赞 评论 收藏
分享
昨天 12:51
已编辑
门头沟学院 Java
点赞 评论 收藏
分享
02-23 11:34
广东海洋大学 前端工程师
点赞 评论 收藏
分享
02-23 17:30
京东_京东零售_运营
拒绝神仙打架！普通人如何靠“求职精灵”死磕下小米运营岗？
1.&nbsp;碎碎念：从“两眼一黑”到“意向到手”家人们，谁懂啊！刚收到小米意向书的那一刻，我手都在抖。先交代一下我的渣渣&nbsp;BG：某双非普通一本，传媒专业，大二大三在两家名不见经传的小公司做过新媒体实习。简历拿出来，在清北复交满地走的校招群里，真的属于那种“背景板”选手。投小米的时候纯属抱着“雷总选我我必冲”的抽奖心态。结果笔试居然过了，收到面试通知那一刻，我整个人直接“两眼一黑”。兴奋也就持续了三秒，紧接着就是无止境的恐慌：我就那点只会写写推文、剪剪视频的皮毛功夫，拿什么去跟那群大厂实习收割机硬刚？尤其是看到面经里说，小米的面试官特别看重底层逻辑和增长思维，我当时心里咯噔一下，感觉自己那点实习经历薄...
你觉得哪一届的校招最难？
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 有转正机会的小厂实习值得去吗？ #
4109次浏览 53人参与
# 工作不开心辞职是唯一出路吗 #
7452次浏览 25人参与
# 开工第一帖 #
6442次浏览 134人参与
# 实习期间如何提升留用概率？ #
241114次浏览 1823人参与
# xx岗简历求拷打 #
2242次浏览 25人参与
# 掌握什么AI技能，会为你的求职大大加分 #
3076次浏览 111人参与
# 联想求职进展汇总 #
334892次浏览 2220人参与
# 牛友投递互助，不漏校招机会 #
438775次浏览 5243人参与
# 携程求职进展汇总 #
877413次浏览 5713人参与
# 牛客租房专区 #
158848次浏览 1858人参与
# 非技术er求职现状 #
138951次浏览 821人参与
# 哪些公司开春招了？ #
30783次浏览 197人参与
# 金三银四，你有感觉到吗 #
689720次浏览 6078人参与
# 大家每天通勤多久？ #
88388次浏览 933人参与
# 你最讨厌面试被问什么 #
4846次浏览 57人参与
# 秋招有哪些公司要求提前实习 #
109411次浏览 563人参与
# 记录实习开销 #
189434次浏览 1068人参与
# 如何缓解入职前的焦虑 #
261835次浏览 1468人参与
# 滴滴求职进展汇总 #
308737次浏览 2470人参与
# 哪些公司主动和你打招呼？ #
78242次浏览 366人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务