Problem - 1858B - Codeforces（1500）（贪心）
这题一个是要读题
在不包括cookie seller的区间才算没吃饼干的时间sum += (s[i] - s[i - 1] - 1) / d;
在加上路过cookie seller时吃的饼干数 sum += m - 1;
然后贪心的思想，遍历删除每个cookie seller
重新计算合并两个区间里吃的饼干数
注意一点，要再处理
s[0]=1-d和s[m+1]=n+1,这里就可以考虑到1~s[1]和s[m]~n区间
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;void solve()
{int n, m, d;cin >> n >> m >> d;vector<int> s(m + 2);for (int i = 1; i<=m;i++){cin >> s[i];}s[0] = 1 - d;s[m + 1] = n + 1;int sum = 0;for (int i = 1; i <= m+1;i++){sum += (s[i] - s[i - 1] - 1) / d;}sum += m - 1;int ans = n + 1, cnt = 0;for (int i = 1; i <= m;i++){int res = sum;res -= (s[i] - s[i - 1] - 1) / d;res -= (s[i + 1] - s[i] - 1) / d;res += (s[i + 1] - s[i - 1] - 1) / d;if(res<ans){ans = res;cnt = 1;}else if(res==ans){cnt++;}}cout << ans << " " << cnt << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - 1385D - Codeforces(string)
分治思想，递归
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
string s;
int getans(int l, int r, char c)
{if (l == r)return s[l] != c;//相等返回0int tot1 = 0, tot2 = 0;int mid = (l + r) >> 1;for (int i = l; i <= mid; i++)if (s[i] != c)tot1++;for (int i = mid + 1; i <= r; i++)if (s[i] != c)tot2++;tot1 += getans(mid + 1, r, c + 1);tot2 += getans(l, mid, c + 1);return min(tot1, tot2);
}void solve()
{int n;cin >> n >> s;cout << getans(0, n - 1, 'a') << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - 873B - Codeforces（01string）（1500）
这题思路简单，存第一次出现数字下标，然后求前缀长度即可
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
int sum[N], f[N], ans;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;string s;cin >> s;s = " " + s;for (int i = 1; i <= n;i++){sum[i] = sum[i - 1] + (s[i] == '1' ? 1 : -1);if(sum[i]==0){ans = max(ans, i);}}for (int i = 1; i <= n;i++){if(f[sum[i]+n])ans = max(ans, i - f[sum[i]+n]);elsef[sum[i]+n] = i;}cout << ans << endl;
}
昨天要做的洛谷题
P2347 [NOIP 1996 提高组] 砝码称重 - 洛谷
01背包问题
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=1010;
int a[N], x, num,ans;
int b[10] = {0, 1, 2, 3, 5, 10, 20};
bool vis[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int x;for (int i = 1; i <= 6;i++){cin >> x;for (int j = 1; j <= x;j++)a[++num] = b[i];}vis[0] = 1;for (int i = 1; i <= num;i++){for (int j = 1000; j >= 0;j--)if(vis[j])vis[j + a[i]] = 1;}for (int i = 1; i <= 1000;i++){if(vis[i])ans++;}cout << "Total=" << ans << endl;
}
bitset解法
用二进制求方案数
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
int a[10], w[10] = {1, 2, 3, 5, 10, 20};
bitset<1010> s;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);for (int i = 0; i < 6;i++){cin >> a[i];}s[0] = 1;for (int i = 0; i < 6;i++){for (int j = 0; j < a[i];j++){s |= s << w[i];}}cout << "Total=" << s.count() - 1;
}