CF
Problem - 1633D - Codeforces
背包dp
要提前预处理，判断最大操作数
可以发现k很大，f[k]不一定存在，当全部都更新成b时的操作总数为12*n，所以答案要找的操作数为min(k,12*n)，所以f[min(k,12*n)]
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=1e3+10;
int s[N], f[12*N];
int b[N], c[N];void solve()
{int n, k;cin >> n >> k;for (int i = 1; i <= n;i++){cin >> b[i];}for (int i = 1; i <= n;i++){cin >> c[i];}for (int i = 0; i <= n * 12;i++){f[i] = 0;}for (int i = 1; i <= n;i++){for (int j = n * 12; j >= s[b[i]];j--){f[j] = max(f[j], f[j - s[b[i]]] + c[i]);}}cout << f[min(k,12*n)] << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;//预处理for (int i = 2; i <= 1000;i++){//注意范围，1000也要更新到，s[1]=0;s[i] = 2e9;}for (int i = 1; i <= 1000;i++){for (int j = 1; j <= i;j++){if(i+i/j<=1000)s[i + i / j] = min(s[i + i / j], s[i] + 1);}}//预处理最大操作数// int maxx = 0;// for (int i = 1; i <= 1000; i++)// {// maxx = max(maxx, s[i]);// }// cout << maxx << endl;while (T--){solve();}
}
Problem - 603A - Codeforces
思维题
要想到反转一次子串，最大增量为2
1001010110（找到两个相等的重复串）
1010101010（交换中间部分，增量为2）
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2e5+10;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;string s;cin >> n >> s;int ans = n;for (int i = 0; i < n-1;i++){ans -= (s[i] == s[i + 1]);//减去重复串个数}cout << min(n, ans + 2) << endl;//如果有两个即以上重复串就+2，否则就是n本身
}
比如只有一个重复串时
100101010
10 1010101（交换重复串的第二个到末尾，增加1，ans=n）
Problem - 817C - Codeforces
二分
统计从 1 到 n 中有几个数减去其各数位之和后大于等于 \(s\)。
有单调性：
- 不进位时：数值+1，位数之和加1，差值不变
（如，x=13，sum=4，diff=9；x=14，sum=5,diff=9） - 进位时：数值变大，位数之和一定减小，差值增大，也同样满足题意
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2e5+10;
LL n, s;bool check(LL x){LL sum = x, ans = 0;while(sum){ans += sum % 10;sum /= 10;}return x - ans < s;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> s;LL l = 0, r = n + 1;while(l+1<r){LL mid = l + r >> 1;if(check(mid))l = mid;elser = mid;}cout << n - l << endl;
}