- chenshixian 的博客
陈室先的总结7.12day5
-
chenshixian
LV 2
@
2024-7-13 8:41:10
题目传送门🚀️
T1小田的最大价值😄
思路❤️
这道道题有两种情况 1.如果数组最大值与最小值的差>k，输出最大值 2.如果小于时，输出次大值
🎉️代码
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main(){
freopen("max.in","r",stdin);
freopen("max.out","w",stdout);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);
if(a[n]-a[1]>k){
cout<<a[n];
}
else{
cout<<a[n-1];
}
}
T2小田的交换数字😄 😄
😕 错的地方
1.有一个取余细节忘了（位数的），导致丢了50分，以后要细心一点
❤️ 思路
1.一个极大数乘一个极小数积最小，那么我们可以比较两个数的的第i位，大的给第一个数，小的给第二个数 2.在可以手搓高精乘高精，注意位数问题，取余问题
代码🎉️
#include<bits/stdc++.h>
using namespace std;
string a,b;
long long an=0;
long long h=998244353;
int main(){
freopen("mul.in","r",stdin);
freopen("mul.out","w",stdout);
int n;
cin>>n>>a>>b;
for(long long i=0;i<n;i++)if(a[i]-'0'<b[i]-'0')swap(a[i],b[i]);
long long dw=1;
for(int i=n-1;i>=0;i--){
long long k=0;
long long w=dw;
for(int j=n-1;j>=0;j--){
long long aa=(a[j]-'0')%h,bb=(b[i]-'0')%h;
aa%=h,bb%=h;
long long f=w%h;
bb=((bb%h)*(f%h))%h;
bb%=h;
long long cc=((aa%h)*(bb%h))%h;
cc%=h;
k=((k%h)+(cc%h))%h;
k%=h;
w=((w%h)*10)%h;
}
an=((an%h)+(k%h))%h;
an%=h;
dw=((dw%h)*10)%h;
}
cout<<an%h;
}
T3 小田的气球真好看😄 😄
错的点😕
1.大概想到了是双指针，可是思路不清晰，要加强思考能力
❤️ 思路
这道题有两种写法（DP和双指针）
由于小田的气球很好看放到题目中就不好看了，所以我们要介绍好看的dp全班都没有写对双指针的
初始化f[1]=1,fl[a[1]]=1(fl数组是辅助数组) 状态计算
int j=fl[a[i]]
if(i-j<=k)f[i]=min(f[j]+i-j,f[i-1]+1);
if(i-j>k)f[i]=min(i-j,f[i-1]j+1);
双指针的写法还是讲一下吧 枚举起点l,以他为起点找到最后一个合法的r,这个区间有多长就多出几个
判断满不满足条件要用辅助数组
记得还要标记 当l向右走时，如果值在标记数组的最后一位，那么就要消除
代码🎉️
dp
#include<bits/stdc++.h>
using namespace std;
long long a[100010],f[100010],n,k,fl[100010];
int main(){
freopen("balloon.in","r",stdin);
freopen("balloon.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
long long s=0;
f[1]=1;
fl[a[1]]=1;
for(long long i=2;i<=n;i++){
int j=fl[a[i]];
if(j==0)f[i]=min(i,f[i-1]+1);
if(i-j<=k)f[i]=min(f[j]+i-j,f[i-1]+1);
if(i-j>k)f[i]=min(i-j,f[i-1]+1);
fl[a[i]]=i;
s+=f[i];
}
cout<<s+1;
}
双指针
#include <bits/stdc++.h>
using namespace std;
int n,k,a[100010],fl[100010];
long long re;
int main() {
freopen("balloon.in", "r", stdin);
freopen("balloon.out", "w", stdout);
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
int l=1,r=0;
while(l<=n) {
while(r<n&&(r+1-fl[a[r+1]]<=k||!fl[a[r+1]])) {
r++;
fl[a[r]]=r;
}
re+=r-l+1;
if(fl[a[l]]==l)fl[a[l]]=0;
l++;
}
cout<<re;
}
T4 表达式求值😄 😄
错的地方😕
1.表达式求值循环条件写错了，以后要理清题目思路
思路❤️
遇到“（,t,f,”入状态栈 “，”跳过 “&，|，！”入符号栈 “）”开始运算，拿一个运算符，再拿状态栈，直到为‘）’ 最后运算，压入；
代码🚀️
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
int t;
cin>>t;
while(t--){
string s;
cin>>s;
stack<char>f,b;
for(int i=0;i<s.size();i++){
if(s[i]=='!'||s[i]=='&'||s[i]=='|')f.push(s[i]);
else if(s[i]=='('||s[i]=='f'||s[i]=='t')b.push(s[i]);
else if(s[i]==',')continue;
else{
bool an;
if(b.top()=='t')an=1;
else if(b.top()=='f')an=0;
char a=f.top();
f.pop();
if(a=='!'){
b.pop();
if(an==1)b.push('f');
else b.push('t');
}
else{
while(b.top()!='('){
bool h;
if(b.top()=='t')h=1;
else if(b.top()=='f')h=0;
if(a=='|')an=an||h;
else if(a=='&')an=an&&h;
b.pop();
}
b.pop();
if(an==1)b.push('t');
if(an==0)b.push('f');
}
}
}
if(b.top()=='t')cout<<"true"<<"\n";
else cout<<"false"<<"\n";
}
}
T5 小W去冒险😄
思路❤️
深搜，每一次搜索时标记这个点，能在主函数内运行几次就有几个部落
代码🎉️
#include<bits/stdc++.h>
using namespace std;
int a[111][111],f[111][111],an=0; int n,m;
int zx[10]={1,0,-1,0};
int zy[10]={0,1,0,-1};
void dfs(int i,int j){
for(int h=0;h<4;h++){
int xx=i+zx[h];
int yy=j+zy[h];
if(xx>0&&xx<=n&&yy>0&&yy<=m&&a[xx][yy]!=0&&f[xx][yy]==0){
f[xx][yy]=1;
dfs(xx,yy);
}
}
return;
}
int main(){
freopen("ymx.in","r",stdin);
freopen("ymx.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char x;
cin>>x;
a[i][j]=x-'0';
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]!=0&&f[i][j]==0){
dfs(i,j);
an++;
}
}
}
cout<<an;
}
T6检查总结😡😭😱🤢
错的地方
根本没看懂🛸🛰🛬 🚝🚑🚒🚓
以后要加强读题能力
思路🤬
dp，状态转移方程如下 有删和不删两种情况 删：f[i+1]+1 不删:f[i+a[i]+1] 注意判断超过了a[n]没有 超过了就不行 初始化f[n]=1;
代码💘
#include<bits/stdc++.h>
using namespace std;
int a[2000010],f[1000010];
int main(){
freopen("summary.in","r",stdin);
freopen("summary.out","w",stdout);
int n;
cin>>n;
f[n]=1;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n-1;i>=1;i--){
f[i]=1000000;
if(i+a[i]<=n)f[i]=min(f[i+a[i]+1],f[i]);
if(i+1<=n)f[i]=min(f[i],f[i+1]+1);
if(f[i]==1000000)f[i]=0;
}
cout<<f[1];
}
再见 🛩🛫✈🚀🛰🛸🚝🚅🚂