A——眼花缭乱的街市 题目描述 水宝宝的美食街开始营业喽 美食街八大菜肴：烤绿鸟（主食），拔丝QAQ套餐（副食），红烧KMP（主菜），Treap刺身（副菜），油炸内存条（小吃），奶油CPU（甜品），SPFA奶盖（饮品），冰镇机油（饮品） 水宝宝美食街开张第二天，wza神犇来到水宝宝美食街，却被琳琅满目的食品吓住了，他急需知道水宝宝的美食街有没有他想吃的东西
给出n个食物编号,然后有m个询问,每个询问一个整数,询问该整数是否在n个食物编号中出现过,保证编号为正整数 输入描述: 第一行：n
第二行：m
第三行：n个询问的编号
第四行：m个询问的编号 输出描述: 一共m行,若出现则输出"YES",否则输出"NO"
输入 15 3 4 2 1 6 16 4 41 19 37 40 8 71 34 87 47 2 8 198 输出 YES YES NO 说明
对于10%的数据,1<=n,m<=1000
对于30%的数据,1<=n,m<=10000
对于60%的数据,1<=n,m<=200000
对于100%的数据,1<=n,m<=1000000
所有数据<=1e17
ps：这些大佬些太凶了嘛，什么题都有简单的做法，，，，brinary_search函数直接就可以查找是否存在这个数，其本质就是二分，由于我不会，所有手写的二分,还有一种查找方法，类似kmp，刚开始我不知道为什么我没写出来，就用的二分,哎，高手在民间啊orz
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn=1000005; ll a[maxn]; int main() { ios::sync_with_stdio(0); cin.tie(0); ll n,m,x; cin>>n>>m; for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n); while(m--) { cin>>x; if(binary_search(a,a+n,x)) puts("YES"); else puts("NO"); } return 0; } #include<bits/stdc++.h> typedef long long ll; ll a[1000005]; using namespace std; //使用二分法查找 /*@param a[],find *@return true/false */ ll Binary_find(ll a[],ll low,ll high, ll find){ ll mid; while(low<=high) { mid = (low+high)/2; if(a[mid] == find) { return true; }else if(a[mid] < find){ low = mid+1; }else{ high = mid-1; } } return false; } int main(){ ll m,n; bool flag; scanf("%d %d",&m,&n); for(ll i=0;i<m;i++){ scanf("%lld",&a[i]); } sort(a,a+m); for(ll i=0;i<n;i++){ ll find; scanf("%lld",&find); flag = Binary_find(a,0,m-1,find); if(flag){ printf("YES\n"); }else{ printf("NO\n"); } } } #include<bits/stdc++.h> using namespace std; long long a[1000005]; struct st { long long x; int id; }; st b[1000005]; int n , m; bool cmp(st a,st b) { return a.x < b.x; } int ans[1000005]; int main() { scanf("%d%d",&n,&m) ; for(int i = 1;i <= n;i++) { scanf("%lld",&a[i]) ; } for(int i = 1;i <= m;i++) { scanf("%lld",&b[i].x);b[i].id = i; } sort(a+1 , a+n+1); sort(b+1 , b+m+1 , cmp); int nt = 1; a[n + 1] = 1e18; for(int i = 1;i <= m;i++) { while(b[i].x > a[nt]) nt++; if(b[i].x == a[nt]) ans[b[i].id] = 1; } for(int i = 1;i <= m;i++) { if(ans[i]) puts("YES"); else puts("NO"); } return 0; }B——采访
题目描述 你是可以看到第二题defriends呢 ----------水货
有n个人站成一排，水宝宝要采访其中一些人“你幸福吗？”。但是相邻两个人不能都被采访，否则这两个人就会因为相互影响而说出不真实的回答。shui想知道一共有多少种满足条件的采访方法呢？(可以不选) 输入描述: 一行一个n。 输出描述: 一行表示答案。 示例1 输入
复制 1 输出
复制 2 示例2 输入
复制 3 输出
复制 5 备注: 对于30%的数据，1<=n<=10
对于50%的数据，1<=n<=100
对于70%的数据，1<=n<=1000
对于100%的数据，1<=n<=30000
p.s 本题会有轻微卡常(虽然std没用O2)，所以请在代码中加"#pragma GCC optimize(2)“(没有引号) PS：大数fib数列，建议python，但本弱鸡不会，后面还有大佬直接数组模拟的代码，但我不熟练，后面去练习下
n=int(input()) a=1 b=1 for i in range(n): c=a+b a=b b=c print(c) #include <bits/stdc++.h> using namespace std; int a[10000]={1,1},b[10000]={1,1},c[10000]; int main() { int n; cin >> n; for(int i=1;i<=n;i++) { int len=max(a[0],b[0])+1; c[1]=0; for(int j=1;j<=len;j++) { c[j+1]=(c[j]+a[j]+b[j])/10; c[j]=(c[j]+a[j]+b[j])%10; } while(len>1&&c[len]==0) len--; for(int j=1;j<=b[0];j++) a[j]=b[j]; a[0]=b[0]; for(int j=1;j<=len;j++) b[j]=c[j]; b[0]=len; } for(int i=b[0];i>=1;i--) cout << b[i]; return 0； }C——值周 题目描述 题目背景 你是能看见第3题的friends哦 ——taoyc
题目描述 JC内长度为L的马路上有一些值周同学，每两个相邻的同学之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0,1,2,…L，都有一个值周同学。 由于水宝宝有用一些区间来和ssy搞事情，所以为了避免这种事走漏风声，水宝宝要踹走一些区域的人。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的人（包括区域端点处的两个人）赶走。你的任务是计算将这些人都赶走后，马路上还有多少个人。 输入描述: 第一行有2个整数L和M，L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。 接下来的M行每行包含2个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标 输出描述: 1个整数，表示马路上剩余的人的数目。 示例1 输入
复制 500 3 150 300 100 200 470 471 输出
复制 298 说明
对于所有的数据，1≤L≤100000000
对于10%的数据，1<=M<=100
对于20%的数据，1<=M<=1000
对于50%的数据，1<=M<=100000
对于100%的数据，1<=M<=1000000
ps：后面去学一下
#include<bits/stdc++.h> using namespace std; int l,t[100000200]; void add(int x,int y) { if(!x)return; for(;x<=l+1;x+=x&-x) t[x]+=y; } int query(int x) { int s=0; for(;x;x-=x&-x) s+=t[x]; return s; } int main() { int m,x,y; scanf("%d%d",&l,&m); while(m--){ scanf("%d%d",&x,&y); add(x+1,1); add(y+2,-1); } int ans=0; for(int i=1;i<=l+1;i++) { ans+=query(i)==0; } printf("%d\n",ans); return 0; } #include<cstdio> #define N 100000007 using namespace std; int L,m,l,r,sum; int cf[N]; int main() { scanf("%d%d",&L,&m); while(m--) { scanf("%d%d",&l,&r); cf[l]++; cf[r+1]--; //差分可以记录有多少暴政的人类砍了这棵树 } for(int i=0,now=0;i<=L;++i) { now += cf[i]; if(now<=0) sum++; } printf("%d",sum); return 0; }D——瓜瓜
题目描述 小杨是我的唯一哦 ——小瓜
大热天的来吃个西瓜？ 水宝宝是一个不争气的宝宝，所以口水流了下来… 吃西瓜当然要切啦，水宝宝每刀都是笔直地切下去，并且在切完后才会把一块块的西瓜分开。 那么：将西瓜切 n 刀最多能切成几块呢？
答案可能有点大，请对 10^9+7 取模。 输入描述: 多组数据，第一行一个T表示数据组数 接下来T行，每行一个数n，表示要把西瓜切n刀 输出描述: T行，每行一个数对应把西瓜切n刀的答案 示例1 输入
复制 3 1 2 3 输出
复制 2 4 8 说明
对于 20% 的数据，满足 n≤5。
对于 40% 的数据，满足 n≤10000。
对于 70% 的数据，满足 n≤10^9。
对于 100% 的数据，满足 n≤10^21，t<=100。 ps:公式题，但要注意数据范围，进行读写优化与取余
#include<bits/stdc++.h> using namespace std; const long long mod=1000000007; char t[55]; int main() { int k; scanf("%d",&k); while(k--) { memset(t,' ',sizeof(t)); cin>>t; int l=strlen(t); long long n=0; for(int i=0;i<l;++i) n=(n*10+t[i]-'0')%mod; long long ans=((((n*n)%mod*n)%mod+n*5%mod+6)%mod*166666668)%mod; cout<<ans<<endl; } return 0; } #include<bits/stdc++.h> using namespace std; typedef long long int_t; const int_t p = 1000000007; int_t read(){ string str;cin>>str; int_t length = str.length(); int_t ans = 0; for(int_t i=0;i<length;i++) ans = (ans * 10 + str[i] - '0') % p; return ans; } int main(){ int_t T;cin>>T; while(T--){ int_t n = read(); cout<<(n * n % p * n % p + 5 * n % p + 6) * 166666668 % p << endl; } }