第一题 签到

题目大意

n组数据，判断每组是否可以被11整除或者还有两个数位1

两个条件满足其一输出yes 否则输出no

第二题 双指针

题目大意

输入一个序列 只含±1

输出连续子序列乘积为正的数目

#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int num[N];
int main() {int n;int sum=0;int ans=0;cin>>n;for(int i=0;i<n;i++){cin>>num[i];if(num[i]==1)sum++;}ans+=sum;for(int i=0;i<n;i++){int t=num[i];for(int j=i+1;j<n;j++){t*=num[j];if(t==1)ans++;}}cout<<ans<<endl;return 0;
}

第三题 贪心

题目大意

一共有n个顾客 m道菜，原材料只够每道菜做一份，每个顾客点两个菜，只有吃到自己满意的菜才满意，输出顾客满意的最大数目。

#include<bits/stdc++.h>
using namespace std;
int num[50];
typedef pair<int,int> pii;
pii a[50],b[50];
vector<bool> vis;
int main()
{int n,m,ans=0;cin>>n>>m;vis=vector<bool>(m);for(int i=0;i<n;i++){int p,q;cin>>p>>q;a[i]={p,q};num[p]++;num[q]++;}for(int i=0;i<n;i++){int p=a[i].first,q=a[i].second;int sum=0;sum+=num[p]+num[q];b[i]={sum,i};}sort(b,b+n);for(int i=0;i<n;i++){int k=b[i].second;int p=a[k].first,q=a[k].second;if(!vis[p]&&!vis[q]){ans++;vis[p]=vis[q]=true;}}cout<<ans<<endl;return 0;
}

第四题 动态规划 （状态压缩DP）

题目大意

炸弹游戏，初始在房间1，持续时间m，每一s后第i个房间会爆炸，迁移到另一个房间损耗能量1，求无伤通关消耗的最低能量

dfs深度搜索 55%

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int a[N],num[15];
int n,m;
int ans=0x3f3f3f3f;
pair<int,int> p[15];
void dfs(int st,int u,int s){if(s>=ans)return;if(u==m){ans=min(ans,s);return;}if(a[u]==st){for(int i=1;i<=n;i++){int t=p[i].second;if(t!=st&&t!=a[u+1]){dfs(t,u,s+1);break;}}}else{dfs(st,u+1,s);}
}
int main()
{cin>>n>>m;for(int i=0;i<m;i++){scanf("%d",&a[i]);num[a[i]]++;}for(int i=1;i<=n;i++){p[i]={num[i],i};}sort(p,p+n);dfs(1,0,0);cout<<ans<<endl;return 0;
}

如果对您有帮助，免费的赞点一个～～～感谢🙏