T2 知识点和训练

第 4 题：差分求和 公式推导：

第 4 题：差分求和 答案：

方法：差分公式

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n; 
    int a[500000]; 
    for (int i = 0; i < n; ++i)
        cin >> a[i]; 

    long long total_diff = 0; // 用于存储所有差值的总和
    long long prefix_sum = 0; // 前缀和，用于记录数组元素从开始到当前位置的累加和
    long long first_diff = 0; // 存储第一个差值（即 a[1] - a[0]）

    for (long long j = 0; j < n; ++j) {
        if (j > 0) {
          // 计算当前差值：a[j] * j - prefix_sum，a[j] * j 表示当前元素 a[j] 在位置 j 的加权值，prefix_sum 是前 j-1 个元素的累加和
            long long current_diff = a[j] * j - prefix_sum;  
            total_diff += current_diff;                     // 将当前差值累加到总差值中
           
            if (j == 1) {
                first_diff = a[j] - a[j - 1];    // 当 j == 1 时，计算第一个差值 a[1] - a[0]
            }
        }
        prefix_sum += a[j]; // 更新前缀和，加入当前元素 a[j]
    }

    // 计算最终结果：第一个差值减去 (总差值 - 第一个差值)
    // 相当于 2 * first_diff - total_diff
    long long result = first_diff - (total_diff - first_diff);

    cout << result << endl; 
    return 0;
}

T2 知识点和训练

第 3 题：【模板】差分 答案：

方法：差分公式

#include <bits/stdc++.h>
using namespace std;

int main() {
   
    long long a[100005], d[100005];
    int n, m;
    cin >> n >> m;
        
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];          // 读取初始数组并初始化差分数组
        d[i] = a[i] - a[i-1]; // 构造差分数组
    }
    
    while (m--) {        // 处理 m 次操作
        int l, r;
        long long k;
        cin >> l >> r >> k;
        d[l] += k;         // 区间 [l, r] 起始处加 k
        d[r+1] -= k;      // 区间 [r+1, n] 减 k        可以理解为公交车上下乘客
    }
        
    for (int i = 1; i <= n; ++i) {      // 通过差分数组前缀和恢复原数组
        a[i] = a[i-1] + d[i];               // a[i] = d[1] + ... + d[i]
        cout << a[i] << " ";            // 输出结果
    }
    
    return 0;
}

T2 知识点和训练

第 2 题：惆怅的希蒙 答案：

方法：前缀和公式

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    if (m == 0) {// 特殊情况：m = 0
        cout << 0 << endl;
        return 0;
    }
    
    int a[3000001]; // 根据题目最大 n = 3*10^6
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    long long sum = 0;
    for (int i = 0; i < m; ++i) {// 计算第一个窗口的和
        sum += a[i];
    }
    
    long long min_sum = sum; // 初始化最小值
    
    for (int i = m; i < n; ++i) {
        sum = sum - a[i - m] + a[i]; //滑动窗口，减去窗口左端，加上右端
        if (sum < min_sum) {
            min_sum = sum; // 更新最小值
        }
    }
    
    cout << min_sum << endl;
    return 0;
}

T2 知识点和训练

第 1 题：【模板】前缀和 答案：

方法：前缀和公式

#include <bits/stdc++.h>
using namespace std;

int main() {
    
    int n, q;
    cin >> n >> q;
    
    long long a[100001], s[100001]; // n <= 10^5
    s[0] = 0; // 前缀和边界
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s[i] = s[i-1] + a[i]; // 计算前缀和
    }
    
    while (q--) { // 处理 q 次查询，用for循环也OK
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l-1] << endl; // 区间和
    }
    
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n,m;
    int a[100005];
    cin>>n>>m;
    for(int i=0;i<n;++i){
        cin>>a[i];
    }
    if(m==0){
        cout<<0<<endl;
        return 0;
    }
    long long nowsum=0;
    for(int i=0;i<m;++i){
        nowsum+=a[i];
    }
    long long minsum=nowsum;
    for(int i=m;i<n;++i) {
        nowsum=nowsum+a[i]-a[i-m];
        if(nowsum<minsum){
            minsum=nowsum;
        }
    }
    cout<<minsum<<endl;
    return 0;
}

T1 知识点和训练

第 7 题：参考讲解和答案：

方法：数学

#include <bits/stdc++.h>
using namespace std;

int main() {	
	int a, b, c;
	cin >> a >> b >> c;
	cout << 0.2 * a + 0.3 * b + 0.5 * c;
	return 0;
}

T1 知识点和训练

第 6 题：参考讲解和答案：

方法1：遍历统计

#include<bits/stdc++.h>
using namespace std;

int main(){
    int cnt = 0; 
    string s; 
    getline(cin, s); // 读取一行输入的字符串（包括空格）
    for(int i = 0; i < s.size(); i++){ // 遍历字符串的每个字符
        if(s[i] == ' '){ 
            continue;
        }
        else{
            cnt++;
        }
    }
    cout << cnt; 
    return 0; 
}

T1 知识点和训练

第 5 题：参考讲解和答案：

方法1：循环模拟

#include <bits/stdc++.h>
using namespace std;
int main()
{	
	int n,t=0,id=0;//n个苹果，t代表所需的天数，id代表拿走编号为 n的苹果是在第几天
	cin>>n;
	while(n){
		t++;  //第t轮取苹果
		if(n%3==1 && !id) id=t;  //n被独立分组且最后一个苹果尚未取走，这时的 t是答案
		n=n-((n+2)/3);  //每次被拿走 n的1/3，(n+2)/3为 n除以3向上取整 
	}
	cout<<t<<" "<<id;
	return 0;
}

T1 知识点和训练

第 4 题：参考讲解和答案：

方法1：循环方法

#include <bits/stdc++.h>
using namespace std;
 
long long a,b,n=1;
 
int main(){
    cin>>a>>b;
    if(a==1){// 如果a等于1，任何次幂的结果都是1，直接输出1并结束程序；如果没有该特判语句，则会出现超时情况
        cout<<1<<endl;
        return 0;
    }
    for(int i=1;i<=b;++i)
		if(n*a<=1e9)n*=a;
		else{
			cout<<-1<<endl;
			return 0;
		}
    cout<<n<<endl;
    return 0;
}

超时的原因：

方法2：函数法

#include<bits/stdc++.h>
using namespace std;
int main(){
	long int a;
	int b;
	cin>>a>>b;
	long long c=pow(a,b);
	if(c<0||c>1000000000){
		cout<<-1;
		return 0;
	}
	cout<<c;
	return 0;
}

T1 知识点和训练

第 3 题：参考讲解和答案：

方法1：数学方法

#include <bits/stdc++.h> 
using namespace std; 
int main() {
    int n, L, R; // 定义变量：n（除数）、L（范围左边界）、R（范围右边界）
    cin >> n >> L >> R; // 从用户输入读取n、L、R的值
    // 计算小于等于R的n的最大倍数，再减1得到最大可能的余数
    int max_remainder = (R / n) * n - 1;
    // 判断max_remainder是否大于等于L（即是否在[L, R]范围内）
    if (max_remainder >= L) {
        cout << n - 1 << endl; // 如果满足条件，最大余数为n-1
    } else {
        cout << R % n << endl; // 否则，最大余数为R除以n的余数
    }
    return 0; 
}

方法2：暴力法（存在超时）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,l,r;
    cin >> n >> l >> r; 
    int ans=0;
    for (int i=l;i<=r;i++){
        ans=max(ans,i%n);
    }
    cout<<ans;
    return 0;
}

T1 知识点和训练

第 2 题：参考讲解和答案：

方法1：字符数组

#include<bits/stdc++.h>
using namespace std;
int cnt;
int main(){
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++)
		if(s[i]=='1')
			cnt++;
	cout<<cnt;
	return 0;
}

方法2：位运算

#include<cstdio>
using namespace std;
int ans;
int main() {
	for (int i = 0; i < 8; i++) {
		if (!(getchar() ^ '1'))ans++;
	}
	printf("%d", ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n;
    cin>>n;
    if(n & 1){
    	cout<<"-1";
	}else{
		for(int i = 23; i >= 1; i--){
			if(n >> i & 1) cout<<(1 << i)<<" ";
		}
	}
	return 0;
}

T1 知识点和训练

第 1 题：参考讲解和答案：

方法1：迭代法

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int num;
	scanf("%d",&num);
    if(num%2==1)//判断能否拆分
    {
    	printf("%d\n",-1);
    	return 0;//直接退出程序
	}
	for(int i=25;i>=1;i--)//从大到小判断,最大不可能超过2^25 
		if((1<<i)<=num)//输出,1<<i代表1*2^i
		{
			printf("%d ",1<<i);//输出这个数
			num-=(1<<i);//减去它
		}
	puts("");//输出换行
	return 0;
}

方法2：位运算

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int num;
	scanf("%d",&num);
    if(num%2==1)//判断能否拆分
    {
    	printf("%d\n",-1);
    	return 0;//退出程序
	}
	/*将一个数转化为2进制,如6=1*2^2+1*2^1+0*2^0=110(2),也就是从最高位开始判断,
	  第i为如果有1,那么这个数就有一个2^i*/
	for(int i=25;i>=1;i--)//
	    if((num>>i)&1)//看num左移i位后的最高位，也就是第i位是否有1，可以自己画图理解
		    printf("%d ",1<<i);//输出这个数
    puts("");//输出换行
	return 0;
}

方法3：递归

#include<bits/stdc++.h>
using namespace std;
void split(int n)//分解函数
{
	if(n==0)return;//递归边界
	int i=1;//从1开始
	while(n/2>=i)//从大判断 
	    i<<=1;//等同于i*=2
	printf("%d ",i);
	split(n-i);//递归处理剩下的 
}
int main()
{
    int num;
	scanf("%d",&num);
    if(num%2==1)//判断能否拆分
    {
    	printf("%d\n",-1);
    	return 0;
	}
	split(num);//调用分解函数
	puts("");//输出换行
	return 0;
}

班级同学示例：

#include<bits/stdc++.h>  // 包含所有C++标准库
using namespace std;     // 使用标准命名空间，避免写std::

int main(){
    int a;              // 声明整数变量a用于存储输入
    cin>>a;             // 从用户输入读取数字存入a
    
    // 检查输入的数字是否为奇数
    if(a%2!=0){
        cout<<-1;       // 如果是奇数，输出-1
        return 0;       // 结束程序
    }
    
    // 当剩余值大于0时继续循环
    while(a>0){
        int b=2;        // 初始化b为最小的2的幂（2^1）
        
        // 寻找不大于当前剩余值的最大2的幂
        while(a>=2*b){  // 注意：这里原代码有错误，应为2*b
            b*=2;       // b不断乘2直到超过剩余值
        }
        
        cout<<b<<" ";   // 输出找到的2的幂
        a-=b;          // 从剩余值中减去这个2的幂
    }
    
    return 0;          // 程序成功结束
}