CF
Problem - 1418C - Codeforces（dp+贪心好题！）（1500）
dp操作，要分开判断先手和后手
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
int a[N],dp[N][2];
//dp[i][0] 最后一次是后手,dp[i][1] 最后一次是先手
//dp[][]记录先手取 1的最小数量
int inf = 1e9;void solve()
{int n;cin >> n;for (int i = 1; i <= n;i++){cin >> a[i];}for (int i = 0; i <= n;i++){dp[i][0] = inf;dp[i][1] = inf;}dp[0][0] = 0;dp[1][1] = a[1];for (int i = 2; i <= n;i++){dp[i][1] = min(dp[i - 1][0] + a[i], dp[i - 2][0] + a[i] + a[i - 1]);dp[i][0] = min(dp[i - 1][1], dp[i - 2][1]);}cout << min(dp[n][0], dp[n][1]) << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
一个很妙的贪心解法
找全为1的长度段
分成3个1，自己拿2个，朋友skip一个，这满足最小
0的话留给朋友就行了
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
int a[N];void solve()
{int n;int cnt = 0,ans=0;cin >> n;cin >> a[1];for (int i = 2; i <= n;i++){cin >> a[i];if(a[i]==1){cnt++;}else{ans+=cnt/3;cnt = 0;}}ans += cnt / 3;cout << ans + a[1] << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - 1753A2 - Codeforces(贪心)（双指针）
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
int a[N];void solve()
{int n;cin >> n;for (int i = 1; i <= n;i++)cin >> a[i];int sum = 0;for (int i = 1; i <= n;i++){sum += a[i];}if(sum%2){cout << -1 << endl;return;}int l = 1, r;vector<pair<int, int>> ans;while(l<=n){if(a[l]==0){ans.push_back({l, l});l++;continue;}r = l + 1;while(a[r]==0)r++;if(a[l]==a[r]){if((r-l+1)%2==0)ans.push_back({l, r});else{ans.push_back({l, l});ans.push_back({l + 1, r});}}else{if((r-l+1)%2==1){ans.push_back({l, r});}else{ans.push_back({l, l});ans.push_back({l + 1, r});}}l = r + 1;}cout << ans.size() << endl;for(auto x:ans){cout << x.first << " " << x.second << endl;}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - 1307C - Codeforces（贪心）
一道考验观察能力的题
需要发现最大可能要不1个字符，要不2个字符
所以只要贪心就行啦
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
LL c, cnt;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);string s;cin >> s;LL maxx = 0;for (int t = 0; t < 26; t++){for (int j = 0; j < 26; j++){cnt = 0, c = 0;for (int i = 0; i < s.size(); i++){if (s[i] - 'a' == j)cnt += c;if (s[i] - 'a' == t)c++;}maxx = max(maxx, cnt);}maxx = max(maxx, c);}cout << maxx << endl;
}
碎碎念
今天考完人工智能导论了，很忙的期末周马上开始了