Codeforces Round 998 (Div. 3)(部分题解)

补题链接

A. Fibonacciness

思路：了解清楚题意，求得是最大的斐波那契的度，数组只有5个数(最多度为3)，能列出其对应的式子

 或 或

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n, m, k;vector<int> a(4);set<int> s;for (int i= 0; i<4; i++) cin >> a[i];s.insert(a[0]+a[1]);s.insert(a[2]-a[1]);s.insert(a[3]-a[2]);cout << 4-s.size() << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

B. Farmer John's Card Game

 思路：

我的思路偏向于暴力一点，先排好序，并记录位置，再遍历跑一边n*m检查有没有不符合条件的。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define vvi vector<vi>void solve()
{int n, m, k;cin >> n >> m;vvi a(n+1, vi(m+1));map<int, int> mp;for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){cin >> a[i][j];}sort(a[i].begin()+1, a[i].end());mp[a[i][1]] = i;}sort(a.begin()+1, a.end(), [](vi &x, vi &y){return x[1] < y[1];});int flag = 0;int last = -1;for (int i = 1; i <= m; ++i){for (int j = 1; j <= n; ++j){if (a[j][i] < last) {flag = 1;break;}else last = a[j][i];}if (flag) break;}if (flag) cout << -1 << endl;else {for (int i = 1; i <= n; ++i){cout << mp[a[i][1]] << " \n"[i == n];}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

题解的思路会巧一点不用重复遍历。

附上关键代码：

for (vll &we : ve) {for (ll &i : we) cin >> i;ll minN = *min_element(we.begin(), we.end());if (minN < n) p[minN] = c++;val &= minN < n;sort(we.begin(), we.end());ll last = we[0]-n;for (ll i : we) {val &= last+n == i;last = i;}}

C. Game of Mathletes

思路：

记录数字出现的次数，枚举k的一半，（k为偶数特判一下）取mp[i],mp[k-i]的较小值。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>void solve()
{int n, m, k;cin >> n >> k;vi a(n);map<int, int> mp;for (int i = 0; i < n; i++){cin >> a[i];mp[a[i]]++;}int ans = 0;for (int i = 1; i<=k/2; i++){if (k % 2 ==0 && i == k/2) ans += mp[i]/2;else ans += min(mp[i], mp[k-i]);}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

D. Subtract Min Sort

思路：

从头开始遍历，如果a[i-1]>a[i]就不成立，

否则a[i]和a[i-1]都同时减去min(a[i-1],a[i])

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define endl '\n'
void solve()
{int n, m, k;cin >> n;vi a(n);int flag = 0;for (int i = 0; i < n; i++) cin >> a[i];for (int i = 1; i<n; i++){if (a[i-1] > a[i]) {flag = 1;break;}else {int mi = min(a[i-1], a[i]);a[i-1] -= mi;a[i]-=mi;}}if (flag) cout << "NO" << endl;else cout << "YES" << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}