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;
}