1.日期统计
暴力求解所有情况
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100]= {5,6,8,6,9,1,6,1,2,4,9,1,9,8,2,3,6,4,7,7,5,9,5,0,3,8,7,5,8,1,5,8,6,1,8,3,0,3,7,9,2,
7,0,5,8,8,5,7,0,9,9,1,9,4,4,6,8,6,3,3,8,5,1,6,3,4,6,7,0,7,8,2,7,6,8,9,5,6,5,6,1,4,
0,1,0,0,9,4,8,0,9,1,2,8,5,0,2,5,3,3
};
int m[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31};
signed main()
{
int sum=0;
for(int month=1; month<=12; month++) //最多365天，暴力遍历所有日期检查存在的日期
{
for(int day=1; day<=m[month]; day++)
{
int a1[8]={2,0,2,3,month/10,month%10,day/10,day%10};
int j=0;
for(int i=0;i<100;i++)
{
if(a[i]==a1[j])
{
j++;
}
}
if(j==8)
{
sum++;
}
}
}
cout<<sum<<endl;
return 0;
}2.01串的熵
注意精度问题，浮点型相减之差<1e-4 被认为相等
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int n=23333333;
const double result=11625907.5798;
signed main()
{
for(int i=0; i<=n/2; i++) //所有可能0的次数
{
double temp=0;
temp-=i*(i*1.0/n)*(log2(i*1.0/n)); //熵计算公式
temp-=(n-i)*((n-i)*1.0/n)*(log2((n-i)*1.0/n));
if(fabs(temp-result)<1e-4)
{
cout<<i<<endl;
}
}
return 0;
}3.冶炼金属
除法中的上下界问题
方法一：
a/(b+1)<v<a/b;
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
signed main()
{
cin>>n;
int max1=1e9,min1=0;
while(n--)
{
int a,b;
cin>>a>>b;
max1=min(max1,a/b);
min1=max(min1,a/(b+1)+1);
// cout<<a/b<<" "<<a/(b+1)<<endl;
}
cout<<min1<<" "<<max1<<endl;
return 0;
}方法二（二分）：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,maxs;
vector<pair<int,int>>nums;
bool check_min(int mid)
{
for(int i=0;i<nums.size();i++)
{
int temp=nums[i].first/mid;
if(temp>nums[i].second)
{
return false;
}
}
return true;
}
bool check_max(int mid)
{
for(int i=0;i<nums.size();i++)
{
int temp=nums[i].first/mid;
if(temp<nums[i].second)
{
return false;
}
}
return true;
}
signed main()
{
cin>>n;
while(n--)
{
int a,b;
cin>>a>>b;
nums.push_back({a,b});
}
int lmin=0,rmin=1e9;
int max1=0,min1=0;
while(lmin<=rmin)
{
int mid=(lmin+rmin)/2;
if(check_min(mid)) //找最小值
{
min1=mid;
rmin=mid-1;
}
else
{
lmin=mid+1;
}
}
int lmax=0,rmax=1e9;
while(lmax<=rmax)
{
int mid=(lmax+rmax)/2;
if(check_max(mid)) //找最大值
{
max1=mid;
lmax=mid+1;
}
else
{
rmax=mid-1;
}
}
cout<<min1<<" "<<max1<<endl;
return 0;
}4.飞机降落
dfs问题：确保每架飞机的开始时间满足
start_time ∈ [T[i], T[i]+D[i]]
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=15;
int t,n;
bool flag,visit[N];
int T[N],D[N],L[N];
void dfs(int cur,int current_time) //跑道当前可用时间
{
if(flag) return;
if (cur==n)
{
flag=true;
return;
}
for(int i=0; i<n; i++)
{
if(!visit[i])
{
//计算这架飞机的最早和最晚开始降落时间
int start1=T[i];
int start2=T[i]+D[i];
//这架飞机的实际开始时间:当前跑道可用时间和飞机最早时间的最大值
int start_time=max(current_time,start1);
if(start_time<=start2) //检查是否能在最晚时间前开始降落
{
visit[i]=true;
dfs(cur+1,start_time+L[i]);
visit[i]=false;
if(flag) return;
}
}
}
}
signed main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=0; i<n; i++)
{
cin>>T[i]>>D[i]>>L[i];
}
flag=false;
memset(visit,0,sizeof(visit));
dfs(0,0);
cout << (flag ? "YES" : "NO") << endl;
}
return 0;
}5.接龙数列
方法一：使用暴力dfs（20%通过率）
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,ans=0;
vector<int>a(N,0);
int get_first(int x) //获取数字最高位
{
int res=0;
while(x)
{
res=x%10;
x/=10;
}
return res;
}
int get_final(int x) //最后一位
{
return x%10;
}
void dfs(int cur,int sum,int last)
{
if(cur>=n)
{
ans=max(ans,sum);
return;
}
//优化
if(n-cur+sum<=ans)
{
return;
}
//选
if(last==-1 || get_final(last)==get_first(a[cur])) //last=-1表示第一个数
{
dfs(cur+1,sum+1,a[cur]);
}
//不选
dfs(cur+1,sum,last);
}
signed main()
{
cin>>n;
for(int i=0; i<n; i++)
{
cin>>a[i];
}
dfs(0,0,-1); //层数，选取多少个数，最后一个数
cout<<n-ans<<endl;
return 0;
}方法二：动态规划
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,ans=0;
vector<int>a(N,0);
int f[N][15]; //f[i][j]:在前i个数字中选接龙序列,并且该接龙序列的最后一个数字的最后一位是j的最优方案
int get_first(int x) //获取数字最高位
{
int res=0;
while(x)
{
res=x%10;
x/=10;
}
return res;
}
int get_final(int x) //最后一位
{
return x%10;
}
signed main()
{
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>a[i];
}
memset(f,LONG_MAX,sizeof(f));
for(int i=0;i<10;i++)
{
f[0][i]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<10;j++) //删除第i个数字
{
f[i][j]=f[i-1][j]+1; //不选
}
//保留第i个数字
int final=get_final(a[i]);
int first=get_first(a[i]);
f[i][final]=min(f[i-1][first],f[i][final]);
}
int ans=LONG_MAX;
for(int i=0;i<10;i++)
{
ans=min(ans,f[n][i]); //最优方案：最少删除个数
}
cout<<ans<<endl;
return 0;
}6.子串简写
之间博客有总结过，查找子字符串出现次数
#include<bits/stdc++.h>
#define int long long
using namespace std;
int k,sum1=0,sum2=0;
string s;
char c1,c2;
signed main()
{
cin>>k>>s>>c1>>c2;
for(int i=0,j=k-1; i<s.size(); i++,j++)
{
if(s[i]==c1) sum1++;
if(s[j]==c2) sum2+=sum1;
}
cout<<sum2<<endl;
return 0;
} 7.整数删除
1.找出并删除最小数（保证未被删除）
2.相邻数（保证未被删除）加上被删除的数
方法一：暴力（40%通过率）
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int n,k;
int a[N];
bool visit[N];
signed main()
{
cin>>n>>k;
for(int i=1; i<=n; i++) cin>>a[i];
while(k--)
{
int min1=LONG_MAX,sign=0;
for(int i=1; i<=n; i++)
{
if(a[i]<min1 && !visit[i])
{
min1=a[i];
sign=i;
}
}
visit[sign]=true;
for(int j=sign-1; j>=1; j--)
{
if(!visit[j])
{
a[j]+=min1;
break;
}
}
for(int j=sign+1; j<=n; j++)
{
if(!visit[j])
{
a[j]+=min1;
break;
}
}
}
for(int i=1;i<=n;i++)
{
if(!visit[i])
{
cout<<a[i]<<" ";
}
}
return 0;
}方法二:优先队列大根堆
#include <iostream>
#include <queue>
#include <vector>
#include <utility>
typedef long long LL;
using namespace std;
int main()
{
int N, K, i;
cin >> N >> K;
vector<LL> num(N, 0);
vector<int> pre(N, 0), next(N, 0);
priority_queue<pair<LL, int>, vector<pair<LL, int> >, greater<pair<LL, int> > > pq;
for(i = 0; i < N; i++)
{
cin >> num[i];
pq.push({num[i], i});
pre[i] = i - 1;
next[i] = i + 1;
}
while(K > 0)
{
pair<LL, int> temp = pq.top();
pq.pop();
LL val = temp.first;
int pos = temp.second;
int l = pre[pos], r = next[pos];
if(val != num[pos])
{
pq.push({num[pos], pos});
continue;
}
num[pos] = -1;
if(l >= 0)
{
num[l] = num[l] + val;
next[l] = r;
}
if(r < N)
{
num[r] = num[r] + val;
pre[r] = l;
}
K--;
}
for(i = 0; i < N; i++)
{
if(num[i] != -1)
{
cout << num[i] << " " ;
}
}
return 0;
}