枚举专题
字符串相关
字符串比较大小是按照字典序排序,例如:aaaaaaaaaaaa和ababa,此时比较大的应该是ababa.
string a;//自动分配内存
a.find();//返回字串在主串中第一次出现的位置
char a[Max_n];
//字符串读入
int n;
string a;
cin>>n;
getchar();//string需要吸收空格
for(int i=1;i<=n;i++){
string b;
getline(cin,b);//遇到空格输入结束
a+=b;
}
cout<<a<<endl;
cout<<a.size()<<endl;
蓝桥杯历届试题–凑算式
//解法一:暴力枚举
#include<cstdio>
#include<map>
#include<iostream>
using namespace std;
const int Max_n=100005;
typedef long long LL;
map<int,int>m;
int main(){
int cnt=0;
for(int a=1;a<10;a++){
for(int b=1;b<10;b++){
for(int c=1;c<10;c++){
for(int d=1;d<10;d++){
for(int e=1;e<10;e++){
for(int f=1;f<10;f++){
for(int g=1;g<10;g++){
for(int h=1;h<10;h++){
for(int i=1;i<10;i++){
if(a!=b&&a!=c&&a!=d&&a!=e&&a!=f&&a!=g&&a!=h&&a!=i&&
b!=c&&b!=d&&b!=e&&b!=f&&b!=g&&b!=h&&b!=i&&
c!=d&&c!=e&&c!=f&&c!=g&&c!=h&&c!=i&&
d!=e&&d!=f&&d!=g&&d!=h&&d!=i&&
e!=f&&e!=g&&e!=h&&e!=i&&
f!=g&&f!=h&&f!=i&&
g!=h&&g!=i&&
h!=i){
int x=b*(100*g+10*h+i)+(100*d+10*e+f)*c;
int y=c*(100*g+10*h+i);
if(a+(double)(x*1.0)/y==10){
cnt++;
}
}
}
}
}
}
}
}
}
}
}
printf("%d\n",cnt);//29
//int m=6+(double)(8*714+3*952)*1.0/(714*3);
//printf("%d\n",m);
//printf("%d\n",5+3/1+972/486);
return 0;
}
//解法二：
int cnt=0;
int a[10]={0,1,2,3,4,5,6,7,8,9};
do{
int x=a[2]*(a[7]*100+a[8]*10+a[9])+a[3]*(a[4]*100+a[5]*10+a[6]);
int y=a[3]*(a[7]*100+a[8]*10+a[9]);
if(a[1]+(x*1.0)/y==10) cnt++;
}while(next_permutation(a+1,a+10));
printf("%d\n",cnt);//29
蓝桥杯历届试题–生日蜡烛
//解法一
//我没假设从i岁开始过生日j岁结束
for(int i=1;i<236;i++){
for(int j=i;j<236;j++){
int sum=(i+j)*(j-i+1)/2;
if(sum==236) printf("%d\n",i);//26
}
}
//解法二:
for(int i=1;i<236;i++){
int sum=0;
for(int j=i;j<236;j++){
sum+=j;
if(sum==236){
printf("%d\n",i);//26
return 0;
}
}
}
蓝桥杯历届试题–排他平方数
LL res;
for(int a=1;a<10;a++){
for(int b=0;b<10;b++){
for(int c=0;c<10;c++){
for(int d=0;d<10;d++){
for(int e=0;e<10;e++){
for(int f=0;f<10;f++){
memset(vis,0,sizeof(vis));//每来一个新数的时候都要清空一次
if(a!=b&&a!=c&&a!=d&&a!=e&&a!=f&&
b!=c&&b!=d&&b!=e&&b!=f&&
c!=d&&c!=e&&c!=f&&
d!=e&&d!=f&&
e!=f){//互不相同才符合条件
res=a*100000+b*10000+c*1000+d*100+e*10+f;
LL t=res*res;
while(t){
LL r=t%10;
vis[r]++;
t/=10;
}
if(vis[a]==0&&vis[b]==0&&vis[c]==0&&vis[d]==0&&vis[e]==0&&vis[f]==0&&res!=203879){
printf("%lld\n",res);//符合条件才输出,二者都要符合
return 0;
}
}
}
}
}
}
}
}
蓝桥杯历届试题–递增三元组(二分优化)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int Max_n=100005;
int a[Max_n],b[Max_n],c[Max_n];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
sort(a+1,a+n+1);
sort(c+1,c+n+1);
int sum=0;
for(int i=1;i<=n;i++){
int index1=upper_bound(c+1,c+n+1,b[i])-c;//找到大于b[i]的第一个数
int index2=lower_bound(a+1,a+n+1,b[i])-a;//找到大于等于b[i]的第一个数
sum+=(index2-1)*(n-index1+1);
}
printf("%d\n",sum);
return 0;
}
蓝桥杯历届试题–分块巧克力(二分优化)
我们可以选择二分边长,然后检查边长是否符合题意.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int Max_n=100005;
int n,k,hi[Max_n],wi[Max_n];
bool check(int mid){
LL count=0;
for(int i=1;i<=n;i++)
count+=(hi[i]/mid)*(wi[i]/mid);//这里需要注意
if(count<k)
return false;
return true;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d%d",&hi[i],&wi[i]);
int l=0,r=100000,ans=0;
while(l<=r){//枚举天数也可以
int mid=l+(r-l)/2;
if(check(mid)){
l=mid+1;
ans=mid;
}else{
r=mid-1;
}
}
printf("%d\n",ans);
return 0;
}