小美的游戏
题目描述
运行代码
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int main() { long long int a,b,sum=0,n=1e9+7; cin>>a>>b; long long int s[N]; for(int i=0;i<a;i++){ cin>>s[i]; } sort(s,s+a); for(int i=a-1;i>a-b-1;i--){ s[i-1]*=s[i]%n; s[i]=1; } for(int i=0;i<a;i++){ sum+=s[i]%n; } sum=sum%n; cout<<sum; }
代码思路
- 排序:使用
sort(s, s+a)对数组s进行升序排序。这是关键步骤之一，因为代码后续逻辑依赖于排序后的数组顺序。 - 计算乘积和:
从数组尾部开始（即最大元素开始），逆序遍历数组。因为乘积和只关心连续子数组，所以从大到小乘可以避免重复计算。对于每个i（从a-1到a-b），执行以下操作： s[i] = 1：将当前元素置为1，以避免它在下一轮迭代中再次参与乘法（因为乘积计算已经完成）s[i-1] *= s[i] % n：将当前元素与前一个元素的乘积对n取模，然后存回s[i-1]。这一步实际上是在计算一个降序子数组中连续b个元素的乘积，然后将乘积累加到前面的元素上，同时避免了不必要的重复计算。- 累加并取模:遍历整个数组
s[]，累加所有元素的值到sum，每次累加后对n取模，确保结果不会溢出。
小美的01串翻转
题目描述
运行代码
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int p[N],c,a[N],b[N]; int main(){ char s; while(cin>>s){ if(s=='1')p[++c]=1; else if(s=='0')p[++c]=0; else break; } for(int i=1;i<=c;i++){ a[i]=a[i-1]; b[i]=b[i-1]; if(p[i]==i%2)a[i]++; else b[i]++; } int sum=0; for(int i=1;i<=c;i++){ for(int j=i;j<=c;j++){ sum+=min(a[j]-a[i-1],b[j]-b[i-1]); } } cout<<sum; return 0; }
代码思路
- 读取输入:循环读取字符直至遇到字符 '2' 结束，遇到 '1' 时在数组
p[]中存储 1，遇到 '0' 时存储 0。 - 计算前缀和:遍历
p[]，计算两个前缀和数组a[]和b[]。
b[i]类似地，记录位置为偶数且字符为 '0' 的累计数量。注意，这里的初始化a[i]=a[i-1]和b[i]=b[i-1]实际上未改变前缀和的正确计算，因为正确初始化应直接设置为0。a[i]记录从序列开头到当前位置 i（包括 i）为止，位置为奇数且字符为 '1' 的累计数量。
- 统计子串:双重循环遍历所有子串范围，计算满足条件的子串个数。
对于每个子串[i, j]，计算 '1' 的数量和奇数位置数量之差与 '0' 数量和偶数位置数量之差的较小值，累加到sum中。这里用到了min(a[j]-a[i-1], b[j]-b[i-1])来间接计算子串满足条件的数量，但实际上表达式逻辑可能与问题描述不符，正确逻辑应是检查奇偶性与字符值的一致性。
