小美的游戏 小美的01串翻转

小美的游戏

题目描述

运行代码

#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;
}

代码思路

1. 读取输入:循环读取字符直至遇到字符 '2' 结束，遇到 '1' 时在数组 p[] 中存储 1，遇到 '0' 时存储 0。
   
2. 计算前缀和:遍历 p[]，计算两个前缀和数组 a[] 和 b[]。

• b[i] 类似地，记录位置为偶数且字符为 '0' 的累计数量。注意，这里的初始化 a[i]=a[i-1] 和 b[i]=b[i-1] 实际上未改变前缀和的正确计算，因为正确初始化应直接设置为0。
• a[i] 记录从序列开头到当前位置 i（包括 i）为止，位置为奇数且字符为 '1' 的累计数量。

3. 统计子串:双重循环遍历所有子串范围，计算满足条件的子串个数。
   对于每个子串 [i, j]，计算 '1' 的数量和奇数位置数量之差与 '0' 数量和偶数位置数量之差的较小值，累加到 sum 中。这里用到了 min(a[j]-a[i-1], b[j]-b[i-1]) 来间接计算子串满足条件的数量，但实际上表达式逻辑可能与问题描述不符，正确逻辑应是检查奇偶性与字符值的一致性。