比赛传送门:(5条未读通知) 牛客小白月赛48_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)
比赛感受
C过题数居然还没D高,不过C我也卡了很久,我理解错题意了。
A - 孤独的数组
根据题意不难看出答案只能是0或者-1,因为两个原本互质的数字不可能通过乘一个正整数k使得他们不互质。
所以就是判断是否存在不互质的数字对即可。
代码 / code
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 9; int a[maxn]; int gcd(int a,int b){return a == 0 ? b : gcd(b % a, a);} signed main() { ios::sync_with_stdio(0); int N;cin >> N; for(int i = 1;i <= N; ++ i)cin >> a[i]; int ans = 0; for(int i = 1;i < N; ++ i) if(gcd(a[i], a[i + 1]) != 1) ans = -1; printf("%d\n", ans); return 0; }
B - 博弈大师
这题是二分、等差数列求和公式再加判断一个奇偶性。
#include <bits/stdc++.h> #define int long long using namespace std; int f(int x){return x * (x + 1) / 2;} void solve() { int n, a, b;cin >> n >> a >> b; int x = min(a, b); a -= x, b -= x; int l = 0,r = 1e9; while(l + 1 != r) { int mid = (l + r) / 2; if(f(mid) > n)r = mid; else l = mid; } int ans = 1;//1牛牛赢,0牛妹赢 if(r & 1)ans = 1; else ans = 0; if(ans == 0 && a)ans = 1; if(ans == 1 && b)ans = 0; printf("%s\n",ans ? "niuniu" : "niumei"); } signed main() { ios::sync_with_stdio(0); int T;cin >> T; while(T --)solve(); return 0; }
C - 可疑的区间
区间题嗷,我一开始用优先队列,前缀和,map,甚至用了set搞了好久,后面发现理解错题意了。md
先记录每条线的起点和终点,以及编号。然后直接一波暴力就行了。
i作为区间头,i - len作为区间尾,如果头遇到区间起点,就要加上对应的数量和权重,如果尾遇到区间终点,就要减去对应的数量和权重,然后时刻更新一个Max_Interval即可。
代码 / Code
/*Copyright (C) Eriktse 2022*/ #include <bits/stdc++.h> #define int long long #define fi first #define se second using namespace std; const int maxn = 1e7 + 9; int add[maxn], sub[maxn]; int L[maxn], R[maxn]; signed main() { ios::sync_with_stdio(0); int N, len, ed = 0;cin >> N >> len; for(int i = 1;i <= N; ++ i) { int l, r;cin >> l >> r; add[l] ++, sub[r] ++; L[l] += i, R[r] += i; ed = max(ed, r + 1); } //max_itv => Max_Interval pair<int, int> max_itv = {0, 0}, tmp = {0, 0}; int ans = 0; for(int i = 1;i <= ed + len; ++ i) { tmp.fi += add[i]; tmp.se += L[i]; if(i < len)continue; tmp.fi -= sub[i - len]; tmp.se -= R[i - len]; if(max_itv < tmp)max_itv = tmp, ans = 0; if(tmp == max_itv)ans ++; } printf("%lld\n", ans); return 0; }
D - 交替加乘
规律 + 贪心。
因为每个在前面的加数都要乘一个后面的乘数,要使得结果最大,就要从中间开始往两边加和乘,先排序(升序),一开始的数字位a[N / 2 + 1],加数从N / 2开始,以此减小,乘数从N / 2 + 2开始以此增大。
代码 / Code
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e5 + 9, p = 1e9 + 7; int a[maxn]; signed main() { ios::sync_with_stdio(0); int N;cin >> N; for(int i = 1;i <= N; ++ i)cin >> a[i]; sort(a + 1,a + 1 + N); int ans = a[N / 2 + 1]; for(int i = N / 2, j = i + 2; i > 0; -- i, ++ j) { ans += a[i]; if(j <= N)ans *= a[j]; ans %= p; } printf("%lld\n",ans % p); return 0; }
Comments NOTHING