今天血崩，基本没有独立写完的 orz，太菜了还是要要多练练。
P8649 [蓝桥杯 2017 省 B] k 倍区间
一开始就暴力前缀和，结果果然没有全部拿下，剪了一会枝结果并没有什么卵用 orz。出去逛了一圈题解学到了同余的思想，wr 我怎么想不到捏，还是挺好理解的。就是说差是 K 的倍数的两个数，对 K 取余的余数是一致的。然后注意余数为 0 的天然有一个，代码：
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis));
using namespace std;
ll a[100010], cnt[100010];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
mem(a, 0);
mem(cnt, 0);
cnt[0]++;
int n, k;
ll ans = 0;
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> ans;
a[i] = a[i - 1] + ans;
a[i] %= k;
cnt[a[i]]++;
}
ans = 0;
for(int i = 0; i < k; i++){
ans += (cnt[i] * (cnt[i] - 1)) / 2;
}
cout << ans << endl;
return 0;
}
P8697 [蓝桥杯 2019 国 C] 最长子序列
这题第一反应是用 DP，看了一眼标签果然是 DP，推了半天推不出递推式 orz，再逛一圈看到有说用双指针，尝试写了一下，果然通过了。。。。
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis));
using namespace std;
string t, s;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
cin >> s;
int m = t.size(), n = s.size();
int i = 0, j = 0, ans = 0;
while(i < m && j < n){
if(t[i] == s[j]){
ans++, i++, j++;
}else{
i++;
}
}
cout << ans << endl;
return 0;
}
P1043 [NOIP2003 普及组] 数字游戏
绿题对于我来说果然还是太难了，看了半天题解才写出来，用两个数组记录状态，B(S)[i][j][l]表示从 i 到 j 分割成 l 部分的最大(小)值。注意取余的特殊操作和段环为链的操作，然后依次枚举开头点截止点，部分数和前 l-1 部分与第 l 部分的分界点来进行状态转移。注意要初始化，emmm
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis));
using namespace std;
ll a[101], b[101][101][10], s[101][101][10];
int mod(int x){
return ((x % 10) + 10) % 10;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
mem(b, 0);
mem(s, 1);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
a[i + n] = a[i];
}
for(int i = 1; i <= 2 * n; i++){
a[i] += a[i - 1];
}
for(int i = 1; i <= 2 * n; i++){
for(int j = 1; j <= 2 * n; j++){
b[i][j][1] = mod(a[j] - a[i - 1]);
s[i][j][1] = mod(a[j] - a[i - 1]);
}
}
for(int i = 1; i <= 2 * n; i++){
for(int j = i + 1; j <= 2 * n; j++){
for(int l = 2; l <= m; l++){
for(int k = i; k < j; k++){
b[i][j][l] = max(b[i][j][l], b[i][k][l - 1] * b[k + 1][j][1]);
s[i][j][l] = min(s[i][j][l], s[i][k][l - 1] * s[k + 1][j][1]);
}
}
}
}
ll maxl = 0, minl;
mem(&minl, 1);
for(int i = 1; i <= n; i++){
maxl = max(maxl, b[i][i + n - 1][m]);
minl = min(minl, s[i][i + n - 1][m]);
}
cout << minl << endl << maxl << endl;
return 0;
}
