题解 | #北华大学计算机程序设计算法提高训练营个人赛（无L）#

洛姐打题日记

https://ac.nowcoder.com/acm/contest/37219/A

北华大学计算机程序设计算法提高训练营个人赛（无L）

题面相当有意思了，题目感觉出的也挺好，L防ak题吧这也太难了

A-洛姐打题日记

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    string s;
    cin>>s;
    if(s=="AC")cout<<"Accepted";
    else if(s=="WA")cout<<"Wrong Answer";
    else if(s=="RE")cout<<"Runtime Error";
    else if(s=="TLE")cout<<"Time Limit Exceeded";
    else if(s=="PE")cout<<"Presentation Error";
    else if(s=="MLE")cout<<"Memory Limit Exceeded";
    else cout<<"Compile Error";
    return 0;
}

B-鸡兔同笼

问题解析

设有a个鸡，b个兔子。方程就是a+b=H和a*x+b *y=F。解方程即可。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

void solve()
{
    int x,y,h,f;
    cin>>x>>y>>h>>f;
    int b=(h*x-f)/(x-y);
    int a=h-b;
    cout<<a<<" "<<b<<endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

C-小杜的签到

问题解析

把数组升序排序后得到的就是最大值，乘上-1（或把数组降序排序后再算一遍）得到的就是最小值。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;i++)cin>>v[i];
    sort(v.begin(),v.end());
    int sum=0;
    for(int i=1;i<n;i++)
    {
        sum+=v[i]-v[i-1];
    }
    cout<<-1*sum<<" "<<sum<<endl;
    return 0;
}

D-我超！原！

问题解析

一开始还想着完全背包，一看复杂度就肯定不是。

直接贪心模拟，先等差数列前n项和算出需要多少经验才能升到x级，但是要注意初始是1级，所以我们算的是前x-1项和。再算一下我们全部资源有多少经验，如果全部资源都用上经验也不够就输出QAQ。

直接贪心，能用20000的就用，用完了或用了会超就用5000，再是1000，最后离升满级就差不到1000经验，我们再看1000的有没有，没有用5000，再没有用20000。

但是有一点，比如所需经验是17000，5000的有4个，1000的有1个，如果我们用了三个5000后用一个1000的，这样还剩1000经验才到目标，此时1000的用完了，我们只能用5000的，超出经验4000，但我们要是一开始就用4个5000的，那超出经验3000。所以我们在算的过程中可以多加一个步骤，我们不继续细分而是直接用当前档次升满级看需要多少经验。最后这两种途径的取最小值即可。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll n, m, a, b, c;
    cin >> n >> m >> a >> b >> c;
    ll res = 1000 * (n-1) + ((n-2) * (n - 1)) / 2 * m;
    ll ans = a * 20000 + b * 5000 + c * 1000;
    if (res > ans)
    {
        cout << "QAQ" << endl;
        return 0;
    }
    ans=1e18;
    if (a * 20000 >= res)
    {
        a -= res / 20000;
        res %= 20000;
        if(a>0)ans=min(ans,20000-res);
    }
    else
    {
        res -= a * 20000;
        a = 0;
    }

    if (b * 5000 >= res)
    {
        b -= res / 5000;
        res %= 5000;
        if(b>0)ans=min(ans,5000-res);
    }
    else
    {
        res -= b * 5000;
        b = 0;
    }

    if (c * 1000 >= res)
    {
        c -= res / 1000;
        res %= 1000;
        if(c>0)ans=min(ans,1000-res);
    }
    else
    {
        res -= c * 1000;
        c = 0;
    }
    if (res == 0)cout << res << endl;
    else if (c != 0)cout << min(ans,1000 - res) << endl;
    else if (b != 0)cout << min(ans,5000 - res) << endl;
    else if (a != 0)cout << min(ans,20000 - res) << endl;
    return 0;
}

E-佳乐的迷宫

问题解析

可以先把入口的位置都记录下来，然后我们以出口位置进行bfs(dfs)，看那些位置是出口能走到的，那么对应的，这个位置就是能走到出口的，我们再去判断之前那些出口位置有哪些是出口能走到的即可。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

int st[1050][1050];
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<string>v(n);
    for (int i = 0; i < n; i++)cin >> v[i];
    vector<PII>ans(k);
    for (int i = 0; i < k; i++)cin >> ans[i].first >> ans[i].second;
    int x, y;
    cin >> x >> y;
    queue<PII>que;
    que.push({ x,y });
    st[x][y] = 1;
    while (!que.empty())
    {
        int len = que.size();
        for (int i = 0; i < len; i++)
        {
            auto t = que.front();
            que.pop();
            for (int j = 0; j < 4; j++)
            {
                int a = t.first + dx[j], b = t.second + dy[j];
                if (a  >= 1 && b  >= 1 && a  <= n && b  <= m &&v[a-1][b-1] == '.' && st[a ][b] == 0)
                {
                    st[a ][b] = 1;
                    que.push({ a,b });
                }
            }
        }
    }
    vector<int>res;
    int cnt = 0;
    for (auto i : ans)
    {
        cnt++;
        if (st[i.first][i.second])
        {
            res.push_back(cnt);
        }
    }
    cout << res.size() << endl;
    for (auto i : res)cout << i << " ";
    return 0;
}

F-三四五

问题解析

升级办nim游戏，这里先说一个nim游戏的必胜秘诀，如果你每次能拿最多x个石头，那么只要总石头数不是（x+1）的倍数，你就可以赢，如果是则必输。

所以只要第一堆石头是4的倍数or第二堆是5的倍数or第三堆是6的倍数，那么这堆石头我们肯定会输。但这题不是单纯的看是否必输or必赢，而是看谁先输，比如石头数是1，100，20，虽然第二堆石头是5的倍数，我们必输，但是第一堆石头只有1个，我们拿完后对面就直接输了，第一堆石头可以在第一轮分出胜负，而第二堆要20轮才能分出胜负，显然是我们赢。所以我们要看，输最快会在第几轮输，赢最快会在第几轮赢，谁小，那就说明我们会赢（输）。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

void solve()
{
    int a,b,c;
    cin>>a>>b>>c;
    bool flag=true;
    int winer=1e9,loser=1e9;
    if(a%4==0)loser=min(loser,a/4);
    else winer=min(winer,a/4);
    
    if(b%5==0)loser=min(loser,b/5);
    else winer=min(winer,b/5);
    
    if(c%6==0)loser=min(loser,c/6);
    else winer=min(winer,c/6);
    
    if(winer<loser)cout<<"(^-^)"<<endl;
    else cout<<"(T-T)"<<endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

G-杰哥的疑问

问题解析

可以用哈希表记录一下每个数的出现次数，然后对于一个数x来说，能和他相加后等于m的数肯定是m-x。那我们只要看m-x这个数出现了多少次，且x又出现了多少次，就可以知道x和m-x一共可以组合出多少个满足条件的数对。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,m,x,cnt=0;
    cin>>n>>m;
    unordered_map<int,int>mymap;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        cnt+=mymap[m-x];
        mymap[x]++;
    }
    cout<<cnt;
    return 0;
}

H-墨染的斯汀木

问题解析

为了方便，我们可以先把没被污染的字符串全部变成小写字母的形式，然后我们再根据第一个字符串中大小写的情况来还原字符串即可。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    string a,b,s,c;
    cin>>a>>b;
    int n=a.size(),m;
    for(auto i:b)
    {
        if(i>='a'&&i<='z')c+=i;
        else 
        {
            c+=(i+32);
            c+=(i+32);
        }
    }
    m=c.size();
    int l=0,r=0;
    while(l<n&&r<m)
    {
        if(a[l]=='?'||(a[l]>='a'&&a[l]<='z'))s+=c[r++];
        else 
        {
            s+=(c[r]-32);
            r+=2;
        }
        l++;
    }
    cout<<s<<endl;
    return 0;
}

I-Darling（Easy.)和J-Darling（Hard.）

问题解析

i题数据类型教少，建图之后对于每次询问我们都跑一便bfs来求最近的异性即可。

每次向和自己链接的其它点看去，如果这个点和我们的性别不同，那根据bfs特性，这个就是我们最近的异性，如果周围没有异性，那我们就把和自己相邻的点再送去下一轮bfs，同时步数+1。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

unordered_map<int,vector<int>>mymap;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,m,t,x,y;
    cin>>n>>m>>t;
    vector<int>sex(n+1);
    for(int i=1;i<=n;i++)cin>>sex[i];
    for(int i=0;i<m;i++)
    {
        cin>>x>>y;
        mymap[x].push_back(y);
        mymap[y].push_back(x);
    }
    while(t--)
    {
        int res=0;
        cin>>x;
        queue<int>que;
        que.push(x);
        y=-1;
        vector<int>st(1001);
        while(!que.empty())
        {
            res++;
            int len=que.size();
            for(int i=0;i<len;i++)
            {
                int tt = que.front();
                que.pop();
                for(auto j:mymap[tt])
                {
                    if(st[j]==0)
                    {
                        if(sex[j]!=sex[x])
                        {
                        	//找到了，我们直接结束bfs
                            y=res;
                            break;
                        }
                        else 
                        {
                            que.push(j);
                            st[j]=1;
                        }
                    }
                }
                if(y!=-1)break;
            }
            if(y!=-1)break;
        }
        cout<<y<<endl;
    }
    return 0;
}

至于j题，数据提到了1e6，这样再用上面的方法肯定会t。但还是可以用bfs来写。

我们可以把问题分成两部分：给性别为0的找最近的1，给性别为1的找最近的0。用一个二维数组f来存结果：f[i] [0]表示i到最近的0的距离，f[i] [1]表示i到最近的1的距离。

求哪个性别，就可以先遍历全部的点，把那个性别的点存入队列里，并且把f[i] [当前性别]设为0，因为里它最近的这个性别就是他自己。再进行bfs，我们只bfs到哪些性别和我们不同的点上，如果j是和i相连且性别不同的点，那么就有：

f[j] [当前性别]=f[i] [当前性别]+1；（注意当前性别不是说j的性别，而是我们现在求的性别）

这样在k次询问时，我们可以先判断询问的点是哪个性别，再去对应的数组找结果。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6 + 50, MOD = 1e9 + 7;
unordered_map<int, vector<int>>mymap;
int f[N][2], sex[N];
int n, m, t, x, y;

void bfs(int x)
{
    queue<int>que;
    for(int i=1;i<=n;i++)
        if (sex[i] == x)
        {
            que.push(i);
            f[i][x] = 0;
        }
    while (!que.empty())
    {
        int ans = que.front();
        que.pop();
        for (auto i : mymap[ans])
        {
            if (f[i][x] == -1 && sex[i] != x)
            {
                f[i][x] = f[ans][x] + 1;
                que.push(i);
            }
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m >> t;
    for (int i = 1; i <= n; i++)cin >> sex[i];
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        mymap[x].push_back(y);
        mymap[y].push_back(x);
    }
    memset(f, -1, sizeof f);
    bfs(0);
    bfs(1);
    while (t--)
    {
        cin >> x;
        if (sex[x])
        {
            cout << f[x][0] << endl;
        }
        else cout << f[x][1] << endl;
    }
    
    return 0;
}

K-小杜返校记

问题解析

按照舱位和时间找对应的手续费率pi，计算式：*n=n(1-pi/100)**。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    vector<vector<double>>v(3,vector<double>(3));
    double money;
    int h=0;
    cin>>money>>h;
    string s,fw;
    cin>>s>>fw;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            cin>>v[i][j];
    int x;
    if(s[0]=='F')x=0;
    else if(s[0]=='B')x=1;
    else x=2;
    
    if(h>=336)money=money;
    else if(h>=48)money=money*(1-v[x][0]/100);
    else if(h>=4)money=money*(1-v[x][1]/100);
    else money=money*(1-v[x][2]/100);
    cout << fixed << setprecision(2) << money << endl;
    return 0;
}
全部评论

相关推荐

12-09 18:37
嘉士伯_运营管理_HR
为什么建议看看外企
不知不觉已经十一月份了，国庆回来秋招就算真的进入中后期了，基本就是考选调，考体制内了，私企最后能投的一波就是十月上旬了，现在投着，前面大佬释放hc&nbsp;大家还有一点机会1.不喜欢你工作太卷！（俺是卷心菜，虽卷但菜）外企非常严格地遵循无996，955工作制的同时实现WLB（work&nbsp;life&nbsp;balance），即即工作生活平衡，到点就可以走人~如果怕堵车或者有其他事情（比如不太舒服、有急事）都可以提前回去，部分外企每周还有一天或两天居家办公，嘿嘿~2.不喜欢你太给自己设限请大声说:我们都有无限可能不同于国企对应届生身份卡的比较严格，外企尤其往届生友好，毕业两年内还保有应届生身份的姐妹都可以去投！...
百威成长空间 59人发布
点赞 评论 收藏
分享
12-09 00:26
内蒙古科技大学 销售工程师
点赞 评论 收藏
分享
11-08 17:36
诺瓦科技_HR
点赞 评论 收藏
分享
10-30 13:45
南京理工大学 C++
点赞 评论 收藏
分享
12-04 12:06
门头沟学院 Java
算力大陆Java后端开发
timeline11.18&nbsp;b0ss投递简历；11.26&nbsp;一面11.29&nbsp;二面；12.2&nbsp;hr电话告知oc，等待offer审批12.4&nbsp;催了一下，马上邮件录用一面--52minNetty、Http、Socket通信的区别；什么是自定义通信协议序列化方式之间的区别Netty心跳机制是什么；在代码层面是怎么实现的Zookeeper介绍一下，数据结构是什么样的，用来做什么负载均衡是什么意思；一致性哈希算法是怎么实现的，有什么需要注意的点项目里面登录鉴权是怎么做到；后续请求接口怎么知道他有没有登录上传文件、视频是怎么做的；大文件分片是怎么做的；除了存在服务器本地还有什么方案List接口的主要实现类有哪...
查看26道真题和解析
点赞 评论 收藏
分享
评论
5
收藏
分享

全站热榜

正在热议
# 25届秋招总结 #
562575次浏览 5754人参与
# 你都收到了哪些公司的感谢信？ #
3650274次浏览 32058人参与
# 百融云创开奖 #
63962次浏览 652人参与
# 腾讯求职进展汇总 #
220964次浏览 1775人参与
# 如果再来一次，你还会学机械吗？ #
24013次浏览 461人参与
# 同事找你打听工资怎么办 #
10648次浏览 86人参与
# 牛客帮帮团来啦！有问必答 #
2412499次浏览 24886人参与
# 我的求职思考 #
4332867次浏览 58225人参与
# 现在还是0offer，延毕还是备考 #
840287次浏览 6990人参与
# 牛客激励计划 #
53145次浏览 1331人参与
# 想实习转正，又想准备秋招，我该怎么办 #
505128次浏览 5119人参与
# 如何确定求职岗位 #
374978次浏览 4823人参与
# 如果实习可以转正，你会不会放弃秋招 #
218238次浏览 2898人参与
# 秋招结束之后的日子 #
17164次浏览 169人参与
# 实习与准备秋招该如何平衡 #
744071次浏览 8693人参与
# 写简历别走弯路 #
634125次浏览 7492人参与
# 运营面经 #
73665次浏览 989人参与
# 听劝，这个公司值得去吗 #
340479次浏览 1385人参与
# 我的论文进展 #
17856次浏览 234人参与
# 国央企薪资爆料 #
32640次浏览 200人参与
# 不给转正的实习，你还去吗 #
1581602次浏览 17676人参与
牛客网
牛客企业服务