A 二分查找
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,m,t; const int N=1e6+5; ll num[N]; int main() { ios::sync_with_stdio(false); cin>>n>>m; for (ll i=0;i<n;i++) { cin>>num[i]; } sort(num,num+n); while(m--) { cin>>t; ll x=lower_bound(num,num+n,t)-num; if(x<n&&num[x]==t) puts("YES"); else puts("NO"); } return 0; }B 高精度 斐波那契数列
#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define pb push_back using namespace std; typedef long long LL; typedef double db; string add(string x,string y) { int n=x.length(); int m=y.length(); if(m>n)//为了方便，令y为短的那个数 { swap(x,y); swap(n,m); } string ans; int t=0,c=0,d=n-1; for(int i=m-1;i>=0;i--)//对齐最短的，从尾部相加 { int s=x[d--]-'0'+y[i]-'0'+c,flag=0;//c用于进位，flag标记是否要进位 if(s>9) { s=s-10; flag=1;//标记要进位 } ans+=s+'0';//赋给新串 if(flag)//需要进位则下一位+1 c=1; else c=0; } for(int i=d;i>=0;i--)//将长的剩下的赋给新串 { int s=x[i]+c-'0',flag=0; if(s>9) { s=s-10; flag=1; } ans+=s+'0'; if(flag) c=1; else c=0; } if(c)//最后还剩一位没进 { ans+=1+'0'; } string f; for(int i=ans.length()-1;i>=0;i--)//将字符串翻转 f+=ans[i]; return f; } int main() { string a,b,c; a="2",b="3"; int n; scanf("%d",&n); if(n==1){ cout<<2<<endl; return 0; } if(n==2){ cout<<3<<endl; return 0; } for(int i=3;i<=n;i++){ c=add(a,b); a=b,b=c; } cout<<c<<endl; return 0; }C 差分
#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; }B 零钱兑换 背包问题
#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; const int M=1e5+10; int coin[13]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000}; int dp[M]; int main() { int t; cin>>t; while(t--) { int n; scanf("%d",&n); memset(dp,0,sizeof(dp)); dp[0]=1; for (int i=0;i<13;i++) { for (int j=coin[i];j<=n;j++) { dp[j]=(dp[j]+dp[j-coin[i]])%mod; } } cout<<dp[n]<<endl; } return 0; }砝码与天平 将m转化成w进制，然后从小的位数开始遍历一遍如果为0或1不进行操作，如果为w-1则加上一个数使得当前位数变成0，如果为其他数着就可以直接输出NO，如果没有输出NO 则最后输出YES
#include<bits/stdc++.h> using namespace std; int main() { long long n,m; int t,x; long long a[100]; scanf("%d",&t); while(t--) { scanf("%I64d%I64d",&n,&m); x=0; int flag=0; memset(a,0,sizeof(a)); while(m>0) { a[x++]=m%n; m/=n; cout<<a[x-1]<<endl; } int win=0; for(int i=0; i<x; i++) { if(a[i]==0||a[i]==1) continue; else if(a[i]==n-1) { int k=i+1; int s=1; while(s) { a[k]+=s; s=a[k]/n; a[k]%=n; k++; if(x<k) x=k; } } else { flag=1; break; } } if(flag) printf("NO\n"); else printf("YES\n"); } }进制转换
#include <bits/stdc++.h> using namespace std; const int maxn=5000+100; char hashch[maxn]; int hashnum[maxn]; void init() { char ch; for(int i=0; i<62; i++) { if(i<10) ch=i+'0'; else if(i>=10&&i<36) ch='A'+i-10; else ch='a'+i-36; hashch[i]=ch; hashnum[ch]=i; } } string change(int m,int n,string str) { bool flag; string ans=""; int tmp,quotient,remainder; while(true) { flag=false; remainder=0; string div=""; int len=str.length(); for(int i=0; i<len; i++) { tmp = remainder*m+hashnum[str[i]]; quotient=tmp/n; remainder=tmp%n; if(flag) { div+=hashch[quotient]; } else { if(quotient!=0) { flag=true; div+=hashch[quotient]; } } } ans=hashch[remainder]+ans; str=div; if(flag==false) break; } return ans; }