1025普及组模拟考试
卑微小蒟蒻在线被吊打
模拟赛总结
第一题美食街
1.美食街 (street.cpp) 【问题描述】 水宝宝的美食街开始营业喽 美食街八大菜肴：烤绿鸟（主食），拔丝 QAQ 套餐（副食），红烧 KMP（主菜）， Treap 刺身（副菜），油炸内存条（小吃），奶油 CPU（甜品），SPFA 奶盖（饮品），冰镇 机油（饮品） 水宝宝美食街开张第二天，wza 神犇来到水宝宝美食街，却被琳琅满目的食品吓住 了，他急需知道水宝宝的美食街有没有他想吃的东西 给出 n 个食物编号,然后有 m 个询问,每个询问一个整数,询问该整数是否在 n 个食物 编号中出现过,保证编号为正整数
【输入格式】 输入文件名为 street.in。 第一行：n 第二行：m 第三行：n 个询问的编号 第四行：m 个询问的编号
【输出格式】 输出文件名为 street.out。 一共 m 行,若出现则输出”YES”,否则输出”NO”
【说明】 对于 30%的数据,1<=n,m<=1000 对于 60%的数据,1<=n,m<=10000 对于 100%的数据,1<=n,m<=200000 所有数据<=1e17
一看到所有数据小于1e17,就明白了，桶装不下。所以为了节约时间，就把目光投向了二分。其实就是一个二分模版题啦，接下来，放代码（注意，这题如果时间卡1秒，就要加快读呢）
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m; 4 unsigned long long a[200009],x,lc=100000000000000002,rc,mid; 5 inline ll read(){ 6 ll x=0,f=1; 7 char ch=getchar(); 8 while(ch<'0'|| ch>'9'){ if(ch=='-') f=-1;ch=getchar();} 9 while(ch>='0'&& ch<='9'){ x=x*10+ch-'0';ch=getchar();} 10 return x*f; 11 } 12 int main(){ 13 // freopen("street.in","r",stdin); 14 // freopen("street.out","w",stdout); 15 n=read();m=read(); 16 for(int i=1;i<=n;i++){ 17 a[i]=read(); 18 lc=min(lc,a[i]); 19 rc=max(rc,a[i]); 20 } 21 sort(a+1,a+n+1); 22 for(int i=1;i<=m;i++){ 23 x=read(); 24 if(x<lc||x>rc) cout<<"NO"<<endl; 25 else{ 26 int l=1,r=n; 27 while(1){ 28 if(l==r){ 29 if(a[l]==x) cout<<"YES"<<endl; 30 else cout<<"NO"<<endl; 31 break; 32 } 33 mid=(l+r)>>1; 34 if(a[mid]<x) l=mid+1; 35 else r=mid; 36 } 37 } 38 } 39 return 0; 40 }
第二题采访
2. 采访 (interview.cpp) 【问题描述】 有 n 个人站成一排，水宝宝要采访其中一些人“你幸福吗？”。但是相邻两个人不 能都被采访，否则这两个人就会因为相互影响而说出不真实的回答。shui 想知道一共有 多少种满足条件的采访方法呢？(可以不选)
【输入格式】 输入文件名为 interview.in。 一行一个 n。
【输出格式】 输出文件名为 interview.out。 一行表示答案。
【说明】 对于 30%的数据，1<=n<=10 对于 60%的数据，1<=n<=100 对于 100%的数据，1<=n<=1000
分析一下问题，显而易见，这是斐波那契数列呢2 3 5 8 13。。。但是请观察它的数据范围，小于等于1000，说明如果只是用unsigned long long会爆掉，所以这是斐波那契+高精加法，很容易代码实现
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 const int power = 9; 5 const int base = pow(10,power); 6 const int MAXL = 30001; 7 char a[MAXL],b[MAXL]; 8 struct node{ 9 ll a[MAXL]; 10 int part; 11 node(){ memset(a,0,sizeof(a));} 12 node(string s){ 13 memset(a,0,sizeof(a)); 14 int len=s.size(); 15 part=(len-1+power)/power; 16 for(int i=len-1,k=0,t=0,w;i>=0;w*=10,i--,k++){ 17 if(k%power==0){ w=1,t++;} 18 a[t]+=w*(s[i]-'0'); 19 } 20 } 21 void re() { reverse(a+1, a+part+1); } 22 void add(int r){if(r||part) a[++part]=r;} 23 void print(){ 24 printf("%d",a[part]); 25 for(int i=part-1;i>0;i--) printf("%0*d",power,a[i]); 26 } 27 }p,q,ans; 28 node operator + (const node &p,const node &q){ 29 node c; 30 c.part=max(p.part,q.part); 31 for(int i=1;i<=c.part;i++){ 32 c.a[i]=c.a[i]+p.a[i]+q.a[i]; 33 c.a[i+1]+=c.a[i]/base; 34 c.a[i] %=base; 35 } 36 if(c.a[c.part+1]) ++c.part; 37 return c; 38 } 39 int main(){ 40 // freopen("interview.in","r",stdin); 41 // freopen("interview.out","w",stdout); 42 int n; 43 cin>>n; 44 string a,b;a="2",b="3"; 45 if(n==1){cout<<a;return 0;} 46 if(n==2){cout<<b;return 0;} 47 p=node(a),q=node(b); 48 for(int i=1;i<=n-2;i++){ 49 ans=p+q; 50 p=q;q=ans; 51 } 52 ans.print(); 53 return 0; 54 }
第三题值周
【问题描述】 JC 内长度为 L 的马路上有一些值周同学，每两个相邻的同学之间的间隔都是 1 米。 我们可以把马路看成一个数轴，马路的一端在数轴 0 的位置，另一端在 L 的位置； 数轴上的每个整数点，即 0,1,2,…L，都有一个值周同学。 由于水宝宝有用一些区间来和 ssy 搞事情，所以为了避免这种事走漏风声，水宝宝要踹 走一些区域的人。这些区域用它们在数轴上的起始点和终止点表示。 已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要 把这些区域中的人（包括区域端点处的两个人）赶走。 你的任务是计算将这些人都赶走后，马路上还有多少个人
【输入格式】 输入文件名为 move.in。 第一行有 2 个整数 L 和 M，L 代表马路的长度，M 代表区域的数目，L 和 M 之间用一个空 格隔开。 接下来的 M 行每行包含 2 个不同的整数，用一个空格隔开，表示一个区域的起始点和终 止点的坐标
【输出格式】 输出文件名为 move.out。 1 个整数，表示马路上剩余的人的数目。
【数据规模与约定】 对于所有的数据，1≤L≤100000000 对于 30%的数据，1<=M<=100 对于 60%的数据，1<=M<=1000 对于 100%的数据，1<=M<=100000
这道题我也不知道我当时怎么想的，就打了个暴力，结果爆了个零。。。
然后改的时候我感觉排序可以，差分也可以
1 #include<bits/stdc++.h> 2 using namespace std; 3 int l,n,k,tot; 4 struct node{ 5 int e,b; 6 }a[100009],ans[100009]; 7 bool cmp(node x,node y){ 8 return x.b>y.b; 9 } 10 int main(){ 11 // freopen("move.in","r",stdin); 12 // freopen("move.out","w",stdout); 13 cin>>l>>n; 14 for(int i=1;i<=n;i++){ 15 cin>>a[i].b>>a[i].e; 16 } 17 sort(a+1,a+1+n,cmp); 18 k++; 19 ans[k].e=a[1].e; 20 ans[k].b=a[1].b; 21 for(int i=1;i<=n;i++){ 22 if(a[i].e>ans[k].b){ 23 if(a[i].b<ans[k].b) ans[k].b=a[i].b; 24 } 25 else{ 26 k++; 27 ans[k].e=a[i].e; 28 ans[k].b=a[i].b; 29 } 30 } 31 for(int i=1;i<=k;i++){ 32 tot+=ans[i].e-ans[i].b+1; 33 } 34 cout<<l-tot+1; 35 return 0; 36 } 37 //500 3 38 //150 300 39 //100 200 40 //470 471
第四题吃西瓜
【问题描述】 没事就来吃个西瓜？ 水宝宝是一个不争气的宝宝，所以口水流了下来…… 吃西瓜当然要切啦，水宝宝每 刀都是笔直地切下去，并且在切完后才会把一块块的西瓜分开。 那么：将西瓜切 n 刀最多能切成几块呢？ 答案可能有点大，请对 10^9+7 取模。 【输入格式】 输入文件名为 watermelon.in。 多组数据，第一行一个 T 表示数据组数 接下来 T 行，每行一个数 n，表示要把西瓜切 n 刀 【输出格式】 输出文件名为 watermelon.out。 T 行，每行一个数对应把西瓜切 n 刀的答案【数据规模与约定】 对于 10% 的数据，满足 n≤5。 对于 50% 的数据，满足 n≤10000。 对于 100% 的数据，满足 n≤10^9,T≤100。
这明明就是个神奇的小学数学题嘛！！！那你考这个就是想虐我是吧 哼
很显然，切的刀数与切出来的块数的联系是一个三次方程，（毕竟是个三维空间），切一刀2，切两刀4，切三刀8，切四刀15（我就是这里模拟错了，当时是真没想到它怎样用四刀切出15块）解方程ing 嘿嘿
算出来是n3+5*n呢，所以找出规律后的代码就是有手就行
期待（星星眼）鬼知道我在期待着啥