【蓝桥杯1】栈

例一：求和（2022 省赛 2080）

时间限制：1s????????内存限制：256MB

题目描述：

给定n个整数,求它们两两相乘再相加的和，即:

输入：

输入的第一行包含一个整数n

第二行包含n个整数

输出：

输出一个整数S，表示所求的和。请使用合适数据类型进行运算。

样例输入：

4

1 3 6 9

样例输出：

117

提示：对于30%的数据，????????

对于所有测评用例，

1.分析：

如何降低时间复杂度？

这样就变为一重循环，时间复杂度降为O（n）

2.代码实现：

#include<iostream>
using namespace std;

int main(){
    int n,*data;
    long s=0,sum=0;
    cin>>n;
    data=new int[n];
    for(int i=0;i<n;i++){
        scanf("%d",&data[i]);
        sum+=data[i];
    }
    for(int i=0;i<n;i++){
        sum-=data[i];
        s+=data[i]*sum;
    }
    cout<<s;
    delete [] data;
    return 0;
}

例二：选数异或(2022 省赛 2081)

时间限制：1s????????内存限制：256MB

题目描述：

给定一个长度为n的数列和一个非负整数x，给定m次查询，每次询问能否从某个区间[l,r]中选择两个数，使得它们的异或等于x。

输入：

输入的第一行包含三个整数n，m，x。第二行包括n个整数。接下来m行，每行包括两个整数,表示询问区间

输出：

对于每个询问，如果该区间内存在两个数的异或为x，则输出yes，否则输出no。

样例输入：

4 4 1

1 2 3 4

1 4

1 2

2 3

3 3

样例输出：

yes

no

yes

no

?1.分析：

如果a^b==x,那么a^x==b,b^x==a

为每个元素a[i]求出p[i]=x^a[i];

对于[l,r]范围，查看a[i]所对应的p[i]是否在[l,r]范围内，也就是有一个a[j]=p[i]

如果[l,r]的一个子集符合条件，那么[l,r]自然也符合条件。

问题转化为，求以一个数为右端口时最大的区间左端口

补充：C++中的map

map是STL的一个关联容器，它提供一对一的hash。

• 第一个可以称为关键字(key)，每个关键字只能在map中出现一次；
• 第二个可能称为该关键字的值(value)；

map以模板方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。

Map主要用于一对一映射(one-to-one)的情況。

map内部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能。

在map内部所有的数据都是有序的。

比如一个班级中，每个学生的学号跟他的姓名就存在着一对一映射的关系。

在map中查找元素：

1. map[key]

通过键直接查找，如果存在就返回对应的值，如果不存在则返回0

2. map.find(key)

返回key对应的迭代器，如果不存在则返回map.end()，时间复杂度为O(logN)

3. map.count(key)

如果key存在就返回1，如果不存在则返回0。

补充：ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

在C++中关闭输入输出流的同步，以提高程序的执行效率。

1. 提高执行效率：默认情况下，C++的输入输出流与C标准库的输入输出函数是同步的，这会造成一定的性能损失。通过使用ios::sync_with_stdio(0)可以关闭这种同步，从而加快输入输出的速度，提高程序的执行效率。

2. 解绑输入输出流：使用cin.tie(0)和cout.tie(0)可以取消cin与cout之间的绑定，这意味着在进行输入操作时，不需要强行刷新输出缓冲区。这样可以进一步提高程序性能。

3.关闭了同步流（也就是使用这段代码），不能再用cout<<endl。而应该改用cout<<'\n'。

4.不能混用输入输出函数：在使用了这段代码后，应避免使用C标准库的输入输出函数（如printf和scanf），因为这些函数与输入输出流的同步已被关闭。简单来说，关闭了同步流，就不能用scanf和printf。

?

#include<iostream>
#include<map>

using namespace std;
const int N=1e5+5;

long long n,m,x;
int dp[N]={0};
map<long long,int> mp;

int max(int a,int b){
    return a>b?a:b;
}

int main(){
    ios::sync_with_stdio(0);//关闭输入输出流的同步
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m>>x;
    
    for(int i=1;i<=n;i++){
        long long data;
        cin>>data;
        dp[i]=max(dp[i-1],mp[data^x]);
        mp[data]=i;
    }
    
    while(m--){
        int l,r;
        cin>>l>>r;
        if(dp[r]>=l)
            cout<<"yes\n";//这里不能用endl，否则会刷新缓冲区
        else
            cout<<"no\n";
    }
    return 0;
}