111

༺དༀ༒清樾༒ༀཌ༻（三角洲a）

2025-07-22 18:53:34

发布于：浙江

12阅读

0回复

0点赞

前缀和数组：前 $i$ 和数之和

pre[i]=pre[i-1]+a[i]

for(int i=1;i<=n;i++){
    pre[i]=pre[i-1]+a[i];
}

a[L,R]的和

for(int i=1;i<=n;i++){//进行n次区间和
    int L,R;
    cin>>L>>R;
    cout<<pre[R]-pre[L-1]<<endl;
}

回原数组

for(int i=1;i<=n;i++){
    a[i]=pre[i]-pre[i-1];
}

对于原数组区间 a[l,r] 整体加 a 时，差分数组只需要修改第 l 项 (+a) 和第 r+1 项 (-a)

差分数组：d[i]=a[i]-a[i-1];

前缀和数组和做差分操作得到原数组

差分数组做前缀和操作得到原数组

原数组做前缀和操作得到前缀和数组

原数组做差分操作得到差分数组

变差分数组

    for(int i=1;i<=n;i++){
        d[i]=a[i]-a[i-1];
    }

对于原数组区间 a[l,r] 整体加 a 时，差分数组只需要修改第 l 项 (+a) 和第 r+1 项 (-a)

差分数组：d[i]=a[i]-a[i-1];

前缀和数组：前 $i$ 和数之和

pre[i]=pre[i-1]+a[i]

for(int i=1;i<=n;i++){
    pre[i]=pre[i-1]+a[i];
}

$~~~$ $~~~$
$~~~$
$~~~$
$~~~$
$~~~$
$~~~$
$~~~$
$~~~$
$~~~$
$~~~$
$~~~$
$~~~$
$~~~$
$~~~$
$~~~$
$~~~$

720晚笔记

T1

#include <iostream>
#include <string>
using namespace std;
struct student {
	string name;
	int weight;
} a[110];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i].name >> a[i].weight;
	}
	for (int i = 0; i < n; i++) {
		//  格式化输出：姓名->体重
		cout << a[i].name << "->" <<a[i].weight << '\n';
	}
	return 0;
}

T2

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
struct Stu{
	string name;
	double score;
	int age;
	int sx;//输入顺序 
}a[10010];
//按照成绩从大到小进行排名。如果有同学的成绩相同，则后输入的同学先输出。
bool cmp(Stu x,Stu y){
	if(x.score!=y.score) 
		return x.score >y.score;
	else 
		return x.sx>y.sx;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].name>>a[i].score>>a[i].age;
		a[i].sx=i;
	}
	sort(a+1,a+n+1,cmp);//排序 
	for(int i=1;i<=n;i++){
		cout<<a[i].name<<" "<<a[i].age<<endl;
	}
	return 0;
}

T3

#include<bits/stdc++.h>
using namespace std;
struct mouse{//结构体存储小白鼠的信息
	int w;//体重
    string c;//帽子颜色
}arr[110];//结构体数组
bool cmp(mouse a,mouse b){//排序函数
	return a.w<b.w;//按体重小的在前排序
}
int main(){
	int n;
    cin>>n;//n只老鼠
    for(int i=1;i<=n;i++){
    	cin>>arr[i].w>>arr[i].c;//输入第i项的体重和帽子颜色
    }sort(arr+1,arr+n+1,cmp);//按照题目规则排序
    for(int i=1;i<=n;i++){//排好序后在前的先输出
    	cout<<arr[i].c<<endl;//输出帽子颜色即可
    }
}

T4

#include<bits/stdc++.h>
using namespace std;
struct node{//定义新结构体，存储货物信息
	int a;//单件重量
    int b;//单件价值
}arr[100100];//定义结构体数组
bool cmp(node a,node b){//按照对应结构体创建排序规则
	if(a.a!=b.a)return a.a<b.a;//如果重量不相等，重量轻的在前
    else return a.b>b.b;//如重量相等则价值大的在前
}int main(){
	int n,k;//定义并输入n与k
    cin>>n>>k;
    for(int i=1;i<=n;i++){
    	cin>>arr[i].a>>arr[i].b;//输入每一项的重量和价值
    }sort(arr+1,arr+n+1,cmp);//按照题目对应规则排序
    cout<<arr[k].a<<" "<<arr[k].b;//输出第k项的信息
}

T5

#include<bits/stdc++.h>
using namespace std;
struct sh{//结构体sh记录商品
	int id;//物品id
    int v;//物品价值
}a[100100];//数组
bool cmp(sh a,sh b){//结构体sh的两个元素进行排序
	if(a.v!=b.v)return a.v<b.v;//先买价格低的
    else return a.id>b.id;//如价格相同按id排序，id大的优先
}int main(){
	int n,m;//输入n和m
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	cin>>a[i].v;//输入数组a的第i项的价格
        a[i].id=i;//for循环的i即为id
    }
    sort(a+1,a+n+1,cmp);//排序
    for(int i=1;i<=n;i++){
    	if(m>a[i].v){//如果妈妈带的钱还够
        	cout<<a[i].id<<endl;//输出
            m-=a[i].v;//减去对应的钱
        }
        else break;//如果不够则结束循环
    }
    

}

T6

#include<bits/stdc++.h>
using namespace std;
bool cmp(double a,double b){
	return a>b;//身高更高的在前面
}
int main(){
	double male[40],female[40];//存储男生身高和女生身高
    int cntm=0,cntf=0,n;//存储男生人数和女生人数
    cin>>n;
    for(int i=1;i<=n;i++){
    	string p;//每轮for循环都定义字符串p，存储当前输入的男女情况
        cin>>p;//输入p
        if(p=="male"){//如果p是男
            double q;//定义存储身高的浮点数q
            cin>>q;
            cntm++;//男生+1
            male[cntm]=q;//男身高数组对应项设为q
        }
        else if(p=="female"){//如p为女性
            double q;//定义存储身高的浮点数q
            cin>>q;
            cntf++;//女生+1
            female[cntf]=q;//女生对应项设为身高q
        }
    }sort(male+1,male+cntm+1);//男生数组按规定排序
    sort(female+1,female+cntf+1,cmp);//女生数组按规定排序
    for(int i=1;i<=cntm;i++){//先输出男
    	printf("%.2f ",male[i]);//保留2位小数格式化输入输出（已按从小到大排序）
    }for(int i=1;i<=cntf;i++){//再输出女
    	printf("%.2f ",female[i]);//保留2位小数格式化输入输出（已按从大到小排序）
    }
}

作业T11

#include<bits/stdc++.h>
using namespace std;
struct oldill{//存储老人
    string name;//老人名字
    int year;//老人年龄
    int id;//老人的取号顺序
}arr[220];//定义一个长度为220的数组存储老人
struct yill{//存储小于60岁的人
    string name;//名字
    int year;//年龄
    int id;//取号顺序
}ass[220];
bool cmpy(yill a,yill b){
    return a.id<b.id;//年轻人按照取号顺序排序
}
bool cmpo(oldill a,oldill b){ 
    return a.id<b.id;//老人按照取号顺序排序
}
int main(){
    int n,cntold=0,cnty=0;//存储n名病人，存储老人和年轻人，老人和年轻人的数量初始化为0
    cin>>n;
    for(int i=1;i<=n;i++){
        string a;
        cin>>a;//定义并接受当前人姓名
        int p;
        cin>>p;//定义并接受当前人年龄
        int pid;
        cin>>pid;//定义并接受当前人取号顺序
        if(p>60){
            cntold++;//老人数量+1
            arr[cntold].name=a;//名字
            arr[cntold].year=p;//年龄
            arr[cntold].id=pid;}//如果是老人，把对应元素存储到老人数组
        else {
            cnty++;//年轻人数量+1
            ass[cnty].name=a;
            ass[cnty].year=p;
            ass[cnty].id=pid;//同上
        }//如果不是老人（年轻人），存到年轻人数组
    }sort(arr+1,arr+cntold+1,cmpo);//老人数组按照题规则排序
     sort(ass+1,ass+cnty+1,cmpy);//年轻人数组按照题规则排序
    for(int i=1;i<=cntold;i++){//先输出老人，因为题目规定老人优先
        cout<<arr[i].name<<endl;//输出每一个老人的名字，并换行
    }for(int i=1;i<=cnty;i++){//题目要求再输出年轻人
        cout<<ass[i].name<<endl;//按照题目规定顺序输出年轻人的顺序
    }
}

719笔记

//冒泡、选择、插入，桶排序 
#include<bits/stdc++.h>
using namespace std;
int a[100] ;//数组元素的范围 
int main(){
	//10
	//1 13 12 15 4 12 13 13 15 4
	//10
	//a b c d b c d x y z
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		char x;
		cin>>x;
		a[x-'a']++;//桶标记（桶计数） 
	} 
	for(int i=0;i<26;i++){
		//a:x
		//b:y
		if(a[i]>0) cout<<char(i+'a')<<":"<<a[i]<<endl;
	} 
	return 0;
}