2023河南萌新联赛第（五）场：郑州轻工业大学

A.买爱心气球

原题链接 : 登录—专业IT笔试面试备考平台_牛客网

 博弈论 : 

#include <iostream>
using namespace std;
int t,n,m;
string s1 = "Alice",s2 = "Bob";
int main() {cin>>t;while(t--){cin>>n>>m;if (n % 3 == 0) {cout << s1 << endl;continue;}if (n % 3 == 1) {cout << (m != 1 ? "Alice\n" : "Bob\n");continue;}if (n % 3 == 2) {cout << (m != 2 ? "Alice\n" : "Bob\n");continue;}}return 0;
}

B.亚托莉 -我挚爱的时光-

原题链接 : 登录—专业IT笔试面试备考平台_牛客网

题面 :  

思路  : 模拟

#include "bits/stdc++.h"using namespace std;
using i64 = long long;int main() { int n;cin >> n;auto useless = cin.get();vector<string> a(n);for (int i = 0 ;i  < n ;i ++) {getline(cin, a[i]);}string c[] = {"sudo pacman -S ","pacman -R ","pacman -Rscn ","sudo rm -rf /*"};unordered_set<string> st[2];for (int i = 0; i < n; i++) {auto check = [&](int j) {int x = a[i].size(), y = c[j].size();if (x >= y && a[i].substr(0, y) == c[j]) {return true;} return false;};if (check(0)) {auto s = a[i].substr(c[0].size());st[0].insert(s);st[1].insert(s);} else if (check(1)) {auto s = a[i].substr(c[1].size());st[0].erase(s);} else if (check(2)) {auto s = a[i].substr(c[2].size());st[0].erase(s);st[1].erase(s);} else if (check(3)) {cout << "wuwuwu\n";return 0;} else {auto o = a[i][0] - '0' - 1;auto s = a[i].substr(2);cout << (st[o].count(s) ? "yes" : "no") << '\n';}}return 0;
}

 D.01分数规划

链接 : 登录—专业IT笔试面试备考平台_牛客网

题面 :  

 思路 : 分两种情况，?全替换为0,或全替换为1.

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
string s,t; int T,n;
void solve(){cin>>n; cin>>s;s=' '+s; t=s;for(int i=1;i<=n;i++) if(s[i]=='?') s[i]='1';for(int i=1;i<=n;i++) if(t[i]=='?') t[i]='0';int ans = 0;for(int i=1;i<=n;i++){int j =i;while(j<=n&&s[j]==s[i]) j++; j--;ans = max(ans,j-i+1);i=j;}for(int i=1;i<=n;i++){int j = i;while(j<=n&&t[j]==t[i]) j++; j--;ans = max(ans,j-i+1);i=j;}cout<<ans<<endl;return ;
}
int main(){cin>>T;while(T--)  solve();return 0;
}

I.双指针

原题链接 : 登录—专业IT笔试面试备考平台_牛客网

题面 :  

 思路 : 用hash表来存每次的a/b，然后ans加上之前在map中出现相反数的次数

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
const int N = 2e5+10;
unordered_map<double,int> mp;
int a[N],b[N],n;
inline void solve(){mp.clear();cin>>n;LL ans = 0;for(int i=1;i<=n;i++) cin>>a[i];for(int j=1;j<=n;j++) cin>>b[j];for(int i=1;i<=n;i++){double x = 1.0*a[i]/b[i],y=1.0*b[i]/a[i];ans += mp[x];mp[y]++;}cout<<ans<<endl;
}int main()
{IOSint _;cin >> _;while(_ --) solve();return 0;
}
// ai*aj =bi*bj
// ai / bi = bj / aj
// 1 2 1 1/2 3/2

J.树上dp

原题链接 : 登录—专业IT笔试面试备考平台_牛客网

题面 :  

 思路 : 贪心，权值大的考虑放在深度大的地方

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 200010, M = N * 2;int h[N], e[M], ne[M], idx;
int val[N], d[N];
bool st[N];inline void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}void dfs(int u)
{st[u] = true;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(st[j])continue;d[j] = d[u] + 1;dfs(j);}
}inline void solve()
{memset(h, -1, sizeof h);idx = 0;int n;cin >> n;for(int i = 1; i < n; i ++){int a, b;cin >> a >> b;add(a, b), add(b, a);}for(int i = 1; i <= n; i ++){cin >> val[i];st[i] = false;}d[1] = 1;dfs(1);sort(d + 1, d + 1 + n);sort(val + 1, val + 1 + n);ll ans = 0;for(int i = 1; i <= n; i ++){ans += (ll)val[i] * (ll)d[i];}cout << ans << endl;
}int main()
{IOSint _;cin >> _;while(_ --){solve();}return 0;
}