过了四题，第一次排名进前1000，打比赛确实可以带来进步，继续加油！
C 智乃买瓜(another version)
原题传送门
官方题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int N = 1e3 + 10, mod = 1e9 + 7;
ll dp[N];
int n, m;
vector<int> ans;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
dp[0] = 1;
cin>>m;
for(int i = 1; i <= m; i ++ ){
cin>>dp[i];
}
for(int i = 1; i <= m; ++ i){
//这里的i代表的是基础质量，就是说如果存在dp[i]，那么说明得出dp[m]的过程中用到了dp[i]，进而就考虑dp[i]和那些数相加得到了dp[m]
while(dp[i]){
ans.push_back(i * 2);//因为质量都是偶数，所以都考虑用了一半的
for(int j = 0; j <= m; ++ j){//这里的j枚举的是质量
if(i + j <= m) dp[i + j] -= dp[j];
//此时背包的基础容量是i，如果i+j<=m就代表m可以装下i+j质量的西瓜，考虑方案数dp[i]时考虑了dp[j]，所以要减去dp[j]的方案数
while(i + j <= m && dp[i + j] < 0) dp[i + j] += mod;
if(i + i + j <= m) dp[i + i + j] -= dp[j];
//此时背包的基础容量是i，如果i+i+j<=m就代表m可以装下i+i+j质量的西瓜，考虑方案数dp[i]时考虑了dp[j]，所以要减去dp[j]的方案数
while(i + i + j <= m && dp[i + i + j] < 0) dp[i + i + j] += mod;
}
}
}
cout<<ans.size()<<endl;
for(int i = 0; i < ans.size(); ++ i){
cout<<ans[i]<<" ";
}
return 0;
}
I 智乃的密码
原题传送门
官方题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int l, r, n;
int limit[4];//记录四种密码元素的最短区间左边界
int a[4][N];
char s[N];
ll ans;
int type(char c){
if(c >= 'A' && c <= 'Z') return 1;
else if(c >= 'a' && c <= 'z') return 2;
else if(c >= '0' && c <= '9') return 3;
else return 0;
}
void presum(int a[]){
for(int i = 1; i <= n; ++ i){
a[i] += a[i - 1];
}
}
int has(int a[], int l, int r){//判断l~r还有没有a[]对应的元素
return a[r] - a[l - 1] > 0;
}
int get_d(){
int temp[4];
memcpy(temp, limit, sizeof temp);//此时limit内装的是i对应的四种密码的最小包含区间
//temp[0]记录的是包含大写字母的区间的左端点
//temp[1]记录的是包含小写字母的区间的左端点
//temp[2]、temp[3]此时的含义与上同
sort(temp , temp + 4);
//排完序后
//temp[0]记录的是四个最小区间中最靠左的左端点，因为只需三种必要元素就可以得到密码，所以temp[0]战略性放弃
return temp[1];//返回可以构成密码的最小区间的左端点
}
int cal(int i){
int L = 1, R = n;
L = max(L, i - r + 1);//L此时记录的是密码长度最长的情况下最左端的端点值
R = min(R, i - l + 1);//R此时记录的是密码长度最短的情况下最左端的端点值
R = min(get_d(), R);//R此时的值更新为能构成区间的最左端的点
return R - L >= 0 ? R - L + 1 : 0;//R-L>0表示以i为右端点，向左延伸长度为r的字符串中，左边部分的无关元素数量大于0,这些无关元素的数量就是可以构成的密码数量
//如果五官元素的数量小于0,表示不能构成密码，返回构成的密码数量为0
}
//妙在利用a数组，以前缀和的形式判断这个区间内有没有密码对应的元素
int main()
{
cin>>n>>l>>r;
scanf("%s", s + 1);
for(int i = 1; i <= n; ++ i){
a[type(s[i])][i] ++ ;//标记s[i]是那种密码
}
for(int i = 0; i < 4; ++ i){
presum(a[i]);//找出每种密码的数量前缀和
}
for(int i = 1; i <= n; ++ i){
for(int j = 0; j < 4; ++ j){//分别判断这四种密码的最小存在区间的区间左端点
while(has(a[j], limit[j] + 1, i)) limit[j] ++ ;//字符串是从1开始记录的，limit数组内的值默认为0，应该+1开始
}
//分别找到i对应的包含四种密码的最短区间
ans += cal(i);//找到以i为右端点的合法的密码数量，遍历每个i，加在一起就是总的密码数量
}
cout<<ans<<endl;
return 0;
}