当前位置:   article > 正文

【蓝桥杯1】栈_关闭同步流后使用printf

关闭同步流后使用printf

例一:求和(2022 省赛 2080)

时间限制:1s        内存限制:256MB

题目描述:

给定n个整数a_1,a_2,...a_n,求它们两两相乘再相加的和,即:S=a_1*a_2+a_1*a_3+...+a_2*a_3+...+a_{n-1}*a_n

输入:

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

第二行包含n个整数a_1,a_2,...a_n

输出:

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

样例输入:

4

1 3 6 9

样例输出:

117

提示:对于30%的数据,1\leq n\leq 1000        1\leq a_i\leq 100

对于所有测评用例,1\leq n\leq 200000,1\leq a_i\leq 1000

1.分析:

如何降低时间复杂度

S=a_1(a_2+a_3+...+a_n)+a_2(a_3+a_4+...+a_n)+...+a_{n-1}a_n

这样就变为一重循环,时间复杂度降为O(n)

2.代码实现:

  1. #include<iostream>
  2. using namespace std;
  3. int main(){
  4. int n,*data;
  5. long s=0,sum=0;
  6. cin>>n;
  7. data=new int[n];
  8. for(int i=0;i<n;i++){
  9. scanf("%d",&data[i]);
  10. sum+=data[i];
  11. }
  12. for(int i=0;i<n;i++){
  13. sum-=data[i];
  14. s+=data[i]*sum;
  15. }
  16. cout<<s;
  17. delete [] data;
  18. return 0;
  19. }

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

时间限制:1s        内存限制:256MB

题目描述:

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

输入:

输入的第一行包含三个整数n,m,x。第二行包括n个整数A_1,A_2,...,A_n。接下来m行,每行包括两个整数l_i,r_i,表示询问区间[l_i,r_i]

输出:

对于每个询问,如果该区间内存在两个数的异或为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

 

  1. #include<iostream>
  2. #include<map>
  3. using namespace std;
  4. const int N=1e5+5;
  5. long long n,m,x;
  6. int dp[N]={0};
  7. map<long long,int> mp;
  8. int max(int a,int b){
  9. return a>b?a:b;
  10. }
  11. int main(){
  12. ios::sync_with_stdio(0);//关闭输入输出流的同步
  13. cin.tie(0);
  14. cout.tie(0);
  15. cin>>n>>m>>x;
  16. for(int i=1;i<=n;i++){
  17. long long data;
  18. cin>>data;
  19. dp[i]=max(dp[i-1],mp[data^x]);
  20. mp[data]=i;
  21. }
  22. while(m--){
  23. int l,r;
  24. cin>>l>>r;
  25. if(dp[r]>=l)
  26. cout<<"yes\n";//这里不能用endl,否则会刷新缓冲区
  27. else
  28. cout<<"no\n";
  29. }
  30. return 0;
  31. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/煮酒与君饮/article/detail/1005394
推荐阅读
相关标签
  

闽ICP备14008679号