第十四届蓝桥杯c++b组

前四位已经固定，四重循环暴力生成后四位，并将合法的日期记录下来，然后检验这些日期能否被生成

具体如何检验：

由于题目说的是子序列，所以可以跳着选，但是相对顺序是不能变的，所以对于给定的100个数，从前往后一位一位和日期的8位匹配，如果一位匹配成功就匹配下一位，如果日期的8位都匹配成功了，那么就说明该日期合法

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int mon[13]={-1,31,29,31,30,31,30,31,31,30,31,30,31};
void solve() {set<int>s;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};for(int i=0;i<=9;i++){for(int j=0;j<=9;j++){for(int k=0;k<=9;k++){for(int m=0;m<=9;m++){int tmp=2023;tmp=tmp*10+i;tmp=tmp*10+j;tmp=tmp*10+k;tmp=tmp*10+m;string x=to_string(tmp);int month=(x[4]-'0')*10+x[5]-'0';int day=(x[6]-'0')*10+x[7]-'0';if(month>=1&&month<=12&&day>=1&&day<=mon[month]) s.insert(tmp);}}}}int ans=0;for(auto v:s){string t=to_string(v);int cnt=0;for(int i=0;i<100;i++){if(a[i]==t[cnt]-'0') cnt++;}if(cnt==(int)t.size()) ans++;}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

就是很简单的式子，枚举0的个数和1的个数，检验能否满足给定式子

#include<bits/stdc++.h>
#define endl '\n'
#define eps 1e-4
#define int long long
using namespace std;
void solve() {for(int i=0;i<=23333333;i++){//枚举0的个数int j=23333333-i;//1的个数if(i>j) break;double p0=(double)i/23333333;//0的占比double p1=(double)j/23333333;//1的占比double sum0=(-1)*i*p0*log2(p0);double sum1=(-1)*j*p1*log2(p1);double sum=sum0+sum1;if(abs(sum-11625907.5798)<eps){cout<<i<<endl;return;}}
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

法一：

找一下规律，比如题目中的样例

3
75 3
53 2
59 2

75/3=25
75/4=1875/25=3
75/24=3
75/23=3
...
75/19=3
75/18=4

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e4+10;
int a[N],b[N];
int n;
void solve() {cin>>n;for(int i=1;i<=n;i++) cin>>a[i]>>b[i];int maxn=2e9,minn=0;for(int i=1;i<=n;i++){int u=a[i]/b[i];int v=a[i]/(b[i]+1)+1;maxn=min(maxn,u);minn=max(minn,v);}cout<<minn<<' '<<maxn<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

法二：二分答案

在[1,1e9]二分出一个答案

如果是求最小的转换率，那么对于每个答案，check每条记录是否满足产出均小于等于b[i]，如果是返回true，找到最小的返回为true的转换率

产出的均小于等于b,需要找到最小的x满足产出均等于b[i],一定存在,因为题目说一定有解

求最大的转换率同理

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e4+10;
int a[N],b[N];
int n;
bool check1(int x){for(int i=1;i<=n;i++){if(a[i]/x>b[i]) return false;}return true;//产出的均小于等于b,需要找到最小的x满足产出均等于b[i],一定存在,因为题目说一定有解
}
bool check2(int x){for(int i=1;i<=n;i++){if(a[i]/x<b[i]) return false;}return true;//产出的均大于等于b,需要找到最大的x满足产出均等于b[i],一定存在,因为题目说一定有解
}
void solve() {cin>>n;for(int i=1;i<=n;i++) cin>>a[i]>>b[i];int l=1,r=1e9;while(l<r){int mid=(l+r)>>1;if(check1(mid)) r=mid;else l=mid+1;}int minn=l;l=1,r=1e9;while(l<r){int mid=(l+r+1)>>1;if(check2(mid)) l=mid;else r=mid-1;}int maxn=l;cout<<minn<<' '<<maxn<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

数据很小，直接暴力枚举每种情况，并check是否至少一种情况可以使得飞机成功降落

全排列即可

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=15;
int t[N],d[N],l[N];
int a[N];
int n;
void solve() {cin>>n;for(int i=1;i<=n;i++) cin>>t[i]>>d[i]>>l[i],a[i]=i;do{bool ok=true;int ed=0;//上一架飞机降落结束时间for(int i=1;i<=n;i++){if(t[a[i]]+d[a[i]]<ed){ok=false;break;}int st=max(ed,t[a[i]]);//开始降落时间ed=st+l[a[i]];}if(ok){cout<<"YES"<<endl;return;}}while(next_permutation(a+1,a+1+n));cout<<"NO"<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

问最少删除几个，也就是说最多保留几个

其实可以先求最长接龙子序列的长度，再用总长度减去它

从前往后枚举每个数，当以这个数作为接龙子序列的结尾时，它前面一个数的尾必须是它的头，所以dp[尾]=max(dp[尾],dp[头]+1)

dp[x]表示x作为尾的接龙子序列的最长长度

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
int dp[N];
int n;
void solve() {cin>>n;int ans=0;for(int i=1;i<=n;i++){string s;cin>>s;int len=s.size()-1;int x=s[0]-'0';int y=s[len-1]-'0';dp[y]=max(dp[y],dp[x]+1);ans=max(ans,dp[y]);}cout<<n-ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

和外海接触的岛屿肯定不是子岛屿

先将外围一圈标记为外海，从(0,0)开始搜，将所有的外海搜出来（8方向），标记为2

然后对于那些内海，仍为0，将它们都标记为陆地

最后搜陆地一共有几个连通块即可

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int N=55;
char s[N][N];
int m,n;
int dx1[8]={0,0,1,-1,1,1,-1,-1},dy1[8]={1,-1,0,0,-1,1,-1,1};
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
void dfs1(int x,int y){//找和外海相连的海,将所有外海标记为2s[x][y]='2';for(int i=0;i<8;i++){int tx=x+dx1[i],ty=y+dy1[i];if(tx<0||tx>m+1||ty<0||ty>n+1||s[tx][ty]!='0') continue;dfs1(tx,ty);}
}
void dfs2(int x,int y){//对于找到的所有外海,去找和外海接壤的陆地s[x][y]='3';for(int i=0;i<4;i++){int tx=x+dx[i],ty=y+dy[i];if(tx<0||tx>m+1||ty<0||ty>n+1||s[tx][ty]!='1') continue;dfs2(tx,ty);}
}
void solve() {cin>>m>>n;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){cin>>s[i][j];}}//外海一圈,朝8个方向搜,搜到所有的外海for(int i=0;i<=m+1;i++){for(int j=0;j<=n+1;j++){if(s[i][j]=='1'||s[i][j]=='0') continue;s[i][j]='0';}}dfs1(0,0);for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(s[i][j]=='0') s[i][j]='1';//将内海变成陆地}}int ans=0;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(s[i][j]=='1'){dfs2(i,j);ans++;}}}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

将字符为c1的位置都存储下来，然后枚举到字符为c2时，二分到最大的满足以c2结尾，c1开头的长度大于等于k的位置，然后该位置以及前面的c1都满足，作为对答案的贡献

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int k;
string s;
char c1,c2;
void solve() {cin>>k;cin>>s;cin>>c1>>c2;map<char,int>mp;vector<int>a;int ans=0;for(int i=0;i<(int)s.size();i++){if(s[i]==c1) a.push_back(i);else if(s[i]==c2){if(!a.size()) continue;int l=0,r=a.size()-1;while(l<r){int mid=(l+r+1)>>1;if(i-a[mid]+1>=k) l=mid;else r=mid-1;}if(i-a[l]+1>=k) ans+=l+1;}}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

线性存储结构进行删除操作时间复杂度为O（n），使用链式存储结构更适合

用双链表，这里用数组模拟

利用优先队列（小根堆），方便取出值最小的元素

这里我们删除一个元素时，需要将它左右两边的元素都加上它的值，但是我们无法在优先队列随意修改元素，所以这里有一个技巧，先记录下来下标为x的元素更新后的值，先不急着更新优先队列，类似于线段树的懒标记，等到用到了才更新优先队列，当队头的值是最新的值的时候，那么说明更新过了，那么执行删除操作，否则，需要在优先队列中更新它的值

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int N=5e5+10;
int a[N];
int l[N],r[N];//用数组模拟双链表
int n,k;
void del(int x){l[r[x]]=l[x],r[l[x]]=r[x];a[l[x]]+=a[x],a[r[x]]+=a[x];
}
void solve() {cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) l[i]=i-1;r[0]=1;for(int i=n;i>=1;i--) r[i]=i+1;priority_queue<PII,vector<PII>,greater<PII>>q;for(int i=1;i<=n;i++) q.push({a[i],i});while(k--){auto t=q.top();q.pop();if(t.first!=a[t.second]){q.push({a[t.second],t.second});k++;}else del(t.second);}for(int i=r[0];i<=n;i=r[i]) cout<<a[i]<<' ';cout<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}