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;
}
